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.SIPProblem
— Type SIPProblem
Structure storing problem information for the solution routine.
EAGO.SIPResult
— TypeSIPResult
Structure storing the results of the SIPRes
algorithm.
EAGO.SIPRes
— TypeSIPRes
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.
EAGO.SIPResRev
— TypeSIPResRev
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.
EAGO.SIPHybrid
— TypeSIPHybrid
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.
EAGO.get_sip_optimizer
— Functionget_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)
.
EAGO.build_model
— Functionbuild_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)
.
EAGO.sip_llp!
— Functionsip_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)
.
EAGO.sip_bnd!
— Functionsip_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)
.
EAGO.sip_res!
— Functionsip_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, ...)
.
EAGO.sip_solve
— Functionsip_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).
References
- Mitsos A (2009). Global optimization of semi-infinite programs via restriction of the right-hand side. Optimization, 60(10-11):1291-1308.
- 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.