Signomials¶
A signomial is a linear combination of exponentials, composed with linear functions. Signomials look like the following:
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 prebuilt functions for constructing and working with convex relaxations of signomial minimization problems (both constrained, and unconstrained). Those prebuilt 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 tuplesofnumbers to scalars. The keys will be converted to rows of a matrix which we callalpha
, and the values will be assembled into a vector which we callc
.If
alpha_maybe_c
is an ndarray, then the argumentc
must also be an ndarray, andc.size
must equal the number of rows inalpha_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 functionlambda 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 dictionaryalpha_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 vectorsa
. 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 propertyc
. Type
ndarray

c
¶ Has shape
(m,)
. The scalarc[i]
is this Signomial’s coefficient on the basis functionlambda x: exp(alpha[i, :] @ x)
. It is possible to havec.dtype == object
. Type
ndarray

alpha_c
¶ The keys of
alpha_c
are tuples of lengthn
, containing real numeric types (e.g int, float). These tuples define linear functions. This Signomial could be evaluated by the code snippetlambda 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
wheres2
is a numeric type or Signomial, but ifs2
is a Signomial, then its coefficient vectors2.c
can only contain one nonzero entry.You can also use
+
,
, and*
for pairs involving one Signomial and one nonSignomial. Ifs3
is the result of such an operation, thens3.c
will be an ndarray withs3.dtype == object
.Function evaluations.
Signomial objects are callable. If
s
is a Signomial object andx
is a numpy array of lengths.n
, thens(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 vectorc
as numpy arrays. So these fields are also maintained explicitly.If a user modifies the fields
alpha
orc
directly, there may be an inconsistency between these fields, and the dictionaryalpha_c
. Therefore the fieldsalpha
andc
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 haveself(x) == f(np.exp(x))
. Return type

constant_location
()¶ Return the index
i
so thatalpha[i, :]
is the zero vector.

property
grad
¶ A numpy ndarray of shape
(n,)
whose entries are Signomials. For a numpy ndarrayx
,grad[i](x)
is the partial derivative of this Signomial with respect to coordinatei
, evaluated atx
. 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 ndarrayx
,hess[i,j](x)
is the (i,j)th partial derivative of this Signomial, evaluated atx
. 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 toself.n  1
. Returns
p – The function obtained by differentiating this signomial with respect to its ith argument.
 Return type

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
, andalpha_c
to remove nonconstant terms wherec[i] == 0
.

signomials.
standard_sig_monomials
()¶ Return
y
wherey[i](x) = np.exp(x[i])
for every numericx
of lengthn
. 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
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
andeqs
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
andeqs
.gts (list of Signomials) – For every
g in gts
, there is a desired constraint that variablesx
satisfyg(x) >= 0
.eqs (list of Signomials) – For every
g in eqs
, there is a desired constraint that variablesx
satisfyg(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
 Returns
prob – A coniclifts Problem which represents the SAGE relaxation, with given parameters. The relaxation can be solved by calling
prob.solve()
. Return type
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
. Ifmod_supp
is not None, then the rows of this array define the exponents of a positive definite modulating Signomialt
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
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 “XSAGE”. 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 variablesx
satisfyg(x) >= 0
.eqs (list of Signomial) – For every
g in eqs
, there is a desired constraint that variablesx
satisfyg(x) == 0
.X (SigDomain) – If
X
is None, then we produce a bound onf
subject only to the constraints ingts
andeqs
.form (str) – Either
form='primal'
orform='dual'
.
 Returns
prob
 Return type
Notes
This function also accepts the following keyword arguments:
 pint
Controls the complexity of Lagrange multipliers on explicit signomial constraints
gts
andeqs
. Defaults top=0
, which corresponds to scalar Lagrange multipliers. qint
The lists
gts
andeqs
are replaced by lists of signomials formed by all products of<= q
elements fromgts
andeqs
respectively. Defaults toq = 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 XSAGE 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=1e08, eq_tol=1e06, 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 dualform 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 leastsquares 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=1e07, maxfun=10000.0)¶ Use SciPy’s COBYLA solver in an attempt to find a minimizer of
f
subject to inequality constraints ingts
and equality constraints ineqs
. Parameters
f (a callable function) – The minimization objective.
gts (a list of callable functions) – Each
g in gts
specifies an inequality constraintg(x) >= 0
.eqs (a list of callable functions) – Each
g in eqs
specifies an equality constraintg(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
andeqs
, which are lists of inequality constraints (g(x) >= 0
) and equality constraints (g(x) == 0
) respectively. The following code completes the example aboveimport 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
andgts
. 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 representX
. eqslist of callable
Equality constraint functions (
g(x) == 0
) which can be used to representX
. 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 firstn
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
andconiclifts_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
andself.eqs
atx_val
, to check ifx_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 byself
, up to infeasibility tolerancetol
. 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 qfold constraints
qgts
andqeqs
, by taking all products of<= q
elements fromgts
andeqs
respectively. Then form the Lagrangian\[L = f  \gamma  \sum_{g \, \in \, \mathtt{qgts}} s_g \cdot g  \sum_{g \, \in \, \mathtt{qeqs}} 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 variablesx
satisfyg(x) >= 0
.eqs (list of Signomials) – For every
g in eqs
, there is a desired constraint that variablesx
satisfyg(x) == 0
.p (int) – Controls the complexity of
s_g
andz_g
.q (int) – The number of folds of constraints
gts
andeqs
.
 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, thens_g
is a generalized Lagrange multiplier to the constraintg(x) >= 0
.eq_dual_sigs (a list of pairs of Signomial objects.) – If the pair
(z_g, g)
is in this list, thenz_g
is a generalized Lagrange multiplier to the constraintg(x) == 0
.gamma (coniclifts.Variable.) – In primalform SAGE relaxations, we want to maximize
gamma
. In dual form SAGE relaxations,gamma
induces an equality constraint.
Notes
The Lagrange multipliers
s_g
andz_g
share a common matrix of exponent vectors, which we callalpha_hat
.When
p = 0
,alpha_hat
consists of a single row, of all zeros. In this case,s_g
andz_g
are constant Signomials, and the coefficient vectorss_g.c
andz_g.c
are effectively scalars. Whenp > 0
, the rows ofalpha_hat
are set to allp
wise sums of exponent vectors appearing in eitherf
, or someg in gts
, or someg in eqs
.