107_Convex Functions

In optimization problems, getting a satisfying answer to "How can the optimal solution be found?" is not straightforward. However, if the optimization problem can be proven to be convex, any local minimum also becomes a global minimum.

Furthermore, the KKT necessary conditions are not only necessary but also sufficient for minimum point.

 

In this post, I will study convex functions and their properties, and address the outcomes regarding global optimal soultions.

 

If ${P_1}$ and ${P_2}$ are any points within set $S$, then the entire line segment ${P_1}-{P_2}$ also belong to $S$. This is the necessary and sufficient condition for the convexity of set $S$, and a convex set $S$ consists of points that have this attribute.

 

 

In the figure, the points along a segment on the $x$-axis represent a convex set. Consider the interval between $a$ and $b$. To demonstrate that this is a convex set, consider two points ${x_1}$ and ${x_2}$ within the interval. The line segment between the points can be expressed as follows.

 

 

The expression clearly shows that the defined line lies within the interval $[a,b]$, as when $a=0$, $x={x_1}$, and when $a=1$, $x={x_2}$. Therefore, since the entire line segment lies on the line between $a$ and $b$, the set of points between them forms a convex set.

 

Generally, in an $n$-dimensional space, the line segment between any two points ${x_1}$ and ${x_2}$ can be expressed as shown, which is known as the parametric representation of the line segment between points ${x_1}$ and ${x_2}$. If the entire line segment lies within set $S$, then $S$ is a convex set.

 

Consider the function $f(x) = {x^2}$ of a single variable.

 

 

When a straight line is drawn between any two points $({x_1}, f({x_1}))$ and $({x_2}, f({x_2}))$ on the curve of $f(x)$, this line always lies above the $f(x)$ curve for all points between ${x_1}$ and ${x_2}$. This characteristic is a feature of convex functions.

 

A convex function $f(x)$ of a single variable is defined over a convex set. That is, the independent variable $x$ must lie within a convex set. A function $f(x)$ is convex over a convex set $S$ when the graph of the function lies below the line connecting any two points on the curve $f(x)$. The definition of a convex function can be expressed as follows.

 

 

Considering the previously mentioned condition $x = \alpha {x_2} + (1 - \alpha ){x_1}$, it can be represented as follows.

 

 

The definition of a convex function for a single variable can be generalized to functions fo $n$ variables. A function $f(x)$ defined over a convex set $S$ is convex if it satisfies the above inequality.

Here, $0 \leqslant \alpha  \leqslant 1$, and it holds for any two points ${x_1}, {x_2}$ within $S$. These expressions provide necessary and sufficient conditions for the convexity of a function. However, in practice, applying this is challenging because it requires checking an infinite number of points.

 

Therefore, verifying convexity through the sign of the Hessian matrix is a commonly used method. The Hessian matrix is composed of the second-order partial derivatives of a function, and the function is convex if its Hessian matrix is positive semidefinite or positive definite at every point within the set $S$.

 

When the Hessian matrix is positive definite at every point within the set, $f$ is referred to as a strictly convex function. The Hessian condition is both a necessary and sufficient condition, meaning if the Hessian is positive semidefinite at all points within set $S$, the function is not convex.