Convex programming

Convex programming is a subdomain of mathematical optimization that studies the problem of minimizing convex functions on convex sets . While many classes of convex programming problems admit polynomial time algorithms ^[1] , mathematical optimization in the general case is NP-hard ^[2] ^[3] ^[4] .

Convex programming is used in a number of disciplines, such as automatic control systems , signal estimation and processing , communication and networks, circuitry ^[5] , data analysis and modeling, finance , statistics ( ) ^[6] and ^[7] . The development of computer technology and optimization algorithms has made convex programming almost as simple as linear programming ^[8] .

Content

Definition

The convex programming problem is an optimization problem in which the objective function is a convex function and the domain of feasible solutions is convex . Function $f$ ${\ displaystyle f}$ displaying some subset $\mathbb {R} ^{n}$ ${\ displaystyle \ mathbb {R} ^ {n}}$ at $\mathbb {R} \cup \{\pm \infty \}$ ${\ displaystyle \ mathbb {R} \ cup \ {\ pm \ infty \}}$ is convex if the domain of definition is convex and for all $\theta \in [0,1]$ ${\ displaystyle \ theta \ in [0,1]}$ and all $x, y$ ${\ displaystyle x, y}$ in their area of definition $f(\theta x+(1-\theta )y)\leqslant \theta f(x)+(1-\theta )f(y)$ ${\ displaystyle f (\ theta x + (1- \ theta) y) \ leqslant \ theta f (x) + (1- \ theta) f (y)}$ . The set is convex if, for all its elements $x, y$ ${\ displaystyle x, y}$ and any $\theta \in [0,1]$ ${\ displaystyle \ theta \ in [0,1]}$ also $\theta x+(1-\theta )y$ ${\ displaystyle \ theta x + (1- \ theta) y}$ belongs to the multitude.

In particular, the problem of convex programming is the problem of finding some $\mathbf {x^{\ast }} \in C$ {\ displaystyle \ mathbf {x ^ {\ ast}} \ in C} on which is achieved

\inf\{f(\mathbf {x} ):\mathbf {x} \in C\}

{\ displaystyle \ inf \ {f (\ mathbf {x}): \ mathbf {x} \ in C \}}

,

where is the objective function $f$ ${\ displaystyle f}$ convex, like many admissible solutions $C$ ${\ displaystyle C}$ ^[9] ^[10] . If such a point exists, it is called the optimal point . The set of all optimal points is called the optimal set . If a $f$ ${\ displaystyle f}$ not limited to $C$ ${\ displaystyle C}$ or the infimum is not reached, they say that optimization is not limited . If $C$ ${\ displaystyle C}$ empty, they say about an unacceptable task ^[11] .

Standard form

They say that the convex programming problem is presented in standard form if it is written as

Minimize

f(\mathbf {x} )

{\ displaystyle f (\ mathbf {x})}

Under conditions

{\begin{aligned}&&g_{i}(\mathbf {x} )\leqslant 0,\quad i=1,\dots ,m\\&&h_{i}(\mathbf {x} )=0,\quad i=1,\dots ,p,\end{aligned}}

{\ displaystyle {\ begin {aligned} && g_ {i} (\ mathbf {x}) \ leqslant 0, \ quad i = 1, \ dots, m \\ && h_ {i} (\ mathbf {x}) = 0, \ quad i = 1, \ dots, p, \ end {aligned}}}

Where $x\in \mathbb {R} ^{n}$ ${\ displaystyle x \ in \ mathbb {R} ^ {n}}$ is a variable optimization function $f,g_{1},\ldots ,g_{m}$ ${\ displaystyle f, g_ {1}, \ ldots, g_ {m}}$ convex, and functions $h_{1},\ldots ,h_{p}$ ${\ displaystyle h_ {1}, \ ldots, h_ {p}}$ affinity ^[11] .

In these terms, the function $f$ ${\ displaystyle f}$ is the objective function of the task, and the functions $g_{i}$ ${\ displaystyle g_ {i}}$ and $h_{i}$ ${\ displaystyle h_ {i}}$ referred to as constraint functions. An admissible set of solutions to an optimization problem is a set consisting of all points $x\in \mathbb {R} ^{n}$ ${\ displaystyle x \ in \ mathbb {R} ^ {n}}$ satisfying the conditions $g_{1}(x)\leqslant 0,\ldots ,g_{m}(x)\leqslant 0$ ${\ displaystyle g_ {1} (x) \ leqslant 0, \ ldots, g_ {m} (x) \ leqslant 0}$ and $h_{1}(x)=0,\ldots ,h_{p}(x)=0$ ${\ displaystyle h_ {1} (x) = 0, \ ldots, h_ {p} (x) = 0}$ . This set is convex, since the convex function are convex, affine sets are also convex, and the intersection of convex sets is a convex set ^[12] .

Many optimization tasks can be reduced to this standard form. For example, the problem of maximizing a concave function $f$ ${\ displaystyle f}$ can be reformulated equivalently as the problem of minimizing a convex function $-f$ ${\ displaystyle -f}$ , so the problem of maximizing a concave function on a convex set is often referred to as the problem of convex programming

Properties

Useful properties of convex programming problems ^[13] ^[11] :

any local minimum is a global minimum ;
the optimal set is convex;
if the objective function is strongly convex, the problem has a maximum of one optimal point.

These results are used in the theory of convex minimization together with geometric concepts from functional analysis (on Hilbert spaces ), such as theorem, the support hyperplane theorem , and the Farkash lemma .

Examples

Hierarchy of convex programming tasks.
(LP: linear programming,
QP: quadratic programming,
SOCP: conical programming on a second-order cone,
SDP: semi-defined programming,
CP: conical programming,
GFP: programming graphic forms.)

The following classes of problems are convex programming problems or can be reduced to convex programming problems by simple transformations ^[11] ^[14] :

Least square method
Line programming
Convex quadratic optimization with linear constraints
Geometric programming
Semi-defined programming
with suitable constraints

Lagrange multiplier method

Consider a convex minimization problem defined in a standard form with a price function $f(x)$ ${\ displaystyle f (x)}$ and inequality constraints $g_{i}(x)\leqslant 0$ ${\ displaystyle g_ {i} (x) \ leqslant 0}$ for $1\leqslant i\leqslant m$ ${\ displaystyle 1 \ leqslant i \ leqslant m}$ . Then the domain ${\mathcal {X}}$ ${\ displaystyle {\ mathcal {X}}}$ is equal to:

{\mathcal {X}}=\left\{x\in X\vert g_{1}(x),\ldots ,g_{m}(x)\leqslant 0\right\}.

{\ displaystyle {\ mathcal {X}} = \ left \ {x \ in X \ vert g_ {1} (x), \ ldots, g_ {m} (x) \ leqslant 0 \ right \}.}

Lagrange function for the task

L(x,\lambda _{0},\lambda _{1},\ldots ,\lambda _{m})=\lambda _{0}f(x)+\lambda _{1}g_{1}(x)+\cdots +\lambda _{m}g_{m}(x).

{\ displaystyle L (x, \ lambda _ {0}, \ lambda _ {1}, \ ldots, \ lambda _ {m}) = \ lambda _ {0} f (x) + \ lambda _ {1} g_ {1} (x) + \ cdots + \ lambda _ {m} g_ {m} (x).}

For any point $x$ ${\ displaystyle x}$ of $X$ ${\ displaystyle X}$ which minimizes $f$ ${\ displaystyle f}$ on $X$ ${\ displaystyle X}$ , there are real numbers $\lambda _{0},\lambda _{1},\ldots ,\lambda _{m},$ ${\ displaystyle \ lambda _ {0}, \ lambda _ {1}, \ ldots, \ lambda _ {m},}$ , called Lagrange multipliers , for which conditions are simultaneously satisfied:

$x$ ${\ displaystyle x}$ minimizes $L(y,\lambda _{0},\lambda _{1},\ldots ,\lambda _{m})$ ${\ displaystyle L (y, \ lambda _ {0}, \ lambda _ {1}, \ ldots, \ lambda _ {m})}$ above all $y\in X,$ ${\ displaystyle y \ in X,}$
$\lambda _{0},\lambda _{1},\ldots ,\lambda _{m}\geqslant 0,$ ${\ displaystyle \ lambda _ {0}, \ lambda _ {1}, \ ldots, \ lambda _ {m} \ geqslant 0,}$ with at least one $\lambda _{k}>0,$ ${\ displaystyle \ lambda _ {k}> 0,}$
$\lambda _{1}g_{1}(x)=\cdots =\lambda _{m}g_{m}(x)=0$ ${\ displaystyle \ lambda _ {1} g_ {1} (x) = \ cdots = \ lambda _ {m} g_ {m} (x) = 0}$ (complementary nonrigidity).

If there is a “strong allowable point”, that is, a point $z$ ${\ displaystyle z}$ satisfying

g_{1}(z),\ldots ,g_{m}(z)<0,

{\ displaystyle g_ {1} (z), \ ldots, g_ {m} (z) <0,}

then the statement above can be strengthened to the requirement $\lambda _{0}=1$ ${\ displaystyle \ lambda _ {0} = 1}$ .

And vice versa, if some $x$ ${\ displaystyle x}$ of $X$ ${\ displaystyle X}$ satisfies conditions (1) - (3) for scalars $\lambda _{0},\ldots ,\lambda _{m}$ ${\ displaystyle \ lambda _ {0}, \ ldots, \ lambda _ {m}}$ with $\lambda _{0}=1$ ${\ displaystyle \ lambda _ {0} = 1}$ then $x$ ${\ displaystyle x}$ definitely minimizes $f$ ${\ displaystyle f}$ on $X$ ${\ displaystyle X}$ .

Algorithms

Convex programming problems are solved by the following modern methods: ^[15]

(Wolf, Lemerical, Kivel),
Methods (Pole),
The internal point method ^[1] , using self-consistent barrier functions ^[16] and self-regulatory barrier functions ^[17] .
Secant Plane Method
Ellipsoid method

Subgradient methods can be implemented simply, because they are widely used ^[18] ^[19] . Dual subgradient methods are subgradient methods applied to a dual problem . method is similar to the dual subgradient method, but uses the time average of the main variables.

Extensions

Convex programming extensions include optimizing , pseudoconvex, and quasiconvex functions. Extensions of the theory of convex analysis and iterative methods for the approximate solution of non-convex optimization problems are found in the field of generalized convexity , known as abstract convex analysis.

Notes

↑ ¹ ² Nesterov, Nemirovskii, 1994 .
↑ Murty, Kabadi, 1987 , p. 117–129.
↑ Sahni, 1974 , p. 262-279.
↑ Pardalos, Vavasis, 1991 , p. 15-22.
↑ Boyd, Vandenberghe, 2004 , p. 17.
↑ Christensen, Klarbring, 2008 , p. chpt. four.
↑ Boyd, Vandenberghe, 2004 .
↑ Boyd, Vandenberghe, 2004 , p. eight.
↑ Hiriart-Urruty, Lemaréchal, 1996 , p. 291.
↑ Ben-Tal, Nemirovskiĭ, 2001 , p. 335–336.
↑ ¹ ² ³ ⁴ Boyd, Vandenberghe, 2004 , p. chpt. four.
↑ Boyd, Vandenberghe, 2004 , p. chpt. 2.
↑ Rockafellar, 1993 , p. 183–238.
↑ Agrawal, Verschueren, Diamond, Boyd, 2018 , p. 42-60.
↑ For methods of convex programming, see the books of Irriart-Urruti and Lemerical (several books) and the books of Rushczynski, Bercekas , as well as Boyd and Vanderberg (internal point methods).
↑ Nesterov, Nemirovskii, 1995 .
↑ Peng, Roos, Terlaky, 2002 , p. 129–171.
↑ Bertsekas, 2009 .
↑ Bertsekas, 2015 .

Literature

Jean-Baptiste Hiriart-Urruty, Claude Lemaréchal. Convex analysis and minimization algorithms: Fundamentals . - 1996. - ISBN 9783540568506 .
Aharon Ben-Tal, Arkadiĭ Semenovich Nemirovskiĭ. Lectures on modern convex optimization: analysis, algorithms, and engineering applications . - 2001. - ISBN 9780898714913 .
Katta Murty, Santosh Kabadi. Some NP-complete problems in quadratic and nonlinear programming // Mathematical Programming. - 1987. - T. 39 , no. 2 . - S. 117–129 . - DOI : 10.1007 / BF02592948 .
Sahni S. Computationally related problems // SIAM Journal on Computing. - 1974. - Vol. 3 .
Panos M. Pardalos, Stephen A. Vavasis. Quadratic programming with one negative eigenvalue is NP-hard // Journal of Global Optimization. - 1991. - T. 1 , No. 1 .
R. Tyrrell Rockafellar. Convex analysis. - Princeton: Princeton University Press, 1970.
R. Tyrrell Rockafellar. Lagrange multipliers and optimality // SIAM Review. - 1993. - T. 35 , no. 2 . - DOI : 10.1137 / 1035044 .
Akshay Agrawal, Robin Verschueren, Steven Diamond, Stephen Boyd. A rewriting system for convex optimization problems // Control and Decision. - 2018 .-- T. 5 , no. 1 . - DOI : 10.1080 / 23307706.2017.1397554 .
Yurii Nesterov, Arkadii Nemirovskii. Interior-Point Polynomial Algorithms in Convex Programming. - Society for Industrial and Applied Mathematics, 1995. - ISBN 978-0898715156 .
Yurii Nesterov, Arkadii Nemirovskii. Interior Point Polynomial Methods in Convex Programming. - SIAM, 1994. - T. 13. - (Studies in Applied and Numerical Mathematics). - ISBN 978-0-89871-319-0 .
Yurii Nesterov. Introductory Lectures on Convex Optimization. - Boston, Dordrecht, London: Kluwer Academic Publishers, 2004 .-- T. 87. - (Applied Optimization). - ISBN 1-4020-7553-7 .
Jiming Peng, Cornelis Roos, Tamás Terlaky. Self-regular functions and new search directions for linear and semidefinite optimization // Mathematical Programming. - 2002. - T. 93 , no. 1 . - ISSN 0025-5610 . - DOI : 10.1007 / s101070200296 .
Dimitri P. Bertsekas, Angelia Nedic, Asuman Ozdaglar. Convex Analysis and Optimization. - Athena Scientific, 2003. - ISBN 978-1-886529-45-8 .
Dimitri P. Bertsekas. Convex Optimization Theory. - Belmont, MA .: Athena Scientific, 2009 .-- ISBN 978-1-886529-31-1 .
Dimitri P. Bertsekas. Convex Optimization Algorithms. - Belmont, MA .: Athena Scientific, 2015 .-- ISBN 978-1-886529-28-1 .
Stephen P. Boyd, Lieven Vandenberghe. Convex Optimization . - Cambridge University Press, 2004. - ISBN 978-0-521-83378-3 .
Jonathan M. Borwein, Adrian Lewis. Convex Analysis and Nonlinear Optimization. - Springer, 2000. - (CMS Books in Mathematics). - ISBN 0-387-29570-4 .
Peter W. Christensen, Anders Klarbring. An introduction to structural optimization. - Springer Science & Businees Media, 2008 .-- T. 153. - ISBN 9781402086663 .
Jean-Baptiste Hiriart-Urruty, Claude Lemaréchal. Fundamentals of Convex analysis. - Berlin: Springer, 2004 .-- (Grundlehren text editions). - ISBN 978-3-540-42205-1 .
Jean-Baptiste Hiriart-Urruty, Claude Lemaréchal. Convex analysis and minimization algorithms, Volume I: Fundamentals. - Berlin: Springer-Verlag, 1993 .-- T. 305 .-- C. xviii + 417. - ISBN 978-3-540-56850-6 .
Jean-Baptiste Hiriart-Urruty, Claude Lemaréchal. Convex analysis and minimization algorithms, Volume II: Advanced theory and bundle methods. - Berlin: Springer-Verlag, 1993 .-- T. 306. - C. xviii + 346. - ISBN 978-3-540-56852-0 .
Krzysztof C. Kiwiel. Methods of Descent for Nondifferentiable Optimization. - New York: Springer-Verlag, 1985. - (Lecture Notes in Mathematics). - ISBN 978-3-540-15642-0 .
Claude Lemaréchal. Lagrangian relaxation // Computational combinatorial optimization: Papers from the Spring School held in Schloß Dagstuhl, May 15–19, 2000. - Berlin: Springer-Verlag, 2001. - T. 2241. - P. 112–156. - ISBN 978-3-540-42877-0 . - DOI : 10.1007 / 3-540-45586-8_4 .
Andrzej Ruszczyński. Nonlinear Optimization. - Princeton University Press, 2006.
Kamenev GK Optimal adaptive methods for polyhedral approximation of convex bodies. M.: VTs RAS, 2007, 230 p. ISBN 5-201-09876-2 .
Kamenev GK Numerical study of the effectiveness of the methods of polyhedral approximation of convex bodies. M: Publ. Computing Center of the Russian Academy of Sciences, 2010, 118 p. ISBN 978-5-91601-043-5 .

Links

Stephen Boyd, Lieven Vandenberghe, Convex optimization (pdf)
EE364a: Convex Optimization I , EE364b: Convex Optimization II , Oxford University Course Page
6.253: Convex Analysis and Optimization , MIT OCW Course Page
Brian Borchers, An overview of software for convex optimization

[_51399823f45d6ecc-1] ¹ ² Nesterov, Nemirovskii, 1994 .

[_14cee9d6d3e11861-2] Murty, Kabadi, 1987 , p. 117–129.

[_756dd35531ffbfcd-3] Sahni, 1974 , p. 262-279.

[_f976f03b760d823c-4] Pardalos, Vavasis, 1991 , p. 15-22.

[_1e755c5ee458b750-5] Boyd, Vandenberghe, 2004 , p. 17.

[_508f06e048b9ca04-6] Christensen, Klarbring, 2008 , p. chpt. four.

[_98a1133c19e48b84-7] Boyd, Vandenberghe, 2004 .

[_3e3f331fff591174-8] Boyd, Vandenberghe, 2004 , p. eight.

[_f4068259bf6d291a-9] Hiriart-Urruty, Lemaréchal, 1996 , p. 291.

[_ad42f11aece1161f-10] Ben-Tal, Nemirovskiĭ, 2001 , p. 335–336.

[_f33a55902fa370a9-11] ¹ ² ³ ⁴ Boyd, Vandenberghe, 2004 , p. chpt. four.

[_f33a55902fa370af-12] Boyd, Vandenberghe, 2004 , p. chpt. 2.

[_54f2bf8807a11ebb-13] Rockafellar, 1993 , p. 183–238.

[_cf720d4ad817d410-14] Agrawal, Verschueren, Diamond, Boyd, 2018 , p. 42-60.

[15] For methods of convex programming, see the books of Irriart-Urruti and Lemerical (several books) and the books of Rushczynski, Bercekas , as well as Boyd and Vanderberg (internal point methods).

[_890c4ff540f27fb1-16] Nesterov, Nemirovskii, 1995 .

[_94584996249ba114-17] Peng, Roos, Terlaky, 2002 , p. 129–171.

[_cbc6bb2ff592af24-18] Bertsekas, 2009 .

[_7d5e5956a341985b-19] Bertsekas, 2015 .