Convex optimization: Difference between revisions

Revision as of 07:59, 10 December 2023

Revision as of 08:01, 10 December 2023

Line 5:

==Definition==

=== Abstract form ===

A convex optimization problem is defined by two ingredients:<ref>{{cite book |last1=Hiriart-Urruty |first1=Jean-Baptiste |url=https://books.google.com/books?id=Gdl4Jc3RVjcC&q=lemarechal+convex+analysis+and+minimization |title=Convex analysis and minimization algorithms: Fundamentals |last2=Lemaréchal |first2=Claude |year=1996 |isbn=9783540568506 |page=291}}</ref><ref>{{cite book |last1=Ben-Tal |first1=Aharon |url=https://books.google.com/books?id=M3MqpEJ3jzQC&q=Lectures+on+Modern+Convex+Optimization:+Analysis,+Algorithms, |title=Lectures on modern convex optimization: analysis, algorithms, and engineering applications |last2=Nemirovskiĭ |first2=Arkadiĭ Semenovich |year=2001 |isbn=9780898714913 |pages=335–336}}</ref>

Line 30 ⟶ 31:

where:<ref name="bv4" />

* <math>\mathbf{x} \in \mathbb{R}^n</math> is the vector of optimization variablevariables;

* The objective function <math>f: \mathcal D \subseteq \mathbb{R}^n \to \mathbb{R}</math> is a [[convex function]];

* The inequality constraint functions <math>g_i : \mathbb{R}^n \to \mathbb{R}</math>, <math>i=1, \ldots, m</math>, are convex functions;

* The equality constraint functions <math>h_i : \mathbb{R}^n \to \mathbb{R}</math>, <math>i=1, \ldots, p</math>, are [[affine transformation]]s, that is, of the form: <math>h_i(\mathbf{x}) = \mathbf{a_i}\cdot \mathbf{x} - b_i</math>, where <math>\mathbf{a_i}</math> is a vector and <math>b_i</math> is a scalar.

The feasible set <math>C</math> of the optimization problem consists of all points <math>\mathbf{x} \in \mathcal{D}</math> satisfying the inequality and the equality constraints. This set is convex because <math>\mathcal{D}</math> is convex, the [[sublevel set]]s of convex functions are convex, affine sets are convex, and the intersection of convex sets is convex.<ref>{{harvnb|Boyd|Vandenberghe|2004|loc=chpt. 2}}</ref>

This notation describes the problem of finding <math>\mathbf{x} \in \mathbb{R}^n</math> that minimizes <math>f(\mathbf{x})</math> among all <math>\mathbf{x}</math> satisfying <math>g_i(\mathbf{x}) \leq 0</math>, <math>i=1, \ldots, m</math> and <math>h_i(\mathbf{x}) = 0</math>, <math>i=1, \ldots, p</math>. The function <math>f</math> is the objective function of the problem, and the functions <math>g_i</math> and <math>h_i</math> are the constraint functions.

The feasible set <math>C</math> of the optimization problem consists of all points <math>\mathbf{x} \in \mathcal{D}</math> satisfying the constraints. This set is convex because <math>\mathcal{D}</math> is convex, the [[sublevel set]]s of convex functions are convex, affine sets are convex, and the intersection of convex sets is convex.<ref>{{harvnb|Boyd|Vandenberghe|2004|loc=chpt. 2}}</ref>

A solution to a convex optimization problem is any point <math>\mathbf{x} \in C</math> attaining <math>\inf \{ f(\mathbf{x}) : \mathbf{x} \in C \}</math>. In general, a convex optimization problem may have zero, one, or many solutions.<ref>{{cite web | url=https://inst.eecs.berkeley.edu/~ee227a/fa10/login/l_cvx_pbs.html | title=Convex Problems }}</ref>

Many optimization problems can be equivalently formulated in this standard form. For example, the problem of maximizing a [[concave function]] <math>f</math> can be re-formulated equivalently as the problem of minimizing the convex function <math>-f</math>. The problem of maximizing a concave function over a convex set is commonly called a convex optimization problem.<ref>{{cite web | url=https://www.solver.com/convex-optimization | title=Optimization Problem Types - Convex Optimization | date=9 January 2011 }}</ref>