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