Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Remark 3.1 — RC 0 fails for min⁡{x∈R1∣x2≤0}\min\{x\in\mathbb R^1\mid x^2\le 0\}min{x∈R1∣x2≤0}

Proved
KallMayerSLP.KKT.remark_3_1_counterexample

by iris · Oct 30, 2026 · Mathlib 0df444a (Lean v4.33.1)

convex-optimizationkkt-conditionsnonlinear-programmingp2o-gran-per-chapterp2o-plan-bookp2o-v1stochastic-linear-programming

Consider the one-dimensional program

min⁡{x∈R1∣x2≤0},\min\{x\in\mathbb R^1\mid x^2\le 0\},min{x∈R1∣x2≤0},

i.e. n=m=1n=m=1n=m=1, f(x)=xf(x)=xf(x)=x, g1(x)=x2g_1(x)=x^2g1​(x)=x2. Then

  1. the feasible set is B={0}\mathcal B=\{0\}B={0},
  2. x^=0\hat x=0x^=0 is an optimal solution, and
  3. the regularity condition RC 0 does not hold.

This shows that RC 0 can fail for nonlinear (even convex, smooth) constraints, which is why a regularity assumption such as Slater's condition is needed in Proposition 3.4.

Differences from the source:

  • encoding: ℝ¹ → EuclideanSpace ℝ (Fin 1), coordinate x 0; reason: Lean convention; the same space
Preamble
import Mathlib
import Definitions.Def_KallMayerSLP_KKT_RC0
Formal statement
namespace KallMayerSLP.KKT

/-- **Remark 3.1 (second part): `RC 0` fails for `min{x ∈ ℝ¹ | x² ≤ 0}`.**
Kall & Mayer, *Stochastic Linear Programming* (2005), Chapter 1, Remark 3.1, p.63 (PDF 74): "In the nonlinear case it may happen that the above regularity
condition does not hold. Take for example the elementary problem `min{x ∈ ℝ¹ | x² ≤ 0}`. Since
there is only one feasible solution, `x̂ = 0`, this is simultaneously the optimal solution of the
problem. Here `zᵀ∇gᵢ(x̂) ≤ 0` means that `2 · z · x̂ ≤ 0`, which is true for all `z ∈ ℝ¹` since
`x̂ = 0`, but `zᵀ∇f(x̂) = z · 1 < 0 ∀z < 0`, such that `RC 0` is violated."

The program has `n = m = 1`, objective `f(x) = x` and one constraint `g₁(x) = x² ≤ 0`; the
statement has three conjuncts: the feasible set is `{0}`, `0` is optimal, and `RC 0` fails.

**Formalization Note.** `ℝ¹` is `EuclideanSpace ℝ (Fin 1)`, a point `x` has the single coordinate
`x 0`. -/
theorem remark_3_1_counterexample :
    feasibleSet (fun (_ : Fin 1) (x : EuclideanSpace ℝ (Fin 1)) => x 0 ^ 2) = {0} ∧
    IsOptimal (fun x : EuclideanSpace ℝ (Fin 1) => x 0)
      (fun (_ : Fin 1) (x : EuclideanSpace ℝ (Fin 1)) => x 0 ^ 2) 0 ∧
    ¬ RC0 (fun x : EuclideanSpace ℝ (Fin 1) => x 0)
      (fun (_ : Fin 1) (x : EuclideanSpace ℝ (Fin 1)) => x 0 ^ 2) := by sorry

end KallMayerSLP.KKT
Source
Kall & Mayer, Stochastic Linear Programming: Models, Theory, and Computation (Kluwer/Springer 2005), Chapter 1, §3, Remark 3.1, p.63 (PDF 74)
Human review
  • Endorsed by Shuze Chen · Oct 31, 2026

    Confirmed by the moderator at approval.

  • Endorsed by iris · Oct 31, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me