Working with SAGE signomials.

optimization

sageopt.sig_relaxation(f, form='dual', ell=0, X=None, mod_supp=None)

Construct a coniclifts Problem instance for producing a lower bound on

\[\min\{ f(x) \,:\, x \in X \}\]

where X = \(R^{\texttt{f.n}}\) by default.

If form='dual', we can also attempt to recover solutions to the above problem.

Parameters

  • f (Signomial) – The objective function to be minimized.

  • form (str) – Either form='primal' or form='dual'.

  • ell (int) – The level of the SAGE hierarchy. Must be nonnegative.

  • X (dict) – If X is None, then we produce a bound on f over \(R^{\texttt{f.n}}\). If X is a dict, then it must contain three fields: 'AbK', 'gts', and 'eqs'. For almost all applications, the appropriate dict X can be generated for you by calling conditional_sage_data(...).

  • mod_supp (NumPy ndarray) – This parameter is only used when ell > 0. If mod_supp is not None, then the rows of this array define the exponents of a positive definite modulating Signomial in the SAGE hierarchy.

Returns

prob – A coniclifts Problem which represents the SAGE relaxation, with given parameters. The relaxation can be solved by calling prob.solve().

Return type

sageopt.coniclifts.Problem

Notes

When form='primal', the Problem can be stated in full generality without too much trouble. We define a multiplier signomial t (with the canonical choice t = Signomial(f.alpha, np.ones(f.m))), then return problem data representing

max  gamma
s.t.    f_mod.c in C_{SAGE}(f_mod.alpha, X)
where   f_mod := (t ** ell) * (f - gamma).

Our implementation of Signomial objects allows Variables in the coefficient vector c. As a result, the map from gamma to f_mod.c is an affine function that takes in a Variable and returns an Expression. This makes it very simple to represent f_mod.c in C_{SAGE}(f_mod.alpha, X) via coniclifts Constraints.

sageopt.sig_constrained_relaxation(f, gts, eqs, form='dual', p=0, q=1, ell=0, X=None)

Construct a coniclifts Problem instance representing a level-(p, q, ell) SAGE relaxation for the signomial program

\[\begin{split}\begin{align*} \min\{ f(x) :~& g(x) \geq 0 \text{ for } g \in \text{gts}, \\ & g(x) = 0 \text{ for } g \in \text{eqs}, \\ & \text{and } x \in X \} \end{align*}\end{split}\]

where X = \(R^{\texttt{f.n}}\) by default. The optimal value of this relaxation will produce a lower bound on the minimization problem described above. When form='dual', a solution to this relaxation can be used to help recover optimal solutions to the problem described above.

Parameters

  • f (Signomial) – The objective function to be minimized.

  • gts (list of Signomials) – For every g in gts, there is a desired constraint that variables x satisfy g(x) >= 0.

  • eqs (list of Signomials) – For every g in eqs, there is a desired constraint that variables x satisfy g(x) == 0.

  • form (str) – Either form='primal' or form='dual'.

  • p (int) – Controls the complexity of Lagrange multipliers in the primal formulation, and (equivalently) constraints in the dual formulation. The smallest value is p=0, which corresponds to scalar Lagrange multipliers.

  • q (int) – The number of folds applied to the constraints gts and eqs. The smallest value is q=1, which means “leave gts and eqs as-is.”

  • ell (int) – Controls the complexity of any modulator applied to the Lagrangian in the primal formulation, and (equivalently) constraints in the dual formulation. The smallest value is ell=0, which means the primal Lagrangian must be a SAGE signomial.

  • X (dict) – If X is None, then this parameter is ignored. If X is a dict, then it must contain three fields: 'AbK', 'gts', and 'eqs'. For almost all applications, the appropriate dict X can be generated for you by calling conditional_sage_data(...).

Returns

prob

Return type

sageopt.coniclifts.Problem

Notes

The exact meaning of parameters p and q is determined by the function make_lagrangian(...)..

The meaning of the parameter ell is most clear from the implementation of sig_constrained_primal(...), although both sig_constrained_primal and sig_constrained_dual contain logic for handling this parameter.

sageopt.relaxations.sage_sigs.make_sig_lagrangian(f, gts, eqs, p, q)

Given a problem

\[\begin{split}\begin{align*} \min\{ f(x) :~& g(x) \geq 0 \text{ for } g \in \text{gts}, \\ & g(x) = 0 \text{ for } g \in \text{eqs}, \\ & \text{and } x \in X \} \end{align*}\end{split}\]

construct the q-fold constraints q-gts and q-eqs, and the Lagrangian

\[L = f - \gamma - \sum_{g \, \in \, \text{q-gts}} s_g \cdot g - \sum_{g \, \in \, \text{q-eqs}} z_g \cdot g\]

where \(\gamma\) and the coefficients on Signomials \(s_g\) and \(z_g\) are coniclifts Variables.

Parameters

  • f (Signomial) – The objective in a desired minimization problem.

  • gts (list of Signomials) – For every g in gts, there is a desired constraint that variables x satisfy g(x) >= 0.

  • eqs (list of Signomials) – For every g in eqs, there is a desired constraint that variables x satisfy g(x) == 0.

  • p (int) – Controls the complexity of s_g and z_g.

  • q (int) – The number of folds of constraints gts and eqs.

Returns

  • L (Signomial) – L.c is an affine expression of coniclifts Variables.

  • ineq_dual_sigs (a list of pairs of Signomial objects.) – If the pair (s1, s2) is in this list, then s1 is a generalized Lagrange multiplier to the constraint s2(x) >= 0.

  • eq_dual_sigs (a list of pairs of Signomial objects.) – If the pair (s1, s2) is in this list, then s1 is a generalized Lagrange multiplier to the constraint s2(x) == 0. This return value is not accessed for primal-form SAGE relaxations.

  • gamma (coniclifts.Variable.) – In primal-form SAGE relaxations, we want to maximize gamma. In dual form SAGE relaxations, gamma induces a normalizing equality constraint. This return value is not accessed for dual-form SAGE relaxations.

Notes

The values returned by this function are used to construct constrained SAGE relaxations. The basic primal SAGE relaxation is obtained by maximizing gamma, subject to the constraint that L and each s_g are SAGE functions. The dual SAGE relaxation is obtained by symbolically applying conic duality to the primal.

certificates of nonnegativity

sageopt.relaxations.sage_sigs.sage_feasibility(f, X=None, additional_cons=None)

Constructs a coniclifts maximization Problem which is feasible iff f admits an X-SAGE decomposition.

Parameters

  • f (Signomial) – We want to test if this function admits an X-SAGE decomposition.

  • X (dict) – If X is None, then we test nonnegativity of f over \(R^{\texttt{f.n}}\). If X is a dict, then it must contain three fields: 'AbK', 'gts', and 'eqs'. For almost all applications, the appropriate dict X can be generated for you by calling conditional_sage_data(...).

  • additional_cons (list of sageopt.coniclifts.Constraint) – This is mostly used for SAGE polynomials. When provided, it should be a list of Constraints over coniclifts Variables appearing in f.c.

Returns

prob – A coniclifts maximization Problem. If f admits an X-SAGE decomposition, then we should have prob.value > -np.inf, once prob.solve() has been called.

Return type

sageopt.coniclifts.Problem

Constructs a coniclifts maximization Problem which is feasible if f can be certified as nonnegative over X, by using an appropriate X-SAGE modulating function.

Parameters

  • f (Signomial) – We want to test if f is nonnegative over X.

  • level (int) – Controls the complexity of the X-SAGE modulating function. Must be a positive integer.

  • X (dict) – If X is None, then we test nonnegativity of f over \(R^{\texttt{f.n}}\). If X is a dict, then it must contain three fields: 'AbK', 'gts', and 'eqs'. For almost all applications, the appropriate dict X can be generated for you by calling conditional_sage_data(...).

Returns

prob

Return type

sageopt.coniclifts.Problem

Notes

This function provides an alternative to moving up the SAGE hierarchy, for the goal of certifying nonnegativity of a signomial f over some convex set X. In general, the approach is to introduce a signomial

mult = Signomial(alpha_hat, c_tilde)

where the rows of alpha_hat are all level-wise sums of rows from f.alpha, and c_tilde is a coniclifts Variable defining a nonzero X-SAGE function. Then we check if f_mod = f * mult is X-SAGE for any choice of c_tilde.

helper functions

sageopt.relaxations.sage_sigs.conditional_sage_data(f, gts, eqs)

Identify a subset of the constraints in gts and eqs which can be incorporated into conditional SAGE relaxations. Generate conic data that relaxation-constructors will need in downstream applications.

Parameters

  • f (Signomial) – The objective in a desired optimization problem. This parameter is only used to determine the dimension of the set defined by constraints in gts and eqs.

  • gts (list of Signomials) – For every g in gts, there is a desired constraint that variables x satisfy g(x) >= 0.

  • eqs (list of Signomial) – For every g in eqs, there is a desired constraint that variables x satisfy g(x) == 0.

Returns

X – X is keyed by three strings: 'AbK', 'gts', and 'eqs'.

X['gts'] is a list of Signomials so that every g in X['gts'] has an efficient convex representation of {x : g(x) >= 0}. The intersection of all of these sets is contained within {x : g(x) >= 0 for all g in gts}. X['eqs'] is defined similarly, but for equality constraints instead of inequality constraints. X['AbK'] is a conic representation of the feasible set cut out by X['gts'] and X['eqs']. The conic representation is a triple X['AbK'] = (A, b, K), where A is a SciPy sparse matrix, b is a numpy 1d array, and K is a list of coniclifts Cone objects. The number of columns for A in X['AbK'] will always be at least f.n. If the number of columns is greater than f.n, then the first f.n columns of A correspond to the variables over which f is defined. Any remaining columns are auxiliary variables needed to represent X in coniclifts primitives.

Return type

dict

Notes

This function essentially defines the requirements for X which may be passed to conditional SAGE relaxations defined in this python module.

If a user wants to define their own X without calling this function, that is doable. A possible use-case here is when X has a simple convex description, but not a simple description in terms of signomial inequality and equality constraints.

Suppose for example that we want X to represent the ell-2 unit ball in R^{f.n}. This can be accomplished as follows

import sageopt.coniclifts as cl
import numpy as np
x = cl.Variable(shape=(f.n,), name='x')
constraints = [1 >= cl.vector2norm(x)]
A, b, K, _, _ = cl.compile_constrained_system(constraints)
cl.clear_variable_indices()
my_gts = [lambda dummy_x: 1 - np.linalg.norm(dummy_x, ord=2)]
my_eqs = []
X = {'AbK': (A, b, K), 'gts': my_gts, 'eqs': my_eqs}

The message of this example is that X['gts'] and X['eqs'] don’t actually need to be lists of Signomials. They just need to be callable functions which define membership in X['AbK]. To really hit this home, functions in X['gts'] don’t even need to be continuous! For example, if you wanted to test membership in the ell-2 ball without allowing even the smallest constraint violation, you could use the function

my_gts = [lambda dummy_x: 1 if 1 >= np.linalg.norm(dummy_x, ord=2) else -np.inf]

and every important feature of sageopt’s signomial relaxations would work as expected.