Optimization Online


Generalized Lagrangian Duals and Sums of Squares Relaxations of Sparse Polynomial Optimization Problems

Sunyoung Kim (skim***at***ewha.ac.kr)
Masakazu Kojima (kojima***at***is.titech.ac.jp)
Hayato Waki (waki9***at***is.titech.ac.jp)

Abstract: Sequences of generalized Lagrangian duals and their SOS (sums of squares of polynomials) relaxations for a POP (polynomial optimization problem) are introduced. Sparsity of polynomials in the POP is used to reduce the sizes of the Lagrangian duals and their SOS relaxations. It is proved that the optimal values of the Lagrangian duals in the sequence converge to the optimal value of the POP using a method from the penalty function approaches. The sequence of SOS relaxations is transformed into a sequence of SDP (semidefinite program) relaxations of the POP, which correspond to duals of modification and generalization of SDP relaxations given by Lasserre for the POP.

Keywords: Polynomial Optimization Problem, Sparsity, Global Optimization, Lagrangian Relaxation, Lagrangian Dual, Sums of Squares Optimization, Semidefinite Program, Semidefinite Program Relaxation

Category 1: Global Optimization (Theory )

Category 2: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Citation: Research Report B-395, Dept. of Mathematical and Computing Sciences, Tokyo Institute of Technology, Tokyo, Japan, Sept./2003

Download: [Postscript][PDF]

Entry Submitted: 09/29/2003
Entry Accepted: 09/30/2003
Entry Last Modified: 09/29/2003

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society