§4.2 case (b.2), first bullet, p. 493 — if bᵀx* = 0, v = u + τx* has vᵀx* ≠ 0 and vᵀ(A + λ*I)v < 0 for the stated τ < 0
ProvedTaoAnDCA.Restart.restart_case_b2_zerokuhn-tuckernegative-curvaturep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1restarttrust-region
Let be a real symmetric matrix, , , and let be a Kuhn–Tucker point of with multiplier and . Let satisfy and , assume , and put . Then:
- if , then and for every ;
- if , then and for every with
Such a is the direction with which case (b.1) is re-entered when and .
Formalization Note The page prints the range in item 2 as , without the factor . With the curvature is , so the correct bound carries the factor 2, and the printed range is false for a general (take , , : the curvature is ). The statement uses the corrected bound. It takes a general with negative curvature rather than the eigenvector of §4.2: for an eigenvector with one has , so item 2 would be vacuous.
Preamble
import Mathlib import Definitions.Def_TaoAnDCA_Restart_Setting
Formal statement
namespace TaoAnDCA.Restart
theorem restart_case_b2_zero {n : ℕ} (A : EuclideanSpace ℝ (Fin n) →L[ℝ] EuclideanSpace ℝ (Fin n)) (hA : IsSelfAdjoint A)
(b : EuclideanSpace ℝ (Fin n)) (r : ℝ) (hr : 0 < r)
(xs : EuclideanSpace ℝ (Fin n)) (lamStar : ℝ) (hkkt : TaoAnDCA.TRS.IsKKT A b r xs lamStar) (hnorm : ‖xs‖ = r)
(u : EuclideanSpace ℝ (Fin n)) (hu : inner ℝ u (A u + lamStar • u) < 0) (hux : inner ℝ u xs = 0)
(hb : inner ℝ b xs = 0) :
(inner ℝ b u ≤ 0 → ∀ τ : ℝ, τ < 0 →
inner ℝ (u + τ • xs) xs ≠ 0 ∧
inner ℝ (u + τ • xs) (A (u + τ • xs) + lamStar • (u + τ • xs)) < 0) ∧
(0 < inner ℝ b u → ∀ τ : ℝ, inner ℝ u (A u + lamStar • u) / (2 * inner ℝ b u) < τ → τ < 0 →
inner ℝ (u + τ • xs) xs ≠ 0 ∧
inner ℝ (u + τ • xs) (A (u + τ • xs) + lamStar • (u + τ • xs)) < 0) := by sorry
end TaoAnDCA.Restart
Source
Pham Dinh & Le Thi, A d.c. optimization algorithm for solving the trust-region subproblem, SIAM J. Optim. 8 (1998), p. 493, §4.2, case (b.2), first bullet
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.