ICCOPT 2013 Talk, Room 1.1, Thursday, August 1, 11:00-12:30

 Speaker: Naohiko Arima, Tokyo Institute of Technology, Japan
 Title: A quadratic optimization model for completely positive programming and its application to 0-1 mixed integer linearly constrained quadratic optimization problems
 Co-authors: Sunyoung Kim, Masakazu Kojima

 Abstract:
Scientific Program

We propose a class of QOP (quadratic optimization problems) whose exact global optimal values can be obtained by its CPP (completely positive programming relaxation problems). The objective and constraint functions of this QOP model are all represented in terms of quadratic forms, and all constraints are homogeneous equalities except one inhomogeneous equality where the quadratic form is set to be one. It is shown that the QOP model represents fairly general quadratically constrained quadratic optimization problems. First, we provide conditions for the QOP model to have the exactly same global optimal value as its CPP. Next, we consider a linearly constrained QOP in continuous and binary variables as a special case. We reformulate the QOP into a simple QOP with a single equality constraint in nonnegative variables, and derive a CPP and its dual problem CP (copositive programming problem) which all have the same optimal value as the original QOP. We also introduce Lagrangian relaxation problems, with a single positive Lagrangian parameter, of the simplified QOP, and drive its CPP and CP, which have a common optimal value for a fixed positive Lagrangian parameter. We show that the common optimal value of these three Lagrangian relaxation problems monotonically converges to the exact global optimal value of the original QOP as the Lagrangian parameter tends to infinity.


 Talk in: Organized Session Thu.B.11 Modeling and computation in copositive programming
 Cluster: Conic and polynomial optimization


 Go to: Thu.B
 Go to: unframed Scientific Program

 Go to: ICCOPT 2013 Main Webpage