Abstract
For bilevel programs with a convex lower level program, the classical approach replaces the lower level program with its Karush-Kuhn-Tucker (KKT) condition and solves the resulting mathematical program with complementarity constraint (MPCC). It is known that when the set of lower level multipliers is not unique, MPCC may not be equivalent to the original bilevel problem, and many MPCC-tailored constraint qualifications do not hold. In this paper, we study bilevel programs where the lower level is generalized convex. Applying the equivalent reformulation via Moreau envelope, we derive new directional optimality conditions. Even in the nondirectional case, the new optimality condition is stronger than the strong stationarity for the corresponding MPCC.
Introduction
Bilevel optimization involves a hierarchical structure where an upper-level objective is minimized subject to the optimal solution of a lower-level problem. This structure is prevalent in machine learning, economics, and engineering. The classical "first-order approach" replaces the lower-level problem with its Karush-Kuhn-Tucker (KKT) conditions, transforming the bilevel program (BP) into a Mathematical Program with Complementarity Constraints (MPCC). However, this transformation is fraught with theoretical difficulties, particularly when the lower-level problem lacks unique Lagrange multipliers. In such cases, the MPCC may not be equivalent to the original BP, and standard constraint qualifications often fail.
The Pitfalls of the KKT Approach
The standard first-order approach relies on the assumption that the lower-level problem can be perfectly represented by its KKT conditions. This leads to two major issues:
- Non-Equivalence: If the lower-level problem has multiple Lagrange multipliers, a local minimum for the resulting MPCC might not actually be a local minimum for the original bilevel problem.
- Constraint Qualification Failure: Many standard tools used to prove optimality, such as the Mangasarian-Fromovitz Constraint Qualification (MFCQ), automatically fail for MPCCs in these scenarios, rendering the resulting optimality conditions unreliable.
Methodology: The Moreau Envelope Reformulation
To address these limitations, this research utilizes a value function reformulation. Instead of the KKT conditions, the authors employ the Moreau envelope ($v_\gamma$) to characterize the lower-level optimal solution. The Moreau envelope is a tool from convex analysis that provides a regularized, "smoothed" version of a function while preserving its global minima.
The core of the reformulation lies in replacing the lower-level optimality constraint with an inequality involving the Moreau envelope:
$$f(x, y) - v_\gamma(x, y) \leq 0$$
where $f$ is the lower-level objective. This approach allows the authors to leverage directional variational analysis. By focusing on directional subdifferentials and directional versions of "calmness" and "metric subregularity," the framework provides a more granular analysis of the objective landscape than traditional gradient-based methods.
Key Theoretical Insights
The paper culminates in the derivation of new directional optimality conditions (Theorems 5.1 and 5.2). These conditions offer several advantages over existing methods:
- Stronger Stationarity: The authors formally prove that their derived conditions are strictly stronger than the "Strong (S-) stationarity" typically applied to MPCCs. This implies that the Moreau envelope approach can identify and exclude points that MPCC-based methods might incorrectly flag as candidates for a minimum.
- Generalized Convexity: Unlike many value-function approaches that require joint convexity of the lower-level problem, this framework applies to "generalized convex" programs. This includes problems where the objective is convex and constraints are quasi-convex, significantly broadening the applicability of the theory.
- Sharp Subdifferential Estimates: By performing a detailed sensitivity analysis of the Moreau envelope, the researchers provide sharp upper estimates for its subdifferential, leading to more restrictive and useful optimality conditions.
Conclusion and Future Work
While this paper establishes a robust theoretical foundation, several avenues for future research remain. The current work focuses on necessary optimality conditions; the development of specific numerical algorithms to compute these points is a logical next step. Furthermore, the choice of the regularization parameter $\gamma$ in the Moreau envelope is critical, as the reformulation requires $\gamma$ to be sufficiently small, which could be computationally delicate in practice.
Finally, while the generalized convex assumption is a significant step forward, extending these results to fully non-convex lower-level problems remains a challenging open problem in the field of bilevel optimization.
Summary updated