Optimization Online


Trust-Region Problems with Linear Inequality Constraints: Exact SDP Relaxation, Global Optimality and Robust Optimization

V. Jeyakumar (v.jeyakumar***at***unsw.edu.au)
G. Li (g.li***at***unsw.edu.au)

Abstract: 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.

Keywords: Extended trust-regions problems, exact semi-definite programming relaxations, necessary and sufficient global optimality, strong duality, robust optimization

Category 1: Linear, Cone and Semidefinite Programming

Category 2: Robust Optimization

Category 3: Nonlinear Optimization (Quadratic Programming )

Citation: Applied mathematics report, UNSW, to appear in Mathematical Programming.

Download: [PDF]

Entry Submitted: 09/11/2013
Entry Accepted: 09/12/2013
Entry Last Modified: 09/12/2013

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society