Introduction of Convex Optimization

Ahmad Bazzi 5 months ago 2

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.

Ahmad Bazzi

Ahmad Bazzi is an Electrical Engineer and YouTuber. Ahmad Bazzi is a signal processing engineer at CEVA DSP. He holds a PhD in Electrical Engineering from EURECOM. Ahmad Bazzi is a EURECOM alumni. Ahmad Bazzi obtained his Master studies (Summa Cum Laude) in Electrical Engineering at SUPELEC, Paris. Ahmad Bazzi has many publications in well-known IEEE conferences, including a nomination award and is a co-inventor in several patents. Ahmad Bazzi dedicates time to publish high level lectures on Mathematics (including convex optimization) and Programming. Ahmad Bazzi also focuses on Machine Learning, Convex Optimization, Linear Algebra, Python, SymPy, NumPy, Pandas, CVXOPT, MATLAB, C++ for firmware systems.

2 thoughts on “Introduction of Convex Optimization”

Leave a Reply

Your email address will not be published. Required fields are marked *

Next Post

Soft & Hard Margin Support Vector Machine (SVM)| Machine Learning with TensorFlow & scikit-learn

Thu Jan 7 , 2021
đź“šAbout This lecture focuses on the theoretical as well as practical aspects of the Support Vector Machines. It is a supervised learning model associated with learning algorithms that analyze data used for classification and regression analysis. Developed at AT&T Bell Laboratories by Vapnik with colleagues (Boser et al., 1992, Guyon […]

You May Like