  


Simplified Copositive and Lagrangian Relaxations for Linearly Constrained Quadratic Optimization Problems in Continuous and Binary Variables
Naohiko Arima (arima.n.abm.titech.ac.jp) Abstract: For a quadratic optimization problem (QOP) with linear equality constraints in continuous nonnegative variables and binary variables, we propose three relaxations in simplified forms with a parameter $\lambda$: Lagrangian, completely positive, and copositive relaxations. These relaxations are obtained by reducing the QOP to an equivalent QOP with a single quadratic equality constraint in nonnegative variables, and applying the Lagrangian relaxation to the resulting QOP. As a result, an unconstrained QOP with a Lagrangian multiplier $\lambda$ in nonnegative variables is obtained. The other two relaxations are a primaldual pair of a completely positive programming (CPP) relaxation in a variable matrix with the upperleft element set to 1 and a copositive programming (CP) relaxation in a single variable. The CPP relaxation is derived from the unconstrained QOP with the parameter $\lambda$, based on the recent result by Arima, Kim and Kojima. The three relaxations with a same parameter value $\lambda > 0$ work as relaxations of the original QOP. The optimal values $\zeta(\lambda)$ of the three relaxations coincide, and monotonically converge to the optimal value of the original QOP as $\lambda$ tends to infinity under a moderate assumption. The parameter $\lambda$ serves as a penalty parameter when it is chosen to be positive. Thus, the standard theory on the penalty function method can be applied to establish the convergence. Keywords: Nonconvex quadratic optimization, 01 mixed integer program, Lagrangian relaxation, copositve programming relaxation, completely positive programming relaxation Category 1: Linear, Cone and Semidefinite Programming Citation: Research Report B469, Department of Mathematical and Computing Sciences, Tokyo Institute of Technology, OhOkayama, Meguroku, Tokyo 1528552, October 2012 Download: [PDF] Entry Submitted: 10/22/2012 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  