Introduction of Convex Optimization


Mathematical optimization is a problem that takes the following form

(1)   \begin{equation*}\begin{aligned}& \underset{x}{\text{minimize}}& & f_0(x) \\& \text{subject to}& & f_i(x) \leq b_i, \; i = 1, \ldots, m.\end{aligned}\end{equation*}

where x is a vector containing all the variables of the problem

(2)   \begin{equation*}x=\begin{bmatrix}x_1 & x_2 & \ldots & x_n\end{bmatrix}\end{equation*}

The function f_0: \mathbb{R}^n \rightarrow \mathbb{R} is referred to as the cost or the objective function. Moreover, the functions f_1 \ldots f_m :\mathbb{R}^n \rightarrow \mathbb{R} are referred to as constraint functions. In most cases, our goal is to find a (or the) point x^ which is feasible (i.e. satisfies f_i(x) \leq b_i, i = 1 \ldots m and f_0(x^*) is minimum. Rigorously stated, x^ is optimal if

(3)   \begin{equation*} \forall x : f_i(x) \leq b_i, i = 1 \ldots m , \text{ we have } f_0(x) \geq f_0(x^*)\end{equation*}

Well, we can state many applications. In finance and stock analysis, a well-known one is Markowitz portfolio optimization. This problem takes the form

(4)   \begin{equation*}\begin{aligned}& \underset{x}{\text{minimize}}& & x^T \Sigma x \\& \text{subject to}& & p^T x \geq r \\& & & 1^T x = 1 \\& & & x \geq 0\end{aligned}\end{equation*}

Here n will reflect the number of assets (or stocks) held over a period of time. For example, let’s say you decide to buy stocks in the period of time between today and 6 months from now. You are interested in the following stocks: CEVA, GOOGL, LVMH and NIO. This means you have decided on 4 assets and hence your n = 4. Furthermore, let’s denote by x_i the amount of asset i held throughout the period of investment. A long position in asset i would indicate x_i > 0, and a short position in asset i would mean x_i < 0. Moreover, p_i is the change in price divided by the initial price (i.e. today’s price). Your return will simply be

(5)   \begin{equation*}p^T x = p_1x_1 + \ldots + p_nx_n\end{equation*}

Anyone investing (short or long term) would simply want to maximize p^T x. However, no constraints would simply mean that x is a vector of all-\infty, which is unrealistic. Keeping our feet on the ground, we should understand that a vector of all-\infty is un-achievable, but we can accept a minimum return as

(6)   \begin{equation*}p^T x \geq r\end{equation*}

where r is a minimum return you seek from the investment over your investing period. The above equation will then suit one of our constraints. Note that the above is a way of saying “I want maximum return”. To embed risk somewhere, volatility has to be included. A suitable measure of volatility seems to be the variance of the asset prices, which is captured in covariance matrix \Sigma. The variance would then by the term x^T \Sigma x. Markowitz introduced the problem of minimizing risk subject to maximum and acceptable return

(7)   \begin{equation*}\begin{aligned}& \underset{x}{\text{minimize}}& & x^T \Sigma x \\& \text{subject to}& & p^T x \geq r \\& & & 1^T x = 1 \\& & & x \geq 0\end{aligned}\end{equation*}

Note that the constraint 1^T x = 1 along with x \geq 0 imposes a probability constraint on vector x. In other words, we are interested in vectors that contains probabilities (or proportions). Markowitz portfolio optimization lies under the category of convex optimization problems of type QP (Quadratic Programming). In Electrical Engineering, convex optimization finds application in many communication and electronic manufacturing problems, such as water filling and electronic micro scale design.