Semismooth Newton-type method for bilevel optimization: global convergence and extensive numerical experiments
Author(s)
Fischer, Andreas
Zemkoho, Alain B
Zhou, Shenglong
Type
Journal Article
Abstract
We consider the standard optimistic bilevel optimization problem, in particular upper- and lower-level constraints can be coupled. By means of the lower-level value function, the problem is transformed into a single-level optimization problem with a penalization of the value function constraint. For treating the latter problem, we develop a framework that does not rely on the direct computation of the lower-level value function or its derivatives. For each penalty parameter, the framework leads to a semismooth system of equations. This allows us to extend the semismooth Newton method to bilevel optimization. Besides global convergence properties of the method, we focus on achieving local superlinear convergence to a solution of the semismooth system. To this end, we formulate an appropriate CD-regularity assumption and derive sufficient conditions so that it is fulfilled. Moreover, we develop conditions to guarantee that a solution of the semismooth system is a local solution to the bilevel optimization problem. Extensive numerical experiments on 124 examples of nonlinear bilevel optimization problems from the literature show that this approach exhibits a remarkable performance, where only a few penalty parameters need to be considered.
Date Issued
2022-05-01
Date Acceptance
2021-08-10
Citation
Optimization Methods and Software, 2022, 37 (5), pp.1770-1804
ISSN
1055-6788
Publisher
Informa UK Limited
Start Page
1770
End Page
1804
Journal / Book Title
Optimization Methods and Software
Volume
37
Issue
5
Copyright Statement
© 2021 The Author(s). Published by Informa UK Limited, trading as Taylor & Francis Group
This is an Open Access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
This is an Open Access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
License URL
Identifier
https://www.tandfonline.com/doi/full/10.1080/10556788.2021.1977810
Publication Status
Published
Date Publish Online
2021-12-02