§4.2 case a), p. 492 — if ⟨b, x*⟩ > 0 then x̄ = −x* is feasible and f(x̄) = f(x*) − 2⟨b, x*⟩ < f(x*)
ProvedTaoAnDCA.Restart.restart_case_akuhn-tuckerp2o-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 . If , then satisfies and
This is the first case of the paper's construction of a starting point for restarting the DCA from a Kuhn–Tucker point that is not a global solution.
Preamble
import Mathlib import Definitions.Def_TaoAnDCA_Restart_Setting
Formal statement
namespace TaoAnDCA.Restart
theorem restart_case_a {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) (hb : 0 < inner ℝ b xs) :
‖-xs‖ ≤ r ∧
TaoAnDCA.TRS.quad A b (-xs) = TaoAnDCA.TRS.quad A b xs + 2 * inner ℝ (A xs + lamStar • xs) xs ∧
TaoAnDCA.TRS.quad A b xs + 2 * inner ℝ (A xs + lamStar • xs) xs = TaoAnDCA.TRS.quad A b xs - 2 * inner ℝ b xs ∧
TaoAnDCA.TRS.quad A b (-xs) < TaoAnDCA.TRS.quad A b xs := 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. 492, §4.2, "How to compute the initial point for restarting the DCA", case a)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.