清华大学凸优化讲义 qcqp-integer_8630010

时间：2025-04-21

清华大学凸优化讲义

五道口最有人气的论坛 http://www.77cn.com.cn/bbs

Extended Canonical Duality and Conic Programming for Solving 0-1 Quadratic Programming ProblemsWenxun Xing Department of Mathematical Sciences, Tsinghua University, Beijing, 100084 Email: wxing@http://www.77cn.com.cn Coauthors: Cheng Lu, Zhenbo Wang and Shu-Cherng Fang

五道口最好的生活网 http://www.77cn.com.cnTsinghua University, June, 2010

清华大学凸优化讲义

OUTLINE五道口最有人气的论坛 http://www.77cn.com.cn/bbs1

0-1 Quadratic Programming Canonical duality approach Canonical duality for 0-1 quadratic programming Extended canonical duality and conic programming Practical algorithm and numerical experiments Concluding remarks

五道口最好的生活网 http://www.77cn.com.cnTsinghua University, June, 2010

清华大学凸优化讲义

0-1 Quadratic Programming (QIP)五道口最有人气的论坛 http://www.77cn.com.cn/bbsZ0= min F (x)= 1 x T Qx+ c T x 2 s.t. x∈{0, 1}n, where Q is an n× n real symmetric matrix and c is a vector in Rn . QIP in applications: the max-cut problem in combinatorial optimization. QIP is NP-Hard. Quadratically constrained quadratic problem (QCQP) Z0= min F (x)= 1 x T Qx+ c T x 2 s.t. xi2 xi= 0, i= 1, 2,···, n.

五道口最好的生活网 http://www.77cn.com.cnTsinghua University, June, 2010

清华大学凸优化讲义

Solution procedures for (QIP)Find an exact global optimal solution to QIP: some well performed enumeration strategies like the branch-and-bound algorithm with a lower bound estimation. Approximation algorithms for nding an approximate solution to some classes of quadratic integer problems, the 0.878 approximation algorithm for max-cut. Identify some sub-classes that can be solved in polynomial time, for examples, the canonical duality theory, spectrum decomposition methods. Our work extends the canonical duality theory to solve the 0-1 quadratic programming problem, discovers a new global optimality condition for solving QIP and identi es a new solvable sub-class of QIP .

五道口最有人气的论坛 http://www.77cn.com.cn/bbs

五道口最好的生活网 http://www.77cn.com.cnTsinghua University, June, 2010

清华大学凸优化讲义

Recent 0-1 quadratic programming papersS.-C. Fang, D.Y. Gao, R.-L. Sheu and S.-Y. Wu, Canonical dual approach to solving 0-1 quadratic programming problem, J. Industrial and Management Optimization, 3, (2007), 125-142. C. Lu, Z. Wang and W. Xing, An improved lower bound and approximation algorithm for binary constrained quadratic programming problem, J. Global Optimization, DOI: 10.1007/s10898-009-9504-1. X. Sun, C. Liu, D. Li and J. Gao, On duality gap in binary quadratic programming, available at: http://www.77cn.com.cn/DB FILE/2010/01/2512.pdf. Z. Wang, S.-C. Fang, D.Y. Gao and W. Xing, Global extremal conditions for multi-integer quadratic programming, J. Industrial and Management Optimization, 4, (2008), 213-225. Z. Wang, S.-C. Fang, D.Y. Gao and W. Xing, Canonical dual approach to solving the maximum cut problem, Working Paper, to appear in J. Global Optimization.五道

口最好的生活网 http://www.77cn.com.cnTsinghua University, June, 2010

五道口最有人气的论坛 http://www.77cn.com.cn/bbs

清华大学凸优化讲义

Canonical duality approachPrimal Problem

五道口最有人气的论坛 http://www.77cn.com.cn/bbsZ0= min s.t.1 P(x)= 2 x T Q0 x+ f0T x 1 T 2 x Qi x

+ fiT x≤ ci, i= 1, 2,···, m,

Lagrangian Function L(x,λ)= 1 T x (Q0+ 2m m m

λi Qi )x+ (f0+i=1 i=1

λi fi )T x i=1

λi ci,

whereλ= (λ1,λ2,···,λm )≥ 0. Bridge: Karush-Kuhn-Tucker condition L(x,λ)= (Q0+ mλi Qi )x+ f0+ mλi fi= 0 x i=1 i=1 λj ( 1 x T Qj x+ fjT x cj )= 0, j= 1, 2,···, m, 2 λ≥ 0.

五道口最好的生活网 http://www.77cn.com.cn

Tsinghua University, June, 2010

清华大学凸优化讲义

Canonical duality approachKey Assumption: (Q0+¯ x= (Q0+i=1

五道口最有人气的论坛 ) is invertible. http://www.77cn.com.cn/bbs mλQi=1 i i m m

λi Qi ) 1 (f0+i=1

λi fi ).

Canonical Duality Function¯ P d (λ)= L(x,λ)= 1 (f0+ 2m m m

λi fi )T (Q0+i=1 i=1

λi Qi ) 1 (f0+i=1

λi fi ) λT C.

五道口最好的生活网 http://www.77cn.com.cnTsinghua University, June, 2010