Lemma 4.2, p. 492 — if (A + μI)y = −b then f(x) = f(y) − (μ/2)(‖x‖² − ‖y‖²) + ½⟨x − y, (A + μI)(x − y)⟩
ProvedTaoAnDCA.Restart.lemma_4_2p2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1quadratic-programmingtrust-region
Let be a real symmetric matrix, , and . If and satisfy , then for every
Applied at a Kuhn–Tucker point with this is (22), the expansion from which every restart point of §4.2 is shown to decrease .
Preamble
import Mathlib import Definitions.Def_TaoAnDCA_Restart_Setting
Formal statement
namespace TaoAnDCA.Restart
theorem lemma_4_2 {n : ℕ} (A : EuclideanSpace ℝ (Fin n) →L[ℝ] EuclideanSpace ℝ (Fin n)) (hA : IsSelfAdjoint A)
(b : EuclideanSpace ℝ (Fin n)) (mu : ℝ) (y : EuclideanSpace ℝ (Fin n)) (hy : A y + mu • y = -b) :
∀ x : EuclideanSpace ℝ (Fin n), TaoAnDCA.TRS.quad A b x = TaoAnDCA.TRS.quad A b y - mu / 2 * (‖x‖ ^ 2 - ‖y‖ ^ 2)
+ 1 / 2 * inner ℝ (x - y) (A (x - y) + mu • (x - y)) := 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, Lemma 4.2
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.