I am trying to minimize a non-linear function with both equality and non-negativity constraints numerically (not analytically) using gradient based methods and without software packages.
$f(x)=x_1^2+x_2^2 \quad $ s.t. $ \quad x_1+x_2=1,x_1>0,x_2>0$
I started out by solving a subset of the problem, which only had the equality constraint:
$f(x)=x_1^2+x_2^2 \quad $ s.t. $ \quad x_1+x_2=1$
Using a Lagrange multiplier, I minimized the following function with no problems using gradient descent and conjugate gradients:
$L(x_1,x_2,\lambda)=x_1^2+x_2^2+\lambda(x_1+x_2-1)$
As stated above, I would like to add non-negativity constraints, but I am under the impression that there are other concepts that I need to understand first. I have tried to minimize the following function, but I am certain it is incorrect:
$L(x_1,x_2,\lambda_1,\lambda_2,\lambda_3)=x_1^2+x_2^2+\lambda_1(x_1+x_2-1)-\lambda_2x_1-\lambda_3x_2$
What function should I be minimizing to satisfy all of the constraints? Do I need other concepts beyond Lagrange multipliers?
Best Answer
What you need to look at are the Karush-Kuhn-Tucker conditions.
EDIT: In your example, the non-negativity constraints $x_1 \ge 0$ and $x_2 \ge 0$ (I hope you did mean $\ge$, not $>$, otherwise you might not get any minimum) each will get a Lagrange multiplier, which is required to be nonnegative (while the Lagrange multiplier for an equality constraint can have any sign). The KKT conditions are
$$ \eqalign{-2 x_1 - \lambda_1 + \lambda_2 &= 0\cr -2 x_2 - \lambda_1 + \lambda_3 & = 0\cr \lambda_2 x_1 &= 0\cr \lambda_3 x_2 &= 0\cr x_1 + x_2 &= 1\cr x_1, x_2, \lambda_2, \lambda_3 &\ge 0\cr}$$
Case 1. If $x_1 = 0$, then $x_2 = 1\ne 0$ so $\lambda_3 = 0$. Then the first two KKT conditions say $$ \eqalign{-\lambda_1 + \lambda_2 &= 0\cr -2 - \lambda_1 &= 0\cr}$$ so $\lambda_1 = -2$ and $\lambda_2 = -2$, which is impossible.
Case 2. Similarly we find that $x_2 = 0$ is impossible.
Case 3. If $x_1 \ne 0$ and $x_2 \ne 0$, $\lambda_2 = \lambda_3 = 0$ and the first two KKT conditions give you $-2 x_1 = \lambda_1 = -2 x_2$, so $x_1 = x_2 = 1/2$; that's your only candidate for a minimum (and indeed it is the minimum).