DSLs like cvxpy and solvers like MOSEK are amazing for rapid prototyping and can carry you very far. However, you’ll often get stuck by commercial s

The Art of Deconstraining - by Ben Recht - arg min

submited by
Style Pass
2024-11-14 01:30:03

DSLs like cvxpy and solvers like MOSEK are amazing for rapid prototyping and can carry you very far. However, you’ll often get stuck by commercial solver limitations as you scale to larger data or need to accelerate run-time because of production demands. Eventually, all optimizers need to roll their own solvers.

Having done this before, I can attest that writing a custom primal-dual interior point method is much easier than it sounds. The basic iterations just require structured solutions of linear systems. The outer loop is based upon scheduling your trajectory along the central path, and I’ve found Mehrota’s Predictor Corrector algorithm robust, efficient, and easy to implement for this task. 

However, we’re in the age of LLMs, and no one likes to solve linear systems anymore. Instead, they want something you can Pytorch. Pytorching usually means that we need to transform our constrained problem into an unconstrained problem so that we can just autodiff our way to glory. It’s not obvious, but a revisionist reading of Boyd and Vandenberghe tells you how to do this.

First, how do you get rid of equality constraints? Suppose you want to enforce Ax=b, where A is p x n. Most deep learners tend to make equality constraints into regularized penalties. They add a term ||Ax-b||^2 to your cost function, and with an appropriate weighting, you can get this small. 

Leave a Comment