Constraints

Recall that a general optimization problem is of the form

$$\begin{array}{rlr}& \underset{x}{\mathrm{minimize}}& f(x)\\ & \text{subect to}& x\in \mathcal{X}.\end{array}$$

The feasible set $\mathcal{X}$ is an example of a constraint. Our goal is to transform constrained problems into unconstrained problems. Typically constraints are not presented with feasible sets, but instead a collection of equalities and inequalities.

Often times bound constraints can be removed by transforming $x$. For example, the bound constraint $a\le x\le b$ can be removed by letting

$$x=t_{a,b}(\hat{x})=\frac{b+a}{2}+\frac{b-a}{2}\left(\frac{2\hat{x}}{1+{\hat{x}}^2}\right).$$

For example,

$$\begin{array}{rlr}& \underset{x}{\mathrm{minimize}}& x\sin (x)\\ & \text{subject to}& 2\le x\le 6\end{array}$$

is equivalent to

$$\underset{\hat{x}}{\mathrm{minimize}}\left(4+2\left(\frac{2\hat{x}}{1+{\hat{x}}^2}\right)\right)\sin \left(4+2\left(\frac{2\hat{x}}{1+{\hat{x}}^2}\right)\right)$$

Some equality constraints can be reduced by solving for $x_n$ given $x_1,\dots ,x_{n-1}$. For example,

$$\begin{array}{rlr}& \underset{x}{\mathrm{minimize}}& f(x)\\ & \text{subject to}& c_1{x}_1+c_2{x}_2+\cdots +c_n{x}_n=0\end{array}$$

is equivalent to

$$\underset{x_1,\dots ,x_{n-1}}{\mathrm{minimize}}f\left(x_1,\dots ,x_{n-1},\frac{1}{c_n}\left(-c_1{x}_1-c_2{x}_2-\cdots -c_{n-1}{x}_{n-1}\right)\right)$$

given that $c_n\ne 0$.

Lagrange Multipliers

The method of Lagrange multipliers is to solve problems of the form

$$\begin{array}{rlr}& \underset{\text{x}}{\mathrm{minimize}}& f(\text{x})\\ & \text{subject to}& h(\text{x})=0\end{array}$$

where $f$ and $h$ have continuous partial derivatives. Recall that the gradient of a function at a point is perpendicular to the contour line of that function through said point. So the gradient of $h$ is perpendicular to the contour line $h(\text{x})=0$.

Thus, we seek the best $\text{x}$ that satisfies the constraint $h(\text{x})=0$ and

$$\nabla f(\text{x})=\lambda \nabla h(\text{x})$$

for some Lagrange multiplier $\lambda$.

We define the Lagrangian as the multivariate function

$$\mathcal{L}(\text{x},\lambda )=f(\text{x})-\lambda h(x).$$

Notice that

$${\nabla }_{\text{x}}\mathcal{L}(\text{x},\lambda )=\nabla f(\text{x})-\lambda \nabla h(\text{x})$$

and ${\nabla }_{\lambda }\mathcal{L}(x,\lambda )=-h(\text{x})$. Thus, solving $\nabla \mathcal{L}(\text{x},\lambda )=0$ solves both $h(\text{x})=0$ and $\nabla f(\text{x})=\lambda \nabla h(\text{x})$.

Example

Consider the following problem:

$$\begin{array}{rlr}& \underset{\text{x}}{\mathrm{minimize}}& -\exp \left(-{\left(x_1{x}_2-\frac{3}{2}\right)}^2-{\left(x_2-\frac{3}{2}\right)}^2\right)\\ & \text{subject to}& x_1-x_2^2=0.\end{array}$$

We start by forming the Lagrangian

$$\mathcal{L}(x_1,x_2,\lambda )=-\exp \left(-{\left(x_1{x}_2-\frac{3}{2})\right)}^2-{\left(x_2-\frac{3}{2}\right)}^2\right)-\lambda (x_1-x_2^2)$$

and compute the gradient

$$\begin{array}{rl}\frac{\partial \mathcal{L}}{\partial x_1}& =2x_{2}f(\text{x})\left(\frac{3}{2}-x_1{x}_2\right)-\lambda \\ \frac{\partial \mathcal{L}}{\partial x_2}& =2\lambda x_2+f(\text{x})\left(-2x_1(x_1{x}_2-\frac{3}{2})-2(x_2-\frac{3}{2})\right)\\ \frac{\partial \mathcal{L}}{\partial \lambda }& =x_2^2-x_1.\end{array}$$

Setting the gradient to zero and solving yields $x_1\approx 1.358$, $x_2\approx 1.165$ and $\lambda \approx 0.17$.

The method of Lagrange multipliers can be extended to multiple equality constraints. For example, the problem

$$\begin{array}{rlr}& \underset{\text{x}}{\mathrm{minimize}}& f(\text{x})\\ & \text{subject to}& h_1(\text{x})=0\\ & & h_2(\text{x})=0\end{array}$$

is equivalent to

$$\begin{array}{rlr}& \underset{\text{x}}{\mathrm{minimize}}& f(\text{x})\\ & \text{subject to}& h_1(\text{x}{)}^2+h_2(\text{x}{)}^2=0\end{array}$$

Giving the Lagrangian of

$$\mathcal{L}(\text{x},{\lambda }_1,{\lambda }_2)=f(\text{x})-{\lambda }_1{h}_1(\text{x}{)}^2-{\lambda }_2{h}_2(\text{x}{)}^2$$

Or in general with $\ell$ Lagrange multipliers and $\ell$ equality constraints:

$$\mathcal{L}(\text{x},\mathbf{\lambda })=f(\text{x})-\sum _{i=1}^{\ell }{\lambda }_i{h}_i(\text{x})=f(\text{x})-{\mathbf{\lambda }}^{\top }\text{h}(\text{x}).$$