A Survey of Hidden Convex Optimization

doi:10.1007/s40305-019-00286-5

摘要/Abstract

Abstract: Motivated by the fact that not all nonconvex optimization problems are difficult to solve, we survey in this paper three widely used ways to reveal the hidden convex structure for different classes of nonconvex optimization problems. Finally, ten open problems are raised.

Key words: Convex programming, Quadratic programming, Quadratic matrix programming, Fractional programming, Lagrangian dual, Semidefinite programming

中图分类号:

. [J]. Journal of the Operations Research Society of China, 2020, 8(1): 1-28.

Yong Xia. A Survey of Hidden Convex Optimization[J]. Journal of the Operations Research Society of China, 2020, 8(1): 1-28.

参考文献

[1] Ahmadi, A.A., Olshevsky, A., Parrilo, P.A., Tsitsiklis, J.N.:NP-hardness of deciding convexity of quartic polynomials and related problems. Math. Program. 137, 453-476(2013)
[2] Hendrickx, J.M., Olshevsky, A.:Matrix p-norms are NP-hard to approximate if p ≠1, 2,∞. SIAM J. Matrix Anal. Appl. 31(5), 2802-2812(2009)
[3] Burer, S.:On the copositive representation of binary and continuous nonconvex quadratic programs. Math. Program. 120(2), 479-495(2009)
[4] Murty, K.G., Kabdai, S.N.:Some NP-complete problems in quadratic and linear programming. Math. Program. 39, 117-129(1987)
[5] Ben-Tal, A., Teboulle, M.:Hidden convexity in some nonconvex quadratically constrained quadratic programming. Math. Program. 72, 51-63(1996)
[6] Horst, R.:On the convexification of nonlinear programming problems:an applications-oriented survey. Eur. J. Oper. Res. 15, 382-392(1984)
[7] Li, D., Wu, Z.Y., Lee, H.W.J., Yang, X.M., Zhang, L.S.:Hidden convex minimization. J. Global Optim. 31, 211-233(2005)
[8] Wu, Z.Y., Li, D., Zhang, L.S., Yang, X.M.:Peeling off a nonconvex cover of an actual convex problem:hidden convexity. SIAM J. Optim. 18(2), 507-536(2007)
[9] Xia, Y., Sun, X.L., Li, D., Zheng, X.J.:On the reduction of duality gap in box constrained nonconvex quadratic program. SIAM J. Optim. 21(3), 706-729(2011)
[10] Lasdon, L.S.:Optimization Theory for Large Systems. Macmillan Company, London (2006)
[11] Li, D.:Zero duality gap for a class of nonconvex optimization problems. J. Optim. Theory Appl. 85(2), 309-324(1995)
[12] Li, D., Sun, X.L.:Towards strong duality in integer programming. J. Global Optim. 35(2), 255-282(2006)
[13] Li, T.,Wang, Y., Liang, Z., Pardalos, P.M.:Local saddle point and a class of convexification methods for nonconvex optimization problems. J. Global Optim. 38, 405-419(2007)
[14] Li, D., Sun, X.L., Biswal, M.P., Gao, F.:Convexification, concavification and monotonization in global optimization. Ann. Oper. Res. 105, 213-226(2001)
[15] Xia, Y., Li, D.:Strong duality in optimization:shifted power reformulation. Optim. Method Softw. 31(4), 720-736(2016)
[16] Sun, P., Freund, R.M.:Computation of minimum-volume covering ellipsoids. Oper. Res. 52(5), 690-706(2004)
[17] Konno, H., Kuno, T.:Multiplicative programming problems. In:Horst, R., Pardalos, P.M. (eds.) Handbook of Global Optimization, pp. 369-405. Kluwer Academic Publishers, Dordrecht (1995)
[18] Matsui, T.:NP-hardness of linear multiplicative programming and related problems. J. GlobalOptim. 9, 113-119(1996)
[19] Duffin, R., Peterson, E., Zener, C.:Geometric Programming:Theory and Application. Wiley, New York (1967)
[20] Charnes, A., Cooper,W.W.:Programming with linear fractional functionals. Nav. Res. Logist. Q. 9, 181-186(1962)
[21] Schaible, S.:Parameter-free convex equivalent and dual programs of fractional programming problems. Zeitschrift für Oper. Res. 18, 187-196(1974)
[22] Carosi, L., Martein, L.:A sequential method for a class of pseudoconcave fractional problems. Cent. Eur. J. Oper. Res. 16, 153-164(2008)
[23] Fakhri, A., Ghatee, M.:Minimizing the sum of a linear and a linear fractional function applying conic quadratic representation:continuous and discrete problems. Optimization 65(5), 1023-1038(2016)
[24] Gay, D.M.:Computing optimal locally constrained steps. SIAM J. Sci. Stat. Comput. 2(2), 186-197(1981)
[25] Yuan, Y.:Recent advances in trust region algorithms. Math. Program. 151, 249-281(2015)
[26] Golub, G.H., VonMatt, U.:Quadratically constrained least squares and quadratic problems. Numer. Math. 59, 561-580(1991)
[27] Martínez, J.M.:Local minimizers of quadratic function on Euclidean balls and spheres. SIAM J. Optim. 4, 159-176(1994)
[28] Stern, R.J., Wolkowicz, H.:Indefinite trust region subproblems and nonsymmetric perturbations. SIAM J. Optim. 5(2), 286-313(1995)
[29] Hsia, Y., Sheu, R.-L., Yuan, Y.:Theory and application of p-regularized subproblems for p>2. Optim. Method Softw. 32(5), 1059-1077(2017)
[30] Loiola, E.M., Abreu, N.M.M., Boaventura-Netto, P.O., Hahn, P., Querido, T.:An analytical survey for the quadratic assignment problem. Eur. J. Oper. Res. 176, 657-690(2007)
[31] Finke, G., Burkard, R.E., Rendl, F.:Quadratic assignment problems. Ann. Discrete Math. 31, 61-82(1987)
[32] Rendle, F., Wolkowicz, H.:Applications of parametric programming and eigenvalue maximazation to the quadratic assignment problem. Math. Program. 53, 63-78(1992)
[33] Anstreicher, K.M., Chen, X., Wolkowicz, H., Yuan, Y.:Strong duality for a trust-region type relaxation of the quadratic assignment problem. Linear Algebra Appl. 301(1-3), 121-136(1999)
[34] Xia, Y.:Global Optimization of a class of nonconvex quadratically constrained quadratic programming problems. Acta. Math. Sin. 27(9), 1803-1812(2011)
[35] Bazaraa, M.S., Sherali, H.D., Shetty, C.M.:Nonlinear Programming:Theory and Algorithms, 2nd edn. Wiley, New York (1993)
[36] Barvinok, A.I.:Feasibility testing for systems of real quadratic equations. Discrete Comput. Geom. 10, 1-13(1993)
[37] Pong, T.K., Wolkowicz, H.:Generalizations of the trust region subproblem. Comput. Optim. Appl. 58(2), 273-322(2014)
[38] Beck, A., Pan, D.:On the solution of the GPS localization and circle fitting problems. SIAM J. Optim. 22(1), 108-134(2012)
[39] Wang, S., Xia, Y.:Strong duality for generalized trust region subproblem:S-lemma with interval bounds. Optim. Lett. 9(6), 1063-1073(2015)
[40] Pólik, I., Terlaky, T.:A survey of the S-Lemma. SIAM Rev. 49(3), 371-418(2007)
[41] Xia, Y.,Wang, S., Sheu, R.L.:S-lemma with equality and its applications.Math. Program. 156(1-2), 513-547(2016)
[42] Ben-Tal, A., den Hertog, D.:Hidden conic quadratic representation of some nonconvex quadratic optimization problems. Math. Program. 143(1-2), 1-29(2014)
[43] Jiang, R., Li, D., Wu, B.:SOCP reformulation for the generalized trust region subproblem via a canonical form of two symmetric matrices. Math. Program. 169(2), 531-563(2018)
[44] Polyak, B.T.:Convexity of quadratic transformations and its use in control and optimization. J. Optim. Theory Appl. 99(3), 553-583(1998)
[45] Xia, Y., Xing, W.:Parametric Lagrangian dual for the binary quadratic programming problem. J. Global Optim. 61(2), 221-233(2015)
[46] Beck, A., Eldar, Y.C.:Strong duality in nonconvex quadratic optimization with two quadratic constraints. SIAM J. Optim. 17(3), 844-860(2006)
[47] Zhao, Q., Karisch, S.E., Rendl, F., Wolkowicz, H.:Semidefinite programming relaxations for the quadratic assignment problem. J. Comb. Optim. 2(1), 71-109(1998)
[48] Wolkowicz, H.:A note on lack of strong duality for quadratic problems with orthogonal constraints. Eur. J. Oper. Res. 143(2), 356-364(2002)
[49] Anstreicher, K.M.,Wolkowicz, H.:On lagrangian relaxation of quadratic matrix constraints. SIAM J. Matrix Anal. Appl. 22, 41-55(2000)
[50] Ding, Y., Ge, D., Wolkowicz, H.:On equivalence of semidefinite relaxations for quadratic matrix programming. Math. Oper. Res. 36(1), 88-104(2011)
[51] Shor, N.Z.:Nondifferentiable Optimization and Polynomial Problems. Springer, Dordrecht (1998)
[52] Motzkin, T.S., Straus, E.G.:Maxima for graphs and a new proof of a theorem of Turán. Can. J. Math. 17, 533-540(1965)
[53] Xia, Y., Sheu, R.L., Sun, X., Li, D.:Tightening a copositive relaxation for standard quadratic optimization problems. Comput. Optim. Appl. 55, 379-398(2013)
[54] Anstreicher, K.M., Burer, S.:Computable representations for convex hulls of low-dimensional quadratic forms. Math. Program. 124, 33-43(2010)
[55] Schaible, S.:Fractional programming I:duality. Manag. Sci. 22(8), 858-867(1976)
[56] Beck, A., Teboulle, M.:A convex optimization approach for minimizing the ratio of indefinite quadratic functions over an ellipsoid. Math. Program. 118, 13-35(2009)
[57] Nguyen, V.-B., Sheu, R.-L., Xia, Y.:An SDP approach for quadratic fractional problems with a two-sided quadratic constraint. Optim. Method Softw. 31(4), 701-719(2016)
[58] Yang, M., Xia, Y.:On Lagrangian duality gap of quadratic fractional programming with a two-sided quadratic constraint. Optim. Lett. https://doi.org/10.1007/s11590-018-1320-4(2018)
[59] Beck, A., Ben-Tal, A., Teboulle, M.:Finding a global optimal solution for a quadratically constrained fractional quadratic problem with applications to the regularized total least squares. SIAM J. Matrix Anal. Appl. 28, 425-445(2006)
[60] Xia, Y.:Convex hull of the orthogonal similarity set with applications in quadratic assignment problems. J. Ind. Manag. Optim. 9(3), 687-699(2013)
[61] Beck, A.:Quadratic matrix programming. SIAM J. Optim. 17, 1224-1238(2006)
[62] Pataki, G.:The geometry of semidefinite programming. In Handbook of Semidefinite Programming. In:International Series in Operations Research andManagement Science, vol. 27, pp. 29-65. Kluwer Academic Publishers, Boston, (2000)
[63] Beck, A., Ben-Tal, A.:On the solution of the Tikhonov regularization of the total least squares problem. SIAM J. Optim. 17(1), 98-118(2006)
[64] Yang, M., Xia, Y., Wang, J., Peng, J.:Efficiently solving total least squares with tikhonov identical regularization. Comput. Optim. Appl. 70(2), 571-592(2018)
[65] Flippo, O.E., Jansen, B.:Duality and sensitivity in nonconvex quadratic optimization over an ellipsoid. Eur. J. Oper. Res. 94, 167-178(1996)
[66] Wang, J., Xia, Y.:A linear-time algorithm for the trust region subproblem based on hidden convexity. Optim. Lett. 11(8), 1639-1646(2017)
[67] Nam, H.N., Kılınç-Karzan, F.:A second-order cone based approach for solving the trust-region subproblem and its variants. SIAM J. Optim. 27(3), 1485-1512(2017)
[68] Hazan, E., Koren, T.:A linear-time algorithm for trust region problems. Math. Program. 158(1), 363-381(2016)
[69] Yamada, S., Takeda, A.:Successive Lagrangian relaxation algorithm for nonconvex quadratic optimization. J. Glob. Optim. 71(2), 313-339(2018)
[70] Haines, S., Loeppky, J., Tseng, P.,Wang, X.:Convex relaxations of the weighted maxmin dispersion problem. SIAM J. Optim. 23, 2264-2294(2013)
[71] Wang, S., Xia, Y.:On the ball-constrained weighted maximin dispersion problem. SIAM J. Optim. 26(3), 1565-1588(2016)
[72] Rendle, F.,Wolkowicz, H.:A semidefinite framework for trust region subproblems with applications to large scale minimization. Math. Program. 77(2), 273-299(1997)
[73] Pataki, G.:On the rank of extreme matrices in semidefinite programs and the multiplicity of optimal eigenvalues. Math. Oper. Res. 23(2), 339-358(1998)
[74] Sturm, J.F., Zhang, S.:On cones of nonnegative quadratic functions.Math.Oper. Res. 28(2), 246-267(2003)
[75] Ye, Y., Zhang, S.:New results on quadratic minimization. SIAM J. Optim. 14(1), 245-267(2003)
[76] Guo, X., Deng, Z., Fang, S.-C., Wang, Z., Xing, W.:Quadratic optimization over a second-order cone with linear equality constraints. J. Oper. Res. Soc. China 2(1), 17-38(2014)
[77] Burer, S., Anstreicher, K.M.:Second-order-cone constraints for extended trust-region subproblems. SIAM J. Optim. 23(1), 432-451(2013)
[78] Burer, S., Yang, B.:The trust-region subproblem with non-intersecting linear constraints. Math. Program. 149(1-2), 253-264(2015)
[79] Burer, S., Kılınç-Karzan, F.:How to convexify the intersection of a second order cone and a nonconvex quadratic. Math. Program. 162(1-2), 393-429(2017)
[80] Dai, J., Fang, S.-C., Xing,W.:Recovering optimal solutions via SOC-SDP relaxation of trust region subproblem with nonintersecting linear constraints. J. Ind. Manag. Optim. https://doi.org/10.3934/jimo.2018117(2019)
[81] Beck, A., Drori, Y., Teboulle, M.:A new semidefinite programming relaxation scheme for a class of quadratic matrix problems. Oper. Res. Lett. 40, 298-302(2012)
[82] Lemon, A., So, A.M.-C., Ye, Y.:Low-rank semidefinite programming:theory and applications. Found. Trends Optim. 2(1-2), 1-156(2016)
[83] Liu, Y.F., Hong, M.Y., Dai, Y.H.:Max-min fairness linear transceiver design problem for a multiuser simo interference channel is polynomial time solvable. IEEE Signal Process. Lett. 20(1), 27-30(2013)
[84] Yang, B., Anstreicher, K., Burer, S.:Quadratic programs with hollows. Math. Program. 170(2), 541-553(2018)
[85] Bienstock, D.:Anote on polynomial solvability of theCDTproblem. SIAMJ.Optim. 26(1), 488-498(2016)
[86] Consolini, L., Locatelli, M.:On the complexity of quadratic programming with two quadratic constraints. Math. Program. 164(1-2), 91-128(2017)
[87] Sakaue, S., Nakatsukasa, Y., Takeda, A., Iwata, S.:Solving generalized CDT problems via twoparameter eigenvalues. SIAM J. Optim. 26(3), 1669-1694(2016)
[88] Bienstock, D., Michalka, A.:Polynomial solvability of variants of the trust-region subproblem. In:ACM-SIAM Symposium on Discrete Algorithms, pp. 380-390. (2014)
[89] Hsia,Y., Sheu, R.-L.:TrustRegion Subproblem with a Fixed Number of Additional Linear Inequality Constraints has Polynomial Complexity. arXiv:1312.1398(2013)
[90] Schonemann, P.H.:A generalized solution of the orthogonal procrustes problem. Psychometrika 31(1), 1-10(1966)
[91] Dodig, M., Stošić, M., Xavier, J.:On minimizing a quadratic function on a Stiefel manifold. Linear Algebra Appl. 475, 251-264(2015)
[92] Zhang, L.H.:On a self-consistent-field-like iteration for maximizing the sum of the Rayleigh quotients. J. Comput. Appl. Math. 257, 14-28(2014)
[93] Wang, L.,Xia,Y.:Alinear-time algorithm for globally maximizing the sum of a generalized Rayleigh quotient and a quadratic form on the unit sphere. SIAM J. Optim. 29(3), 1844-1869(2019)
[94] Hiriart-Urruty, J.B.:Potpourri of conjectures and open questions in nonlinear analysis and optimization. SIAM Rev. 49, 255-273(2007)
[95] Zhao,Y.B.:The Legendre-Fenchel conjugate of the product of two positive-definite quadratic forms. SIAM J. Matrix Anal. Appl. 31(4), 1792-1811(2010)
[96] Xia, Y.:A note on Legendre-Fenchel conjugate of the product of two positive-definite quadratic forms. J. Oper. Res. Soc. China 1(3), 333-338(2013)
[97] Nesterov, Y.:Random walk in a simplex and quadratic optimization over convex polytopes. CORE Discussion Paper 2003/71(2003)
[98] Xia, Y.:On local convexity of quadratic transformations. J. Oper. Res. Soc. China 2, 341-350(2014)
[99] Beck, A.:On the convexity of a class of quadratic mappings and its application to the problem of finding the smallest ball enclosing a given intersection of ball. J. Global Optim. 39(1), 113-126(2007)
[100] Beck, A.:Convexity properties associated with nonconvex quadratic matrix functions and applications to quadratic programming. J. Optim. Theory Appl. 142(1), 1-29(2009)