线性锥规划.ppt

CVX Weak Duality Theorem Strong Duality Theorem Strong Duality Theorem for SDP SDP in Convex Optimization 法1 法2 SDP for Eigenvalue Optimization SDP in Combinatorial Optimization The Coin-Toss Method [Sahni Gonzales ’76 M. X. Goemans and D. P. Williamson. .879-approximation algorithms for max cut and max2sat. In STOC, pages 422–431, 1994. Interior-point Methods the logarithmic barrier problem Karush-Kuhn-Tucker conditions for BSDP (θ) nonlinear The Algorithm The Newton Step Normal Equations Let D ’ and y’ denote the solution to the Normal Equations. Complexity Analysis 线性锥规划 Linear Conic Programming 内容提要 线性锥规划 二阶锥规划及应用 半正定规划 对偶理论 应用 内点算法 求解软件 Cones Conic optimization problem Choices for K Second-order Cone Programming (SOCP) 二阶锥规划 Algorithms and Complexityof SOCP Applications of SOCPLinear regression Applications of SOCP constrained least-squares Applications of SOCP Robust LP Applications of SOCP Robust QP Applications of SOCP Convex QCQP Applications of SOCP Fractional Programming The Conic Sections (Apollonius, 200 B.C.) Semidefinite Programming (SDP) 半正定规划 The trace operator An inner product Positive semidefinite matrices a linear function Example linear program LP is a special case of SDP Duality Alternative System (Farkas Lemma) 反例 Alternative System for SDP (Farkas Lemma)I