A primal-dual penalty method via rounded weighted-ℓ1 Lagrangian duality
| Autor: | Regina S. Burachik, C. Y. Kaya, C. J. Price |
|---|---|
| Přispěvatelé: | Burachik, RS, Kaya, CY, Price, CJ |
| Jazyk: | angličtina |
| Rok vydání: | 2022 |
| Předmět: |
Sequence
021103 operations research Control and Optimization kissing number problem Applied Mathematics MathematicsofComputing_NUMERICALANALYSIS 0211 other engineering and technologies Duality (optimization) 02 engineering and technology Management Science and Operations Research Lagrangian duality 01 natural sciences Markov-Dubins problem Primal dual 010101 applied mathematics Scheme (mathematics) penalty function methods Applied mathematics l(1)-penalty function Penalty method 0101 mathematics Kissing number problem primal-dual methods Mathematics |
| Popis: | We propose a new duality scheme based on a sequence of smooth minorants of the weighted-l1 penalty func- tion, interpreted as a parametrized sequence of augmented Lagrangians, to solve non-convex constrained optimization problems. For the induced sequence of dual problems, we establish strong asymptotic duality properties. Namely, we show that (i) the sequence of dual problems is convex and (ii) the dual values monotonically increase to the optimal primal value. We use these properties to devise a subgradient based primal–dual method, and show that the generated primal sequence accumulates at a solution of the original problem. We illustrate the performance of the new method with three different types of test problems: A polynomial non-convex problem, large-scale instances of the celebrated kissing num- ber problem, and the Markov–Dubins problem. Our numerical experiments demonstrate that, when compared with the tra- ditional implementation of a well-known smooth solver, our new method (using the same well-known solver in its sub- problem) can find better quality solutions, i.e. ‘deeper’ local minima, or solutions closer to the global minimum. Moreover, our method seems to be more time efficient, especially when the problem has a large number of constraints. Refereed/Peer-reviewed |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|