Prove2Me
Navigate
DiscoverCollectionsFormalpediaBlogsUsersMomentumMy Missions+
Prove2Me
⌕
Log in
← Formalpedia

§4, p. 336 — the lexicographic program has a solution, and every solution is nondominated

Proved
SteuerChoo.Lexico.lexMin_exists_and_nondominated

by mikedeng1 · Sep 27, 2026 · Mathlib 0df444a (Lean v4.33.1)

lexicographic-optimizationmulti-objective-optimizationp2o-batch-p200ap2o-gran-per-chapterp2o-plan-paperp2o-v1pareto-optimality

Let Z⊆RkZ\subseteq\mathbb R^kZ⊆Rk (k≥1k\ge1k≥1), z∗∈Rkz^*\in\mathbb R^kz∗∈Rk and weights λ∈Λˉ={λ∈Rk∣λi≥0, ∑iλi=1}\lambda\in\bar\Lambda=\{\lambda\in\mathbb R^k\mid \lambda_i\ge0,\ \sum_i\lambda_i=1\}λ∈Λˉ={λ∈Rk∣λi​≥0, ∑i​λi​=1}. Then:

  1. if ZZZ is compact and nonempty, the lexicographic weighted Tchebycheff program with weights λ\lambdaλ has a minimizer;
  2. every minimizer zzz of the lexicographic weighted Tchebycheff program with weights λ\lambdaλ is nondominated:
z lexicographically minimizes (max⁡iλi(zi∗−zi), eT(z∗−z)) over Z ⟹ z∈N.z \text{ lexicographically minimizes } \big(\max_i\lambda_i(z^*_i-z_i),\ e^{\mathsf T}(z^*-z)\big) \text{ over } Z\ \Longrightarrow\ z\in N .z lexicographically minimizes (imax​λi​(zi∗​−zi​), eT(z∗−z)) over Z ⟹ z∈N.

This makes precise the remark that if the first-stage minimization of α\alphaα does not yield a nondominated vector, the second-stage minimization of eT(z∗−z)e^{\mathsf T}(z^*-z)eT(z∗−z) moves to one that is.

Formalization Note Part 1 uses compactness of ZZZ, an added hypothesis (the paper assumes SSS bounded and speaks of minimizers). Part 2 needs neither compactness nor the ideal-vector property, and z∗z^*z∗ is arbitrary in both parts.

Preamble
import Mathlib
import Definitions.Def_SteuerChoo_Lexico_nondominated
import Definitions.Def_SteuerChoo_Lexico_IsLexMin
Formal statement
namespace SteuerChoo.Lexico

theorem lexMin_exists_and_nondominated {k : ℕ} [NeZero k]
    (Z : Set (Fin k → ℝ)) (zstar lam : Fin k → ℝ)
    (hlam : lam ∈ stdSimplex ℝ (Fin k)) :
    (IsCompact Z → Z.Nonempty → ∃ z, IsLexMin Z lam zstar z) ∧
      ∀ z, IsLexMin Z lam zstar z → z ∈ nondominated Z := by sorry

end SteuerChoo.Lexico
Source
Steuer and Choo, An Interactive Weighted Tchebycheff Procedure for Multiple Objective Programming, Math. Programming 26 (1983), p. 336, §4, paragraph after Theorem 4.6
Human review
  • Endorsed by Shuze Chen · Oct 1, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 1, 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 paper
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me