×
Jeyakumar, V.; Srisatkunarajah, S.

Lagrange multiplier necessary conditions for global optimality for non-convex minimization over a quadratic constraint via S-lemma. (English) Zbl 1154.90574

Optim. Lett. 3, No. 1, 23-33 (2009).
Summary: We present Lagrange multiplier necessary conditions for global optimality that apply to non-convex optimization problems beyond quadratic optimization problems subject to a single quadratic constraint. In particular, we show that our optimality conditions apply to problems where the objective function is the difference of quadratic and convex functions over a quadratic constraint, and to certain class of fractional programming problems. Our necessary conditions become necessary and sufficient conditions for global optimality for quadratic minimization subject to quadratic constraint. As an application, we also obtain global optimality conditions for a class of trust-region problems. Our approach makes use of outer-estimators, and the powerful S-lemma which has played key role in control theory and semidefinite optimization. We discuss numerical examples to illustrate the significance of our optimality conditions.

Cited in 11 Documents

MSC:

90C26 Nonconvex programming, global optimization
90C46 Optimality conditions and duality in mathematical programming
90C32 Fractional programming

Keywords:

smooth non-convex minimization; difference of quadratic and convex functions; fractional programs; global optimality; Lagrange multipliers; single quadratic constraint
Cite Review PDF
Full Text: DOI

References:

[1] Ben-Tal A., Nemirovski A.: Lectures on Modern Convex Optimization: Analysis Algorithms and Engineering Applications. SIAM-MPS, Philadelphia (2000) · Zbl 0986.90032
[2] Davidon W.C.: Conic approximations and colinear scalings for optimizers. SIAM J. Numer. Anna. 17, 268–281 (1980) · Zbl 0424.65026 · doi:10.1137/0717023
[3] Di S., Sun W.Y.: A trust region method for conic model to solve unconstrained optimization. Optim. Meth. Soft. 6, 237–263 (1996) · doi:10.1080/10556789608805637
[4] Derinkuyu K., Pinar M.C.: On the S-procedure and some variants. Math. Methods Oper. Res. 64, 55–77 (2006) · Zbl 1115.93025 · doi:10.1007/s00186-006-0070-8
[5] Floudas C.A., Visweswaran V.: Quadratic optimization. In: Horst, R., Pardalos, P.M. (eds) Handbook of Global Optimization, pp. 217–269. Kluwer, The Netherlands (1995) · Zbl 0833.90091
[6] Hiriart-Urruty J.B.: Global Optimality Conditions in Maximizing a Convex Quadratic Function under Convex Quadratic Constraints. J. Global Optim. 21, 445–455 (2001) · Zbl 1172.90501 · doi:10.1023/A:1012752110010
[7] Jeyakumar V.: Farkas Lemma: Generalizations, Encylopedia of optimization, vol. 2, pp. 87. Kluwer, Boston (2000)
[8] Jeyakumar V., Rubinov A.M., Wu Z.Y.: Sufficient global optimality conditions for non-convex quadratic minimization problems with box constraints. J. Global Optim. 36, 471–481 (2006) · Zbl 1131.90060 · doi:10.1007/s10898-006-9022-3
[9] Jeyakumar V., Rubinov A.M., Wu Z.Y.: Non-convex quadratic minimization problems with quadratic constraints: Global optimality conditions. Math. Program. Ser. A. 110, 521–541 (2007) · Zbl 1206.90178 · doi:10.1007/s10107-006-0012-5
[10] Moré J.: Generalizatons of the trust region problem. Optim. Meth. Soft. 2, 189–209 (1993) · doi:10.1080/10556789308805542
[11] Peng J.M., Yuan Y.: Optimization conditions for the minimization of a quadratic with two quadratic constraints. SIAM J. Optim. 7, 579–594 (1997) · Zbl 0891.90150 · doi:10.1137/S1052623494261520
[12] Ni Q.: Optimality conditions for trust-region subproblems involving a conic model. SIAM J. Optim. 3, 836–837 (2005) · Zbl 1114.90126
[13] Pardalos P., Romeijn H.: Handbook in Global Optimization, vol. 2. Kluwer, Dordrecht (2002) · Zbl 0991.00017
[14] Polyak B.T.: Convexity of quadratic transformations and its use in control and optimization. J. Optim. Theor. Appl. 99, 553–583 (1998) · Zbl 0961.90074 · doi:10.1023/A:1021798932766
[15] Pólik I., Terlaky T.: A survey of the S-Lemma. SIAM Rev. 49, 371–418 (2007) · Zbl 1128.90046 · doi:10.1137/S003614450444614X
[16] Yakubovich V.A.: The S-procedure in nonlinear control theory. Vestnik Leningr. Univ. 4, 73–93 (1977)
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.