Conic optimization

Conic optimization

Conic optimization is a subfield of convex optimization that studies a class of structured convex optimization problems called conic optimization problems. A conic optimization problem consists of minimizing a convex function over the intersection of an affine subspace and a convex cone.

The class of conic optimization problems is a subclass of convex optimization problems and it includes some of the most well known classes of convex optimization problems, namely linear and semidefinite programming.

Contents

Definition

Given a real vector space X, a convex, real-valued function

f:C \to \mathbb R

defined on a convex cone C \subset X, and an affine subspace \mathcal{H} defined by a set of affine constraints h_i(x) = 0 \ , a conic optimization problem is to find the point x in C \cap \mathcal{H} for which the number f(x) is smallest. Examples of C include the positive semidefinite matrices \mathbb{S}^n_{+}, the positive orthant x \geq \mathbf{0} for x \in \mathbb{R}^n, and the second-order cone \left \{ (x,t) \in \mathbb{R}^{n+1} : \lVert x \rVert \leq t \right \} . Often f \ is a linear function, in which case the conic optimization problem reduces to a semidefinite program, a linear program, and a second order cone program, respectively.

Duality

Certain special cases of conic optimization problems have notable closed-form expressions of their dual problems.

Conic LP

The dual of the conic linear program

minimize c^T x \
subject to Ax = b, x \in C \

is

maximize b^T y \
subject to y^T A + s= c, s \in C^* \

where C * denotes the dual cone of C \ .

Semidefinite Program

The dual of a semidefinite program in inequality form,

minimize c^T x \ subject to

x_1 F_1 + \cdots + x_n F_n + G \leq 0

is given by

maximize \mathrm{tr}\ (GZ)\ subject to

\mathrm{tr}\ (F_i Z) +c_i =0,\quad i=1,\dots,n
Z \geq0

External links


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать курсовую

Look at other dictionaries:

  • Convex optimization — Convex minimization, a subfield of optimization, studies the problem of minimizing convex functions over convex sets. Given a real vector space X together with a convex, real valued function defined on a convex subset of X, the problem is to find …   Wikipedia

  • Mathematical optimization — For other uses, see Optimization (disambiguation). The maximum of a paraboloid (red dot) In mathematics, computational science, or management science, mathematical optimization (alternatively, optimization or mathematical programming) refers to… …   Wikipedia

  • List of mathematics articles (C) — NOTOC C C closed subgroup C minimal theory C normal subgroup C number C semiring C space C symmetry C* algebra C0 semigroup CA group Cabal (set theory) Cabibbo Kobayashi Maskawa matrix Cabinet projection Cable knot Cabri Geometry Cabtaxi number… …   Wikipedia

  • List of numerical analysis topics — This is a list of numerical analysis topics, by Wikipedia page. Contents 1 General 2 Error 3 Elementary and special functions 4 Numerical linear algebra …   Wikipedia

  • Analyse numérique — L’analyse numérique est une discipline des mathématiques. Elle s’intéresse tant aux fondements théoriques qu’à la mise en pratique des méthodes permettant de résoudre, par des calculs purement numériques, des problèmes d’analyse mathématique.… …   Wikipédia en Français

  • Semidefinite Optimierung — In der Semidefiniten Programmierung (SDP, auch Semidefinite Optimierung) werden Optimierungsprobleme untersucht, deren Variablen keine Vektoren, sondern symmetrische Matrizen sind. Als Nebenbedingung wird verlangt, dass diese Matrizen positiv… …   Deutsch Wikipedia

  • Semidefinite Programmierung — In der Semidefiniten Programmierung (SDP, auch Semidefinite Optimierung) werden Optimierungsprobleme untersucht, deren Variablen keine Vektoren, sondern symmetrische Matrizen sind. Als Nebenbedingung wird verlangt, dass diese Matrizen positiv… …   Deutsch Wikipedia

  • mathematics — /math euh mat iks/, n. 1. (used with a sing. v.) the systematic treatment of magnitude, relationships between figures and forms, and relations between quantities expressed symbolically. 2. (used with a sing. or pl. v.) mathematical procedures,… …   Universalium

  • Ellipse — Elliptical redirects here. For the exercise machine, see Elliptical trainer. This article is about the geometric figure. For other uses, see Ellipse (disambiguation). Not to be confused with ellipsis. An ellipse obtained as the intersection of a… …   Wikipedia

  • History of mathematics — A proof from Euclid s Elements, widely considered the most influential textbook of all time.[1] …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”