.. _coniclifts: ``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 ------------------ .. autoclass:: sageopt.coniclifts.Variable :members: 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 :ref:`cl_expression_system` and :ref:`cl_compilerinterface`. .. autoclass:: sageopt.coniclifts.Problem :members: .. _cl_expression_system: 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. .. autoclass:: sageopt.coniclifts.Expression :members: SAGE constraints ---------------- .. _MCW2019: https://arxiv.org/abs/1907.00814 .. _MCW2018: https://arxiv.org/abs/1810.01614 Coniclifts provides direct implementations of the primal and dual signomial SAGE cones: - :class:`sageopt.coniclifts.PrimalSageCone`, and - :class:`sageopt.coniclifts.DualSageCone`. 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 ~~~~~~~~~~~~~~~~~~~~~~~ .. autoclass:: sageopt.coniclifts.PrimalSageCone :members: Dual SAGE constraints ~~~~~~~~~~~~~~~~~~~~~ .. autoclass:: sageopt.coniclifts.DualSageCone :members: .. _cl_sage_options: 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. .. autofunction:: sageopt.coniclifts.presolve_trivial_age_cones .. autofunction:: sageopt.coniclifts.heuristic_reduce_cond_age_cones .. autofunction:: sageopt.coniclifts.age_cone_reduction_solver .. autofunction:: sageopt.coniclifts.sum_age_force_equality .. autofunction:: sageopt.coniclifts.compact_sage_duals .. autofunction:: sageopt.coniclifts.kernel_basis_age_witnesses .. _cl_compilerinterface: 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 :math:`X \subset R^n`, there exists a matrix :math:`A \in R^{k \times m}` , a vector :math:`b \in R^k`, and a convex cone :math:`K \subset R^k` so that :math:`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 :math:`K` is a product of elementary convex cones #. The zero cone. #. The nonnegative orthant. #. The exponential cone. #. The second-order cone. #. 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. .. autofunction:: sageopt.coniclifts.compilers.compile_constrained_system