Back-End Reductions

The reductions listed here are specific to the choice of back end, i.e., solver. Currently, we support two types of back ends: conic solvers and quadratic program solvers. When a problem is solved through the solve() method, CVXPY attempts to find the best back end for your problem. The Dcp2Cone reduction converts DCP-compliant problems into conic form, while the Qp2SymbolicQp converts problems with quadratic, piecewise affine objectives, affine equality constraints, and piecewise-linear inequality constraints into a form that is closer to what is accepted by solvers. The problems output by both reductions must be passed through another sequence of reductions, not documented here, before they are ready for to be solved.

Please see our disclaimer about the Reductions API before using these directly in your code.

Dcp2Cone

class cvxpy.reductions.dcp2cone.dcp2cone.Dcp2Cone(problem=None, quad_obj: bool = False)

Bases: Canonicalization

Reduce DCP problems to a conic form.

This reduction takes as input (minimization) DCP problems and converts them into problems with affine or quadratic objectives and conic constraints whose arguments are affine.

accepts(problem)

A problem is accepted if it is a minimization and is DCP.

apply(problem)

Converts a DCP problem to a conic form.

canonicalize_expr(expr, args, affine_above: bool) → Tuple[Expression, list]

Canonicalize an expression, w.r.t. canonicalized arguments.

Parameters:

• expr (The expression tree to canonicalize.) –

• args (The canonicalized arguments of expr.) –

• affine_above (The path up to the root node is all affine atoms.) –

Return type:

A tuple of the canonicalized expression and generated constraints.

canonicalize_tree(expr, affine_above: bool) → Tuple[Expression, list]

Recursively canonicalize an Expression.

Parameters:

• expr (The expression tree to canonicalize.) –

• affine_above (The path up to the root node is all affine atoms.) –

Return type:

A tuple of the canonicalized expression and generated constraints.

Qp2SymbolicQp

class cvxpy.reductions.qp2quad_form.qp2symbolic_qp.Qp2SymbolicQp(problem=None)

Bases: Canonicalization

Reduces a quadratic problem to a problem that consists of affine expressions and symbolic quadratic forms.

accepts(problem)

Problems with quadratic, piecewise affine objectives, piecewise-linear constraints inequality constraints, and affine equality constraints are accepted.

apply(problem)

Converts a QP to an even more symbolic form.

Dualize

class cvxpy.reductions.cone2cone.affine2direct.Dualize

CVXPY represents cone programs as

(P-Opt) min{ c.T @ x : A @ x + b in K } + d,

where the corresponding dual is

(D-Opt) max{ -b @ y : c = A.T @ y, y in K^* } + d.

For some solvers, it is much easier to specify a problem of the form (D-Opt) than it is to specify a problem of the form (P-Opt). The purpose of this reduction is to handle mapping between (P-Opt) and (D-Opt) so that a solver interface can pretend the original problem was stated in terms (D-Opt).

Usage

Dualize applies to ParamConeProg problems. It accesses (P-Opt) data by calling c, d, A, b = problem.apply_parameters(). It assumes the solver interface has already executed its format_constraints function on the ParamConeProg problem.

A solver interface is responsible for calling both Dualize.apply and Dualize.invert. The call to Dualize.apply should be one of the first things that happens, and the call to Dualize.invert should be one of the last things that happens.

The “data” dict returned by Dualize.apply is keyed by s.A, s.B, s.C, and ‘K_dir’, which respectively provide the dual constraint matrix (A.T), the dual constraint right-hand-side (c), the dual objective vector (-b), and the dual cones (K^*). The solver interface should interpret this data is a new primal problem, just with a maximization objective. Given a numerical solution, the solver interface should first construct a CVXPY Solution object where \(y\) is a primal variable, divided into several blocks according to the structure of elementary cones appearing in K^*. The only dual variable we use is that corresponding to the equality constraint \(c = A^T y\). No attempt should be made to map unbounded / infeasible status codes for (D-Opt) back to unbounded / infeasible status codes for (P-Opt); all such mappings are handled in Dualize.invert. Refer to Dualize.invert for detailed documentation.

Assumptions

The problem has no integer or boolean constraints. This is necessary because strong duality does not hold for problems with discrete constraints.

Dualize.apply assumes “SOLVER.format_constraints()” has already been called. This assumption allows flexibility in how a solver interface chooses to vectorize a feasible set (e.g. how to order conic constraints, or how to vectorize the PSD cone).

Additional notes

Dualize.invert is written in a way which is agnostic to how a solver formats constraints, but it also imposes specific requirements on the input. Providing correct input to Dualize.invert requires consideration to the effect of SOLVER.format_constraints and the output of problem.apply_parameters.

static invert(solution, inv_data)

solution is a CVXPY Solution object, formatted where

(D-Opt) max{ -b @ y : c = A.T @ y, y in K^* } + d

is the primal problem from the solver’s perspective. The purpose of this function is to map such a solution back to the format

(P-Opt) min{ c.T @ x : A @ x + b in K } + d.

This function handles mapping of primal and dual variables, and solver status codes. The variable “x” in (P-Opt) is trivially populated from the dual variables to the constraint “c = A.T @ y” in (D-Opt). Status codes also map back in a simple way.

Details on required formatting of solution.primal_vars

We assume the dict solution.primal_vars is keyed by string-enums FREE (‘fr’), NONNEG (‘+’), SOC (‘s’), PSD (‘p’), and DUAL_EXP (‘de’). The corresponding values are described below.

solution.primal_vars[FREE] should be a single vector. It corresponds to the (possibly concatenated) components of “y” which are subject to no conic constraints. We map these variables back to dual variables for equality constraints in (P-Opt).

solution.primal_vars[NONNEG] should also be a single vector, this time giving the possibly concatenated components of “y” which must be >= 0. We map these variables back to dual variables for inequality constraints in (P-Opt).

solution.primal_vars[SOC] is a list of vectors specifying blocks of “y” which belong to the second-order-cone under the CVXPY standard ({ z : z[0] >= || z[1:] || }). We map these variables back to dual variables for SOC constraints in (P-Opt).

solution.primal_vars[PSD] is a list of symmetric positive semidefinite matrices which result by lifting the vectorized PSD blocks of “y” back into matrix form. We assign these as dual variables to PSD constraints appearing in (P-Opt).

solution.primal_vars[DUAL_EXP] is a vector of concatenated length-3 slices of y, where each constituent length-3 slice belongs to dual exponential cone as implied by the CVXPY standard of the primal exponential cone (see cvxpy/constraints/exponential.py:ExpCone). We map these back to dual variables for exponential cone constraints in (P-Opt).

Slacks

class cvxpy.reductions.cone2cone.affine2direct.Slacks

CVXPY represents mixed-integer cone programs as

(Aff) min{ c.T @ xA @ x + b in K,

x[bools] in {0, 1}, x[ints] in Z } + d.

Some solvers do not accept input in the form (Aff). A general pattern we find across solver types is that the feasible set is represented by

(Dir) min{ f @ yG @ y <=_{K_aff} h, y in K_dir

y[bools] in {0, 1}, y[ints] in Z } + d,

where K_aff is built from a list convex cones which includes the zero cone (ZERO), and K_dir is built from a list of convex cones which includes the free cone (FREE).

This reduction handles mapping back and forth between problems stated in terms of (Aff) and (Dir), by way of adding slack variables.

Notes

Support for semidefinite constraints has not yet been implemented in this reduction.

If the problem has no integer constraints, then the Dualize reduction should be used instead.

Because this reduction is only intended for mixed-integer problems, this reduction makes no attempt to recover dual variables when mapping between (Aff) and (Dir).

static apply(prob, affine)

“prob” is a ParamConeProg which represents

(Aff) min{ c.T @ xA @ x + b in K,

x[bools] in {0, 1}, x[ints] in Z } + d.

We return data for an equivalent problem

(Dir) min{ f @ yG @ y <=_{K_aff} h, y in K_dir

y[bools] in {0, 1}, y[ints] in Z } + d,

where

1. K_aff is built from cone types specified in “affine” (a list of strings),

2. a primal solution for (Dir) can be mapped back to a primal solution for (Aff) by selecting the leading c.size block of y’s components.

In the returned dict “data”, data[s.A] = G, data[s.B] = h, data[s.C] = f, data[‘K_aff’] = K_aff, data[‘K_dir’] = K_dir, data[s.BOOL_IDX] = bools, and data[s.INT_IDX] = ints. The rows of G are ordered according to ZERO, then (as applicable) NONNEG, SOC, and EXP. If “c” is the objective vector in (Aff), then y[:c.size] should contain the optimal solution to (Aff). The columns of G correspond first to variables in cones FREE, then NONNEG, then SOC, then EXP. The length of the free cone is equal to c.size.

Assumptions

The function call c, d, A, b = prob.apply_parameters() returns (A,b) with rows formatted first for the zero cone, then for the nonnegative orthant, then second order cones, then the exponential cone. Removing this assumption will require adding additional data to ParamConeProg objects.