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
Additional Information
- Simai He
- Affiliation: Department of Management Sciences, City University of Hong Kong, Hong Kong
- Email: simaihe@cityu.edu.hk
- Zhening Li
- Affiliation: (corresponding author) Department of Mathematics, University of Portsmouth, Portsmouth PO1 3HF, United Kingdom
- Email: zheningli@gmail.com
- Shuzhong Zhang
- Affiliation: Department of Industrial and Systems Engineering, University of Minnesota, Minneapolis, Minnesota 55455
- Email: zhangs@umn.edu
- Received by editor(s): June 29, 2011
- Received by editor(s) in revised form: September 11, 2012, and June 13, 2013
- Published electronically: July 24, 2014
- Additional Notes: The research of the first author was supported in part by Hong Kong GRF #CityU143711
The research of the second author was supported in part by Natural Science Foundation of China #11371242, Natural Science Foundation of Shanghai #12ZR1410100, and Ph.D. Programs Foundation of Chinese Ministry of Education #20123108120002.
The research of the third author was supported in part by National Science Foundation of USA #CMMI1161242 - © Copyright 2014 American Mathematical Society
- Journal: Math. Comp. 84 (2015), 715-741
- MSC (2010): Primary 90C26, 90C59, 65Y20, 68W25, 15A69
- DOI: https://doi.org/10.1090/S0025-5718-2014-02875-5
- MathSciNet review: 3290961