Back to Search
Start Over
A hybrid discretization algorithm with guaranteed feasibility for the global solution of semi-infinite programs
- Source :
- Journal of Global Optimization. 68:227-253
- Publication Year :
- 2016
- Publisher :
- Springer Science and Business Media LLC, 2016.
-
Abstract
- A discretization-based algorithm for the global solution of semi-infinite programs (SIPs) is proposed, which is guaranteed to converge to a feasible, $$\varepsilon $$ΕΊ-optimal solution finitely under mild assumptions. The algorithm is based on the hybridization of two existing algorithms. The first algorithm (Mitsos in Optimization 60(10---11):1291---1308, 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):705---716, 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.
- Subjects :
- 0209 industrial biotechnology
Mathematical optimization
education.field_of_study
Binary search algorithm
021103 operations research
Control and Optimization
Discretization
Applied Mathematics
Population
0211 other engineering and technologies
02 engineering and technology
Management Science and Operations Research
Hybrid algorithm
Oracle
Computer Science Applications
020901 industrial engineering & automation
Test case
Convergence (routing)
education
Global optimization
Mathematics
Subjects
Details
- ISSN :
- 15732916 and 09255001
- Volume :
- 68
- Database :
- OpenAIRE
- Journal :
- Journal of Global Optimization
- Accession number :
- edsair.doi...........64901b5abbe2fcb6c4590b8748fc19ef