Convex optimization: Difference between revisions

Revision as of 07:53, 10 December 2023

Revision as of 07:59, 10 December 2023

Line 5:

==Definition==

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>

A convex optimization problem is an [[optimization problem]] in which the objective function is a [[convex function]] and the [[Feasible region|feasible set]] is a [[convex set]]. A function <math>f</math> mapping some subset of <math>\mathbb{R}^n</math>into <math>\mathbb{R} \cup \{\pm \infty\}</math> is convex if its ___domain is convex and for all <math>\theta \in [0, 1]</math> and all <math>x, y</math> in its ___domain, the following condition holds: <math>f(\theta x + (1 - \theta)y) \leq \theta f(x) + (1 - \theta) f(y)</math>. A set S is convex if for all members <math>x, y \in S</math> and all <math>\theta \in [0, 1]</math>, we have that <math>\theta x + (1 - \theta) y \in S</math>.

* The ''objective function'', which is a real-valued [[convex function]] of ''n'' variables, <math>f :\mathcal D \subseteq \mathbb{R}^n \to \mathbb{R}</math>.;

Concretely, a convex optimization problem is the problem of finding some <math>\mathbf{x^\ast} \in C</math> attaining

* The ''feasible set'', which is a convex subset <math>C\subseteq \mathbb{R}^n</math>.

:<math>\inf \{ f(\mathbf{x}) : \mathbf{x} \in C \}</math>,

where the objective function <math>f :\mathcal D \subseteq \mathbb{R}^n \to \mathbb{R}</math> is convex, as is the feasible set <math>C</math>.<ref>{{cite book|url=https://books.google.com/books?id=Gdl4Jc3RVjcC&q=lemarechal+convex+analysis+and+minimization|title=Convex analysis and minimization algorithms: Fundamentals|last1=Hiriart-Urruty|first1=Jean-Baptiste|last2=Lemaréchal|first2=Claude|year=1996|page=291|isbn=9783540568506}}</ref>

Concretely,The agoal convexof optimizationthe problem is the problem ofto findingfind some <math>\mathbf{x^\ast} \in C</math> attaining

<ref>{{cite book|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|last1=Ben-Tal|first1=Aharon|last2=Nemirovskiĭ|first2=Arkadiĭ Semenovich|year=2001|pages=335–336|isbn=9780898714913}}</ref> If such a point exists, it is referred to as an ''optimal point'' or ''solution''; the set of all optimal points is called the ''optimal set''. If <math>f</math> is unbounded below over <math>C</math> or the infimum is not attained, then the optimization problem is said to be ''unbounded''. Otherwise, if <math>C</math> is the empty set, then the problem is said to be ''infeasible''.<ref name="bv4">{{harvnb|Boyd|Vandenberghe|2004|loc=chpt. 4}}</ref>

:<math>\inf \{ f(\mathbf{x}) : \mathbf{x} \in C \}</math>,.

In general, there are three options regarding the existence of a solution:<ref name="bv4">{{harvnb|Boyd|Vandenberghe|2004|loc=chpt. 4}}</ref>

* If such a point ''x''* exists, it is referred to as an ''optimal point'' or ''solution''; the set of all optimal points is called the ''optimal set''; and the problem is called ''solvable''.

* If <math>f</math> is unbounded below over <math>C</math>, or the infimum is not attained, then the optimization problem is said to be ''unbounded''.

* Otherwise, if <math>C</math> is the empty set, then the problem is said to be ''infeasible''.

===Standard form===