Global solution of semi-infinite programs

TitleGlobal solution of semi-infinite programs
Publication TypeJournal Article
Year of Publication2005
AuthorsBhattacharjee B, Lemonidis P, Green WH, Barton PI
JournalMathematical Programming

Optimization problems involving a finite number of decision variables and an infinite number of constraints are referred to as semi-infinite programs ({SIPs}). Existing numerical methods for solving nonlinear {SIPs} make strong assumptions on the properties of the feasible set, e.g., convexity and/or regularity, or solve a discretized approximation which only guarantees a lower bound to the true solution value of the {SIP}. Here, a general, deterministic algorithm for solving semi-infinite programs to guaranteed global optimality is presented. A branch-and-bound ({B&B}) framework is used to generate convergent sequences of upper and lower bounds on the SIP solution value. The upper-bounding problem is generated by replacing the infinite number of real-valued constraints with a finite number of constrained inclusion bounds; the lower-bounding problem is formulated as a convex relaxation of a discretized approximation to the {SIP}. The {SIP} {B&B} algorithm is shown to converge finitely to epsiv–optimality when the subdivision and discretization procedures used to formulate the node subproblems are known to retain certain convergence characteristics. Other than the properties assumed by globally-convergent {B&B} methods (for finitely-constrained {NLPs}), this {SIP} algorithm makes only one additional assumption: For every minimizer $x^\ast$ of the {SIP} there exists a sequence of {S}later points $x_n$ for which $łim_{n\rightarrowınfty}x_n=x^\ast$ and $q_{x_n}^1