Content area
Full Text
J Glob Optim (2013) 55:209226
DOI 10.1007/s10898-012-9857-8
V. Jeyakumar G. Y. Li
Received: 12 July 2010 / Accepted: 24 January 2012 / Published online: 7 February 2012 Springer Science+Business Media, LLC. 2012
Abstract In this paper we examine non-convex quadratic optimization problems over a quadratic constraint under unknown but bounded interval perturbation of problem data in the constraint and develop criteria for characterizing robust (i.e. uncertainty-immunized) global solutions of classes of non-convex quadratic problems. Firstly, we derive robust solvability results for quadratic inequality systems under parameter uncertainty. Consequently, we obtain characterizations of robust solutions for uncertain homogeneous quadratic problems, including uncertain concave quadratic minimization problems and weighted least squares. Using homogenization, we also derive characterizations of robust solutions for non-homogeneous quadratic problems.
Keywords Non-convex quadratic programming under uncertainty Robust optimization
Single quadratic constraint Robust solutions Global optimality conditions
Mathematics Subject Classication (2000) 90C20 90C30 90C26 90C46
1 Introduction
Consider the non-convex quadratic optimization model problem with a quadratic inequality constraint
The authors are grateful to the referee and the editors for their valuable comments and constructive suggestions which have contributed to the nal preparation of the paper. Research was partially supported by a grant from the Australian Research Council.
V. Jeyakumar (B) G. Y. Li
Department of Applied Mathematics, University of New South Wales, Sydney 2052, Australia e-mail: [email protected]
G. Y. Lie-mail: [email protected]
Robust solutions of quadratic optimization over single quadratic constraint under interval uncertainty
123
210 J Glob Optim (2013) 55:209226
minxR
s.t. 1
2 xT Bx ,
where the data inputs consist of the n n matrices A, B and the vector a, and is a scalar.
Model problems of this form, in particular, appear in wireless communication and signal processing [19,26], and also arise as a subproblem in trust-region algorithms for unconstrained optimization and have been studied extensively in the literature [18,2022,27,30]. These problems enjoy theoretically useful and computationally attractive features, including no duality gap [27,31], tight semi-definite programming relaxation [22,29] and dual characterization of the solution [13]. Unfortunately, these features can not, in general, be extended to quadratic problems with more than one quadratic constraint [1,2,16,22]. Moreover, in these models, it is assumed that data inputs are precisely known despite the reality of input data uncertainty in real-world models due to...