Signomials

A signomial is a linear combination of exponentials, composed with linear functions. Signomials look like the following:

\[x \mapsto \sum_{i=1}^m c_i \exp({\alpha}_i \cdot x)\]

The section “signomial objects” covers sageopt’s Signomial class, plus one extra helper function. The section on conditioning covers the basics of a powerful connection between signomials and convexity. Sageopt has pre-built functions for constructing and working with convex relaxations of signomial minimization problems (both constrained, and unconstrained). Those pre-built functions are described in the section on optimization. We also address some advanced topics.

signomial objects

Here we cover the sageopt.Signomial class, and the helper function sageopt.standard_sig_monomials(). The helper function is very convenient for constructing Signomial objects; you might even use it more than the Signomial constructor itself. Nevertheless, it is a good idea to review the Signomial class first.

class sageopt.Signomial(alpha_maybe_c, c=None)

A symbolic representation for linear combinations of exponentials, composed with linear functions. The constructor for this class can be called in two different ways, and the arguments to the constructor have names which reflect the different possibilities. Refer to the Examples if you find the description of the constructor arguments unclear.

Parameters
  • alpha_maybe_c (dict or ndarray) –

    If alpha_maybe_c is a dict, then it must be a dictionary from tuples-of-numbers to scalars. The keys will be converted to rows of a matrix which we call alpha, and the values will be assembled into a vector which we call c.

    If alpha_maybe_c is an ndarray, then the argument c must also be an ndarray, and c.size must equal the number of rows in alpha_maybe_c.

  • c (None or ndarray) – This value is only used when alpha_maybe_c is an ndarray. If that is the case, then this Signomial will represent the function lambda x: c @ np.exp(alpha_maybe_c @ x).

Examples

There are two ways to call the Signomial constructor.

The first way is to specify a dictionary from tuples to scalars. The tuples are interpreted as linear functionals appearing in the exponential terms, and the scalars are the corresponding coefficients.:

alpha_and_c = {(1,): 2}
f = Signomial(alpha_and_c)
print(f(1))  # equal to 2 * np.exp(1).
print(f(0))  # equal to 2.

The second way is to specify two arguments. In this case the first argument is an ndarray where the rows represent linear functionals, and the second argument is a vector of corresponding coefficients.:

alpha = np.array([[1, 0], [0, 1], [1, 1]])
c = np.array([1, 2, 3])
f = Signomial(alpha, c)
x = np.random.randn(2)
print(f(x) - c @ np.exp(alpha @ x))  # zero, up to rounding errors.
n

The dimension of the space over which this Signomial is defined. The number of columns in alpha, and the length of tuples appearing in the dictionary alpha_c.

Type

int

m

The number of terms needed to express this Signomial in a basis of monomial functions lambda x: exp(a @ x) for row vectors a. The signomial is presumed to include a constant term.

Type

int

alpha

Has shape (m, n). Each row specifies a vector appearing in an exponential function which defines this Signomial. The rows are ordered for consistency with the property c.

Type

ndarray

c

Has shape (m,). The scalar c[i] is this Signomial’s coefficient on the basis function lambda x: exp(alpha[i, :] @ x). It is possible to have c.dtype == object.

Type

ndarray

alpha_c

The keys of alpha_c are tuples of length n, containing real numeric types (e.g int, float). These tuples define linear functions. This Signomial could be evaluated by the code snippet lambda x: np.sum([ alpha_c[a] * np.exp(a @ x) for a in alpha_c]). The default value for this dictionary is zero.

Type

defaultdict

Notes

Operator overloading.

The Signomial class implements +, -, *, and ** between pairs of Signomials, and pairs involving one Signomial and one numeric type.

The Signomial class also implements s1 / s2 where s2 is a numeric type or Signomial, but if s2 is a Signomial, then its coefficient vector s2.c can only contain one nonzero entry.

You can also use +, -, and * for pairs involving one Signomial and one non-Signomial. If s3 is the result of such an operation, then s3.c will be an ndarray with s3.dtype == object.

Function evaluations.

Signomial objects are callable. If s is a Signomial object and x is a numpy array of length s.n, then s(x) computes the Signomial object as though it were any other elementary Python function.

Signomial objects provide functions to compute gradients (equivalently, Jacobians) and Hessians. These methods operate by caching and evaluating symbolic representations of the relevant partial derivatives.

Internal representations.

Both self.alpha_c and (self.alpha, self.c) completely specify a Signomial object.

alpha_c is the dictionary which is taken to define this Signomial as a mathematical object.

However, it is useful to have rapid access to the matrix of linear functionals alpha, or the coefficient vector c as numpy arrays. So these fields are also maintained explicitly.

If a user modifies the fields alpha or c directly, there may be an inconsistency between these fields, and the dictionary alpha_c. Therefore the fields alpha and c should not be modified without taking great care to ensure consistency with the signomial’s dictionary representation.

as_polynomial()

This function is only applicable if alpha is a matrix of nonnegative integers.

Returns

f – For every vector x, we have self(x) == f(np.exp(x)).

Return type

Polynomial

constant_location()

Return the index i so that alpha[i, :] is the zero vector.

property grad

A numpy ndarray of shape (n,) whose entries are Signomials. For a numpy ndarray x, grad[i](x) is the partial derivative of this Signomial with respect to coordinate i, evaluated at x. This array is constructed only when necessary, and is cached upon construction.

grad_val(x)

Return the gradient of this Signomial (as an ndarray) at the point x.

property hess

A numpy ndarray of shape (n, n), whose entries are Signomials. For a numpy ndarray x, hess[i,j](x) is the (i,j)-th partial derivative of this Signomial, evaluated at x. This array is constructed only when necessary, and is cached upon construction.

hess_val(x)

Return the Hessian of this Signomial (as an ndarray) at the point x.

partial(i)

Compute the symbolic partial derivative of this signomial, at coordinate i.

Parameters

i (int) – i must be an integer from 0 to self.n - 1.

Returns

p – The function obtained by differentiating this signomial with respect to its i-th argument.

Return type

Signomial

query_coeff(a)

Returns the coefficient of the basis function lambda x: np.exp(a @ x) for this Signomial.

remove_terms_with_zero_as_coefficient()

Update alpha, c, and alpha_c to remove nonconstant terms where c[i] == 0.

signomials.standard_sig_monomials()

Return y where y[i](x) = np.exp(x[i]) for every numeric x of length n.

Parameters

n (int) – The signomials will be defined on \(R^n\).

Returns

y – An array of length n, containing Signomial objects.

Return type

ndarray

Example

This function is useful for constructing signomials in an algebraic form.

y = standard_sig_monomials(3)
f = (y[0] ** 1.5) * (y[2] ** -0.6) - y[1] * y[2]

conditioning

The primary contribution of MCW2019 was to show that convex sets have a special place in the theory of SAGE relaxations. In particular, SAGE can incorporate convex constraints into a problem by a lossless process known as partial dualization. You can think of partial dualization as a type of “conditioning”, in the sense of conditional probability.

We designed sageopt so users can leverage the full power of partial dualization without being experts on the subject. If you want to optimize a signomial over the set

\[\Omega = \{ x \,:\, g(x) \geq 0 \text{ for }g \in \mathtt{gts}, ~~ \phi(x)=0 \text{ for } \phi \in \mathtt{eqs}\}\]

then you just need to focus on constructing the lists of signomials gts and eqs. Once these lists are constructed, you can call the following function to obtain a convex set \(X \supset \Omega\) which is implied by the constraint signomials.

sageopt.relaxations.sage_sigs.infer_domain(f, gts, eqs, check_feas=True)

Identify a subset of the constraints in gts and eqs which can be incorporated into conditional SAGE relaxations for signomials. Construct a SigDomain object from the inferred constraints.

Parameters
  • f (Signomial) – The objective in a desired SAGE relaxation. 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 Signomials) – For every g in eqs, there is a desired constraint that variables x satisfy g(x) == 0.

  • check_feas (bool) – Indicates whether or not to verify that the returned SigDomain is nonempty.

Returns

X

Return type

SigDomain or None

It is possible that the function above cannot capture a convex set of interest. This is particularly likely if the desired convex set is not naturally described by signomials. If your find yourself in this situation, refer to the advanced topics section.

optimization

Here are sageopt’s core functions which can assist with signomial optimization:

We assume the user has already read the section on signomial conditioning. Newcomers to sageopt might benefit from reading this section in one browser window, and keeping our page of Examples open in an adjacent window. It might also be useful to have a copy of MCW2019 at hand, since that article is referenced throughout this section.

A remark: The functions described here are largely reference implementations. Depending on the specifics of your problem, it may be beneficial to implement variants of these functions by directly working with sageopt’s backend: coniclifts.

convex constraints

sageopt.sig_relaxation(f, X=None, form='dual', **kwargs)

Construct a coniclifts Problem instance for producing a lower bound on

\[f_X^{\star} \doteq \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.

  • X (SigDomain) – If X is None, then we produce a bound on f over \(R^{\texttt{f.n}}\).

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

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

This function also accepts the following keyword arguments:

ellint

The level of the SAGE hierarchy. Must be nonnegative.

mod_suppNumPy ndarray

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 t in the SAGE hierarchy.

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

\[\begin{split}\begin{align*} \mathrm{maximize} &~ \gamma \\ \text{subject to} &~ \mathtt{f{\_}mod} := t^\ell \cdot (f - \gamma), \text{ and} \\ &~ \mathtt{f{\_}mod.c} \in C_{\mathrm{SAGE}}(\mathtt{f{\_}mod.alpha}, X) \end{align*}\end{split}\]

The rationale behind this formation is simple: the minimum value of a function \(f\) over a set \(X\) is equal to the largest number \(\gamma\) where \(f - \gamma\) is nonnegative over \(X\). The SAGE constraint in the problem is a proof that \(f - \gamma\) is nonnegative over \(X\). However the SAGE constraint may be too restrictive, in that it’s possible that \(f - \gamma\) is nonnegative on \(X\), but not “X-SAGE”. Increasing \(\ell\) expands the set of functions which SAGE can prove as nonnegative, and thereby improve the quality the bound produced on \(f_X^\star\). The improved bound comes at the expense of solving a larger optimization problem. For more discussion, refer to Section 2.3 of MCW2019.

arbitrary constraints

The next function allows the user to specify their problem not only with convex constraints via a set “\(X\)”, but also with explicit signomial inequality constraints and equality constraints. Such explicit signomial constraints are necessary when the feasible set is nonconvex, although they can be useful in other contexts.

sageopt.sig_constrained_relaxation(f, gts, eqs, X=None, form='dual', **kwargs)

Construct a coniclifts Problem representing a SAGE relaxation for the signomial program

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

where X = \(R^{\texttt{f.n}}\) by default. When form='dual', a solution to this relaxation can be used to help recover optimal solutions to the problem described above. Refer to the Notes for keyword arguments accepted by this function.

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

  • gts (list of Signomial) – 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.

  • X (SigDomain) – If X is None, then we produce a bound on f subject only to the constraints in gts and eqs.

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

Returns

prob

Return type

sageopt.coniclifts.Problem

Notes

This function also accepts the following keyword arguments:

pint

Controls the complexity of Lagrange multipliers on explicit signomial constraints gts and eqs. Defaults to p=0, which corresponds to scalar Lagrange multipliers.

qint

The lists gts and eqs are replaced by lists of signomials formed by all products of <= q elements from gts and eqs respectively. Defaults to q = 1.

ellint

Controls the strength of the SAGE proof system, as applied to the Lagrangian. Defaults to ell=0, which means the primal Lagrangian must be an X-SAGE signomial.

For further explanation of the parameters p, q, and ell in the function above, we refer the user to the advanced topics section.

solution recovery

Section 3.2 of MCW2019 introduces two solution recovery algorithms for dual SAGE relaxations. The main algorithm (“Algorithm 1”) is implemented by sageopt’s function sig_solrec, and the second algorithm (“Algorithm 1L”) is simply to use a local solver to refine the solution produced by the main algorithm. The exact choice of local solver is not terribly important. For completeness, sageopt includes a local_refine function which relies on the COBYLA solver, as described in MCW2019.

sageopt.sig_solrec(prob, ineq_tol=1e-08, eq_tol=1e-06, skip_ls=False)

Recover a list of candidate solutions from a dual SAGE relaxation. Solutions are guaranteed to be feasible up to specified tolerances, but not necessarily optimal.

Parameters
  • prob (coniclifts.Problem) – A dual-form SAGE relaxation.

  • ineq_tol (float) – The amount by which recovered solutions can violate inequality constraints.

  • eq_tol (float) – The amount by which recovered solutions can violate equality constraints.

  • skip_ls (bool) – Whether or not to skip constrained least-squares solution recovery.

Returns

sols – A list of feasible solutions, sorted in increasing order of objective function value. It is possible that this list is empty, in which case no feasible solutions were recovered.

Return type

list of ndarrays

sig_solrec actually implements a slight generalization of “Algorithm 1” from MCW2019. The generalization is used to improve performance in more complex SAGE relaxations, such as those from sig_constrained_relaxation with ell > 0.

Users can replicate “Algorithm 1L” from MCW2019 by running sig_solrec, and then applying the following function to its output.

sageopt.local_refine(f, gts, eqs, x0, rhobeg=1, rhoend=1e-07, maxfun=10000.0)

Use SciPy’s COBYLA solver in an attempt to find a minimizer of f subject to inequality constraints in gts and equality constraints in eqs.

Parameters
  • f (a callable function) – The minimization objective.

  • gts (a list of callable functions) – Each g in gts specifies an inequality constraint g(x) >= 0.

  • eqs (a list of callable functions) – Each g in eqs specifies an equality constraint g(x) == 0.

  • x0 (ndarray) – An initial point for COBYLA.

  • rhobeg (float) – Controls the size of COBYLA’s initial search space.

  • rhoend (float) – Termination criteria, controlling the size of COBYLA’s smallest search space.

  • maxfun (int) – Termination criteria, bounding the number of COBYLA’s iterations.

Returns

x – The solution returned by COBYLA.

Return type

ndarray

advanced topics

SigDomain objects

class sageopt.SigDomain(n, **kwargs)

Represent a convex set \(X \subset R^n\), for use in signomial conditional SAGE relaxations.

Parameters

n (int) – The dimension of the space in which this set lives.

Example

Suppose you want to represent the \(\ell_2\) unit ball in \(R^{5}\). This can be done as follows,

import sageopt as so
import sageopt.coniclifts as cl
x_var = cl.Variable(shape=(5,), name='temp')
cons = [cl.vector2norm(x_var) <= 1]
X = so.SigDomain(5)
X.parse_coniclifts_constraints(cons)

As written, that SigDomain cannot be used for solution recovery from SAGE relaxations. To fully specify a SigDomain, you need to set attributes gts and eqs, which are lists of inequality constraints (g(x) >= 0) and equality constraints (g(x) == 0) respectively. The following code completes the example above

import numpy as np
my_gts = [lambda dummy_x: 1 - np.linalg.norm(dummy_x, ord=2)]
X.gts = my_gts
X.eqs = []

This class does not check for correctness of eqs and gts. It is up to the user to ensure these values represent this SigDomain in the intended way.

Notes

The constructor accepts the following keyword arguments:

coniclifts_cons: list of coniclifts.constraints.Constraint

Constraints over a single coniclifts Variable, which define this SigDomain.

gtslist of callable

Inequality constraint functions (g(x) >= 0) which can be used to represent X.

eqslist of callable

Equality constraint functions (g(x) == 0) which can be used to represent X.

check_feasbool

Whether or not to check that X is nonempty. Defaults to True.

AbKtuple

Specify a convex set in the coniclifts standard. AbK[0] is a SciPy sparse matrix. The first n columns of this matrix correspond to the variables over which this set is supposed to be defined. Any remaining columns are for auxiliary variables.

Only one of AbK and coniclifts_cons can be provided upon construction. If more than one of these value is provided, the constructor will raise an error.

check_membership(x_val, tol)

Evaluate self.gts and self.eqs at x_val, to check if x_val belongs to this SigDomain.

Parameters
  • x_val (ndarray) – Check if x_val belongs in this domain.

  • tol (float) – Infeasibility tolerance.

Returns

res – True iff x_val belongs in the domain represented by self, up to infeasibility tolerance tol.

Return type

bool

parse_coniclifts_constraints(constraints)

Modify this SigDomain object, so that it represents the set of values which satisfy the provided constraints.

Parameters

constraints (list of coniclifts.Constraint) – The provided constraints must be defined over a single coniclifts Variable.

hierarchy parameters

Here we describe the precise meanings of parameters p and ell in sig_constrained_relaxation. In primal form, sig_constrained_relaxation operates by moving explicit signomial constraints into a Lagrangian, and attempting to certify the Lagrangian as nonnegative over X; this is a standard combination of the concepts reviewed in Section 2 of MCW2019. Parameter ell is essentially the same as in sig_relaxation: to improve the strength of the SAGE proof system, modulate the Lagrangian L - gamma by powers of the signomial t = Signomial(L.alpha, np.ones(L.m)). Parameters p and q affect the unmodulated Lagrangian seen by sig_constrained_relaxation; this unmodulated Lagrangian is constructed with the following function.

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 \mathtt{gts}, \\ & g(x) = 0 \text{ for } g \in \mathtt{eqs}, \\ & \text{and } x \in X \} \end{align*}\end{split}\]

construct the q-fold constraints q-gts and q-eqs, by taking all products of <= q elements from gts and eqs respectively. Then form the Lagrangian

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

where \(\gamma\) is a coniclifts Variable of dimension 1, and the coefficients on Signomials \(s_g\) and \(z_g\) are coniclifts Variables of a dimension determined by p.

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 (s_g, g) is in this list, then s_g is a generalized Lagrange multiplier to the constraint g(x) >= 0.

  • eq_dual_sigs (a list of pairs of Signomial objects.) – If the pair (z_g, g) is in this list, then z_g is a generalized Lagrange multiplier to the constraint g(x) == 0.

  • gamma (coniclifts.Variable.) – In primal-form SAGE relaxations, we want to maximize gamma. In dual form SAGE relaxations, gamma induces an equality constraint.

Notes

The Lagrange multipliers s_g and z_g share a common matrix of exponent vectors, which we call alpha_hat.

When p = 0, alpha_hat consists of a single row, of all zeros. In this case, s_g and z_g are constant Signomials, and the coefficient vectors s_g.c and z_g.c are effectively scalars. When p > 0, the rows of alpha_hat are set to all p-wise sums of exponent vectors appearing in either f, or some g in gts, or some g in eqs.