Penalty relaxation feasibility bound for convex constrained optimization

Let ff and gg define a convex constrained optimization problem of the form

minxf(x)subject tog(x)0.\min_x f(x)\quad\text{subject to}\quad g(x)\leq 0.

For a penalty parameter Λ\Lambda, consider the penalty relaxation

minxf(x)+Λ[g(x)]+,\min_x f(x)+\Lambda [g(x)]_+,

where [g(x)]+[g(x)]_+ denotes the positive part of g(x)g(x), and let Δ(δ)\Delta(\delta) denote the quantity appearing in the source's Slater-type bound. Penalty relaxation feasibility conjecture. The penalty relaxation can guarantee δ\delta-feasibility whenever δ\delta solves

δΔ(δ)Λ.\delta\geq\frac{\Delta(\delta)}{\Lambda}.

This is presented as following from a Slater-type argument, but the source does not provide enough surrounding definitions to determine the precise meaning of Δ(δ)\Delta(\delta) or whether the claim has been established as a theorem.

Sources & referencesView supporting material

Primary source

Guy Kornowski, Swati Padmanabhan, Kai Wang, Zhe Zhang and Suvrit Sra, “First-Order Methods for Linearly Constrained Bilevel Optimization”, arXiv:2406.12771 (2025).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.