**Theorem 12.1: Consider the following convex programming problem**

$\begin{array}{ll}{\mathrm{min}}_{\text{\psi}\in {\mathbb{R}}^{q}}\hfill & r\left(\text{\psi}\right)\hfill \\ \text{Subjectto}\hfill & {h}_{i}\left(\text{\psi}\right)\ge 0,\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}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{\theta}}_{i}}{h}_{i}\left(\psi \right)$

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

$L\left(\psi *,\theta \right)\text{\hspace{0.17em}}\le \text{\hspace{0.17em}}L\left(\psi *,\theta *\right)\le \text{\hspace{0.17em}}L\left(\psi ,\theta *\right)\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{forall}\psi \text{\hspace{0.17em}}\text{and}\text{\hspace{0.17em}}\theta \text{\hspace{0.17em}}\ge \text{\hspace{0.17em}}0$ |
(12.22) |

${\text{\theta}}_{i}^{*}\text{\hspace{0.17em}}\ge \text{\hspace{0.17em}}0,\text{\hspace{0.17em}}i=1,\mathrm{\dots},m$ |
(12.23) |

${\text{\theta}}_{i}^{*}{h}_{i}\left(\psi *\right)=0,\text{\hspace{0.17em}}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_{θ≥0}*L*(**ψ***, **θ**). Although it ...

Get *Digital Signal Processing with Examples in MATLAB®, 2nd Edition* now with the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.