Appendix, (II), p. 15 — conic quadratic duality: strictly feasible and bounded below ⇒ dual solvable, equal values
ProvedRobustUncLP.Ellipsoidal.cqp_dualityconic-quadraticdualityp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1strong-duality
Consider the conic quadratic problem (CQP) and its dual (CQP). Suppose that:
- (CQP) is strictly feasible: some satisfies and for every ;
- the objective is bounded below on the feasible set of (CQP).
Then there is a real number which is the infimum of the primal objective over the primal feasible set, and which is attained as the maximum of the dual objective over the dual feasible set:
The paper quotes this from Nesterov and Nemirovski (1994), Theorem 4.2.1, and applies it to each problem .
Formalization Note "The dual is solvable and the optimal values are equal" is encoded as IsGLB of the primal objective values together with IsGreatest of the dual objective values at the same . The dual uses the sum over in its equality constraint (see the CQP definition). The rows of need not be linearly independent.
Preamble
import Mathlib import Definitions.Def_RobustUncLP_Ellipsoidal_Setting import Definitions.Def_RobustUncLP_Ellipsoidal_CQP
Formal statement
namespace RobustUncLP.Ellipsoidal
open Matrix CQPData
/-- Appendix, claim (II), p. 15 (conic quadratic duality, cited from Nesterov–Nemirovski 1994,
Theorem 4.2.1): if `(CQP_p)` is strictly feasible and its objective is bounded below on its
feasible set, then `(CQP_d)` is solvable and the two optimal values coincide. -/
theorem cqp_duality {N p k : ℕ} (P : CQPData N p k)
(hstrict : ∃ z, P.R *ᵥ z = P.r ∧ ∀ ℓ, euclidNorm (P.A ℓ *ᵥ z - P.b ℓ) < P.c ℓ ⬝ᵥ z - P.d ℓ)
(hbdd : BddBelow (P.primalObj '' P.primalFeas)) :
∃ v : ℝ, IsGLB (P.primalObj '' P.primalFeas) v ∧ IsGreatest (P.dualObj '' P.dualFeas) v := by sorry
end RobustUncLP.Ellipsoidal
Source
Ben-Tal & Nemirovski, Robust solutions of uncertain linear programs, Oper. Res. Lett. 25 (1999); authors' manuscript, Appendix, p. 15, claim (II) (citing Nesterov–Nemirovski 1994, Thm 4.2.1)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.