Working with SAGE polynomials.

optimization

sageopt.poly_relaxation(f, form='dual', poly_ell=0, sigrep_ell=0, X=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 (Polynomial) – The objective function to be minimized.

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

  • poly_ell (int) – Controls the complexity of a polynomial modulating function. Must be nonnegative.

  • sigrep_ell (int) – Controls the complexity of the SAGE certificate applied to the Lagrangian’s signomial representative.

  • 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: 'log_AbK', 'gts', and 'eqs'. For most situations, the appropriate dict X can be generated with conditional_sage_data(...).

Returns

prob

Return type

sageopt.coniclifts.Problem

sageopt.poly_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 polynomial optimization 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}\]

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 (Polynomial) – The objective to be minimized.

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

  • eqs (list of Polynomials) – 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 polynomial.

  • X (dict) – If not-None, then X must be dictionary with three keys 'log_AbK', 'gts', 'eqs' such as that generated by the function conditional_sage_data(...).

Returns

prob

Return type

sageopt.coniclifts.Problem

sageopt.relaxations.sage_polys.make_poly_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 Polynomials \(s_g\) and \(z_g\) are coniclifts Variables.

Parameters

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

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

  • eqs (list of Polynomials) – 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 (Polynomial) – L.c is an affine expression of coniclifts Variables.

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

  • eq_dual_polys (a list of pairs of Polynomials.) – 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 polynomials. The dual SAGE relaxation is obtained by symbolically applying conic duality to the primal.

certificates of nonnegativity

sageopt.relaxations.sage_polys.sage_feasibility(f, X=None)

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

Parameters

  • f (Polynomial) – 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: 'log_AbK', 'gts', and 'eqs'. For almost all applications, the appropriate dict X can be generated for you by calling conditional_sage_data(...).

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 (Polynomial) – 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: 'log_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 polynomial f over some set X where |X| is log-log convex. In general, the approach is to introduce a polynomial

mult = Polynomial(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 SAGE polynomial. Then we can check if f_mod = f * mult is SAGE for any choice of c_tilde.

helper functions

sageopt.relaxations.sage_polys.conditional_sage_data(f, gts, eqs)
Parameters

  • f (Polynomial) – 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 Polynomials) – For every g in gts, there is a desired constraint that variables x satisfy g(x) >= 0.

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

Returns

X – X will be keyed by three strings: 'log_AbK', 'gts', and 'eqs'.

X['gts'] is a list of Polynomials so that every g in X['gts'] has an efficient convex representation for {log(|x|) : g(|x|) >= 0, |x| > 0}. (Where the vertical bars denote elementwise absolute value, and the logarithm is meant elementwise.) The intersection of all of these sets is contained within

{log(|x|) : g(|x|) >= 0 for all g in gts, |x| > 0}.

X['eqs'] is defined similarly, but for equality constraints.

If both X['gts'] and X['eqs'] are empty, then X['log_AbK'] is None. Otherwise, X['log_AbK'] is a conic representation of the pointwise, elementwise log-absolute-values of the feasible sets cut out by X['gts'] and X['eqs']. The conic representation is a triple X['log_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 (in order!) to the log-absolute-values of 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 polynomial relaxations defined in this python module.

It is possible for a user to properly define their own dict X without calling this function. The only benefit to such an approach is that X['gts'] and X['eqs'] don’t need to be Polynomial objects. As long as X['gts'] and X['eqs'] are callable python functions and relate to X['log_AbK'] in the manner described above, then you should be able to pass that dict to SAGE relaxations defined in this module without trouble. Bear in mind that the functions in X['gts'] and X['eqs'] will only be passed elementwise-positive arguments.