  


An explicit equivalent positive semidefinite program for nonlinear 01 programs
Jean B. Lasserre (lasserrelaas.fr) Abstract: We consider the general nonlinear optimization problem in 01 variables and provide an explicit equivalent positive semidefinite program in $2^n1$ variables. The optimal values of both problems are identical. From every optimal solution of the former one easily find an optimal solution of the latter and conversely, from every solution of the latter one may construct an optimal solution of the former. For illustration, the equivalent psd program is explicited for quadratic 01 programs and MAXCUT in $\R^3$. For unconstrained 01 programs, a special representation in terms of weighted sum of squares is provided. Keywords: 01 programming; SDP relaxations; Category 1: Integer Programming (01 Programming ) Category 2: Linear, Cone and Semidefinite Programming (Semidefinite Programming ) Category 3: Other Topics (Other ) Citation: SIAM J. Optim. 12 (2002), pp. 756769. http://epubs.siam.org/sambin/dbq/article/38007 Download: Entry Submitted: 12/06/2001 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  