Lagrange Multipliers Technique

Method (Constrained Optimization)

Want to minimize a function $f(x^{n})$ over its alphabet $x^{n}=(x_{1},\ldots,x_{n})\in\mathbb{R}^{n}$ subject to inequality constraints $g_{i}(x^{n})\le0, \ i=1,\ldots,m$ and equality constraints $h_{j}(x^{n})=0, \ j=1,\ldots,l$ i.e. we want to determine $\tag{\#}\min_{x^{n}\in Q}f(x^{n})$ where $Q=\{x^{n}\in\mathbb{R}^{n}: g_{i}(x^{n}\le0,i=1,\ldots,m\mbox{ and }h_{j}(x^{n})=0,j=1,\ldots,l \}$

Definition (Karush-Kuhn-Tucker Conditions (KKT))

Point $x^{n}=(x_{1},\ldots,x_{n})$ and multipliers $\lambda^{m}=(\lambda_{1},\ldots,\lambda_{m})$ and $v^{l}=(v_{1},\ldots,v_{l})$ are said to satisfy the KKT conditions if $\begin{cases} g_{i}(x^{n})\le0, \ \lambda_{i}\ge0, \ \lambda_{i}g_{i}(x^{n})=0&\mbox{for }i=1,\ldots,m \\ h_{j}(x^{n})=0&\mbox{for }j=1,\ldots,l \\ \frac{\partial f(x^{n})}{\partial x_{K}}+\sum\limits^{m}_{i=1}\lambda_{i}\frac{\partial g_{i}(x^{n})}{\partial x_{K}}+\sum\limits^{l}_{j=1}v_{j}\frac{\partial h_{j}(x^{n})}{\partial x_{K}}=0&\mbox{for }K=1,\ldots,n \end{cases}$

Remark

In general $\#$ is hard to solve so instead we consider a dual optimization without constraints given by $L(\lambda^{m},v^{l}):=\min_{x^{n}\in\mathbb{R}^{n}}\left[f(x^{n})+\sum\limits_{i=1}^{m}\lambda_{i}g_{i}(x^{n})+\sum\limits_{j=1}^{l}v_{j}h_{j}(x^{n})\right]$ If $f$ and $\{g_{i}\}_{i=1}^{m}$ are differentiable convex functions and $\{h_{j}\}_{j=1}^{l}$ are affine, then it can be shown that $\exists$ multipliers $\tilde\lambda^{m}=(\tilde\lambda_{1},\ldots,\tilde\lambda_{m})$ with $\tilde\lambda_{i}\ge0, \ i=1,\ldots,m$ and $\tilde v^{l}=(\tilde v_{1},\ldots, \tilde v_{l})$ such that $L(\tilde\lambda^{m},\tilde v^{l})=\min_{x^{n}\in Q}f(x^{n})=f(x^{+^{n}})$ (where $x^{+^n}$ is the optimizer point) iff $x^{*n}=(x_{1}^{*},\ldots,x_{n}^{*}), \ \tilde\lambda^{m}$ and $\tilde v^{l}$ satisfy the following () conditions (i.e. we have solved $\#$ via $L(\tilde\lambda^{m},\tilde v^{l}$ ).

Linked from

Optimal Power Allotment