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.

On December 18, 2020 By Ahmad Bazzi

Convex Optimization

2 thoughts on “Introduction of Convex Optimization”

ashutosh jha says:

February 1, 2021 at 1:29 pm

THANKS FOR MAKING VIDEO ABOUT CONVEX OPTIMIZATION KEEP GOING

Reply
rohan says:

February 1, 2021 at 1:32 pm

first time watching your video but you are just amazing thanks a lot sir for making vieo about concex optimization digital shiksha!

Reply

2 thoughts on “Introduction of Convex Optimization”

Leave a Reply Cancel reply

You may also like

But why isn't Markowitz Working ?

Log Barrier Minimization: An Intuitive Approach

Markowitz Portfolio Optimization in Stock Market Analysis

Strong Alternatives