Newton and interior-point methods for (constrained) nonconvex-nonconcave minmax optimization with stability and instability guarantees
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2022
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866909100828262400 |
|---|---|
| author | Chinchilla, Raphael Yang, Guosong Hespanha, Joao P. |
| author_facet | Chinchilla, Raphael Yang, Guosong Hespanha, Joao P. |
| contents | We address the problem of finding a local solution to a nonconvex-nonconcave minmax optimization using Newton type methods, including interior-point ones. We modify the Hessian matrix of these methods such that, at each step, the modified Newton update direction can be seen as the solution to a quadratic program that locally approximates the minmax problem. Moreover, we show that by selecting the modification in an appropriate way, the only stable equilibrium points of the algorithm's iterations are local minmax points. As a consequence, the algorithm can only converge towards an equilibrium point if such point is a local minmax, and it will escape if the point is not a local minmax. Using numerical examples, we show that the computation time of our algorithm scales roughly linearly with the number of nonzero elements in the Hessian. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2205_08038 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Newton and interior-point methods for (constrained) nonconvex-nonconcave minmax optimization with stability and instability guarantees Chinchilla, Raphael Yang, Guosong Hespanha, Joao P. Optimization and Control Systems and Control We address the problem of finding a local solution to a nonconvex-nonconcave minmax optimization using Newton type methods, including interior-point ones. We modify the Hessian matrix of these methods such that, at each step, the modified Newton update direction can be seen as the solution to a quadratic program that locally approximates the minmax problem. Moreover, we show that by selecting the modification in an appropriate way, the only stable equilibrium points of the algorithm's iterations are local minmax points. As a consequence, the algorithm can only converge towards an equilibrium point if such point is a local minmax, and it will escape if the point is not a local minmax. Using numerical examples, we show that the computation time of our algorithm scales roughly linearly with the number of nonzero elements in the Hessian. |
| title | Newton and interior-point methods for (constrained) nonconvex-nonconcave minmax optimization with stability and instability guarantees |
| topic | Optimization and Control Systems and Control |
| url | https://arxiv.org/abs/2205.08038 |