Convex Optimization 2026, 19 - Theorems of Alternatives

Lagrange duality can be used for determining feasibility of a system of (in-)equalities. Assume the domain of the inequality system defining the problem as 𝔻 = ∩^m_i=1 dom f_i ⋂ ∩^p_i=1 dom h_i is nonempty, then the problem is standard with objective f₀ = 0. If the problem is feasible, then the optimal value is 0, if it's not then the optimal value diverges. Solving the optimization problem then is the same as solving the inequality system (5.8.1.0). Using the dual function for the optimization problem, the emerging dual problem is to maximize it w.r.t. 0 ⪯ λ. The optimal value of this dual problem behaves analogously to that of the root problem. It also gives the inequality system 0 ⪯ λ, 0 < g(λ, ν). If this is feasible, then the inequality system is infeasible, since that requires that the optimal value of the dual problem diverges. Any solution (λ, ν) is a proof of feasibility of the original system. Two systems of (in)equalities are weak alternatives, if at most one of them is feasible (5.8.1.1). For strict inequality systems with the same dual function, 0 ⪯ λ ≠ 0; g(λ, ν) ≥ 0 is a weak alternative (5.8.1.2).

For a convex inequality system, the pairs of weak alternatives described above are strong alternatives, so exactly one of the two alternatives holds. Each of the inequality systems is feasible iff the other is infeasible. Assume in the following that f_i are convex and h_i are affine. A strict inequality system f_i(x) < 0, Ax = b with alternative 0 ⪯ λ ≠ 0, g(λ, ν) ≥ 0. There is a x ∈ relint 𝔻 with Ax = b. This is a strong alternatives. This comes from the related optimization problem minimizing s, subject to f_i(x) - s ≤ 0; Ax = b. The Lagrange dual function

is either g(λ, ν) for 1^Tλ = 1; and -∞ otherwise. By Slater's condition, there is a (λ', ν') so that g(λ', ν') = p', 0 ⪯ λ', 1^Tλ' = 1. A nonstrict inequality system with alternative are strong alternatives, given that ∃ x ∈ relint 𝔻; Ax = b and an optimal value p' for the Lagrange dual function (5.8.2).