Solving SDPvia LP 1 Abstract Asemidenite programming problem can be regarded as a … to solve the linear programming relaxations approximately … leading to a dense linear programming problem A Linear Programming Approach to Semidenite Programming Problems JohnE. Mitchell Department of Mathematical Sciences Rensselaer Polytechnic Institute Troy, NY 12180 USA mitchj@rpi.edu http://www.rpi.edu/~mitchj Joint work with Kartik Krishnan . IBMYorktown Heights 6April 2001 Solving SDPvia LP 1 Abstract Asemidenite programming problem can …

Asemidenite programming problem can be regarded as a convex nonsmooth optimization problem, so it can be represented asasemi-innitelinear programming problem. Thus, in principle, it can be solved usingacutting plane approach; we describe suchamethod. The cutting plane method uses an interior point algorithm to solve the linear programming relaxations approximately, because this resulted in the generation of better constraints than a simplex cutting plane method. Further, the bundle method of Helm berg and Rendl can be used to generateasetof linear constraints. Typically, these alone are not sucienttogivea good linear programming relaxation. Nonetheless, if they are used in conjunction with some families of problem speciccon- straints, tight LP relaxations can be obtained. Solving SDPvia LP 3 1 Introduction Standard form: min CX subject to A ( X )= b ( SDP ) X 0 ; with dual max bTy subject to AT y + S = C ( SDD ) S 0 X and S are square matrices. Constraints require that X and S be positive semidef- inite . Inner products are the Frobeniusinner product . AX = 2 6 6 6 6 6 6 6 4 A 1 X . . . A k X 3 7 7 7 7 7 7 7 5 , ATy =Pk i =1 y j A j ,where each A j is asymmetric matrix. C is symmetric and b is an k -vector. Primal-dual interior point approaches are limited in the size of problems they can solve….. Solving SDPvia LP 5 Primal formulation: min CX subject to A ( X )= b dT Xd 0 8 dwith jjdjj2 =1 : Since X is n n and symmetric, we have a linear program in n ( n +1) 2 variables. Need to be selective with the vectors d included in the constraints. For example, usea cutting plane approach to select vectors d . Typically, we will need some vectors d that are dense , leading to a dense linear programming problem.

Download A Linear Programming Approach to Semidenite Programming Problems.Pdf