§4.2, p. 491 — the multiplier of a Kuhn–Tucker point is λ* = (−⟨x*, Ax*⟩ − ⟨x*, b⟩)/r²
ProvedTaoAnDCA.Restart.lamStar_eqkuhn-tuckerlagrange-multiplierp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1trust-region
Let be a real symmetric matrix, , , and let be a Kuhn–Tucker point of the trust-region subproblem with multiplier , that is, , , and . Then
The multiplier is therefore computable from alone, which is what the global-optimality test of §4.2 () needs.
Formalization Note The paper derives the formula "from Theorem 2.1"; the statement only uses the Kuhn–Tucker conditions. When , complementarity gives and the right-hand side vanishes as well, since .
Preamble
import Mathlib import Definitions.Def_TaoAnDCA_Restart_Setting
Formal statement
namespace TaoAnDCA.Restart
theorem lamStar_eq {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) :
lamStar = (-(inner ℝ xs (A xs)) - inner ℝ xs b) / r ^ 2 := 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. 491, §4.2, display after "from Theorem 2.1 it follows that"
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.