How to implement convex optimization package?

Question

I fully realize that Convex Optimization packages, like Linear Algebra packages, should be things you use, not implement. However, for purely education purposes -- is there any good resource -- link / book on how to implement a convex optimization package? (like for quadratic programs with quadratic constraints?)

Thanks!

Answer 1

Any good textbook on convex optimization would have stuff you are looking for. One such free, but great resource is here: CO Book. Note that, as you correctly mention, implementing algorithms mentioned in this book will definitely need linear algebra libraries, which you may or may not choose to implement as well.

Answer 2

There's a relevant article in Optima, a newsletter of the mathematical optimization society called "Rapid Development of an Open-source Minlp Solver with COIN-OR". It describes building a nonlinear solver using the some of the coin-or packages. Most of the coin-or stuff is written in c++.

For python, you might consider using the linear algebra data structure and algorithms available in numpy. The related scipy package has some nonlinear optimizers but nothing specific for convex optimization.

And last, you can look at the Boyd's GPL's python-based convex optimizer cvxopt to get an idea of what kind of task you have ahead of you.

Answer 3

It depends on what you're going, but you should go to prof. in math optimization in your university in which you're right now or which you graduated and you should ask him directly.

I implemented solvers for several problems reduced to convex optimization (http://cs229.stanford.edu/proj2017/) - cvx4ml which works faster then similar solution from SkLearn, and I passed 24 hour exam to Stephen Boyd, so I can give advice what you can do and describe for your very rough plan:

So you're going to create own package I will write step-by-step instruction:

1. You should create library for work with dense matrix/vectors
2. You should create library for work with sparse matrix/vectors
3. Implement around 20 different algorithms to solve system of linear equations (because depend on situation you will need different of them)
4. Introduce concepts how describe constraints, function domain, etc in your programming language or you system that you created.
5. Implement several norms and dual norms evaluation, some factorization technics like LU, Cholesky.

6. Implement custom simple conic solver for non-negative orthont cone. And it depends on what you're going todo. 6.a - write solver based on interior point method. 6.b - write solver with support distributed optimization 6.c - write solver based on some projected subgradient method.

7. Improve it to support other cones

8. Enhanced you solver with step "5"

And if you want to be at level of CVXPY then

9. Implement parsing of program description like CVXPY do and transform problem into conic form.

p.s. If you feel sloppy with some of this topics, then:

• Read linear algebra book which wrote prof. from your university

• Look in the youtube into EE263 with S.Boyd, EE364A with S.Boyd, EE364B with S.Boyd.