Reductions -

⏱️ Help us benchmark CVXPY solvers! Contribute problems and results to the Solver Benchmarks project. Read our new paper on the CVXPY internals!
A Reduction is a transformation from one problem to an equivalent problem. Two problems are equivalent if a solution of one can be converted to a solution of the other with no more than a moderate amount of effort. CVXPY uses reductions to rewrite problems into forms that solvers will accept.
The majority of users do not need to know anything about CVXPY’s reduction system. Indeed, most users need not even know that reductions exist!
In order to make sure that we have flexibility to improve CVXPY’s speed and capabilities while preserving backwards-compatibility, we have determined that the reduction system will not be considered part of CVXPY’s public API. As such, aspects of this system can change without notice in future releases.
We provide this documentation for CVXPY contributors, for the curious, and for those who are okay with building on an API that may not be available in future versions of CVXPY. Please contact us if you have an interesting application which requires direct access to the Reduction system and if you care about forward compatibility with future versions of CVXPY.
Reductions allow CVXPY to support different problem classes such as convex and log-log convex programming. They also help CVXPY target different categories of solvers, such as quadratic programming solvers and conic solvers.
Appropriating terminology from software compilers, we classify reductions as either middle-end reductions or back-end reductions. A reduction that simplifies a source problem without regard to the targeted solver is called a middle-end reduction, whereas a reduction that takes a source problem and converts it to a form acceptable to a category of solvers is called a back-end reduction. Each solver (along with the mode in which it is invoked) is called a back-end or target.
Here’s a breakdown of CVXPY’s reductions:
Reductions exchange data and operate by way of the following classes. Other data structures can be used, such as dicts keyed by strings, but these are the main classes which define the Reduction system.
A solution to an optimization problem.
A map from variable ids to optimal values.
dict of id to NumPy ndarray
A map from constraint ids to dual values.
dict of id to NumPy ndarray
Miscellaneous information propagated up from a solver.
Abstract base class for reductions.
A reduction is an actor that transforms a problem into an equivalent problem. By equivalent we mean that there exists a mapping between solutions of either problem: if we reduce a problem \(A\) to another problem \(B\) and then proceed to find a solution to \(B\), we can convert it to a solution of \(A\) with at most a moderate amount of effort.
A reduction that is instantiated with a non-None problem offers two key methods: reduce and retrieve. The reduce() method converts the problem the reduction was instantiated with to an equivalent problem. The retrieve() method takes as an argument a Solution for the equivalent problem and returns a Solution for the problem owned by the reduction.
Every reduction offers three low-level methods: accepts, apply, and invert. The accepts method of a particular reduction specifies the types of problems that it is applicable to; the apply method takes a problem and reduces it to an equivalent form, and the invert method maps solutions from reduced-to problems to their problems of provenance.
A problem owned by this reduction; possibly None.
Construct a reduction for reducing problem.
If problem is not None, then a subsequent invocation of reduce() will reduce problem and return an equivalent one.
States whether the reduction accepts a problem.
The problem to check.
True if the reduction can be applied, False otherwise.
Applies the reduction to a problem and returns an equivalent problem.
The problem to which the reduction will be applied.
Problem or dict – An equivalent problem, encoded either as a Problem or a dict.
InverseData, list or dict – Data needed by the reduction in order to invert this particular application.
Returns a solution to the original problem given the inverse_data.
A solution to a problem that generated the inverse_data.
The data encoding the original problem.
A solution to the original problem.
Reduces the owned problem to an equivalent problem.
An equivalent problem, encoded either as a Problem or a dict.
ValueError – If this Reduction was constructed without a Problem.
Retrieves a solution to the owned problem.
A solution to the problem emitted by reduce().
A solution to the owned problem.
ValueError – If self.problem is None, or if reduce() was not previously called.