§4.2 "Summing up", p. 493 — a Kuhn–Tucker point x* with an eigenpair (λ₁, u), λ* + λ₁ < 0, admits x̄ with ‖x̄‖ ≤ r and f(x̄) < f(x*)
ProvedTaoAnDCA.Restart.restart_existsLet be a real symmetric matrix, , , and . Let be a Kuhn–Tucker point of the trust-region subproblem with multiplier : , , , . Let be an eigenvector of , , with
Then there exists with
In §4.2 the condition , with the smallest eigenvalue of , is the test that detects a Kuhn–Tucker point which is not a global solution; this theorem says that such a point can always be improved, so the DCA can be restarted from a strictly better feasible point. That is the basis of the paper's global algorithm GDCA.
Formalization Note The page speaks of the smallest eigenvalue and of a point "produced by the DCA"; neither is used, so the statement holds for every Kuhn–Tucker point and every eigenpair with , which is stronger. The hypothesis is the paper's test , not " is not a global solution", which would make the conclusion a restatement of the hypothesis.
import Mathlib import Definitions.Def_TaoAnDCA_Restart_Setting
namespace TaoAnDCA.Restart
theorem restart_exists {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)
(lam1 : ℝ) (u : EuclideanSpace ℝ (Fin n)) (hu : u ≠ 0) (hAu : A u = lam1 • u) (hneg : lamStar + lam1 < 0) :
∃ xbar : EuclideanSpace ℝ (Fin n), ‖xbar‖ ≤ r ∧ TaoAnDCA.TRS.quad A b xbar < TaoAnDCA.TRS.quad A b xs := by sorry
end TaoAnDCA.Restart
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.