Optimization Online


A Hybrid Discretization Algorithm with Guaranteed Feasibility for the Global Solution of Semi-Infinite Programs

Hatim Djelassi (hatim.djelassi***at***avt.rwth-aachen.de)
Alexander Mitsos (alexander.mitsos***at***avt.rwth-aachen.de)

Abstract: A discretization-based algorithm for the global solution of semi-infinite programs (SIPs) is proposed, which is guaranteed to converge to a feasible, ε-optimal solution finitely under mild assumptions. The algorithm is based on the hybridization of two existing algorithms. The first algorithm (Mitsos in Optimization 60(1011):12911308, 2011) is based on a restriction of the right-hand side of the constraints of a discretized SIP. The second algorithm (Tsoukalas and Rustem in Optim Lett 5(4):705716, 2011) employs a discretized oracle problem and a binary search in the objective space. Hybridization of the approaches yields an algorithm, which leverages the strong convergence guarantees and the relatively tight upper bounding problem of the first approach while employing an oracle problem adapted from the second approach to generate cheap lower bounds and adaptive updates to the restriction of the first approach. These adaptive updates help in avoiding a dense population of the discretization. The hybrid algorithm is shown to be superior to its predecessors both theoretically and computationally. A proof of finite convergence is provided under weaker assumptions than the assumptions in the references. Numerical results from established SIP test cases are presented.

Keywords: SIP; NLP; nonconvex; feasible point method; global optimization

Category 1: Infinite Dimensional Optimization (Semi-infinite Programming )

Citation: Djelassi, H. & Mitsos, A. J Glob Optim (2016). doi:10.1007/s10898-016-0476-7


Entry Submitted: 04/04/2016
Entry Accepted: 04/04/2016
Entry Last Modified: 11/04/2016

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society