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)\]

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

Signomial objects

This section covers how to construct and use instances of the sageopt.Signomial class.

class sageopt.Signomial(alpha, c)

A concrete representation for a function of the form \(x \mapsto \sum_{i=1}^m c_i \exp(\alpha_i \cdot x)\).

Operator overloading.

The operators +, -, and * are defined between pairs of Signomials, and pairs {s, t} where s is a Signomial and t is “scalar-like.” Specific examples of “scalar-like” objects include numeric types, and coniclifts Expressions of size one.

A Signomial s can be raised to a numeric power p by writing s**p; if s.c contains more than one nonzero entry, it can only be raised to nonnegative integer powers.

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

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 partial derivatives.

Parameters

  • alpha (ndarray) – The rows of alpha comprise this Signomial’s exponent vectors.

  • c (None or ndarray) – An ndarray of coefficients, with one coefficient for each row in alpha.

Examples

There are three ways to make Signomial objects. The first way is to call the constructor:

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.

You can also use Signomial.from_dict which maps exponent vectors (represented as tuples) to scalars:

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

The final way to construct a Signomial is with algebraic syntax, like:

y = sageopt.standard_sig_monomials(2)  # y[i] represents exp(x[i])
f = (y[0] - y[1]) ** 3 + 1 / y[0]  # a Signomial in two variables
x = np.array([1, 1])
print(f(x))  # np.exp(-1), up rounding errors.

Signomial objects are not limited to numeric problem data for alpha and c. In fact, it’s very common to have c contain a coniclifts Expression. For example, if we started with a Signomial f and then updated

gamma = sageopt.coniclifts.Variable()
f =  f - gamma

then f.c would be a coniclifts Expression depending on the variable gamma.

Notes

Signomial objects have a dictionary attribute called metadata. You can store any information you’d like in this dictionary. However, the information in this dictionary will not automatically be propogated when creating new Signomial objects (as happens when performing arithmetic on Signomials).

property n

The dimension of the space over which this Signomial is defined; this Signomial accepts inputs in \(\mathbb{R}^{n}\).

property m

The number of monomial basis functions \(x \mapsto \exp(a \cdot x)\) used by this Signomial.

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

property c

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

property 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]).

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.

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.

query_coeff(a)

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

constant_location()

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

without_zeros()

Return a Signomial which is symbolically equivalent to self, but which doesn’t track basis functions alpha[i,:] for which c[i] == 0.

grad_val(x)

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

hess_val(x)

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

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

static from_dict(d)

Construct a Signomial object which represents the function:

lambda x: np.sum([ d[a] * np.exp(a @ x) for a in d])
Parameters

d (Dict[Tuple[Float], Float]) –

Returns

s

Return type

Signomial

sageopt.standard_sig_monomials(n)

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

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 MCW2019. 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 convenience functions for 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 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.

Optimization with 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 = \(\mathbb{R}^{\texttt{f.n}}\) by default.

When form='dual', a solution to this convex relaxation can be used to recover optimal solutions to the problem above. Refer to the Notes for keyword arguments accepted by this function.

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

Optimization with arbitrary signomial 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 equations and inequalities. Such 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.

slacksbool

For dual relaxations, determines if constraints “mat @ vec in dual SAGE cone” is represented by “mat @ vec == temp, temp in dual SAGE cone”. Defaults to False.

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 for signomial optimization

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.

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.

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

suppfunc(y)

The support function of the convex set \(X\) associated with this SigDomain, evaluated at \(y\):

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

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