The Method of Lagrangian Multipliers and The KKT Conditions

This article simply introduced strategies for finding the stationary points of the objective function subject to one or more equality or inequality constraints.

Consider a standard form of continuous optimization problem, $$\underset{\mathbf{x}}{min}f(\mathbf{x})\mathrm{s}.\mathrm{t}.;;g_k(\mathbf{x})\le 0,;;k=1,2,\cdots ,m{h}_l(\mathbf{x})=0,;;l=1,2,\cdots ,p$$ in which $$\mathbf{x}\in {\mathrm{\Re }}^{n}f,g_k,h_l:{\mathrm{\Re }}^n\to \mathrm{\Re };;\mathrm{f}\mathrm{o}\mathrm{r};;k=1,2,\cdots ,m;;\mathrm{a}\mathrm{n}\mathrm{d};;l=1,2,\cdots ,pm,p\ge 0$$ And $f,g_k,h_l$ are all continuous differentable.

We divided the problem into two cases: $p=0$ or $p\ne 0$. For the former we introduced The Method of Lagrange Multipliers as the solving strategy, and simply introduced KKT Conditions for the other one when it suits some Regularity Conditions.

Notice that it was easy to treat a maximization problem by negating the objective function, we only use the maximization problem as a general example.

The Method of Lagrange Multipliers

Consider the optimization problem $$\underset{\mathbf{x}}{min}f(\mathbf{x})\mathrm{s}.\mathrm{t}.;;g_k(\mathbf{x})=0;;\mathrm{f}\mathrm{o}\mathrm{r};;k=1,2,\cdots ,m.$$ To transfer the constrained problem into an unconstrained one, we define the Lagrange Function, $$L(\mathbf{x}\mathbf{,}\overrightarrow{\lambda })=f(\mathbf{x})+\sum _{k=1}^m{\lambda }_k{g}_k(\mathbf{x})$$ In which ${\lambda }_k\in \mathrm{\Re };;\mathrm{f}\mathrm{o}\mathrm{r};;k=1,2,\cdots ,m$. Then we have the necessary conditions for the optimal solution, which is $$ \left{$$\begin{array}{c}{▽}_{\mathbf{x}}L=\mathbf{0}{▽}_{\overrightarrow{\lambda }}L=\mathbf{0}\end{array}$$\right. $$ called Stationary Equation and Constraints separately. Then solving the $n+m$ simultaneous equations, and the solution $({\bf x^},\overrightarrow{\lambda}!^)$ are stationary points and corresponding coefficients.

$\mathbf{N}\mathbf{O}\mathbf{T}\mathbf{E}.$ Cause we could get stationary point through Lagrange Multipliers directly, the minimization/maximization problems are treated in same way.

$\mathbf{E}\mathbf{X}\mathbf{A}\mathbf{M}\mathbf{P}\mathbf{L}\mathbf{E}.$ Maximize $f(x,y,z)=8xyz$ subject to ${\displaystyle \frac{x^2}{a^2}}+{\displaystyle \frac{y^2}{b^2}}+{\displaystyle \frac{z^2}{c^2}}=1$.

$\mathbf{S}\mathbf{O}\mathbf{L}\mathbf{U}\mathbf{T}\mathbf{I}\mathbf{O}\mathbf{N}.$ Form the Lagrange Function $$L(x,y,z,\lambda )=8xyz+\lambda ({\displaystyle \frac{x^2}{a^2}}+{\displaystyle \frac{y^2}{b^2}}+{\displaystyle \frac{z^2}{c^2}}-1)$$ Then calculate gradient of the function $L$ and set it to $\mathbf{0}$. $$▽L=\left[\begin{array}{cccc}(8yz+{\displaystyle \frac{2\lambda x}{a^2}})& (8xz+{\displaystyle \frac{2\lambda y}{b^2}})& (8xy+{\displaystyle \frac{2\lambda z}{c^2}})& ({\displaystyle \frac{x^2}{a^2}}+{\displaystyle \frac{y^2}{b^2}}+{\displaystyle \frac{z^2}{c^2}}-1)\end{array}\right]=\mathbf{0}$$ We could get the solution $$ \left{$$\begin{array}{c}x={\displaystyle \frac{\sqrt{3}}{3}}ay={\displaystyle \frac{\sqrt{3}}{3}}bz={\displaystyle \frac{\sqrt{3}}{3}}c\end{array}$$\right. $$Consideringthebackgroundofthequestion,themaximumsolutionmustexist.Nowwecangettheanswer$$ f_{\rm max}(x,y,z)=\dfrac{8\sqrt{3}}{9}abc $$

KKT Conditions

For convinience, we consider the case without equality constraint but with a single inequality constraint first, $$\underset{\mathbf{x}}{min}f(\mathbf{x})\mathrm{s}.\mathrm{t}.;;g(\mathbf{x})\le 0.$$ Then define the feasible region $\text{Missing or unrecognized delimiter for left}$ and assuming that ${\bf x}^$isthebestsolutionundertheconstraintcondition$g$.Accordingtowhether${\bf x}^$isontheborderof$\mathbb{K}$ or not, we can divide the problem into two cases and discuss them separately.

${\bf C{\scriptsize ASE}; 1}.;; g({\bf x}^) <0.$ The best solution is inside $\mathbb{K}$. At this time we call ${\bf x}^$ as the interior solution. Obviously, at this time, an infinitesimal displacement of the point towards any direction will not against the constraint, so we call that the constraint condition$g$ is inactive.

${\bf C{\scriptsize ASE};2}.;;g({\bf x}^)=0.$ The best solution is on the border of $\mathbb{K}$. At this time we call ${\bf x}^$ as the boundary solution. Correspondingly, now we call that the constraint condition $g$ is active.

Likely, defining the Lagrangian Function $$L(\mathbf{x},\lambda )=f(\mathbf{x})+\lambda g(\mathbf{x})$$ According to $g$ is active or inactive, the necessary condition for us to get the best solution are different.

$\mathbf{C}\mathbf{A}\mathbf{S}\mathbf{E}\mathbf{;}\mathbf{I}\mathbf{N}\mathbf{A}\mathbf{C}\mathbf{T}\mathbf{I}\mathbf{V}\mathbf{E}.$Cause the constraint condition $g$ has no influence on getting the best solution, we could make $\lambda =0$ directly. Now the task is equivalent to unconstrained optimization, and only $▽f=\mathbf{0}$ is needed.

$\mathbf{C}\mathbf{A}\mathbf{S}\mathbf{E}\mathbf{;}\mathbf{A}\mathbf{C}\mathbf{T}\mathbf{I}\mathbf{V}\mathbf{E}.$ Now the constraint condition $g$ is equivalent to $$g(\mathbf{x})=0$$ Notice that for every points $\mathbf{x}\in g$, there is $▽g(\mathbf{x})$ orthogonal to $g$. Likely, it is obvious to find that $\bigtriangledown f({\bf x}^)$isalsoorthogonalto$g$.So,wecaneasilyprovethat$\bigtriangledown f \in {\rm span}(\bigtriangledown g)$at${\bf x}^$.Thatistosay,thereexists$\lambda$whichmakesthat$${▽}_{\mathbf{x}}f=-\lambda {▽}_{\mathbf{x}}g$$I{t}^{\prime }seasytofindthat$\lambda \geq 0$shouldbekept,causewewanttominimize$f$,and$\bigtriangledown f({\bf x}^*)$(pointingtothefastestgrowingdirection)shouldpointtotheinteriorof$\mathbb{K}$.However,$\bigtriangledown g$pointstotheoutsideof$\mathbb{K}$,so$\lambda$shouldbekeptnotlessthan$0$, which is called dual feasibility. Likely, if we want to maximize $f$, we should keep $\lambda \le 0$.

Obviously, there will always be either $\lambda$ or $g$ equal to $0$, so it always holds that $\lambda g(\mathbf{x})=0$, which is called complementary slackness.

Thus we can summarize all necessary conditions mentioned above as KKT Conditions,

$$\begin{array}{rlrlr}{▽}_{\mathbf{x}}f+\lambda {▽}_{\mathbf{x}}g& =\mathbf{0}\mathbf{g}(\mathbf{x})& \le 0\lambda & \ge 0\lambda g(\mathbf{x})& =0\end{array}$$

Similarly, we can also extend the conclusion to the general continuous optimization problem. The corresponding Lagrangian Function is defined as $$L(\mathbf{x},\overrightarrow{\lambda },\overrightarrow{\mu })=f(\mathbf{x})+\overrightarrow{\lambda }{!}^{\mathrm{\top }}\mathbf{g}(\mathbf{x})+\overrightarrow{\mu }{!}^{\mathrm{\top }}\mathbf{h}(\mathbf{x})$$ And it’s also convinient to write down the corresponding KKT Conditions $$\begin{array}{rlrlrl}{▽}_{\mathbf{x}}f+\overrightarrow{\lambda }{!}^{\mathrm{\top }}{▽}_{\mathbf{x}}\mathbf{g}+\overrightarrow{\mu }{!}^{\mathrm{\top }}{▽}_{\mathbf{x}}\mathbf{h}& =\mathbf{0}{g}_k(\mathbf{x})& \le 0,;;k=1,2,\cdots ,m{h}_l(\mathbf{x})& =0,;;l=1,2,\cdots ,p{\lambda }_k& \ge 0,{\lambda }_k{g}_k(\mathbf{x})& =0\end{array}$$

$\mathbf{N}\mathbf{O}\mathbf{T}\mathbf{E}.$ In order for existing a point ${\mathbf{x}}^{\ast }$ fitting the KKT Conditions, The primal question should satisfy some regular conditions, which has been listed on Wikipedia.

$\mathbf{E}\mathbf{X}\mathbf{A}\mathbf{M}\mathbf{P}\mathbf{L}\mathbf{E}.$ Minimize $x_1^2+x_2^2$ subject to $x_1+x_2=1$ and $x_2\le \alpha$, in which $x_1,x_2,\alpha \in \mathrm{\Re }$.

$\mathbf{S}\mathbf{O}\mathbf{L}\mathbf{U}\mathbf{T}\mathbf{I}\mathbf{O}\mathbf{N}.$ The corresponding Langrangian Function is $$L(\mathbf{x},\lambda ,\mu )=x_1^2+x_2^2+\lambda (x_2-\alpha )+\mu (x_1+x_2-1)$$ According to KKT Condition, there must be $$ \left { $$\begin{array}{rlrlrl}\frac{\partial L}{\partial x_1}=\frac{\partial L}{\partial x_2}& =0x_1+x_2& =1x_2& \le \alpha \lambda & \ge 0\lambda (x_2-\alpha )& =0\end{array}$$ \right. $$whichisequivalentto$$ \left { $$\begin{array}{rlrlr}{x}_1& =-\frac{\mu }{2}{x}_2& =\frac{\mu }{2}+1\mu & \le -1\mu & \le 2\alpha -2\end{array}$$ \right. $$ Now we can divide the problem into 2 cases according to whether $2\alpha -2\ge -1$ or not.

$\mathbf{C}\mathbf{A}\mathbf{S}\mathbf{E};;\alpha \ge {\displaystyle \frac{1}{2}}.$ It is easy to verify that $\mu =-1$ satisfies all KKT Conditions above, so when $x_1=x_2={\displaystyle \frac{1}{2}}$, $x_1^2+x_2^2$ takes minimum value ${\displaystyle \frac{1}{2}}$.

$\mathbf{C}\mathbf{A}\mathbf{S}\mathbf{E};;\alpha <{\displaystyle \frac{1}{2}}.$ There is $\mu =2\alpha -2$ satisfies all KKT Conditions above only, so when $x_1=1-\alpha$and$x_2=\alpha$, $x_1^2+x_2^2$ takes minimum value $1-2\alpha +2{\alpha }^2$.