§3, (D), pp. 481–482 — d.c. duality: inf{g(x) − h(x)} = inf{h*(y) − g*(y)}
ProvedTaoAnDCA.GlobalOpt.dc_dualityconjugatedc-programmingdualityp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let satisfy the standing inclusions and , and adopt the convention . Then the d.c. program (P) and its dual (D) have the same optimal value:
This is the d.c. duality of §3 (Toland duality). The paper derives it by writing , exchanging the two infima, and observing that for and otherwise. It is the first step of the proof of the global optimality condition, Theorem 3.1(i).
Formalization Note Both sides are extended-real infima; the differences are the convention-respecting difference dcSub, so the dual objective is off , as in the paper's rewriting of (D) over all of . No finiteness of is assumed. The standing assumptions and (3) are hypotheses.
Preamble
import Mathlib import Definitions.Def_TaoAnDCA_GlobalOpt_Setting open TaoAnDCA.GlobalOpt
Formal statement
namespace TaoAnDCA.GlobalOpt
theorem dc_duality {n : ℕ} (g h : EuclideanSpace ℝ (Fin n) → EReal) (hgh : DCStanding g h) :
primalValue g h =
⨅ y, dcSub (CondatPD.FinDim.conj h) (CondatPD.FinDim.conj g) y := by sorry
end TaoAnDCA.GlobalOpt
Source
Pham Dinh & Le Thi, A d.c. optimization algorithm for solving the trust-region subproblem, SIAM J. Optim. 8 (1998), pp. 481–482, §3, derivation of (P_y) and display (D)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.