Semidefinite Programming

Link of the Site

SDP

• Introduction of SDP, several examples of SDP.
• Duality properties, dual problem is also SDP, optimal conditions, duality gap, primal-dual problem.
• Log-barrier function, analytic center, central path (objective function, duality gap).

In summary, primal-dual algorithms for semidefinite programs share many of the features and characteristics of the corresponding algorithms for LPs. Our final conclusion is therefore that it is not much harder to solve a rather wide class of nonlinear convex optimization problems than it is to solve LPs.

Contents:

• 1. Introduction
• 2. Examples
  • 2.1 QCQP
  • 2.2 Maximum eigenvalues and matrix norm minimization
  • 2.3 Logarithmic Chebychev approximation
  • 2.4 Structural optimziation
  • 2.5 Pattern separation by ellipsoid
  • 2.6 Statistics
  • 2.7 Control and System theory
• 3. Duality
  • 3.1 Strong Duality
  • 3.2 Optimal Condition
  • 3.3 Primal-Dual
• 4. The Central Path
  • 4.1 Barrier Function for a linear matrix inequality
  • 4.2 Analytic center
  • 4.4 Central Path: Objective
  • 4.5 Central Path: Duality gap
• 5. Primal-dual potential reduction methods
  • 5.1 General Description
  • 5.2 Potential reduction method 1
  • 5.3 Potential reduction method 2
  • 5.4 Potential reduction method 3
  • 5.5 Plane search
  • 5.6 Numerical examples
• 6. Phase I and Phase I-II methods
  • 6.1 Gig-M method
    • 6.1.1 Case 1
    • 6.1.2 Case 2
    • 6.1.3 Case 3
  • 6.2 Others