McCormick-Based Relaxations of Algorithms
Theory and implementation for the global optimization of a wide class of algorithms is presented via convex/affine relaxations. The basis for the proposed relaxations is the systematic construction of subgradients for the convex relaxations of factorable functions by McCormick [Math. Prog., 10 (1976...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Society for Industrial and Applied Mathematics
2010
|
| Online Access: | http://hdl.handle.net/1721.1/52407 https://orcid.org/0000-0003-2895-9443 |
| _version_ | 1826190533144346624 |
|---|---|
| author | Mitsos, Alexander Chachuat, Benoit Barton, Paul I. |
| author2 | Massachusetts Institute of Technology. Department of Chemical Engineering |
| author_facet | Massachusetts Institute of Technology. Department of Chemical Engineering Mitsos, Alexander Chachuat, Benoit Barton, Paul I. |
| author_sort | Mitsos, Alexander |
| collection | MIT |
| description | Theory and implementation for the global optimization of a wide class of algorithms is presented via convex/affine relaxations. The basis for the proposed relaxations is the systematic construction of subgradients for the convex relaxations of factorable functions by McCormick [Math. Prog., 10 (1976), pp. 147–175]. Similar to the convex relaxation, the subgradient propagation relies on the recursive application of a few rules, namely, the calculation of subgradients for addition, multiplication, and composition operations. Subgradients at interior points can be calculated for any factorable function for which a McCormick relaxation exists, provided that subgradients are known for the relaxations of the univariate intrinsic functions. For boundary points, additional assumptions are necessary. An automated implementation based on operator overloading is presented, and the calculation of bounds based on affine relaxation is demonstrated for illustrative examples. Two numerical examples for the global optimization of algorithms are presented. In both examples a parameter estimation problem with embedded differential equations is considered. The solution of the differential equations is approximated by algorithms with a fixed number of iterations. |
| first_indexed | 2024-09-23T08:41:23Z |
| format | Article |
| id | mit-1721.1/52407 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T08:41:23Z |
| publishDate | 2010 |
| publisher | Society for Industrial and Applied Mathematics |
| record_format | dspace |
| spelling | mit-1721.1/524072022-09-30T10:34:10Z McCormick-Based Relaxations of Algorithms Mitsos, Alexander Chachuat, Benoit Barton, Paul I. Massachusetts Institute of Technology. Department of Chemical Engineering Barton, Paul I. Barton, Paul I. Theory and implementation for the global optimization of a wide class of algorithms is presented via convex/affine relaxations. The basis for the proposed relaxations is the systematic construction of subgradients for the convex relaxations of factorable functions by McCormick [Math. Prog., 10 (1976), pp. 147–175]. Similar to the convex relaxation, the subgradient propagation relies on the recursive application of a few rules, namely, the calculation of subgradients for addition, multiplication, and composition operations. Subgradients at interior points can be calculated for any factorable function for which a McCormick relaxation exists, provided that subgradients are known for the relaxations of the univariate intrinsic functions. For boundary points, additional assumptions are necessary. An automated implementation based on operator overloading is presented, and the calculation of bounds based on affine relaxation is demonstrated for illustrative examples. Two numerical examples for the global optimization of algorithms are presented. In both examples a parameter estimation problem with embedded differential equations is considered. The solution of the differential equations is approximated by algorithms with a fixed number of iterations. National Science Foundation (grant CTS-0521962) 2010-03-09T14:01:24Z 2010-03-09T14:01:24Z 2009-05 2008-03 Article http://purl.org/eprint/type/JournalArticle 1052-6234 http://hdl.handle.net/1721.1/52407 Mitsos, Alexander, Benoit Chachuat, and Paul I. Barton. “McCormick-Based Relaxations of Algorithms.” SIAM Journal on Optimization 20.2 (2009): 573-601. © 2009 Society for Industrial and Applied Mathematics https://orcid.org/0000-0003-2895-9443 en_US http://dx.doi.org/10.1137/080717341 SIAM Journal on Optimization Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf Society for Industrial and Applied Mathematics SIAM |
| spellingShingle | Mitsos, Alexander Chachuat, Benoit Barton, Paul I. McCormick-Based Relaxations of Algorithms |
| title | McCormick-Based Relaxations of Algorithms |
| title_full | McCormick-Based Relaxations of Algorithms |
| title_fullStr | McCormick-Based Relaxations of Algorithms |
| title_full_unstemmed | McCormick-Based Relaxations of Algorithms |
| title_short | McCormick-Based Relaxations of Algorithms |
| title_sort | mccormick based relaxations of algorithms |
| url | http://hdl.handle.net/1721.1/52407 https://orcid.org/0000-0003-2895-9443 |
| work_keys_str_mv | AT mitsosalexander mccormickbasedrelaxationsofalgorithms AT chachuatbenoit mccormickbasedrelaxationsofalgorithms AT bartonpauli mccormickbasedrelaxationsofalgorithms |