§4.1, (20), p. 491 — ∂h(x*) = {(ρI − A)x*} ⊂ ∂g(x*) iff x* is a Kuhn–Tucker point of (Q1)
ProvedTaoAnDCA.TRS.eq20_iff_kktdcakuhn-tuckerp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1subdifferentialtrust-region
Let , , , and the decomposition (16) , be as in the trust-region setting, with symmetric and positive semidefinite, and let , i.e. . Then , and the inclusion (20)
holds if and only if there is a real with
This identifies the critical points that the DCA delivers for the decomposition (16) with the Kuhn–Tucker points of the trust-region subproblem.
Formalization Note. The Kuhn–Tucker conditions are the predicate IsKKT A b r x lam. The hypothesis is where the page applies the equivalence: the limit points of the DCA lie in .
Preamble
import Mathlib import Definitions.Def_TaoAnDCA_TRS_Setting open Filter Topology
Formal statement
namespace TaoAnDCA.TRS
theorem eq20_iff_kkt {n : ℕ} (A : EuclideanSpace ℝ (Fin n) →L[ℝ] EuclideanSpace ℝ (Fin n)) (hA : IsSelfAdjoint A)
(b : EuclideanSpace ℝ (Fin n)) (r : ℝ) (hr : 0 < r) (ρ : ℝ) (hρ : 0 < ρ)
(hρA : ∀ z : EuclideanSpace ℝ (Fin n), 0 ≤ inner ℝ z (ρ • z - A z)) (xs : EuclideanSpace ℝ (Fin n)) (hxs : ‖xs‖ ≤ r) :
TaoAnDCA.GlobalOpt.subdiff (hDec A ρ) xs = {ρ • xs - A xs} ∧
(TaoAnDCA.GlobalOpt.subdiff (hDec A ρ) xs ⊆ TaoAnDCA.GlobalOpt.subdiff (gDec b ρ r) xs ↔ ∃ lam : ℝ, IsKKT A b r xs lam) := by sorry
end TaoAnDCA.TRS
Source
Pham Dinh & Le Thi, A d.c. optimization algorithm for solving the trust-region subproblem, SIAM J. Optim. 8 (1998), p. 491, §4.1, proof of Theorem 4.1, display (20) and the sentence after it
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.