CVXOPT Programming

Before I talk about CVXOPT programming, I’m assuming that you know what a convex optimization (or at least an optimization) problem is. If you don’t, it’s okay. I’ll do my best to introduce it in this post. Consider the following problem

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

So, what you’re seeing above is an optimization problem, which is a problem where the task is to find x^* (the optimal vector) that minimizes the cost function f_0(x), respecting all the constraints f_i(x) \leq b_i for all i = 1 \ldots m and h_i(x) \leq 0 for all i = 1 \ldots p. This problem is convex only when all the functions f_0 \ldots f_m are convex in x and the functions h_1 \ldots h_p are affine in x.

Why do we care about convex optimization ? Well, it was first thought that linear optimization problems (i.e. when f_0 \ldots f_m are linear in x) were the “easiest” problems to handle. Easiest is a sloppy term meaning that “efficient algorithms exist to solve linear programming problems in polynomial time”. However, later on, and thanks to many researchers such as Ralph Tyrrell Rockafellar, Yurii Nesterov, Claude Lemaréchal, Krzysztof Czesław Kiwiel, Dimitri Bertsekas, Jean-Baptiste Hiriart-Urruty, Stephen Boyd, and many more; we can now solve convex optimization problems in polynomial time thanks to highly precise algorithms.

Now that we have some background on convex optimization, we can talk about the CVXOPT package. CVXOPT is a free software package for convex optimization based on the Python programming language. It can be used on any interpreter and in any environment supporting python such as Jupyter Notebook on Google Chrome. The main purpose of CVXOPT is to make the development of software for convex optimization applications straightforward by building on Python’s extensive standard library and on the strengths of Python as a high-level programming language. In this lecture, we get you started by showing you how to install CVXOPT on your machine, and using it in your python environment. We show you how to solve two types of widely known convex optimization problems that are linear and quadratic programs. A linear program takes on the following form:

    \begin{equation*}\begin{aligned}& \underset{x}{\text{minimize}}& & c^T x \\& \text{subject to}& & Ax \leq b\end{aligned}\end{equation*}

where A \in \mathbb{R}^{m \times n} and b,c are given vectors that fall in \mathbb{R}^{m \times 1} and \mathbb{R}^{n \times 1}, respectively. On the other hand, a quadratic program looks like this

    \begin{equation*}\begin{aligned}& \underset{x}{\text{minimize}}& & x^T P x + q^T x \\& \text{subject to}& & Gx \leq h \\& & & Ax = b\end{aligned}\end{equation*}

where P\in \mathbb{R}^{n \times n} is a symmetric matrix, and q \in \mathbb{R}^{n \times 1}. Also G \in \mathbb{R}^{m \times n} and h \in \mathbb{R}^{m \times 1}. Likewise, A \in \mathbb{R}^{p \times n} and b \in \mathbb{R}^{p \times 1}. Finally the outline of this lecture is given as follows:

00:00 Intro
01:26 Linear Program on CVXOPT
06:56 Quadratic Program on CVXOPT
11:25 Outro

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.

Leave a Reply

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

Next Post

SciPy Programming

Sun Nov 8 , 2020
SciPy is a free and open-source Python library used for technical computing and scientific computing. SciPy contains modules for optimization, linear algebra, integration, interpolation, special functions, FFT, signal and image processing, ODE solvers and other tasks common in science and engineering. In this lecture, we introduce all SciPy’s functions one will most probably pass through when Jupyter Notebook on Google Chrome, which is one of […]