World Library  
Flag as Inappropriate
Email this Article

Second-order cone programming

Article Id: WHEBN0007500026
Reproduction Date:

Title: Second-order cone programming  
Author: World Heritage Encyclopedia
Language: English
Subject: AMPL, MOSEK, FICO Xpress, Nl (format), Convex optimization
Collection: Convex Optimization, Mathematical Optimization
Publisher: World Heritage Encyclopedia
Publication
Date:
 

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 \rVert_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}\times n}, \ b_i \in \mathbb{R}^{n_i}, \ c_i \in \mathbb{R}^n, \ d_i \in \mathbb{R}, \ F \in \mathbb{R}^{p\times n}, and g \in \mathbb{R}^p. Here x\in\mathbb{R}^n is the optimization variable. [1] 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 linear program. Quadratically constrained quadratic programs can also be formulated as SOCPs by reformulating the objective function as a constraint. Semidefinite programming subsumes SOCPs as the SOCP constraints can be written as linear matrix inequalities (LMI) and can be reformulated as an instance of semi definite program. SOCPs can be solved with great efficiency by interior point methods.

Contents

  • Example: Quadratic constraint 1
  • Example: Stochastic linear programming 2
  • Example: Stochastic second-order cone programming 3
  • Solvers and scripting (programming) languages 4
  • References 5

Example: Quadratic constraint

Consider a quadratic constraint of the form

x^T A^T A x + b^T x + c \leq 0.

This is equivalent to the SOC constraint

\left\| \begin{matrix} (1 + b^T x +c)/2\\ Ax \end{matrix} \right\|_2 \leq (1 - b^T x -c)/2.

Example: Stochastic linear programming

Consider a stochastic linear program in inequality form

minimize \ c^T x \
subject to
P(a_i^Tx \leq b_i) \geq p, \quad i = 1,\dots,m

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

minimize \ c^T x \
subject to
\bar{a}_i^T x + \Phi^{-1}(p) \lVert \Sigma_i^{1/2} x \rVert_2 \leq b_i , \quad i = 1,\dots,m

where \Phi^{-1} \ is the inverse normal cumulative distribution function.[1]

Example: Stochastic second-order cone programming

We refer to second-order cone programs as deterministic second-order cone programs since data defining them are deterministic. Stochastic second-order cone programs[2] is a class of optimization problems that defined to handle uncertainty in data defining deterministic second-order cone programs.

Solvers and scripting (programming) languages

Name License Brief info
AMPL commercial An algebraic modeling language with SOCP support
CPLEX commercial
ECOS GPL v3 SOCP solver for embedded applications
Gurobi commercial parallel SOCP barrier algorithm
JOptimizer Apache License Java library for convex optimization (open source)
MOSEK commercial
OpenOpt BSD universal cross-platform numerical optimization framework, see its SOCP page and other problems involved. Uses NumPy arrays and SciPy sparse matrices.
SDPT3 GPL v2 Matlab package with primal–dual interior point methods[3][2][4][5][6]
Xpress commercial from 7.6 release

References

  1. ^ a b Boyd, Stephen; Vandenberghe, Lieven (2004). Convex Optimization (pdf). Cambridge University Press.  
  2. ^ a b Alzalg, Baha (2012). "Stochastic second-order cone programming: Application models". Applied Mathematical Modeling 36 (10): 5122–5134.  
  3. ^ Toh, K.C.; M.J. Todd; R.H. Tutuncu (1999). "SDPT3 - a Matlab software package for semidefinite programming". Optimization Methods andSoftware 11: 545–581.  
  4. ^ Tutuncu, R.H.; K.C. Toh; M.J. Todd (2003). "Solving semidefinite-quadratic-linear programs using SDPT3". Mathematical Programming. B 95: 189–217.  
  5. ^ |SeDuMi||GPL v3||Matlab package with primal–dual interior point methods
  6. ^ Sturm, Jos F. (1999). "Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones". Optimization Methods and Software. 11-12: 625–653. 
This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
 
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
 
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.
 



Copyright © World Library Foundation. All rights reserved. eBooks from World Library are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.