GitHub

Solving Semi-Infinite Programs

Using EAGO to Solve a Semi-Infinite Program

This example is also provided here as a Jupyter Notebook.

Semi-infinite programming remains an active area of research. In general, the solutions of semi-infinite programs (SIPs) with nonconvex semi-infinite constraints of the following form are extremely challenging:

\[\begin{aligned} f^{*} = & \min_{\mathbf x \in X} f(\mathbf x) \\ {\rm s.t.} \; \; & g(\mathbf x, \mathbf p) \leq 0, \; \; \; \; \forall \mathbf p \in P \\ & \mathbf x \in X = \{ \mathbf x \in \mathbb R^{n_{x}} : \mathbf x^{L} \leq \mathbf x \leq \mathbf x^{U} \} \\ & P = \{ \mathbf p \in \mathbb R^{n_{p}} : \mathbf p^{L} \leq \mathbf p \leq \mathbf p^{U} \} \end{aligned}\]

EAGO implements three different algorithms detailed in [1, 2] to determine a globally optimal solution to problems of the above form. This is accomplished using the sip_solve function which returns the optimal value, the solution, and a boolean feasibility flag. To illustrate the use of this function, a simple example is presented here which solves the problem:

\[\begin{aligned} f(\mathbf x) & = \frac{1}{3} x_{1}^{2} + x_{2}^{2} + \frac{x_{1}}{2} \\ g(\mathbf x, p) & = (1 - x_{1}^{2} p^{2})^{2} - x_{1} p^{2} - x_{2}^{2} + x_{2} \leq 0 \\ & \mathbf x \in X = [-1000, 1000]^{2} \\ & p \in P = [0, 1] \end{aligned}\]

using EAGO, JuMP

# Define semi-infinite program
f(x) = (1/3)*x[1]^2 + x[2]^2 + x[1]/2
gSIP(x, p) = (1.0 - x[1]^2*p[1]^2)^2 - x[1]*p[1]^2 - x[2]^2 + x[2]

x_l = Float64[-1000.0, -1000.0]
x_u = Float64[1000.0, 1000.0]
p_l = Float64[0.0]
p_u = Float64[1.0]

sip_result = sip_solve(SIPRes(), x_l, x_u, p_l, p_u, f, Any[gSIP], res_sip_absolute_tolerance = 1E-3);

Semi-Infinite Solver

EAGO.SIPRes — Type
SIPRes

Specifies that the SIPRes algorithm which implements Algorithm #1 of Djelassi, Hatim, and Alexander Mitsos. "A hybrid discretization algorithm with guaranteed feasibility for the global solution of semi-infinite programs." Journal of Global Optimization 68.2 (2017): 227-253 should be used.

source
EAGO.SIPResRev — Type
SIPResRev

Specifies that the SIPResRev algorithm which implements Algorithm #1 of Djelassi, Hatim, and Alexander Mitsos. "A hybrid discretization algorithm with guaranteed feasibility for the global solution of semi-infinite programs." Journal of Global Optimization 68.2 (2017): 227-253 should be used.

source
EAGO.SIPHybrid — Type
SIPHybrid

Specifies that the SIPHybrid algorithm which implements Algorithm #2 of Djelassi, Hatim, and Alexander Mitsos. "A hybrid discretization algorithm with guaranteed feasibility for the global solution of semi-infinite programs." Journal of Global Optimization 68.2 (2017): 227-253 should be used.

source
EAGO.get_sip_optimizer — Function
get_sip_optimizer

Specifices the optimizer to be used in extension t::EAGO.ExtensionType with algorithm alg::AbstractSIPAlgo in subproblem s::AbstractSubproblemType via the command get_sip_optimizer(t::ExtensionType, alg::AbstractSIPAlgo, s::AbstractSubproblemType).

source
EAGO.build_model — Function
build_model

Create the model and variables used with extension t::EAGO.ExtensionType in algorithm a::AbstractSIPAlgo in subproblem s::AbstractSubproblemType via the command build_model(t::ExtensionType, a::AbstractSIPAlgo, s::AbstractSubproblemType, p::SIPProblem).

source
EAGO.sip_llp! — Function
sip_llp!

Solves the lower level problem for the ith-SIP used with extension t::EAGO.ExtensionType in algorithm a::AbstractSIPAlgo in subproblem s::AbstractSubproblemType via the command sip_llp!(t::ExtensionType, a::AbstractSIPAlgo, s::AbstractSubproblemType, ..., i, tol).

source
EAGO.sip_bnd! — Function
sip_bnd!

Solves the bounding problem for the ith-SIP used with extension t::EAGO.ExtensionType in algorithm a::AbstractSIPAlgo in subproblem s::AbstractSubproblemType via the command sip_bnd!(t::ExtensionType, a::AbstractSIPAlgo, s::AbstractSubproblemType, ..., i, tol).

source
EAGO.sip_res! — Function
sip_res!

Solves the restriction problem for extension t::EAGO.ExtensionType in algorithm a::AbstractSIPAlgo in subproblem s::AbstractSubproblemType via the command sip_res!(t::ExtensionType, a::AbstractSIPAlgo, ...).

source
EAGO.sip_solve — Function
sip_solve

Solve an SIP with decision variable bounds x_l to x_u, uncertain variable bounds p_l to p_u, an objective function of f, and gSIP seminfiniite constraint(s).

source

References

  1. Mitsos A (2009). Global optimization of semi-infinite programs via restriction of the right-hand side. Optimization, 60(10-11):1291-1308.
  2. Djelassi, Hatim, and Alexander Mitsos. A hybrid discretization algorithm with guaranteed feasibility for the global solution of semi-infinite programs. Journal of Global Optimization, 68.2 (2017): 227-253 should be used.