Lemma 2.2, p. 6 — for 0 < p < 1, minimizers of ‖x‖_p^p over ℙ_j ∩ FEA(A,b,σ,1) are extreme points
ProvedSparseLpLq.SmallP.lemma_2_2extreme-pointslp-minimizationnonconvex-optimizationp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1sparse-optimization
Assume the blanket assumptions of the paper for : , and . Let and let be one of the closed orthants of (2.2) with . If is an optimal solution of
that is, and for all in that set, then is an extreme point of .
Combined with the polyhedrality of (Lemma C.1), the lemma confines every optimal solution of problem (1.4) with to the finitely many extreme points of the pieces ; this is the basis of Proposition 2.1.
Formalization Note The orthant is indexed by a sign pattern s : Fin n → Bool. Extreme points are Mathlib's Set.extremePoints ℝ.
Differences from the source:
- encoding: orthant index j ∈ {1, …, 2ⁿ} → sign pattern s : Fin n → Bool (true: xᵢ ≥ 0, false: xᵢ ≤ 0); reason: the sign patterns enumerate the 2ⁿ closed orthants of (2.2) one-to-one
Preamble
import Mathlib import Definitions.Def_SparseLpLq_SmallP_Setting open scoped ENNReal Matrix
Formal statement
namespace SparseLpLq.SmallP
theorem lemma_2_2 {m n : ℕ} (A : Matrix (Fin m) (Fin n) ℝ) (b : Fin m → ℝ) (σ : ℝ)
(hσ : 0 ≤ σ) (hfeas : (FEA A b σ 1).Nonempty) (hb : σ < qNorm 1 b)
(p : ℝ) (hp : p ∈ Set.Ioo (0 : ℝ) 1) (s : Fin n → Bool)
(hne : (orthant s ∩ FEA A b σ 1).Nonempty)
(x : Fin n → ℝ) (hx : x ∈ orthant s ∩ FEA A b σ 1)
(hopt : ∀ y ∈ orthant s ∩ FEA A b σ 1, lpObj p x ≤ lpObj p y) :
x ∈ Set.extremePoints ℝ (orthant s ∩ FEA A b σ 1) := by sorry
end SparseLpLq.SmallP
Source
Yang, Chen & Xiang, Sparse solutions of a class of constrained optimization problems, arXiv:1907.00880v5, p. 6, Lemma 2.2 (problem (2.3), orthants (2.2)); proof p. 7
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.