×

zbMATH — the first resource for mathematics

Trust-region problems with linear inequality constraints: exact SDP relaxation, global optimality and robust optimization. (English) Zbl 1297.90105
Summary: The trust-region problem, which minimizes a nonconvex quadratic function over a ball, is a key subproblem in trust-region methods for solving nonlinear optimization problems. It enjoys many attractive properties such as an exact semi-definite linear programming relaxation (SDP-relaxation) and strong duality. Unfortunately, such properties do not, in general, hold for an extended trust-region problem having extra linear constraints. This paper shows that two useful and powerful features of the classical trust-region problem continue to hold for an extended trust-region problem with linear inequality constraints under a new dimension condition. First, we establish that the class of extended trust-region problems has an exact SDP-relaxation, which holds without the Slater constraint qualification. This is achieved by proving that a system of quadratic and affine functions involved in the model satisfies a range-convexity whenever the dimension condition is fulfilled. Second, we show that the dimension condition together with the Slater condition ensures that a set of combined first and second-order Lagrange multiplier conditions is necessary and sufficient for global optimality of the extended trust-region problem and consequently for strong duality. Through simple examples we also provide an insightful account of our development from SDP-relaxation to strong duality. Finally, we show that the dimension condition is easily satisfied for the extended trust-region model that arises from the reformulation of a robust least squares problem (LSP) as well as a robust second order cone programming model problem (SOCP) as an equivalent semi-definite linear programming problem. This leads us to conclude that, under mild assumptions, solving a robust LSP or SOCP under matrix-norm uncertainty or polyhedral uncertainty is equivalent to solving a semi-definite linear programming problem and so, their solutions can be validated in polynomial time.

MSC:
90C20 Quadratic programming
90C22 Semidefinite programming
90C26 Nonconvex programming, global optimization
49N30 Problems with incomplete information (optimization)
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Alizadeh, F; Goldfarb, D, Second-order cone programming, Math. Program. Ser. B, 95, 351-370, (2003) · Zbl 1153.90522
[2] Burer, S., Anstreicher, K.M.: Second-order cone constraints for extended trust-region problems. Preprint, Optimization online, March (2011) · Zbl 1298.90062
[3] Beck, A; Eldar, YC, Strong duality in nonconvex quadratic optimization with two quadratic constraints, SIAM J. Optim., 17, 844-860, (2006) · Zbl 1128.90044
[4] Beck, A, Convexity properties associated with nonconvex quadratic matrix functions and applications to quadratic programming, J. Optim. Theory Appl., 142, 1-29, (2009) · Zbl 1188.90190
[5] Ben-Tal, A., Nemirovski, A.: Lectures on Modern Convex Optimization: Analysis, Algorithms and Engineering Applications. SIAM-MPS, Philadelphia (2000) · Zbl 0986.90032
[6] Ben-Tal, A., Ghaoui, L.E., Nemirovski, A.: Robust Optimization. Princeton Series in Applied Mathematics (2009) · Zbl 1221.90001
[7] Ben-Tal, A; Nemirovski, A; Roos, C, Robust solutions of uncertain quadratic and conic quadratic problems, SIAM J. Optim., 13, 535-560, (2002) · Zbl 1026.90065
[8] Bertsimas, D; Brown, D; Caramanis, C, Theory and applications of robust optimization, SIAM Rev., 53, 464-501, (2011) · Zbl 1233.90259
[9] Bertsimas, D; Pachamanova, D; Sim, M, Robust linear optimization under general norms, Oper. Res. Lett., 32, 510-516, (2004) · Zbl 1054.90046
[10] Conn, A.R., Gould, N.I.M., Toint, P.L.: Trust-Region Methods. MPS-SIAM Series in Optimization, SIAM, Philadelphia, PA (2000) · Zbl 0958.65071
[11] Dines, LL, On the mapping of quadratic forms, Bull. Am. Math. Soc., 47, 494-498, (1941) · Zbl 0027.15004
[12] Fradkov, AL; Yakubovich, VA, The S-procedure and duality relations in nonconvex problems of quadratic programming. leningrad, Russia, Vestn. Leningr. Univ., 6, 101-109, (1979) · Zbl 0423.49016
[13] Ghaoui, L; Lebret, H, Robust solution to least-squares problems with uncertain data, SIAM J. Matrix Anal. Appl., 18, 1035-1064, (1997) · Zbl 0891.65039
[14] Jeyakumar, V; Lee, GM; Li, GY, Alternative theorems for quadratic inequality systems and global quadratic optimization, SIAM J. Optim., 20, 983-1001, (2009) · Zbl 1197.90315
[15] Jeyakumar, V; Li, G, Strong duality in robust convex programming: complete characterizations, SIAM J. Optim., 20, 3384-3407, (2010) · Zbl 1228.90075
[16] Jeyakumar, V., Li, G.: Exact SDP Relaxations for classes of nonlinear semidefinite programming problems. Oper. Res. Lett. (2012). doi:10.1016/j.orl.2012.09.006 · Zbl 1287.90047
[17] Jeyakumar, V; Huy, NQ; Li, G, Necessary and sufficient conditions for S-lemma and nonconvex quadratic optimization, Optim. Eng., 10, 491-503, (2009) · Zbl 1273.90141
[18] Jeyakumar, V; Li, G, A robust von-Neumann minimax theorem for zero-sum games under bounded payoff uncertainty, Oper. Res. Lett., 39, 109-114, (2011) · Zbl 1218.91006
[19] Jeyakumar, V; Rubinov, AM; Wu, ZY, Non-convex quadratic minimization problems with quadratic constraints: global optimality conditions, Math. Program. Ser. A, 110, 521-541, (2007) · Zbl 1206.90178
[20] Jeyakumar, V; Wolkowicz, H, Zero duality gaps in infinite-dimensional programming, J. Optim. Theory Appl., 67, 87-108, (1990) · Zbl 0687.90077
[21] More, JJ, Generalizations of the trust region subproblem, Optim. Methods Softw., 2, 189-209, (1993)
[22] Pardalos, P., Romeijn, H.: Handbook in Global Optimization, vol. 2. Kluwer Academic Publishers, Dordrecht (2002) · Zbl 0991.00017
[23] Peng, JM; Yuan, YX, Optimality conditions for the minimization of a quadratic with two quadratic constraints, SIAM J. Optim., 7, 579-594, (1997) · Zbl 0891.90150
[24] Pólik, I; Terlaky, T, A survey of the S-lemma, SIAM Rev., 49, 371-418, (2007) · Zbl 1128.90046
[25] Polyak, BT, Convexity of quadratic transformation and its use in control and optimization, J. Optim. Theory Appl., 99, 563-583, (1998) · Zbl 0961.90074
[26] Powell, MJD; Yuan, Y, A trust region algorithm for equality constrained optimization, Math. Program., 49, 189-211, (1990) · Zbl 0816.90121
[27] Stern, RJ; Wolkowicz, H, Indefinite trust region subproblems and nonsymmetric eigenvalue perturbations, SIAM J. Optim., 5, 286-313, (1995) · Zbl 0846.49017
[28] Sturm, JF; Zhang, SZ, On cones of nonnegative quadratic functions, Math. Oper. Res., 28, 246-267, (2003) · Zbl 1082.90086
[29] Yakubovich, YA, The S-procedure in nonlinear control theory, Vestn. Leningr. Univ., 4, 62-77, (1971) · Zbl 0232.93010
[30] Ye, YY; Zhang, SZ, New results of quadratic minimization, SIAM J. Optim., 14, 245-267, (2003) · Zbl 1043.90064
[31] Yuan, YX, On a subproblem of trust region algorithms for constrained optimization, Math. Program., 47, 53-63, (1990) · Zbl 0711.90062
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.