AN IMPLICIT GRADIENT-TYPE METHOD FOR LINEARLY CONSTRAINED BILEVEL PROBLEMS
Ioannis Tsaknakis, Prashant Khanduri, Mingyi Hong
-
SPS
IEEE Members: $11.00
Non-members: $15.00Length: 00:11:42
In this work, we develop an implicit gradient-type (IG-AL) algorithm for bilevel optimization with strongly convex linear inequality constrained lower-level problems. Many learning problems of interest, including problems in distributed optimization, machine learning, economics, and transport research are captured by the above formulation. The key characteristics of the proposed algorithm are: (i) the use of a primal-dual augmented Lagrangian method for solving the lower-level problem, and (ii) construction of an implicit gradient (derived using the KKT conditions of the lower-level problem) for solving the upper-level problem. Importantly, the proposed algorithm avoids the (expensive) projection step to a half-space inherent to gradient descent-based alternatives. The performance of the proposed algorithm is evaluated on a set of numerical experiments.