Optimization Online


Lagrangian-Conic Relaxations, Part I: A Unified Framework and Its Applications to Quadratic Optimization Problems

Naohiko Arima(nao_arima***at***me.com)
Sunyoung Kim(skim***at***ewha.ac.kr)
Masakazu Kojima(kojima***at***is.titech.ac.jp)
Kim-Chuan Toh(mattohkc***at***nus.edu.sg)

Abstract: In Part I of a series of study on Lagrangian-conic relaxations, we introduce a unified framework for conic and Lagrangian-conic relaxations of quadratic optimization problems (QOPs) and polynomial optimization problems (POPs). The framework is constructed with a linear conic optimization problem (COP) in a finite dimensional vector space endowed with an inner product, where the cone used is not necessarily convex. By imposing a copositive condition on the COP, we establish fundamental theoretical results for the COP, its conic relaxations, its Lagrangian-conic relaxations, and their duals. A linearly constrained QOP with complementarity constraints and a general POP can be reduced to the COP satisfying the copositivity condition. Then, the conic and Lagrangian-conic relaxations of such a QOP and POP are discussed in a unified manner. The Lagrangian-conic relaxation takes one of the simplest forms, which is very useful to design efficient numerical methods. As for applications of the framework, we discuss the completely positive programming relaxation, and a sparse doubly nonnegative relaxation for a linearly constrained QOP with complementarity constraints. The unified framework is applied to general POPs in Part II.

Keywords: Lagrangian-conic relaxation, completely positive programming relaxation, doubly nonnegative relaxation, convexification, quadratic optimization problems, exploiting sparsity.

Category 1: Linear, Cone and Semidefinite Programming (Other )

Category 2: Convex and Nonsmooth Optimization (Convex Optimization )


Download: [PDF]

Entry Submitted: 01/06/2014
Entry Accepted: 01/07/2014
Entry Last Modified: 01/06/2014

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 Optimization Society