Second-order cone programming

Second-order cone programming

A second-order cone program (SOCP) is a convex optimization problem of the form

:minimize f^T x subject to

:lVert A_i x + b_i Vert_2 leq c_i^T x + d_i,quad i = 1,dots,m

:Fx = g

where the problem parameters are f in mathbb{R}^n, A_i in mathbb{R}^n_i} imes n}, b_i in mathbb{R}^{n_I}, c_i in mathbb{R}^n, d_i in mathbb{R}, F in mathbb{R}^{p imes n}, and g in mathbb{R}^p. Here xinmathbb{R}^n is the optimization variable. When A_i = 0 for i = 1,dots,m, the SOCP reduces to a linear program. When c_i = 0 for i = 1,dots,m, the SOCP is equivalent to a convex Quadratically constrained quadratic program. SOCPs can be solved with great efficiency by interior point methods.

Example: Stochastic Programming

Consider a stochastic linear program in inequality form

:minimize c^T x subject to

: P(a_i^T(x) geq b_i) geq p, quad i = 1,dots,m

where the parameters a_i are independent Gaussian random vectors with mean ar{a}_i and covariance Sigma_i and pgeq0.5. This problem can be expressed as the SOCP

:minimize c^T x subject to

: ar{a}_i^T (x) + Phi^{-1}(1-p) lVert Sigma_i^{1/2} x Vert_2 geq b_i , quad i = 1,dots,m

where Phi^{-1} is the inverse error function.

External links

* Stephen Boyd and Lieven Vandenberghe, [http://www.stanford.edu/~boyd/cvxbook/ Convex Optimization] (book in pdf).

;Software
* [http://www.mosek.com/ MOSEK] — The first commercially available software package for solution SOCP.
* [http://www.ilog.com/products/cplex/product/algorithms.cfm CPLEX] — Full-featured solver for large scale linear, quadratic, and integer programming problems, including SOCP.


Wikimedia Foundation. 2010.

Игры ⚽ Нужна курсовая?

Look at other dictionaries:

  • Cone — This disambiguation page lists articles associated with the same title. If an internal link led you here, you may wish to change the link to point directly to the intended article …   Wikipedia

  • Semidefinite programming — (SDP) is a subfield of convex optimization concerned with the optimization of a linear objective function over the intersection of the cone of positive semidefinite matrices with an affine space.Semidefinite programming is a relatively new field… …   Wikipedia

  • David Cone — at the 2010 Old Timers Day. Pitcher Born: January 2, 1963 (1963 01 02) …   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

  • 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 (S) — NOTOC S S duality S matrix S plane S transform S unit S.O.S. Mathematics SA subgroup Saccheri quadrilateral Sacks spiral Sacred geometry Saddle node bifurcation Saddle point Saddle surface Sadleirian Professor of Pure Mathematics Safe prime Safe… …   Wikipedia

  • Optimization (mathematics) — In mathematics, the term optimization, or mathematical programming, refers to the study of problems in which one seeks to minimize or maximize a real function by systematically choosing the values of real or integer variables from within an… …   Wikipedia

  • 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

  • CPLEX — Infobox Software name = CPLEX developer = ILOG Inc. latest release version = 11.1 genre = Technical computing status = Active license = Proprietary website = [http://www.ilog.com/products/cplex/ ILOG CPLEX product page] ILOG CPLEX (often… …   Wikipedia

  • 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… …   Wikipedia

Share the article and excerpts

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