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
So, what you’re seeing above is an optimization problem, which is a problem where the task is to find (the optimal vector) that minimizes the cost function , respecting all the constraints for all and for all . This problem is convex only when all the functions are convex in and the functions are affine in .
Why do we care about convex optimization ? Well, it was first thought that linear optimization problems (i.e. when are linear in ) 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:
where and are given vectors that fall in and , respectively. On the other hand, a quadratic program looks like this
where is a symmetric matrix, and . Also and . Likewise, and . Finally the outline of this lecture is given as follows:
01:26 Linear Program on CVXOPT
06:56 Quadratic Program on CVXOPT