×

zbMATH — the first resource for mathematics

A survey of hidden convex optimization. (English) Zbl 1449.90294
Summary: 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.

MSC:
90C25 Convex programming
90C20 Quadratic programming
90C26 Nonconvex programming, global optimization
90C32 Fractional programming
90C22 Semidefinite programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Ahmadi, Aa; Olshevsky, A.; Parrilo, Pa; Tsitsiklis, Jn, NP-hardness of deciding convexity of quartic polynomials and related problems, Math. Program., 137, 453-476 (2013) · Zbl 1274.90516
[2] Hendrickx, Jm; Olshevsky, A., Matrix \(p\)-norms are NP-hard to approximate if \(p\ne 1,2,\infty \), SIAM J. Matrix Anal. Appl., 31, 5, 2802-2812 (2009) · Zbl 1216.68117
[3] Burer, S., On the copositive representation of binary and continuous nonconvex quadratic programs, Math. Program., 120, 2, 479-495 (2009) · Zbl 1180.90234
[4] Murty, Kg; Kabdai, Sn, Some NP-complete problems in quadratic and linear programming, Math. Program., 39, 117-129 (1987) · Zbl 0637.90078
[5] Ben-Tal, A.; Teboulle, M., Hidden convexity in some nonconvex quadratically constrained quadratic programming, Math. Program., 72, 51-63 (1996) · Zbl 0851.90087
[6] Horst, R., On the convexification of nonlinear programming problems: an applications-oriented survey, Eur. J. Oper. Res., 15, 382-392 (1984) · Zbl 0547.90082
[7] Li, D.; Wu, Zy; Lee, Hwj; Yang, Xm; Zhang, Ls, Hidden convex minimization, J. Global Optim., 31, 211-233 (2005) · Zbl 1090.90156
[8] Wu, Zy; Li, D.; Zhang, Ls; Yang, Xm, Peeling off a nonconvex cover of an actual convex problem: hidden convexity, SIAM J. Optim., 18, 2, 507-536 (2007) · Zbl 1211.90241
[9] Xia, Y.; Sun, Xl; Li, D.; Zheng, Xj, On the reduction of duality gap in box constrained nonconvex quadratic program, SIAM J. Optim., 21, 3, 706-729 (2011) · Zbl 1236.90083
[10] Lasdon, Ls, Optimization Theory for Large Systems (2006), London: Macmillan Company, London
[11] Li, D., Zero duality gap for a class of nonconvex optimization problems, J. Optim. Theory Appl., 85, 2, 309-324 (1995) · Zbl 0829.90109
[12] Li, D.; Sun, Xl, Towards strong duality in integer programming, J. Global Optim., 35, 2, 255-282 (2006) · Zbl 1097.90068
[13] Li, T.; Wang, Y.; Liang, Z.; Pardalos, Pm, Local saddle point and a class of convexification methods for nonconvex optimization problems, J. Global Optim., 38, 405-419 (2007) · Zbl 1175.90317
[14] Li, D.; Sun, Xl; Biswal, Mp; Gao, F., Convexification, concavification and monotonization in global optimization, Ann. Oper. Res., 105, 213-226 (2001) · Zbl 0995.90091
[15] Xia, Y.; Li, D., Strong duality in optimization: shifted power reformulation, Optim. Method Softw., 31, 4, 720-736 (2016) · Zbl 1358.90151
[16] Sun, P.; Freund, Rm, Computation of minimum-volume covering ellipsoids, Oper. Res., 52, 5, 690-706 (2004) · Zbl 1165.90571
[17] Konno, H.; Kuno, T.; Horst, R.; Pardalos, Pm, Multiplicative programming problems, Handbook of Global Optimization, 369-405 (1995), Dordrecht: Kluwer Academic Publishers, Dordrecht
[18] Matsui, T., NP-hardness of linear multiplicative programming and related problems, J. Global Optim., 9, 113-119 (1996) · Zbl 0868.90111
[19] Duffin, R.; Peterson, E.; Zener, C., Geometric Programming: Theory and Application (1967), New York: Wiley, New York · Zbl 0171.17601
[20] Charnes, A.; Cooper, Ww, Programming with linear fractional functionals, Nav. Res. Logist. Q., 9, 181-186 (1962) · Zbl 0127.36901
[21] Schaible, S., Parameter-free convex equivalent and dual programs of fractional programming problems, Zeitschrift für Oper. Res., 18, 187-196 (1974) · Zbl 0291.90067
[22] Carosi, L.; Martein, L., A sequential method for a class of pseudoconcave fractional problems, Cent. Eur. J. Oper. Res., 16, 153-164 (2008) · Zbl 1152.90618
[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) · Zbl 1384.90101
[24] Gay, Dm, Computing optimal locally constrained steps, SIAM J. Sci. Stat. Comput., 2, 2, 186-197 (1981) · Zbl 0467.65027
[25] Yuan, Y., Recent advances in trust region algorithms, Math. Program., 151, 249-281 (2015) · Zbl 1317.65141
[26] Golub, Gh; Von Matt, U., Quadratically constrained least squares and quadratic problems, Numer. Math., 59, 561-580 (1991) · Zbl 0745.65029
[27] Martínez, Jm, Local minimizers of quadratic function on Euclidean balls and spheres, SIAM J. Optim., 4, 159-176 (1994) · Zbl 0801.65057
[28] Stern, Rj; Wolkowicz, H., Indefinite trust region subproblems and nonsymmetric perturbations, SIAM J. Optim., 5, 2, 286-313 (1995) · Zbl 0846.49017
[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) · Zbl 1379.49022
[30] Loiola, Em; Abreu, Nmm; Boaventura-Netto, Po; Hahn, P.; Querido, T., An analytical survey for the quadratic assignment problem, Eur. J. Oper. Res., 176, 657-690 (2007) · Zbl 1103.90058
[31] Finke, G.; Burkard, Re; 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) · Zbl 0751.90051
[33] Anstreicher, Km; 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) · Zbl 0953.90034
[34] Xia, Y., Global Optimization of a class of nonconvex quadratically constrained quadratic programming problems, Acta. Math. Sin., 27, 9, 1803-1812 (2011) · Zbl 1225.90094
[35] Bazaraa, Ms; Sherali, Hd; Shetty, Cm, Nonlinear Programming: Theory and Algorithms (1993), New York: Wiley, New York
[36] Barvinok, Ai, Feasibility testing for systems of real quadratic equations, Discrete Comput. Geom., 10, 1-13 (1993) · Zbl 0812.12006
[37] Pong, Tk; Wolkowicz, H., Generalizations of the trust region subproblem, Comput. Optim. Appl., 58, 2, 273-322 (2014) · Zbl 1329.90100
[38] Beck, A.; Pan, D., On the solution of the GPS localization and circle fitting problems, SIAM J. Optim., 22, 1, 108-134 (2012) · Zbl 1259.90097
[39] Wang, S.; Xia, Y., Strong duality for generalized trust region subproblem: S-lemma with interval bounds, Optim. Lett., 9, 6, 1063-1073 (2015) · Zbl 1354.90089
[40] Pólik, I.; Terlaky, T., A survey of the S-Lemma, SIAM Rev., 49, 3, 371-418 (2007) · Zbl 1128.90046
[41] Xia, Y.; Wang, S.; Sheu, Rl, S-lemma with equality and its applications, Math. Program., 156, 1-2, 513-547 (2016) · Zbl 1333.90086
[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) · Zbl 1295.90036
[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) · Zbl 1390.90416
[44] Polyak, Bt, Convexity of quadratic transformations and its use in control and optimization, J. Optim. Theory Appl., 99, 3, 553-583 (1998) · Zbl 0961.90074
[45] Xia, Y.; Xing, W., Parametric Lagrangian dual for the binary quadratic programming problem, J. Global Optim., 61, 2, 221-233 (2015) · Zbl 1334.90076
[46] Beck, A.; Eldar, Yc, Strong duality in nonconvex quadratic optimization with two quadratic constraints, SIAM J. Optim., 17, 3, 844-860 (2006) · Zbl 1128.90044
[47] Zhao, Q.; Karisch, Se; Rendl, F.; Wolkowicz, H., Semidefinite programming relaxations for the quadratic assignment problem, J. Comb. Optim., 2, 1, 71-109 (1998) · Zbl 0904.90145
[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) · Zbl 1058.90046
[49] Anstreicher, Km; Wolkowicz, H., On lagrangian relaxation of quadratic matrix constraints, SIAM J. Matrix Anal. Appl., 22, 41-55 (2000) · Zbl 0990.90088
[50] Ding, Y.; Ge, D.; Wolkowicz, H., On equivalence of semidefinite relaxations for quadratic matrix programming, Math. Oper. Res., 36, 1, 88-104 (2011) · Zbl 1218.90149
[51] Shor, Nz, Nondifferentiable Optimization and Polynomial Problems (1998), Dordrecht: Springer, Dordrecht
[52] Motzkin, Ts; Straus, Eg, Maxima for graphs and a new proof of a theorem of Turán, Can. J. Math., 17, 533-540 (1965) · Zbl 0129.39902
[53] Xia, Y.; Sheu, Rl; Sun, X.; Li, D., Tightening a copositive relaxation for standard quadratic optimization problems, Comput. Optim. Appl., 55, 379-398 (2013) · Zbl 1294.90044
[54] Anstreicher, Km; Burer, S., Computable representations for convex hulls of low-dimensional quadratic forms, Math. Program., 124, 33-43 (2010) · Zbl 1198.90311
[55] Schaible, S., Fractional programming I: duality, Manag. Sci., 22, 8, 858-867 (1976) · Zbl 0338.90050
[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) · Zbl 1176.90451
[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) · Zbl 1385.90027
[58] Yang, M., Xia, Y.: On Lagrangian duality gap of quadratic fractional programming with a two-sided quadratic constraint. Optim. Lett. 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) · Zbl 1115.65065
[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) · Zbl 1136.90025
[62] Pataki, Gábor, The Geometry of Semidefinite Programming, International Series in Operations Research & Management Science, 29-65 (2000), Boston, MA: Springer US, Boston, MA · Zbl 0957.90531
[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) · Zbl 1112.65034
[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) · Zbl 1391.90498
[65] Flippo, Oe; Jansen, B., Duality and sensitivity in nonconvex quadratic optimization over an ellipsoid, Eur. J. Oper. Res., 94, 167-178 (1996) · Zbl 0930.90076
[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) · Zbl 1410.90145
[67] Nam, Hn; 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) · Zbl 1370.90170
[68] Hazan, E.; Koren, T., A linear-time algorithm for trust region problems, Math. Program., 158, 1, 363-381 (2016) · Zbl 1346.90654
[69] Yamada, S.; Takeda, A., Successive Lagrangian relaxation algorithm for nonconvex quadratic optimization, J. Glob. Optim., 71, 2, 313-339 (2018) · Zbl 1402.90112
[70] Haines, S.; Loeppky, J.; Tseng, P.; Wang, X., Convex relaxations of the weighted maxmin dispersion problem, SIAM J. Optim., 23, 2264-2294 (2013) · Zbl 1295.90110
[71] Wang, S.; Xia, Y., On the ball-constrained weighted maximin dispersion problem, SIAM J. Optim., 26, 3, 1565-1588 (2016) · Zbl 1346.90659
[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) · Zbl 0888.90137
[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) · Zbl 0977.90051
[74] Sturm, Jf; Zhang, S., On cones of nonnegative quadratic functions, Math. Oper. Res., 28, 2, 246-267 (2003) · Zbl 1082.90086
[75] Ye, Y.; Zhang, S., New results on quadratic minimization, SIAM J. Optim., 14, 1, 245-267 (2003) · Zbl 1043.90064
[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) · Zbl 1308.90122
[77] Burer, S.; Anstreicher, Km, Second-order-cone constraints for extended trust-region subproblems, SIAM J. Optim., 23, 1, 432-451 (2013) · Zbl 1298.90062
[78] Burer, S.; Yang, B., The trust-region subproblem with non-intersecting linear constraints, Math. Program., 149, 1-2, 253-264 (2015) · Zbl 1308.90121
[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) · Zbl 1358.90095
[80] Dai, Jinyu; Fang, Shu-Cherng; Xing, Wenxun, Recovering optimal solutions via SOC-SDP relaxation of trust region subproblem with nonintersecting linear constraints, Journal of Industrial & Management Optimization, 15, 4, 1677-1699 (2019) · Zbl 1438.90379
[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) · Zbl 1247.90210
[82] Lemon, A.; So, Am-C; Ye, Y., Low-rank semidefinite programming: theory and applications, Found. Trends Optim., 2, 1-2, 1-156 (2016)
[83] Liu, Yf; Hong, My; Dai, Yh, Max-min fairness linear transceiver design problem for a multi-user 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) · Zbl 1401.90147
[85] Bienstock, D., A note on polynomial solvability of the CDT problem, SIAM J. Optim., 26, 1, 488-498 (2016) · Zbl 1382.90083
[86] Consolini, L.; Locatelli, M., On the complexity of quadratic programming with two quadratic constraints, Math. Program., 164, 1-2, 91-128 (2017) · Zbl 1396.90055
[87] Sakaue, S.; Nakatsukasa, Y.; Takeda, A.; Iwata, S., Solving generalized CDT problems via two-parameter eigenvalues, SIAM J. Optim., 26, 3, 1669-1694 (2016) · Zbl 1346.49050
[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) · Zbl 1428.90109
[89] Hsia, Y., Sheu, R.-L.: Trust Region Subproblem with a Fixed Number of Additional Linear Inequality Constraints has Polynomial Complexity. arXiv:1312.1398 (2013)
[90] Schonemann, Ph, A generalized solution of the orthogonal procrustes problem, Psychometrika, 31, 1, 1-10 (1966) · Zbl 0147.19401
[91] Dodig, M.; Stošić, M.; Xavier, J., On minimizing a quadratic function on a Stiefel manifold, Linear Algebra Appl., 475, 251-264 (2015) · Zbl 1312.90051
[92] Zhang, Lh, On a self-consistent-field-like iteration for maximizing the sum of the Rayleigh quotients, J. Comput. Appl. Math., 257, 14-28 (2014) · Zbl 1294.65065
[93] Wang, L.; Xia, Y., A linear-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) · Zbl 1421.90122
[94] Hiriart-Urruty, Jb, Potpourri of conjectures and open questions in nonlinear analysis and optimization, SIAM Rev., 49, 255-273 (2007) · Zbl 1120.15025
[95] Zhao, Yb, The Legendre-Fenchel conjugate of the product of two positive-definite quadratic forms, SIAM J. Matrix Anal. Appl., 31, 4, 1792-1811 (2010) · Zbl 1207.15027
[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) · Zbl 1402.90111
[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) · Zbl 1310.90084
[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) · Zbl 1151.90036
[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) · Zbl 1188.90190
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.