The cluster problem in constrained global optimization
Deterministic branch-and-bound algorithms for continuous global optimization often visit a large number of boxes in the neighborhood of a global minimizer, resulting in the so-called cluster problem (Du and Kearfott in J Glob Optim 5(3):253–265, 1994). This article extends previous analyses of the c...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Springer-Verlag
2018
|
| Online Access: | http://hdl.handle.net/1721.1/116364 https://orcid.org/0000-0003-2895-9443 https://orcid.org/0000-0002-7963-7682 |
| _version_ | 1826218013839327232 |
|---|---|
| author | Barton, Paul I Kannan, Rohit |
| author2 | Massachusetts Institute of Technology. Department of Chemical Engineering |
| author_facet | Massachusetts Institute of Technology. Department of Chemical Engineering Barton, Paul I Kannan, Rohit |
| author_sort | Barton, Paul I |
| collection | MIT |
| description | Deterministic branch-and-bound algorithms for continuous global optimization often visit a large number of boxes in the neighborhood of a global minimizer, resulting in the so-called cluster problem (Du and Kearfott in J Glob Optim 5(3):253–265, 1994). This article extends previous analyses of the cluster problem in unconstrained global optimization (Du and Kearfott 1994; Wechsung et al. in J Glob Optim 58(3):429–438, 2014) to the constrained setting based on a recently-developed notion of convergence order for convex relaxation-based lower bounding schemes. It is shown that clustering can occur both on nearly-optimal and nearly-feasible regions in the vicinity of a global minimizer. In contrast to the case of unconstrained optimization, where at least second-order convergent schemes of relaxations are required to mitigate the cluster problem when the minimizer sits at a point of differentiability of the objective function, it is shown that first-order convergent lower bounding schemes for constrained problems may mitigate the cluster problem under certain conditions. Additionally, conditions under which second-order convergent lower bounding schemes are sufficient to mitigate the cluster problem around a global minimizer are developed. Conditions on the convergence order prefactor that are sufficient to altogether eliminate the cluster problem are also provided. This analysis reduces to previous analyses of the cluster problem for unconstrained optimization under suitable assumptions. |
| first_indexed | 2024-09-23T17:12:46Z |
| format | Article |
| id | mit-1721.1/116364 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T17:12:46Z |
| publishDate | 2018 |
| publisher | Springer-Verlag |
| record_format | dspace |
| spelling | mit-1721.1/1163642022-09-30T00:29:15Z The cluster problem in constrained global optimization Barton, Paul I Kannan, Rohit Massachusetts Institute of Technology. Department of Chemical Engineering Barton, Paul I Kannan, Rohit Deterministic branch-and-bound algorithms for continuous global optimization often visit a large number of boxes in the neighborhood of a global minimizer, resulting in the so-called cluster problem (Du and Kearfott in J Glob Optim 5(3):253–265, 1994). This article extends previous analyses of the cluster problem in unconstrained global optimization (Du and Kearfott 1994; Wechsung et al. in J Glob Optim 58(3):429–438, 2014) to the constrained setting based on a recently-developed notion of convergence order for convex relaxation-based lower bounding schemes. It is shown that clustering can occur both on nearly-optimal and nearly-feasible regions in the vicinity of a global minimizer. In contrast to the case of unconstrained optimization, where at least second-order convergent schemes of relaxations are required to mitigate the cluster problem when the minimizer sits at a point of differentiability of the objective function, it is shown that first-order convergent lower bounding schemes for constrained problems may mitigate the cluster problem under certain conditions. Additionally, conditions under which second-order convergent lower bounding schemes are sufficient to mitigate the cluster problem around a global minimizer are developed. Conditions on the convergence order prefactor that are sufficient to altogether eliminate the cluster problem are also provided. This analysis reduces to previous analyses of the cluster problem for unconstrained optimization under suitable assumptions. BP (Firm) 2018-06-18T17:30:48Z 2018-06-18T17:30:48Z 2017-05 2016-06 2017-11-18T05:57:01Z Article http://purl.org/eprint/type/JournalArticle 0925-5001 1573-2916 http://hdl.handle.net/1721.1/116364 Kannan, Rohit, and Paul I. Barton. “The Cluster Problem in Constrained Global Optimization.” Journal of Global Optimization 69, no. 3 (May 11, 2017): 629–676. https://orcid.org/0000-0003-2895-9443 https://orcid.org/0000-0002-7963-7682 en http://dx.doi.org/10.1007/s10898-017-0531-z Journal of Global Optimization Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ Springer Science+Business Media New York application/pdf Springer-Verlag Springer US |
| spellingShingle | Barton, Paul I Kannan, Rohit The cluster problem in constrained global optimization |
| title | The cluster problem in constrained global optimization |
| title_full | The cluster problem in constrained global optimization |
| title_fullStr | The cluster problem in constrained global optimization |
| title_full_unstemmed | The cluster problem in constrained global optimization |
| title_short | The cluster problem in constrained global optimization |
| title_sort | cluster problem in constrained global optimization |
| url | http://hdl.handle.net/1721.1/116364 https://orcid.org/0000-0003-2895-9443 https://orcid.org/0000-0002-7963-7682 |
| work_keys_str_mv | AT bartonpauli theclusterprobleminconstrainedglobaloptimization AT kannanrohit theclusterprobleminconstrainedglobaloptimization AT bartonpauli clusterprobleminconstrainedglobaloptimization AT kannanrohit clusterprobleminconstrainedglobaloptimization |