2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ You have to minimize $f(\mathbf{x})$ in order to maximize $\pi_{\mathbf{w}}$. $\endgroup$ – Axel Kemper Dec 12 '17 at 8:14
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ $f(x_1,x_2,x_3)$ is not $(x_1^2 + x_2^2 + x_3^2)$ but $(x_1^2 + x_2^2 + 2x_3^2)$. $\endgroup$ – Danny_Kim Dec 12 '17 at 12:06
  • $\begingroup$ OMG, but the principle remains the same. Let me rework while you try at your end too. $\endgroup$ – Satish Ramanathan Dec 12 '17 at 12:08
  • $\begingroup$ Is there any method without defining $g_3(x_1, x_2, x_3)=x_1 \ge 0$, $g_4(x_1, x_2, x_3)=x_1 \ge 0$, and $g_5(x_1, x_2, x_3)=x_1 \ge 0$? It is too hard to solve with five multipliers. $\endgroup$ – Danny_Kim Dec 12 '17 at 12:09
  • $\begingroup$ Lagragian multipliers can stil work but it is just to be dealt with matrices $\endgroup$ – Satish Ramanathan Dec 12 '17 at 12:14
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Sorry I was wrong to convert $x$ to $w$, i.e., second inequality constraint is wrong. (not 2400 but -2400.) However, I saw your solution process, thank you $\endgroup$ – Danny_Kim Dec 13 '17 at 1:23
  • $\begingroup$ Was it helpful? $\endgroup$ – Alex Shtof Dec 13 '17 at 13:59

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.