1
$\begingroup$

I want to solve the following two-variate nonlinear programming using KKT conditions: $$ \begin{align} \begin{split} \max \quad & 15 \sqrt{x_{1}} + 16 \sqrt{x_{2}} \\ \text{s.t.} \quad & x_{1} + x_{2} \leq 120 \\ & x_{1}, x_{2} \in \mathbb{R}^+ \end{split} \end{align} $$

Two parts in the function $L(x_{1}, x_{2}, \lambda)$ are monotonically increasing, so the function is strictly concave. It is obvious that the decision variables belong to a convex set.

Point (1, 1) is a slater point, so the problem satisfies Slater's condition. The strong duality holds.

The Lagrangian function is: $$ \begin{align} \begin{split} L(x_{1}, x_{2}, \lambda) = 15 \sqrt{x_{1}} + 16 \sqrt{x_{2}} - \lambda (x_{1} + x_{2} - 120) \end{split} \end{align} $$ whose derivatives are: $$ \begin{align} \begin{split} \frac{\partial L}{\partial x_{1}} &= \frac{15}{2 \sqrt{x_{1}}} - \lambda \\ \frac{\partial L}{\partial x_{2}} &= 8 / \sqrt{x_{2}} - \lambda \\ \frac{\partial L}{\partial \lambda} &= 120 - x_{1} - x_{2} \end{split} \end{align} $$

Also: $$ \begin{align} x_1, x_2 \geq 0 \\ \lambda \geq 0 \end{align} $$

Critical points can be calculated by the symbolic math toolbox in MATLAB:

syms x1 x2 lbd
eq(1) = lbd * (120 - x1 - x2) == 0;
eq(2) = x1 * (15/2/sqrt(x1) - lbd) == 0;
eq(3) = x2 * (8/sqrt(x2) - lbd) == 0;
sol = solve(eq)

Results are (0, 0, 0), (120, 0, 0.6847), (0, 120, 0.7303), and (56.133, 63.867, 1.0010), and corresponding values of the objective function are 0, 164.3168, 175.2712, and 240.2499. So the point (56.133, 63.867, 1.0010) is chosen as the optimal solution.


Specifically, I have three questions:

  1. Is my writing good enough?
  2. Do I have to solve KKT conditions regarding inequality? MATLAB can't solve the following system of equations because of Division by zero.
eq(1) = lbd1 * (120 - x1 - x2) == 0;
eq(2) = x1 + x2 - 120 <= 0
eq(3) = x1 * (15/2/sqrt(x1) - lbd1) == 0;
eq(4) = 15/2/sqrt(x1) - lbd1 <= 0;
eq(5) = x2 * (8/sqrt(x2) - lbd1) == 0;
eq(6) = 8/sqrt(x2) - lbd1 <= 0;
  1. What if the problem becomes complicated? Are there any softwares to analyse NLPs this way?

Two minor errors pointed out by @prubin and @dhasson are not the primary issue of this post, so I have corrected them. Much appreciated.

$\endgroup$
  • 1
    $\begingroup$ Your final result seems to be good. Using LocalSolver, we obtain an optimal solution with objective value 240.25 for x1 = 56.1329076124275 and x2 = 63.8670923875725 $\endgroup$ – LocalSolver May 16 at 14:23
  • 1
    $\begingroup$ I think it should say the square root functions are concave instead of convex, but that's some minor typo. $\endgroup$ – dhasson May 16 at 16:24
  • 1
    $\begingroup$ I think you lost a "-" in your formula for $\partial L/\partial \lambda$. $\endgroup$ – prubin May 16 at 17:14
  • $\begingroup$ Just for the sake of completeness, for people who are to lazy to use lagrangian multipliers: As you are maximizing and everything is positive, the inequality can be replaced by an equality. Then we have x2 = 120 - x1. You can then replace x2 by 120-x1 in the objective, and find the root of the derivative which is x1 = 27000/481. x2 is then 30720/481. Both values global optimal and feasible as they are positive. $\endgroup$ – T_O May 17 at 13:34
6
$\begingroup$

You should use the KKT conditions (turning the sign restrictions on $x$ into constraints), but it turns out they will not affect the results. First, let me point out that $\partial L/\partial x_1$ is undefined when $x_1=0$, so you need to deal with the case $x_1=0$ (and the case $x_2=0$) separately. Given the monotonicity of $L$, you can easily show that if $x_1=0$ in an optimal solution then necessarily $x_2=120$ and vice versa. Having disposed of those cases, you can now assume that $x_1\gt 0$ and $x_2\gt 0$. In that case, the KKT multipliers for the sign restrictions will be 0 by complementary slackness, and you end up with the same solution you found above.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.