How to solve the optimization problem?

Question

The original problem is to find nonnegative $\mathbf{w}=(w_1, w_2, w_3)$ that maximizes $$\pi_{\mathbf{w}}=\frac14(p_1-w_1)+\frac14(p_2-w_2)+\frac12(p_3-w_3)$$ subject to $$\frac14\sqrt{w_1}+\frac14\sqrt{w_2}+\frac12\sqrt{w_3}-600 \ge 400$$ and $$\frac14\sqrt{w_1}+\frac14\sqrt{w_2}+\frac12\sqrt{w_3}-600 \ge \frac12\sqrt{w_1}+\frac14\sqrt{w_2}+\frac14\sqrt{w_3}-0,$$ where $p_1$, $p_2$, and $p_3$ are given as $1$ million, $4$ million, and $9$ million dollars, respectively.

My professor solved this problem very easily. he said when $w_1=0$ and $w_3=5760000$, the second inequality is satisfied. So is the first inequality. Hence, $(w_1, w_2, w_3)=(0,0,5.76 \text{ million})$ and the total utility becomes $2.87$ million dollars.

---

First, I remove $p_i$'s in the objective function because it does not affect the optimal $w_i$'s.

Then, I normalize constant values.

Finally, I substitute $\sqrt{w_i}$'s with $x_i$'s in order to remove root terms.

Hence, I obtained a problem that finds nonnegative $\mathbf{x}=(x_1, x_2, x_3)$ that maximizes $$f(\mathbf{x})=x_1^2 + x_2^2+ 2x_3^2$$ subject to $$x_1+x_2+2x_3 \ge 4000$$ and $$-x_1 + x_3 \ge 2400.$$

---

I tried to solve the problem with five inequality constraints (additional $x_1\ge0$, $x_2\ge0$, and $x_3\ge0$) using KKT condition.

However, it is so complicated because there are three equality equations from $\nabla L$, where $L$ is a Laplacian equation, five original ineqaulities, five Lagrangian multiplier $\lambda_i$'s inequalities, and five complementary slackness equalities.

Is there any method to solve the problem easily?

Answer 1

I have used Lagragian Multiplier's method to find the minimum of $f(x_1,x_2,x_3)$.

$f(x_1,x_2,x_3)) =x_1^2+x_2^2+2x_3^2$

$g_1(x,y) = x_1+x_2+x_3\ge{4000}$

$g_2(x,y) = x_3-x_1\ge{2400}$

$\nabla f = \lambda \nabla g_1 + \mu \nabla g_2$

$<2x_1, 2x_2,4x_3> = \lambda<1,1,1> + \mu<-1,0,1>$

$\lambda - \mu = 2x_1$

$\lambda = 2x_2$

$\lambda + \mu = 4x_3$

When you substitute the values of $ x_1, x_2, x_3$ in $g_1$ and $g_2$

you solve for $\lambda$ and $\mu$

I get $\lambda = \frac{28800}{7}$ and $\mu = \frac{32000}{7}$

Find $x_1, x_2, x_3$

Finally plug the values of $x_i$'s in the minimization problem and you will find $\pi_w$

I get $x_1 = -\frac{2000}{7}$, $x_2 = \frac{14400}{7}$, $x_2 = \frac{15200}{7}$

And I get $\pi_w = 2321428.57\approx 2.32$ million

Answer 2

First, note that your attempt contains a small mistake - the function you maximize should be $$ \hat{f}(\mathbf{x}) = -x_1^2 - x_2^2 -2x_3^2, $$ or, equivalently, minimize $$ f(\mathbf{x}) = -\hat{f}(\mathbf{x}) = x_1^2 + x_2^2 + 2x_3^2 $$

Now, the problem is the following QP: $$ \begin{aligned} \underset{\mathbf{x} \in \mathbb{R}^3}{\text{minimize}} &\quad x_1^2 + x_2^2 + 2x_3^2 \\ \text{s.t.} &\quad -x_1-x_2-2x_3\leq -4000 \\ &\quad x_1 - x_3 \leq 2400 \\ &\quad \mathbf{x} \geq \mathbf{0} \end{aligned} $$

I do not know how to solve it analytically, but I will solve it graphically using duality. Writing the Lagrangian $L(\mathbf{x}, \mathbf{y})$ with Lagrange multipliers $y_1, y_2$ for the first two constraints, and finding the dual objective, results in: $$ \begin{aligned} q(\mathbf{y}) &= \min_{\mathbf{x} \geq 0} L(\mathbf{x}, \mathbf{y}) \\ &= \min_{x_1 \geq 0} \{ x_1^2 - (y_1 - y_2) x_1 \} + \min_{x_2 \geq 0} \{ x_2^2 - y_1 x_2 \} + \min_{x_3 \geq 0} \{ 2x_3^2 - (2y_1 + y_2) x_3 \} + 4000 y_1 - 2400 y_2 \\ &= -\tfrac{1}{4} \max(0, y_1 - y_2)^2 - \tfrac{1}{4}\max(0, y_1)^2 - \tfrac{1}{8} \max(0, 2y_1 - y_2)^2 + 4000 y_1 - 2400 y_2 \end{aligned} $$ with $$ x_1 = \tfrac{1}{2} \max(y_1 - y_2, 0), \quad x_2 = \tfrac{1}{2} \max(y_1, 0), \quad x_3 = \tfrac{1}{4} \max(2y_1 + y_2, 0) $$ being the minimizers. Thus, can recover the optimal $\mathbf{x}$ using the formulas above after having solved the following dual: $$ \max~q(\mathbf{y}) \quad \text{s.t. } \mathbf{y} \geq 0 $$ Plotting the contours of $q(\mathbf{y})$ on the positive orthant and zooming into the maximizer using e.g. MATLAB results in $y_1 = 2000, y_2 = 0$ being the optimal solution. Recovering the optimal $\mathbf{x}$ results in $$ x_1 = x_2 = x_3 = 1000 $$ Now, you can prove that the above is the minimizer by noting that both are primal and dual feasible, and both objective values are equal.