ncku-talk2010-11-24

NCTS(South) Semidefinite Programming and Its Application to Polynomial Optimization Problems

DATE 2010-11-24　15:00-17:00

PLACE R204, 2F, NCTS, NCKU

SPEAKER Prof. Masakazu Kojima（Dept. of Mathematical and Computing Sciences, Tokyo Institute of Technology, Japan）

TITLE SOS and SDP Relaxation of Polynomial Optimization Problems

ABSTRACT Polynomial optimization problems (POP) are nonlinear optimization problems whose objective and constraint functions involve only polynomials. They, however, provide a general framework to represent various application problems in science and engineering. In particular, POPs include quadratic optimization problems with or without 0-1 constraints on their variables. POPs are nonconvex in general, and they have served as a unified mathematical model for the study of global optimization of nonconvex continuous and discrete optimization problems. This lecture presents a survey on the SDP relaxation method proposed by Lasserre in 2001 for solving polynomial optimization problems. We discuss the primal and dual approaches to derive the SDP and SOS relaxations, and their relationship. Exploiting structured sparsity in the both approaches is presented to enhance their computational efficiency. We also report numerical results on SparsePOP which is a MATLAB implementation of the sparse SDP relaxation for polynomial optimization problems.

NCTS(South) Semidefinite Programming and Its Application to Polynomial Optimization Problems

DATE	2010-11-24　15:00-17:00

PLACE	R204, 2F, NCTS, NCKU

SPEAKER	Prof. Masakazu Kojima（Dept. of Mathematical and Computing Sciences, Tokyo Institute of Technology, Japan）

TITLE	SOS and SDP Relaxation of Polynomial Optimization Problems

ABSTRACT	Polynomial optimization problems (POP) are nonlinear optimization problems whose objective and constraint functions involve only polynomials. They, however, provide a general framework to represent various application problems in science and engineering. In particular, POPs include quadratic optimization problems with or without 0-1 constraints on their variables. POPs are nonconvex in general, and they have served as a unified mathematical model for the study of global optimization of nonconvex continuous and discrete optimization problems. This lecture presents a survey on the SDP relaxation method proposed by Lasserre in 2001 for solving polynomial optimization problems. We discuss the primal and dual approaches to derive the SDP and SOS relaxations, and their relationship. Exploiting structured sparsity in the both approaches is presented to enhance their computational efficiency. We also report numerical results on SparsePOP which is a MATLAB implementation of the sparse SDP relaxation for polynomial optimization problems.