coniclifts is sageopt’s backend

Sageopt does not solve SAGE relaxations on its own; it relies on third party convex optimization solvers, such as ECOS or MOSEK. These solvers require input in very specific standard-forms. Coniclifts provides abstractions that allow us to state SAGE relaxations in high-level syntax, and manage interactions with these low-level solvers.

Overview

Coniclifts employs abstractions that are similar to those in CVXPY. For example, it is possible to construct and solve a linear program using coniclifts:

import sageopt.coniclifts as cl
import numpy as np
# random problem data
G = np.random.randn(3, 6)
h = A @ np.random.rand(6)
c = np.random.rand(6)
# input to coniclift's Problem constructor
x = cl.Variable(shape=(6,))
constrs = [0 <= x, G @ x == h]
objective_expression = c @ x
prob = cl.Problem(cl.MIN, objective_expression, constrs)
prob.solve(solver='ECOS', verbose=False)
x_opt = x.value

In the example above, constrs consists of two coniclifts Constraint objects. Both of these objects were constructed with operator overloading (<= and ==), and the second Constraint made use of operator-overloaded matrix multiplication (@). If you check the datatype of the object y = A @ x, you would find that y is a coniclifts Expression. Expression objects track functions of Variable objects.

Coniclifts has support for nonlinear convex constraints. The most important of these constraints are specified as “set membership”, rather than elementwise inequalities. For example, we have a PrimalSageCone class, which is used to construct some of the SAGE relaxations in the sageopt.relaxations package. Here is a concrete demonstration

alpha = np.array([[0, 0],
                  [1, 0],
                  [0, 1],
                  [1, 1],
                  [0.5, 0],
                  [0, 0.5]])
c = np.array([0, 3, 2, 1, -4, -2])
# alpha, c define a signomial in the usual way
gamma = cl.Variable(shape=(), name='gamma')
c_expr = c.copy()
c_expr[0] -= gamma   # shift the constant term by -gamma
constr = cl.PrimalSageCone(c_expr, alpha, X=None, name='example_constraint')
prob = Problem(cl.MAX, gamma, [constr])
# find largest gamma so shifted signomial is nonnegative
status, val = prob.solve()

By solving the problem described above, we have that val is a lower bound on the signomial which takes values lambda x: c @ np.exp(alpha @ x). There are only a few set-membership constraints currently implemented in coniclifts; they can all be found in sageopt.coniclifts.constraints.set_membership.

Coniclifts contains operators which represent functions applied to Expression objects. The module sageopt/coniclifts/operators/affine.py contains all affine array-manipulation operators you would use on a numpy ndarray [link]. This includes linear algebra operators such as kron or trace, reshaping operators such as hstack or tile, and array-creation routines like diag or triu. These functions behave in identical ways to their numpy counterparts, because Expression objects are actually a custom subclass of numpy’s ndarray datatype.

Coniclifts also has a small selection of nonlinear operators: weighted_sum_exp, vector2norm, and relent. It is easy to add more nonlinear operators, but these three suffice for the internal uses currently found in sageopt. Here is a concrete example

alpha = np.array([[1, 0],
                  [0, 1],
                  [1, 1],
                  [0.5, 0],
                  [0, 0.5]])
c = np.array([3, 2, 1, 4, 2])
x = cl.Variable(shape=(2,), name='x')
cons = [cl.weighted_sum_exp(c, alpha @ x) <= 1]
obj = -x[0] - 2*x[1]
prob = Problem(cl.MIN, obj, cons)
prob.solve()
x_expect = np.array([-4.93083, -2.73838])
x_actual = x.value
print(np.allclose(x_expect, x_actual, atol=1e-4))

If you run the code above, you should find that it prints True.

It is important to note that nonlinear operators are not allowed in the objective function. So if you want to minimize a nonlinear convex function given by expr, you need to create an auxiliary variable such as t = Variable(shape=(1,)), add the constraint expr <= t, and set the objective to minimize t. Here is an example of a constrained least-squares problem we solve for solution recovery in dual SAGE relaxations

A, b, K = con.X.A, con.X.b, con.X.K  # con is a DualSageCone instance
log_v = np.log(con.v.value)
A = np.asarray(A)
x = cl.Variable(shape=(A.shape[1],))
t = cl.Variable(shape=(1,))
cons = [cl.vector2norm(log_v - alpha @ x[:con.n]) <= t,
        cl.PrimalProductCone(A @ x + b, K)]
prob = cl.Problem(cl.MIN, t, cons)

The example above also alludes to a useful set-membership constraint, called PrimalProductCone. Follow this link for source code of set-membership constraints available in coniclifts.

The Variable class

class sageopt.coniclifts.Variable(shape=(), name=None, var_properties=None)

An abstraction for a symbol appearing in constraint sets, or optimization problems.

Variable objects are a custom subclass of numpy ndarrays.

Parameters

  • shape (tuple) – The dimensions of the Variable object. Defaults to shape=().

  • name (str) – A string which should uniquely identify this Variable object in all models where it appears. Ideally, this string should be human-readable. Defaults to 'unnamed_var_N', where N is an integer.

  • var_properties (list of str) – Currently, the only accepted forms of this argument are the empty list (in which case an unstructured Variable is returned), or a list containing the string 'symmetric' (in which case a symmetric matrix Variable is returned).

Examples

The symbol you use in the Python interpreter does not need to match the “name” of a Variable.

x = Variable(shape=(3,), name='my_name')

A Variable object can take on any dimension that a numpy ndarray could take on.

y = Variable(shape=(10,4,1,2), name='strange_shaped_var')

Notes

Upon construction, Variable objects are “proper”. If you index into them, they are still considered Variable objects, but they no longer contain information about all of their components. A Variable object’s name field only uniquely determines the “proper” version of that Variable. If v.is_proper() == False, then it should be possible to recover the original Variable object with original_v = v.base.

x = Variable(shape=(3,), name='x')
print(type(x))  # sageopt.coniclifts.base.Variable
print(x.is_proper())  # True

y = x[1:]
print(type(y))  # sageopt.coniclifts.base.Variable
print(y.is_proper())  # False
print(x.name == y.name)  # True
print(id(x) == id(y.base))  # True; these exist at the same place in memory.
scalar_variables()

Return a list of all ScalarVariables appearing in this Expression.

property scalar_variable_ids

Each component of this Variable object (i.e. each “scalar variable”) contains an index which uniquely identifies it in all models where this Variable appears. Return the list of these indices.

property name

A string which should uniquely identify this object in all models where it appears, provided self.is_proper() == True.

property generation

An internally-maintained index. Variable objects of different “generation” cannot participate in a common optimization problem.

property value

An ndarray containing numeric entries, of shape equal to self.shape. This is the result of the most recent call to set_scalar_variables.

The Problem class

Detailed documentation for the Problem class is given below. Most users will only interact with a few aspects of Problem objects. On a first read, it should be enough just to skim the documentation for this class. If you want to understand all the attributes of a Problem object, you will need to read The Expression system and The compiler interface.

class sageopt.coniclifts.Problem(sense, objective, constraints, **kwargs)

A representation for a convex optimization problem. When this Problem object is constructed, the constraints are immediately compiled into a flattened conic representation. This compilation process may take some time for large problems.

Parameters

  • sense (str) – Either coniclifts.MIN or coniclifts.MAX

  • objective (Expression) – The function to minimize or maximize. ScalarExpressions and real numeric types are also accepted. The final (cast) expression must be linear in its Variables.

  • constraints (list of coniclifts.Constraint) – Variables appearing in objective are subject to Constraint objects in this list.

sense

The value passed by the user to the constructor.

Type

str

objective

The value passed by the user to the constructor.

Type

Expression

constraints

The value passed by the user to the constructor.

Type

list of coniclifts.Constraint

all_variables

All Variable objects needed to represent the feasible set. This includes user-declared Variables, and Variables which were required to write the problem in terms of coniclifts primitives. It is recommended to access this list by calling self.variables().

Type

list of coniclifts.Variable

status

The problem status from the last call to self.solve. Either coniclifts.SOLVED or coniclifts.INACCURATE or coniclifts.FAILED.

Type

str

value
The objective value from the last call to self.solve. Can be a float,

np.inf, -np.inf, or np.NaN.

Type

float

variable_values

A map from a Variable’s name field to a numpy array, containing a feasible value for that Variable for this problem’s constraints.

Type

Dict[str, ndarray]

metadata

A place for users to store metadata produced when constructing this Problem.

Type

dict

timings

Contains runtime (in seconds) for various operations associated with Problem. There is always a field timings['compile_time'], which is the time spent parsing user-specified constraints into a vectorized cone program. Upon a call to self.solve(solver=SOLVER), there is also a dict timings[SOLVER] which contains time spent transforming a coniclifts representation to a solver’s standard form, and time spent by the underlying solver itself.

Type

dict

solver_apply_data

Stores metadata during a call to self.solve(cache_apply_data=True).

Type

Dict[str,dict]

solver_raw_output

Stores metadata during a call to self.solve(cache_raw_output=True).

Type

Dict[str,dict]

A

The matrix in the flattened conic representation of the feasible set.

Type

CSC-format sparse matrix

b

The offset vector in the flattened conic representation of the feasible set.

Type

ndarray

K

The cartesian product of these cones (in order) defines the convex cone appearing in the flattened conic representation of the feasible set.

Type

list of coniclifts.Cone

variable_map

A map from a Variable’s name field to a numpy array. If myvar is a coniclifts Variable appearing in the system defined by constraints, then a point x satisfying \(A x + b \in K\) maps to a feasible value for myvar by

x0 = np.hstack([x, 0])
myvar_val = x0[variable_map[myvar.name]]

In particular, we guarantee myvar.shape == variable_map[myvar.name].shape. Augmenting x by zero to create x0 reflects a convention that if a component of a Variable does not affect the constraints, that component is automatically assigned the value zero.

Type

Dict[str,ndarray]

Notes

Problem status being coniclifts.SOLVED does not mean that the decision variables have been assigned specific values. It only means that the solver returned a normal status code (i.e. that the solver didn’t run into numerical difficulties). If a solver indicates the problem is infeasible or unbounded, we still set self.status = coniclifts.SOLVED. Therefore it is important to check that self.status == coniclifts.SOLVED and that -np.inf < self.value < np.inf before accessing a Variable’s value.

Accepts a keyword argument integer_variables: a list of Variable objects which should be restricted to integer values in this optimization problem. Only applicable when using MOSEK as the solver.

solve(solver=None, **kwargs)
Parameters

solver (str) – None or 'MOSEK' or 'ECOS'. Defaults to the first installed solver found in Problem._SOLVER_ORDER_.

Returns

  • status (str) – Either coniclifts.SOLVED or coniclifts.INACCURATE or coniclifts.FAILED. Refer to the Notes of the Problem class for the meanings of these values.

  • value (float) – The optimal objective value reported by the solver. Can be a float, -np.inf, np.inf, or np.NaN.

Notes

Keyword arguments.

verbose : bool. If False, then suppress solver output from being written to standard-out.

cache_raw_data : bool. If True, then record the raw output of the solver in the dictionary self.solver_raw_output. For MOSEK, this raw output includes the MOSEK Task object.

max_iters : int. Maximum number of iterations for ECOS.

mosek_params : dict. Following CVXPY parameter processing conventions. Also, allows options {'NUM_THREADS': int, 'CO_TOL_NEAR_REL': float, 'TOL_PATH': float, 'TOL_STEP_SIZE': float, 'DEACTIVATE_SCALING': bool}. Refer to the coniclifts MOSEK interface source code for usage of these parameters.

cache_apply_data : bool. If True, then take the put``(data, inv_data)`` returned by the coniclifts interface to the given solver and record it in the dictionary self.solver_apply_data. This data is rarely relevant for users.

dualize : bool. Overrides coniclifts automatic dualization procedure when using MOSEK Setting dualize=True forces dualization, and setting dualize=False prohibits dualization. Not applicable when solving mixed-integer problems.

variables()

Return a shallow copy of self.all_variables.

This function is provided to match the syntax of CVXPY Problem objects.

The Expression system

Coniclifts is built around a few core ideas, including …

  • transparency in the compilation process,

  • ease-of-extension for experts in convex optimization,

  • no dependence on a C or C++ backend,

  • full compatibility with numpy.

In order to achieve full compatibility with numpy, coniclifts takes an elementwise approach to symbolic expressions. Specifically, coniclifts begins with a few simple abstractions for scalar-valued symbolic expressions, and wraps those abstractions in a custom subclass of numpy’s ndarray. The coniclifts abstractions for scalar-valued symbolic expressions are as follows:

  • A ScalarExpression class represents scalar-valued affine functions of certain irreducible primatives. ScalarExpressions are operator-overloaded to support +, -, and *. This allows ndarrays of ScalarExpressions to fall back on many functions which are implemented for numeric ndarrays.

  • An abstract ScalarAtom class specifies the behavior of the irreducible primitives in ScalarExpressions. The ScalarAtom class immediately specializes into ScalarVariables (far and away the most important ScalarAtom), and another abstract class, called NonlinearScalarAtom. NonlinearScalarAtoms are implemented on a case-by-case basis, but include such things as the exponential function and the vector 2-norm.

We ask interested users to refer to the source code for additional information on ScalarExpressions and ScalarAtoms. For most people, all you need to work with is the Expression class.

class sageopt.coniclifts.Expression(obj)

An Expression is an ndarray whose entries are ScalarExpressions. Variable objects are a special case of Expression objects.

Construction

Expression objects can be constructed from ndarrays of numeric types, or ndarrays containing ScalarExpressions. In both cases, the construction syntax is

expr = Expression(existing_array)

Arithmetic operator overloading

Operations +, -, / and * work in the exact same way as for numpy arrays.

Expressions do not allow exponentiation (**).

Expressions overload @ (a.k.a. __matmul__) in a way that is consistent with numpy, but only for arguments which have up to two dimensions.

Constraint-based operator overloading

Operations <= and >= produce elementwise inequality constraints.

The operation == produces an elementwise equality constraint.

The operations >> and << produce linear matrix inequality constraints.

scalar_atoms()

Return a list of all ScalarAtoms appearing in this Expression.

scalar_variables()

Return a list of all ScalarVariables appearing in this Expression.

variables()

Return a list of all Variable objects appearing in this Expression. You can assume that all Variable objects will be “proper”.

is_affine()

True if the Expression is an affine function of Variables within its scope.

is_constant()

True if no Variables appear in this Expression.

is_convex()

Return an ndarray of booleans. For a fixed component index, the value of the returned array indicates if that component of the current Expression is a convex function of Variables within its scope.

is_concave()

Return an ndarray of booleans. For a fixed component index, the value of the returned array indicates if that component of the current Expression is a concave function of Variables within its scope.

factor()

Returns a tuple (A, x, B).

A is a tensor of one order higher than the current Expression object, i.e. A.ndim == self.ndim + 1. The dimensions of A and self agree up until self.ndim, i.e. A.shape[:-1] == self.shape.

x is a list of ScalarAtom objects, with len(x) == A.shape[-1].

B is a numpy array of the same shape as self.

The purpose of this function is to enable faster matrix multiplications of Expression objects. The idea is that if you tensor-contract A along its final dimension according to x, and then add B, you recover this Expression.

property value

An ndarray containing numeric entries, of shape equal to self.shape. This is the result of propagating the value of ScalarVariable objects through the symbolic operations tracked by this Expression.

static are_equivalent(expr1, expr2, rtol=1e-05, atol=1e-08)

Perform a check that expr1 and expr2 are symbolically equivalent, in the sense of affine operators applied to ScalarAtoms. The equivalence is up to numerical tolerance in the sense of np.allclose.

Parameters

  • expr1 (Expression) –

  • expr2 (Expression) –

  • rtol (float) – relative numerical tolerance

  • atol (float) – absolute numerical tolerance

Returns

Return type

True if the Expressions can be verified as symbolically equivalent. False otherwise.

Notes

The behavior of this function is conservative. If self contains a mix of ScalarAtoms (e.g. ScalarVariables and NonlinearScalarAtoms), then this function might return False even when expr1 and expr2 are equivalent. This is due to nondeterministic behavior of Expression.factor in such situations.

SAGE constraints

Coniclifts provides direct implementations of the primal and dual signomial SAGE cones:

These classes have virtually identical constructors and public attributes. In particular, both classes’ constructors require an argument X, which can be None or a SigDomain. Ordinary SAGE constraints are obtained by setting X=None. Conditional SAGE constraints assume the set represented by X is nonempty, and it’s the user’s responsibility to ensure this is the case. The main difference in these classes’ attributes is that PrimalSageCone instances have a dict called age_vectors (which represent the certificates of nonnegativity) and that DualSageCone instances have a dict called mu_vars (which are useful for solution recovery in SAGE relaxations of signomial programs).

The PrimalSageCone class performs a very efficient dimension-reduction procedure by analyzing the signs of the provided vector c. The details of the reduction are described in Corollary 5 of MCW2019. At present, coniclifts does not provide a means to track the signs of Variable objects, and so this reduction is limited to indices i where c[i] is constant. This feature can optionally be carried over to DualSageCone objects, if the user provides a keyword argument c to the DualSageCone constructor.

The PrimalSageCone and DualSageCone classes can perform a more extensive presolve phase to eliminate trivial AGE cones (those which reduce to the nonnegative orthant). By default, this presolve ability is turned off. This default can be changed by calling sageopt.coniclifts.presolve_trivial_age_cones(True). The computational cost of this presolve is borne when the constraint is constructed, and scales linearly in the dimension of the SAGE constraint (equal to constr.alpha.shape[0]). The cost of this presolve can be mitigated by recycling covers = constr.ech.expcovers from one call of a constraint constructor to the next.

Primal SAGE constraints

class sageopt.coniclifts.PrimalSageCone(c, alpha, X, name, **kwargs)

Require that \(f(x) = \sum_{i=1}^m c_i \exp(\alpha_i \cdot x)\) is nonnegative on \(X\), and furthermore that we can prove this nonnegativity by decomposing \(f\) into a sum of “\(X\)-AGE functions.” It is useful to summarize this constraint by writing

\[c \in C_{\mathrm{SAGE}}(\alpha, X).\]

Each \(X\)-AGE function used in the decomposition of \(f\) can be proven nonnegative by certifying a particular relative entropy inequality. This PrimalSageCone object tracks both coefficients of \(X\)-AGE functions used in the decomposition of \(f\), and the additional variables needed to certify the associated relative entropy inequalities.

Parameters

  • c (Expression) – The vector subject to this PrimalSageCone constraint.

  • alpha (ndarray) – The rows of alpha are the exponents defining this primal SAGE cone.

  • X (SigDomain or None) – If None, then this constraint represents a primal ordinary-SAGE cone.

  • name (str) – Uniquely identifies this Constraint in the model where it appears. Serves as a suffix for the name of any auxiliary Variable created when compiling to the coniclifts standard.

Other Parameters

  • settings (Dict[str, Union[str, bool]]) – A dict for overriding default settings which control how this PrimalSageCone is compiled into the coniclifts standard form. Recognized boolean flags are “heuristic_reduction”, “presolve_trivial_age_cones”, “sum_age_force_equality”, and “kernel_basis”. The “kernel_basis” flag is only applicable when X=None. The string flag “reduction_solver” must be either “MOSEK” or “ECOS”.

  • covers (Dict[int, ndarray]) – covers[i] indicates which indices j have alpha[j,:] participate in the i-th AGE cone. Automatically constructed in a presolve phase, if not provided. See also PrimalSageCone.ech.

alpha

The rows of alpha are the exponents defining this primal SAGE cone.

Type

ndarray

c

The vector subject to this PrimalSageCone constraint.

Type

Expression

age_vectors

A vector \(c^{(i)} = \mathtt{age{\_}vectors[i]}\) can have at most one negative component \(c^{(i)}_i\). Such a vector defines a signomial

\[f_i(x) = \textstyle\sum_{j=1}^m c^{(i)}_j \exp(\alpha_j \cdot x)\]

which is nonnegative for all \(x \in X\). Letting \(N \doteq \mathtt{self.age\_vectors.keys()}\), we should have

\[\mathtt{self.c} \geq \textstyle\sum_{i \in N} \mathtt{self.age\_vectors[i]}.\]

See also age_witnesses.

Type

Dict[int, Expression]

age_witnesses

A vector \(w^{(i)} = \mathtt{age{\_}witnesses[i]}\) should certify that the signomial with coefficients \(c^{(i)} = \mathtt{age{\_}vectors[i]}\) is nonnegative on \(X\). Specifically, we should have

\[\sigma_X\left(-\alpha^\intercal w^{(i)}\right) + D\left(w^{(i)}_{\setminus i}, e c^{(i)}_{\setminus i}\right)\leq c^{(i)}_i\]

where \(\sigma_X\) is the support function of \(X\), \(e\) is Euler’s number, \(w^{(i)}_{\setminus i} = ( w^{(i)}_j )_{j \in [m]\setminus \{i\}}\), \(c^{(i)}_{\setminus i} = ( c^{(i)}_j )_{j \in [m]\setminus \{i\}}\), and \(D(\cdot,\cdot)\) is the relative entropy function. The validity of this certificate stems from the weak-duality principle in convex optimization.

Type

Dict[int, Expression]

X

If None, then this constraint represents a primal ordinary-SAGE cone. See also the function PrimalSageCone.sigma_x.

Type

SigDomain or None

name

Uniquely identifies this Constraint in the model where it appears. Serves as a suffix for the name of any auxiliary Variable created when compiling to the coniclifts standard.

Type

str

settings

Specifies compilation options. By default this dict caches global compilation options when this object is constructed. The global compilation options are overridden if a user supplies settings as an argument when constructing this PrimalSageCone.

Type

Dict[str, Union[str, bool]]

ech

A data structure which summarizes the results from a presolve phase. The most important properties of ech can be specified by providing a dict-valued keyword argument “covers” to the PrimalSageCone constructor.

Type

ExpCoverHelper

Notes

The constructor can raise a RuntimeError if the constraint is deemed infeasible.

violation(norm_ord=inf, rough=False)

Return a measure of violation for the constraint that self.c belongs to \(C_{\mathrm{SAGE}}(\alpha, X)\).

Parameters

  • norm_ord (int) – The value of ord passed to numpy norm functions, when reducing vector-valued residuals into a scalar residual.

  • rough (bool) – Setting rough=False computes violation by solving an optimization problem. Setting rough=True computes violation by taking norms of residuals of appropriate elementwise equations and inequalities involving self.c and auxiliary variables.

Notes

When rough=False, the optimization-based violation is computed by projecting the vector self.c onto a new copy of a primal SAGE constraint, and then returning the L2-norm between self.c and that projection. This optimization step essentially re-solves for all auxiliary variables used by this constraint.

sigma_x(y, tol=1e-08)

If \(X = \mathbb{R}^n\), then return \(\infty\) when \(\|y\|_2 > \texttt{tol}\) and \(0\) otherwise. If \(X\) is a proper subset of \(\mathbb{R}^n\), then return the value of the support function of \(X\), evaluated at \(y\):

\[\sigma_X(y) \doteq \max\{ y^\intercal x \,:\, x \in X \}.\]

See also, the attribute PrimalSageCone.age_witnesses.

Dual SAGE constraints

class sageopt.coniclifts.DualSageCone(v, alpha, X, name, **kwargs)

Represent the constraint “\(v \in C_{\mathrm{SAGE}}(\alpha, X)^{\dagger}\)”.

Parameters

  • v (Expression) – The vector subject to the dual SAGE-cone constraint.

  • alpha (ndarray) – The matrix of exponent vectors defining the SAGE cone; alpha.shape[0] == v.size.

  • X (SigDomain or None) – If None, then this constraint represents a dual ordinary-SAGE cone.

  • name (str) – Uniquely identifies this Constraint in the model where it appears. Serves as a suffix for the name of any auxiliary Variable created when compiling to the coniclifts standard.

Other Parameters

  • c (Expression or None) – When provided, this DualSageCone instance will compile to a constraint to ensure that v is a valid dual variable to the constraint that \(c \in C_{\mathrm{SAGE}}(\alpha, X)\), If we have have information about the sign of a component of c, then it is possible to reduce the number of coniclifts primitives needed to represent this constraint.

  • settings (Dict[str, Union[str, bool]]) – A dict for overriding default settings which control how this DualSageCone is compiled into the coniclifts standard form. Recognized boolean flags are “heuristic_reduction”, “presolve_trivial_age_cones”, and “compact_dual”. The string flag “reduction_solver” must be either “MOSEK” or “ECOS”.

  • covers (Dict[int, ndarray]) – covers[i] indicates which indices j have alpha[j,:] participate in the i-th AGE cone. Automatically constructed in a presolve phase, if not provided. See also DualSageCone.ech.

alpha

The rows of alpha are the exponents defining this primal SAGE cone.

Type

ndarray

v

The vector subject to this dual SAGE cone constraint.

Type

Expression

X

If None, then this constraint represents a dual ordinary-SAGE cone.

Type

SigDomain

mu_vars

mu_vars[i] is the auxiliary variable associated with the i-th dual AGE cone. These variables are of shape mu_vars[i].size == alpha.shape[1]. The most basic solution recovery algorithm takes these variables, and considers points x of the form x = mu_vars[i].value / self.v[i].value.

Type

Dict[int, Variable]

settings

Specifies compilation options. By default this dict caches global compilation options when this object is constructed. The global compilation options are overridden if a user supplies settings as an argument when constructing this DualSageCone.

Type

Dict[str, Union[str, bool]]

ech

A data structure which summarizes the results from a presolve phase. The most important properties of ech can be specified by providing a dict-valued keyword argument “covers” to the DualSageCone constructor.

Type

ExpCoverHelper

violation(norm_ord=inf, rough=False)

Return a measure of violation for the constraint that self.v belongs to \(C_{\mathrm{SAGE}}(\alpha, X)^{\dagger}\).

Parameters

  • norm_ord (int) – The value of ord passed to numpy norm functions, when reducing vector-valued residuals into a scalar residual.

  • rough (bool) – Setting rough=False computes violation by solving an optimization problem. Setting rough=True computes violation by taking norms of residuals of appropriate elementwise equations and inequalities involving self.v and auxiliary variables.

Notes

When rough=False, the optimization-based violation is computed by projecting the vector self.v onto a new copy of a dual SAGE constraint, and then returning the L2-norm between self.v and that projection. This optimization step essentially re-solves for all auxiliary variables used by this constraint.

Compilation options

Coniclifts makes several decisions when compiling a SAGE constraint into a form which is acceptable to a solver like MOSEK or ECOS. The following functions allow you to control the defaults for this compilation process. The defaults can always be overridden by providing an appropriate keyword argument to the PrimalSageCone or DualSageCone constructor. Regardless of whether or not the default values are overridden, the settings used in a PrimalSageCone or DualSageCone object are cached upon construction. Therefore it is safe to modify these defaults while constructing different constraints for use in the same model.

sageopt.coniclifts.presolve_trivial_age_cones(true_or_false=False)

Set coniclifts’ behavior for SAGE constraints.

If true_or_false=True, then coniclifts will solve a series of small optimization problems whenever a SAGE constraint (primal or dual) is declared. This presolve behavior reduces the size of the final SAGE relaxation which needs to be solved, and in some sense improves problem conditioning.

The default value for true_or_false in this function’s signature represents sageopt’s default behavior for this setting.

sageopt.coniclifts.heuristic_reduce_cond_age_cones(true_or_false=True)

Set coniclifts’ behavior for conditional SAGE constraints.

If true_or_false=True, then coniclifts will take a particular reduction that is without-loss-of-generality for ordinary SAGE constraints, and apply that reduction to conditional SAGE constraints.

The default value for true_or_false in this function’s signature represents sageopt’s default behavior for this setting.

sageopt.coniclifts.age_cone_reduction_solver(solver_str='ECOS')

Use the provided string as the solver argument when any optimization-based presolve is employed in SAGE constraints.

The default value for solver_str in this function’s signature represents sageopt’s default behavior for this setting.

sageopt.coniclifts.sum_age_force_equality(true_or_false=False)

Set coniclifts’ behavior for compiling PrimalSageCone constraints.

If true_or_false=True, then a PrimalSageCone constraint con will tell the solver to require the values of con.age_vectors sum to con.c.

If true_or_false=False, then a PrimalSageCone constraint con will tell the solver to require the sum of values of con.age_vectors is <= con.c.

The default value for true_or_false in this function’s signature represents sageopt’s default behavior for this setting.

sageopt.coniclifts.compact_sage_duals(true_or_false=True)
Decide how coniclifts compiles constraints

v[i] * log(v[i] / v[j]) <= (alpha[i,:] - alpha[j,:]) @ mu_i (*)

which appear in DualSageCone objects.

If true_or_false=True, then (*) compiles into a constraint that maps (v[i],v[j],mu_i) into a single exponential cone.

If true_or_false=False, then compiling (*) introduces an epigraph variable epi plus the constraints v[i] * log(v[i]/v[j]) <= epi and epi <= (alpha[i,:] - alpha[j,:]) @ mu_i.

The default value for true_or_false in this function’s signature represents sageopt’s default behavior for this setting.

sageopt.coniclifts.kernel_basis_age_witnesses(true_or_false=True)

Set coniclifts’ behavior for SAGE constraints.

If true_or_false=True, then coniclifts will represent primal ordinary SAGE constraints using no equality constraints within an AGE cone. This comes at the expense of taking a longer time for coniclifts to setup the problem. It also might affect solver behavior (probably for the better).

The default value for true_or_false in this function’s signature represents sageopt’s default behavior for this setting.

The compiler interface

Up until now we have only described coniclifts as a tool for creating optimization problems. However, coniclifts’ more fundamental use is to exploit the following fact: for every convex set \(X \subset R^n\), there exists a matrix \(A \in R^{k \times m}\) , a vector \(b \in R^k\), and a convex cone \(K \subset R^k\) so that \(X = \{ (x_1,\ldots,x_n) \,:\, A x + b \in K, x \in R^m \}\). Coniclifts compiles all optimization problems into this standard form, where \(K\) is a product of elementary convex cones

  1. The zero cone.

  2. The nonnegative orthant.

  3. The exponential cone.

  4. The second-order cone.

  5. The vectorized positive semidefinite cone.

Crucially, coniclifts provides a means to map back and forth between models specified in high-level syntax, and models which exist in a flattened conic form using only primitives above.

The most important function in coniclifts’ compilation process is given below. The final return argument mentions “ScalarVariable” objects, which users of coniclifts need not interact with directly.

sageopt.coniclifts.compilers.compile_constrained_system(constraints)

Construct a flattened conic representation of the set of variable values which satisfy the constraints (“the feasible set”). Return the flattened representation of the feasible set, data structures for mapping the vectorized representation back to Variables, and a list of all Variables needed to represent the feasible set.

The final return argument (svid2col) can likely be ignored by end-users.

Parameters

constraints (list of coniclifts.Constraint) –

Returns

  • A (CSC-format sparse matrix) – The matrix appearing in the flattened representation of the feasible set.

  • b (ndarray) – The offset vector appearing in the flattened representation of the feasible set.

  • K (list of coniclifts Cone objects) – The cartesian product of these cones (in order) defines the convex cone appearing in the flattened representation of the feasible set.

  • variable_map (Dict[str, ndarray]) – A map from a Variable’s name field to a numpy array. If myvar is a coniclifts Variable appearing in the system defined by constraints, then a point x satisfying \(A x + b \in K\) maps to a feasible value for myvar by

    x0 = np.hstack([x, 0])
myvar_val = x0[variable_map[myvar.name]]

    In particular, we guarantee myvar.shape == variable_map[myvar.name].shape. Augmenting x by zero to create x0 reflects a convention that if a component of a Variable does not affect the constraints, that component is automatically assigned the value zero.

  • variables (list of coniclifts.Variable) – All proper Variable objects appearing in the constraint set, including any auxiliary variables introduced to obtain a flattened conic system.

  • svid2col (Dict[int, int]) – A map from a ScalarVariable’s id to the index of the column in A where the ScalarVariable participates in the conic system. If the given ScalarVariable does not participate in the conic system, its id maps to -1.