  


On the setsemidefinite representation of nonconvex quadratic programs over arbitrary feasible sets
Gabriele Eichfelder (Gabriele.Eichfelderam.unierlangen.de) Abstract: In the paper we prove that any nonconvex quadratic problem over some set $K\subset \mathbb{R}^n$ with additional linear and binary constraints can be rewritten as linear problem over the cone, dual to the cone of Ksemidefinite matrices. We show that when K is defined by one quadratic constraint or by one concave quadratic constraint and one linear inequality, then the resulting Ksemidefinite problem is actually a semidefinite programming problem. This generalizes a results obtained by Sturm and Zhang ([J.F. Sturm and S. Zhang, On cones of nonnegative quadratic functions. Math. Oper. Res. 28 (2003)]), since we can handle problems with many linear and binary constraints. Our result also generalizes the wellknown completely positive representation result from Burer ([S. Burer, On the copositive representation of binary and continuous nonconvex quadratic programs. Math. Program. 120 (Ser. A) (2009), pp. 479–495]), which is actually a special instance of our result with $K=\mathbb{R}^n$. Keywords: setpositivity, semidefinite programming, copositive programming, mixed integer programming. Category 1: Linear, Cone and Semidefinite Programming Category 2: Nonlinear Optimization (Quadratic Programming ) Category 3: Convex and Nonsmooth Optimization Citation: Preprint No. 349, PreprintSeries of the Institute of Applied Mathematics, Univ. ErlangenNürnberg, Germany, 2011. See also published version in Optimization Letters DOI: 10.1007/s1159001204503 Download: [PDF] Entry Submitted: 06/30/2011 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  