Digital Signal Processing with Examples in MATLAB®, 2nd Edition

Theorem 12.1: Consider the following convex programming problem

$\begin{array}{ll}{\min }_{\text{ψ}\in {ℝ}^q}\hfill & r\left(\text{ψ}\right)\hfill \\ \text{Subject to}\hfill & h_i\left(\text{ψ}\right)\ge 0,i=1,\mathrm{\dots },m\hfill \end{array}$

where r and h_i, i = 1, …, m are convex and there exists a ψ′ such that h_i(ψ′) > 0 for all i = 1, 2, …, m. Define the Lagrangian

$L\left(\psi ,\theta \right)=r\left(\psi \right)-{\displaystyle \sum _{i=1}^m{\text{θ}}_i}{h}_i\left(\psi \right)$

where θ = (θ₁, ., θ_m)^T. If ψ* solves the convex programming problem, then there exists Lagrange multipliers $\theta *={\left({\text{θ}}_1^{*},\mathrm{\dots },{\text{θ}}_m^{*}\right)}^T$ such that the following three conditions hold:

$L\left(\psi *,\theta \right)\le L\left(\psi *,\theta *\right)\le L\left(\psi ,\theta *\right)\text{for all }\psi \text{and}\theta \ge 0$

(12.22)

${\text{θ}}_i^{*}\ge 0,i=1,\mathrm{\dots },m$

(12.23)

${\text{θ}}_i^{*}{h}_i\left(\psi *\right)=0,i=1,\mathrm{\dots },m$

(12.24)

■

This theorem tells us that ψ* can be found by solving the unconstrained optimization problem min_ψL(ψ, θ*), and that θ* can be found by solving the Lagrangian dual problem max_θ≥0L(ψ*, θ). Although it ...