Reductions

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.

Reductions allow CVXPY to simplify problems and target different categories of solvers (quadratic program solvers and conic solvers are two examples of solver categories). 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.

The majority of users will not need to know anything about the reduction API; indeed, most users need not even know that reductions exist. But those who wish to extend CVXPY or contribute to it may find the API useful, as might those who are simply curious to learn how CVXPY works.

• Middle-End Reductions
  • Complex2Real
    • Complex2Real
      • Complex2Real.accepts()
      • Complex2Real.apply()
      • Complex2Real.invert()
  • CvxAttr2Constr
    • CvxAttr2Constr
      • CvxAttr2Constr.accepts()
      • CvxAttr2Constr.apply()
      • CvxAttr2Constr.invert()
  • Dgp2Dcp
    • Dgp2Dcp
      • Dgp2Dcp.accepts()
      • Dgp2Dcp.apply()
      • Dgp2Dcp.canonicalize_expr()
      • Dgp2Dcp.invert()
  • EvalParams
    • EvalParams
      • EvalParams.accepts()
      • EvalParams.apply()
      • EvalParams.invert()
  • FlipObjective
    • FlipObjective
      • FlipObjective.accepts()
      • FlipObjective.apply()
      • FlipObjective.invert()
• Back-End Reductions
  • Dcp2Cone
    • Dcp2Cone
      • Dcp2Cone.accepts()
      • Dcp2Cone.apply()
  • Qp2SymbolicQp
    • Qp2SymbolicQp
      • Qp2SymbolicQp.accepts()
      • Qp2SymbolicQp.apply()

Solution

class cvxpy.reductions.solution.Solution(status, opt_val, primal_vars, dual_vars, attr)

Bases: object

A solution to an optimization problem.

status

The status code.

Type:

str

opt_val

The optimal value.

Type:

float

primal_vars

A map from variable ids to optimal values.

Type:

dict of id to NumPy ndarray

dual_vars

A map from constraint ids to dual values.

Type:

dict of id to NumPy ndarray

attr

Miscelleneous information propagated up from a solver.

Type:

dict

Reduction

class cvxpy.reductions.reduction.Reduction(problem=None)

Bases: object

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.

Parameters:

problem (Problem) – A problem owned by this reduction; possibly None.

__init__(problem=None) → 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.

accepts(problem)

States whether the reduction accepts a problem.

Parameters:

problem (Problem) – The problem to check.

Returns:

True if the reduction can be applied, False otherwise.

Return type:

bool

abstract apply(problem)

Applies the reduction to a problem and returns an equivalent problem.

Parameters:

problem (Problem) – The problem to which the reduction will be applied.

Returns:

• 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.

abstract invert(solution, inverse_data)

Returns a solution to the original problem given the inverse_data.

Parameters:

• solution (Solution) – A solution to a problem that generated the inverse_data.

• inverse_data – The data encoding the original problem.

Returns:

A solution to the original problem.

Return type:

Solution

reduce()

Reduces the owned problem to an equivalent problem.

Returns:

An equivalent problem, encoded either as a Problem or a dict.

Return type:

Problem or dict

Raises:

ValueError – If this Reduction was constructed without a Problem.

retrieve(solution)

Retrieves a solution to the owned problem.

Parameters:

solution (Solution) – A solution to the problem emitted by reduce().

Returns:

A solution to the owned problem.

Return type:

Solution

Raises:

ValueError – If self.problem is None, or if reduce() was not previously called.

Chain

class cvxpy.reductions.chain.Chain(problem=None, reductions=None)

Bases: Reduction

A logical grouping of multiple reductions into a single reduction.

reductions

A list of reductions.

Type:

list[Reduction]

accepts(problem) → bool

A problem is accepted if the sequence of reductions is valid.

In particular, the i-th reduction must accept the output of the i-1th reduction, with the first reduction (self.reductions[0]) in the sequence taking as input the supplied problem.

Parameters:

problem (Problem) – The problem to check.

Returns:

True if the chain can be applied, False otherwise.

Return type:

bool

apply(problem, verbose: bool = False)

Applies the chain to a problem and returns an equivalent problem.

Parameters:

• problem (Problem) – The problem to which the chain will be applied.

• verbose (bool, optional) – Whehter to print verbose output.

Returns:

• Problem or dict – The problem yielded by applying the reductions in sequence, starting at self.reductions[0].

• list – The inverse data yielded by each of the reductions.

invert(solution, inverse_data)

Returns a solution to the original problem given the inverse_data.

SolvingChain

class cvxpy.reductions.solvers.solving_chain.SolvingChain(problem=None, reductions=None)

Bases: Chain

A reduction chain that ends with a solver.

Parameters:

reductions (list[Reduction]) – A list of reductions. The last reduction in the list must be a solver instance.

reductions

A list of reductions.

Type:

list[Reduction]

solver

The solver, i.e., reductions[-1].

Type:

Solver

prepend(chain) → SolvingChain

Create and return a new SolvingChain by concatenating chain with this instance.

solve(problem, warm_start: bool, verbose: bool, solver_opts)

Solves the problem by applying the chain.

Applies each reduction in the chain to the problem, solves it, and then inverts the chain to return a solution of the supplied problem.

Parameters:

• problem (Problem) – The problem to solve.

• warm_start (bool) – Whether to warm start the solver.

• verbose (bool) – Whether to enable solver verbosity.

• solver_opts (dict) – Solver specific options.

Returns:

solution – A solution to the problem.

Return type:

Solution

solve_via_data(problem, data, warm_start: bool = False, verbose: bool = False, solver_opts={})

Solves the problem using the data output by the an apply invocation.

The semantics are:

data, inverse_data = solving_chain.apply(problem)
solution = solving_chain.invert(solver_chain.solve_via_data(data, ...))

which is equivalent to writing

solution = solving_chain.solve(problem, ...)

Parameters:

• problem (Problem) – The problem to solve.

• data (map) – Data for the solver.

• warm_start (bool) – Whether to warm start the solver.

• verbose (bool) – Whether to enable solver verbosity.

• solver_opts (dict) – Solver specific options.

Returns:

The information returned by the solver; this is not necessarily a Solution object.

Return type:

raw solver solution