The problem is to find \[\begin{array}{lrl} & {\displaystyle \min_{x}} & f(x) \\ \text{subject to} && g(x) \le 0 \end{array}\] Note that \(x\in \mathbb{R}^d\).
A direction characterized by a (unit) vector \(d\) is said to be a descent direction at a point \(x\) if \[d^T \nabla f(x) < 0\]
The value of the objective function will necessarily decrease if one moves along a descent direction. As such, a descent direction is a property of the objective function \(f(x)\).
At a point \(x\) in the constraint region \(g(x)\le 0\), a direction characterized by a unit vector \(d\) is said to be a feasible direction if there exists a \(\eta_0>0\) such that for all \(\eta \in (0, \eta_0]\), the point \(x+\eta d\) is still in the constraint region, i.e. \(g(x+\eta d) \le 0\). In simple terms, a feasible direction at a point is a direction along which we can move by some step size so that we still remain in the constraint region.
The feasible direction is a property of the constraint function \(g(x)\).
Necessary conditions: If \(x^*\) is an optimal point that minimizes the objective function \(f\), then at the point \(x^*\):
no descent direction should be a feasible direction,
\(\nabla f(x^*) = -\lambda \nabla g(x^*)\) for some \(\lambda \ge 0\), and
\(\lambda g(x^*)=0\) for the same \(\lambda\) as above.
The problem is to find \[\begin{array}{lrl} & {\displaystyle \min_{x}} & f(x) \\ \text{subject to} && g(x) = 0 \end{array}\] Note that \(x\in \mathbb{R}^d\).
Necessary conditions: If \(x^*\) is an optimal point that minimizes the objective function \(f\), then at the point \(x^*\):
\(g(x^*)=0\)
\(d^T\nabla g(x^*)=0\) for any feasible direction \(d\),
\(\nabla f(x^*) = -\lambda \nabla g(x^*)\) for some arbitrary \(\lambda \in \mathbb{R}\).
Notice that in this case \(\lambda\) is allowed to take either positive or negative values. \(\lambda\) is referred to as the Lagrange multiplier and equation (iii) above is the Lagrange equation.
In general, it may not be feasible to solve the system of equations that satisfy the Lagrange equations.
In case the constraint region \(\Omega = \{ x \mid g(x)\le 0\}\) is convex, the projected gradient descent algorithm can be applied and the optimum \(x^*\) can be found as the limit of sequence \(\{x_0, x_1, x_2, \ldots \}\), where \[x_k = \prod (x_{k-1} - \eta_k \nabla f(x_{k-1})) , \quad k = 1, 2, \ldots\]
The projection operator \(\prod\) projects any vector onto \(\Omega\): \[\prod (v) = \min_{x\in \Omega} \Vert v-x \Vert^2\]
A set \(S\subset \mathbb{R}^d\) is a convex set if for every pair of points \(x_1\) and \(x_2\) which are in \(S\), the line segment joining these points is also entirely in \(S\), i.e. \[\forall \ x_1, x_2 \in S \Rightarrow \lambda x_1 + (1-\lambda) x_2 \in S, \ \lambda \in [0, 1]\]
Examples of convex sets include:
the empty set
a set consisting of a single point
a line or a line segment
a subspace
a hyperplane
a linear variety (a translation of a subspace)
a half-space
\(\mathbb{R}^d\)
Convex sets in \(\mathbb{R}^d\) have the following properties:
If \(S\) is a convex set and \(\beta\) is any real number, then the set \[\beta S = \{x \mid x = \beta v, \ v\in S\}\] is also convex.
If \(S_1\) and \(S_2\) are convex sets, then the set \[S_1+S_2 = \{ x \mid x =v_1 + v_2 , \ v_1\in S_1, v_2 \in S_2\}\] is also convex.
The intersection of any collection of convex sets is also convex.
Convex Combination: Let \(S=\{x_1,\, x_2,\, \ldots,\, x_n\} \subset \mathbb{R}^d\). Then a convex combination of the elements of \(S\) is a linear combination of the elements of \(S\) so that the multiplying coefficients are all non-negative and sum up to 1. That is to say, any \(z\in\mathbb{R}^d\) is a convex combination of the elements of \(S\) if \(\exists\) \(\lambda_1\), \(\lambda_2\), …, \(\lambda_n\) so that \[\begin{matrix} \lambda_i \ge 0, \quad i=1, 2, \ldots, n \\[2ex] {\displaystyle\sum_{i=1}^n \lambda_i = 1}, \text{ and }\\[3ex] z = \lambda_1 x_1 + \lambda_2 x_2 + \ldots + \lambda_n x_n \end{matrix}\]
Convex Hull: Let \(S=\{x_1,\, x_2,\, \ldots,\, x_n\} \subset \mathbb{R}^d\). The convex hull of the set \(S\), denoted \(\textrm{CH}(S)\) is the set of all possible convex combinations of the elements of \(S\): \[CH(S)=\{ z \mid z = \sum_{i=1}^n \lambda_i x_i, \,\text{ for } \lambda_1, \lambda_2 \ldots, \lambda_n \ge 0, \, \sum_{i=1}^n \lambda_i = 1 \}\]
The convex hull of the set \(S\) can also be defined as the intersection of all convex sets that contain the set \(S\).
Epigraph of a function: Let \(X\subset \mathbb{R}^d\) and \(Y\subset \mathbb{R}\) and consider a function \(f:X\to Y\). It’s epigraph is then the set \[\mathrm{epi}(f) = \left\{ \begin{bmatrix} x \\ z \end{bmatrix} \subset X \times Y \mid z \ge f(x) \right\}\] That is, the epigraph of \(f\) consists of all points “on or above” the graph of \(f\).
A function \(f:\mathbb{R}^d \to \mathbb{R}\) is said to be a convex function if any of the following holds:
the \(\mathrm{epi}(f)\subset \mathbb{R}^{d+1}\) is a convex set.
\(\forall\, x_1, x_2 \in \mathbb{R}^d\) and \(\forall \,\lambda \in [0, 1]\) \[f\left(\lambda x_1 + (1-\lambda)x_2\right) \le \lambda f(x_1) + (1-\lambda) f(x_2)\]
for any point \(y\) in a neighbourhood of \(x\), \[f(y) \ge f(x) + (y-x)^T \nabla f(x)\] assuming \(f\) to be differentiable.
the Hessian of \(f\) is a positive semi-definite matrix.
If \(f\) is a convex function, then all local minima of \(f\) are also global minima.
The set of all global minima of a convex function is a convex set.
If \(f:\mathbb{R}^d \to \mathbb{R}\) be a differentiable, convex function, then for a point \(x^*\in \mathbb{R}^d\) to be a global minimum of \(f\), the necessary and sufficient condition is \(\nabla f(x^*)=0\).
If \(f, g : \mathbb{R}^d \to \mathbb{R}\) be convex functions, then their sum \(f(x)+g(x)\) is also a convex function.
If \(f:\mathbb{R} \to \mathbb{R}\) be a convex and non-decreasing function, and \(g:\mathbb{R}^d \to \mathbb{R}\) be a convex function, then their composition \(f(g(x))\) is a convex function.
If \(f:\mathbb{R} \to \mathbb{R}\) be a convex and non-increasing function, and \(g:\mathbb{R}^d \to \mathbb{R}\) be a concave function, then their composition \(f(g(x))\) is a convex function.
The composition of two convex functions need not be convex.
A function \(f\) is concave if and only if \(-f\) is convex.