Inhomogeneous polynomial optimization over a convex set: An approximation approach

He, Simai; Li, Zhening; Zhang, Shuzhong

doi:10.1090/S0025-5718-2014-02875-5

Inhomogeneous polynomial optimization over a convex set: An approximation approach
HTML articles powered by AMS MathViewer

by Simai He, Zhening Li and Shuzhong Zhang PDF

Math. Comp. 84 (2015), 715-741 Request permission

Abstract:

In this paper, we consider computational methods for optimizing a multivariate inhomogeneous polynomial function over a general convex set. The focus is on the design and analysis of polynomial-time approximation algorithms. The methods are able to deal with optimization models with polynomial objective functions in any fixed degrees. In particular, we first study the problem of maximizing an inhomogeneous polynomial over the Euclidean ball. A polynomial-time approximation algorithm is proposed for this problem with an assured (relative) worst-case performance ratio, which is dependent only on the dimensions of the model. The method and approximation ratio are then generalized to optimize an inhomogeneous polynomial over the intersection of a finite number of co-centered ellipsoids. Furthermore, the constraint set is extended to a general convex compact set. Specifically, we propose a polynomial-time approximation algorithm with a (relative) worst-case performance ratio for polynomial optimization over some convex compact sets, e.g., a polytope. Finally, numerical results are reported, revealing good practical performance of the proposed algorithms for solving some randomly generated instances.

References

Noga Alon and Assaf Naor, Approximating the cut-norm via Grothendieck’s inequality, SIAM J. Comput. 35 (2006), no. 4, 787–803. MR 2203567, DOI 10.1137/S0097539704441629
G.M. de Athayde and R.G. Flôres, Jr., Incorporating skewness and kurtosis in portfolio optimization: A multidimensional efficient set, in S. Satchell and A. Scowcroft (Eds.), Advances in Portfolio Construction and Implementation, Butterworth-Heinemann, Oxford, UK, Chapter 10, 243–257, 2003.
A. Barmpoutis, B. Jian, B. C. Vemuri, and T. M. Shepherd, Symmetric positive 4th order tensors & their estimation from diffusion weighted MRI, Proceedings of the 20th International Conference on Information Processing in Medical Imaging, 308–319, 2007.
Stephen Boyd and Lieven Vandenberghe, Convex optimization, Cambridge University Press, Cambridge, 2004. MR 2061575, DOI 10.1017/CBO9780511804441
Bilian Chen, Simai He, Zhening Li, and Shuzhong Zhang, Maximum block improvement and polynomial optimization, SIAM J. Optim. 22 (2012), no. 1, 87–107. MR 2902686, DOI 10.1137/110834524
Geir Dahl, Jon Magne Leinaas, Jan Myrheim, and Eirik Ovrum, A tensor product matrix approximation problem in quantum physics, Linear Algebra Appl. 420 (2007), no. 2-3, 711–725. MR 2278245, DOI 10.1016/j.laa.2006.08.026
A. Ghosh, E. Tsigaridas, M. Descoteaux, P. Comon, B. Mourrain, and R. Deriche, A Polynomial based approach to extract the maxima of an antipodally symmetric spherical function and its application to extract fiber directions from the orientation distribution function in diffusion MRI, Proceedings of the 11th International Conference on Medical Image Computing and Computer Assisted Intervention, 237–248, 2008.
Michel X. Goemans and David P. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, J. Assoc. Comput. Mach. 42 (1995), no. 6, 1115–1145. MR 1412228, DOI 10.1145/227683.227684
Leonid Gurvits, Classical deterministic complexity of Edmond’s problem and quantum entanglement, Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing, ACM, New York, 2003, pp. 10–19. MR 2121068, DOI 10.1145/780542.780545
Simai He, Zhening Li, and Shuzhong Zhang, Approximation algorithms for homogeneous polynomial optimization with quadratic constraints, Math. Program. 125 (2010), no. 2, Ser. B, 353–383. MR 2733568, DOI 10.1007/s10107-010-0409-z
S. He, Z. Li, and S. Zhang, Approximation algorithms for discrete polynomial optimization, Journal of the Operations Research Society of China, 1, 3–36, 2013.
Simai He, Zhi-Quan Luo, Jiawang Nie, and Shuzhong Zhang, Semidefinite relaxation bounds for indefinite homogeneous quadratic optimization, SIAM J. Optim. 19 (2008), no. 2, 503–523. MR 2425027, DOI 10.1137/070679041
Didier Henrion, Jean-Bernard Lasserre, and Johan Löfberg, GloptiPoly 3: moments, optimization and semidefinite programming, Optim. Methods Softw. 24 (2009), no. 4-5, 761–779. MR 2554910, DOI 10.1080/10556780802699201
Etienne de Klerk and Monique Laurent, Error bounds for some semidefinite programming approaches to polynomial minimization on the hypercube, SIAM J. Optim. 20 (2010), no. 6, 3104–3120. MR 2735946, DOI 10.1137/100790835
S. Khot and A. Naor, Linear equations modulo 2 and the $L_1$ diameter of convex bodies, Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, 318–328, 2007.
Polyxeni-Margarita Kleniati, Panos Parpas, and Berç Rustem, Partitioning procedure for polynomial optimization, J. Global Optim. 48 (2010), no. 4, 549–567. MR 2735297, DOI 10.1007/s10898-010-9529-5
Eleftherios Kofidis and Phillip A. Regalia, On the best rank-1 approximation of higher-order supersymmetric tensors, SIAM J. Matrix Anal. Appl. 23 (2001/02), no. 3, 863–884. MR 1896822, DOI 10.1137/S0895479801387413
Tamara G. Kolda and Brett W. Bader, Tensor decompositions and applications, SIAM Rev. 51 (2009), no. 3, 455–500. MR 2535056, DOI 10.1137/07070111X
Jean B. Lasserre, Global optimization with polynomials and the problem of moments, SIAM J. Optim. 11 (2000/01), no. 3, 796–817. MR 1814045, DOI 10.1137/S1052623400366802
Jean B. Lasserre, Polynomials nonnegative on a grid and discrete optimization, Trans. Amer. Math. Soc. 354 (2002), no. 2, 631–649. MR 1862561, DOI 10.1090/S0002-9947-01-02898-7
Monique Laurent, Sums of squares, moment matrices and optimization over polynomials, Emerging applications of algebraic geometry, IMA Vol. Math. Appl., vol. 149, Springer, New York, 2009, pp. 157–270. MR 2500468, DOI 10.1007/978-0-387-09686-5_{7}
Z. Li, Polynomial Optimization Problems—Approximation Algorithms and Applications, Ph.D. Thesis, The Chinese Univesrity of Hong Kong, Shatin, Hong Kong, 2011.
Chen Ling, Jiawang Nie, Liqun Qi, and Yinyu Ye, Biquadratic optimization over unit spheres and semidefinite programming relaxations, SIAM J. Optim. 20 (2009), no. 3, 1286–1310. MR 2546345, DOI 10.1137/080729104
Zhi-Quan Luo, Nicholas D. Sidiropoulos, Paul Tseng, and Shuzhong Zhang, Approximation bounds for quadratic optimization with homogeneous quadratic constraints, SIAM J. Optim. 18 (2007), no. 1, 1–28. MR 2299671, DOI 10.1137/050642691
Zhi-Quan Luo and Shuzhong Zhang, A semidefinite relaxation scheme for multivariate quartic polynomial optimization with quadratic constraints, SIAM J. Optim. 20 (2010), no. 4, 1716–1736. MR 2600236, DOI 10.1137/090772952
Boris Maričić, Zhi-Quan Luo, and Timothy N. Davidson, Blind constant modulus equalization via convex optimization, IEEE Trans. Signal Process. 51 (2003), no. 3, 805–818. MR 1963878, DOI 10.1109/TSP.2002.808112
Dietmar Maringer and Panos Parpas, Global optimization of higher order moments in portfolio selection, J. Global Optim. 43 (2009), no. 2-3, 219–230. MR 2471883, DOI 10.1007/s10898-007-9224-3
A. Nemirovski, Lectures on Modern Convex Optimization, The H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GA, 2005.
A. Nemirovski, C. Roos, and T. Terlaky, On maximization of quadratic form over intersection of ellipsoids with common center, Math. Program. 86 (1999), no. 3, Ser. A, 463–473. MR 1733748, DOI 10.1007/s101070050100
Yu. Nesterov, Semidefinite relaxation and nonconvex quadratic optimization, Optim. Methods Softw. 9 (1998), no. 1-3, 141–160. MR 1618100, DOI 10.1080/10556789808805690
Yu. Nesterov, Random Walk in a Simplex and Quadratic Optimization over Convex Polytopes, CORE Discussion Paper 2003/71, Université catholique de Louvain, Louvain-la-Neuve, Belgium, 2003.
Qin Ni, Liqun Qi, and Fei Wang, An eigenvalue method for testing positive definiteness of a multivariate form, IEEE Trans. Automat. Control 53 (2008), no. 5, 1096–1107. MR 2445667, DOI 10.1109/TAC.2008.923679
J. Nie, An approximation bound analysis for Lasserre’s relaxation in multivariate polynomial optimization, Journal of the Operations Research Society of China 1 (2013), 313–332.
P. A. Parrilo, Structured Semidefinite Programs and Semialgebraic Geometry Methods in Robustness and Optimization, Ph.D. Dissertation, California Institute of Technology, Pasadena, CA, 2000.
Pablo A. Parrilo, Semidefinite programming relaxations for semialgebraic problems, Math. Program. 96 (2003), no. 2, Ser. B, 293–320. Algebraic and geometric methods in discrete optimization. MR 1993050, DOI 10.1007/s10107-003-0387-5
A. J. Prakash, C. H. Chang, and T. E. Pactwa, Selecting a portfolio with skewness: Recent evidence from US, European, and Latin American equity markets, Journal of Banking & Finance, 27, 1375–1390, 2003.
Liqun Qi, Extrema of a real polynomial, J. Global Optim. 30 (2004), no. 4, 405–433. MR 2115027, DOI 10.1007/s10898-004-6875-1
Liqun Qi, Eigenvalues and invariants of tensors, J. Math. Anal. Appl. 325 (2007), no. 2, 1363–1377. MR 2270090, DOI 10.1016/j.jmaa.2006.02.071
Liqun Qi and Kok Lay Teo, Multivariate polynomial minimization and its application in signal processing, J. Global Optim. 26 (2003), no. 4, 419–433. MR 1989748, DOI 10.1023/A:1024778309049
Liqun Qi, Zhong Wan, and Yu-Fei Yang, Global minimization of normal quartic polynomials based on global descent directions, SIAM J. Optim. 15 (2004), no. 1, 275–302. MR 2112986, DOI 10.1137/S1052623403420857
Anthony Man-Cho So, Deterministic approximation algorithms for sphere constrained homogeneous polynomial optimization problems, Math. Program. 129 (2011), no. 2, Ser. B, 357–382. MR 2837886, DOI 10.1007/s10107-011-0464-0
Jos F. Sturm and Shuzhong Zhang, On cones of nonnegative quadratic functions, Math. Oper. Res. 28 (2003), no. 2, 246–267. MR 1980662, DOI 10.1287/moor.28.2.246.14485
Wenyu Sun and Ya-Xiang Yuan, Optimization theory and methods, Springer Optimization and Its Applications, vol. 1, Springer, New York, 2006. Nonlinear programming. MR 2232297
Yinyu Ye, Approximating quadratic programming with bound and quadratic constraints, Math. Program. 84 (1999), no. 2, Ser. A, 219–226. MR 1690021, DOI 10.1007/s10107980012a
Yinyu Ye, Approximating global quadratic optimization with convex quadratic constraints, J. Global Optim. 15 (1999), no. 1, 1–17. MR 1706356, DOI 10.1023/A:1008370723217
Ya-xiang Yuan, A review of trust region algorithms for optimization, ICIAM 99 (Edinburgh), Oxford Univ. Press, Oxford, 2000, pp. 271–282. MR 1824450
Shuzhong Zhang, Quadratic maximization and semidefinite relaxation, Math. Program. 87 (2000), no. 3, Ser. A, 453–465. MR 1757558, DOI 10.1007/s101070050006
Shuzhong Zhang and Yongwei Huang, Complex quadratic optimization and semidefinite programming, SIAM J. Optim. 16 (2006), no. 3, 871–890. MR 2197560, DOI 10.1137/04061341X
Xinzhen Zhang, Liqun Qi, and Yinyu Ye, The cubic spherical optimization problems, Math. Comp. 81 (2012), no. 279, 1513–1525. MR 2904588, DOI 10.1090/S0025-5718-2012-02577-4