PolyJuMP.jl
PolyJuMP.jl is a JuMP extension for formulating and solving polynomial optimization problems. This extension includes the following:
- Polynomial functions on JuMP decisions variables. These can be solved with the
PolyJuMP.QCQP.Optimizer
orPolyJuMP.KKT.Optimizer
. - Constraints that a polynomial is nonnegative where the coefficients of the polynomials depend on JuMP decision variables. These nonnegativity constraints can be reformulated using sufficient conditions using
PolyJuMP.RelativeEntropy
submodule or SumOfSquares.jl.
License
PolyJuMP.jl
is licensed under the MIT license.
Installation
Install PolyJuMP
using Pkg.add
:
import Pkg
Pkg.add("PolyJuMP")
Use with JuMP
Polynomial nonnegativity constraints
PolyJuMP
allows encoding a constraint that a polynomial should be nonnegative for all values of some symbolic variables defined with DynamicPolynomials.@polyvar
or TypedPolynomials.@polyvar
as follows. For instance, the following constrains the JuMP decision variable a
to be such that a * x * y^2 + y^3 - a * x
is nonnegative for all real values of x
and y
:
using DynamicPolynomials
@polyvar x y
using JuMP
model = Model()
@variable(model, a)
@constraint(model, a * x * y^2 + y^3 >= a * x)
Determining the nonnegativity of a multivariate polynomial is however NP-hard so sufficient conditions are used instead. You need to specify which sufficient condition is used explicitly. To use Sum-of-Arithmetic-Geometric-Exponentials (SAGE), use
import PolyJuMP
PolyJuMP.setpolymodule!(model, PolyJuMP.SAGE)
To use Sum-of-Squares (SOS), use
import SumOfSquares
PolyJuMP.setpolymodule!(model, SumOfSquares)
or replace model = Model()
by model = SOSModel()
.
Alternatively, the nonnegativity constraint can be explicit:
@constraint(model, a * x * y^2 + y^3 - a * x in PolyJuMP.SAGE.Polynomials())
@constraint(model, a * x * y^2 + y^3 - a * x in SumOfSquares.SOSCone())
This allows mixing SAGE and SOS constraints in the same model.
Polynomial optimization
PolyJuMP also allows solving polynomial optimization problems using the QCQP
and KKT
solvers. Polynomial optimization problems do not involve any symbolic variables from DynamicPolynomials or TypedPolynomials, instead all variables are JuMP decision variables.
The QCQP
solver is parametrized by a nonconvex QCQP inner solver. It reformulates the polynomial optimization problem into a nonconvex QCQP
and relies on the inner solver to solve it. For instance, to use the QCQP
solver with JuMP with Gurobi.Optimizer
as inner solver, use:
using JuMP, PolyJuMP, Gurobi
model = Model(() -> PolyJuMP.QCQP.Optimizer(Gurobi.Optimizer))
The KKT
solver is parametrized by an inner solver of algebraic systems of equations implementing the SemialgebraicSets interface. It reformulates the polynomial optimization problem into a system of polynomial equations and relies on the inner solver to solve it. For instance, to use the QCQP
solver with JuMP with HomotopyContinuation.SemialgebraicSetsHCSolver
as inner solver, use:
using JuMP, PolyJuMP, HomotopyContinuation
model = Model(optimizer_with_attributes(
PolyJuMP.KKT.Optimizer,
"solver" => HomotopyContinuation.SemialgebraicSetsHCSolver(),
))
Documentation
Documentation for PolyJuMP.jl
is included in the documentation for SumOfSquares.jl.