Limiting Stationarity of Regularized Gap-Function Reformulations for Bilevel Optimization with Unbounded Multipliers

Value-function-type reformulations have generated a broad class of methods for bilevel optimization.

However, the corresponding value-function-type constraints are inherently degenerate and generally fail to satisfy standard constraint qualifications, so the associated multiplier sequences may be unbounded and bounded-multiplier convergence analyses become inapplicable.

We study this issue for the regularized gap-function reformulation of bilevel problems with constrained convex lower-level programs.

We prove that accumulation points of approximate stationary sequences are C-stationary for the corresponding Karush-Kuhn-Tucker-based mathematical program with complementarity constraints (MPCC), even when the multiplier sequence associated with the regularized gap-function constraint is unbounded.

The result holds under Mangasarian-Fromovitz constraint qualification (MFCQ) for the upper- and lower-level constraint systems and MPCC-MFCQ at the limiting MPCC point, without any constraint qualification on the regularized gap-function constraint itself.

We further provide an example showing that approximate stationary points of the standard regularized gap-function reformulation may converge to a point that is C-stationary but not M-stationary.

To guarantee M-stationarity, we introduce a slack-based two-parameter penalty formulation preserving exact multiplier-slack complementarity and establish M-stationarity under a domination condition on the penalty parameters.

We develop an inexact slack-penalty method with adaptive penalty updates and feasibility correction, whose accumulation points are M-stationary under the stated assumptions.