2
$\begingroup$

My textbook came up with a solution without explanation. I'm looking for a systematic way of solving the following optimization problems and similar ones (by hand), because I'm drawing a blank:

minimize 

$$\max(x_1, x_2)$$ and after, $$x_1^2 + 9x_2^2$$

subject to 

$$2x_1 + x_2 \ge 1$$ $$x_1 + 3x_2 \ge1$$ $$x_1 \ge 0, x_2 \ge 0$$

BTW the answer is $\left(\dfrac{1}{3}, \dfrac{1}{3}\right)$.

$\endgroup$
  • $\begingroup$ Edited question to reflect second objective $f(x_1, x_2)$ function example and fix title. $\endgroup$ – JDS Mar 28 '14 at 18:05
  • $\begingroup$ @Magdiragdag the question wants to minimize objectives in the form $f(x_1, x_2)$ over the given constraints in R2. $\endgroup$ – JDS Mar 28 '14 at 18:06
  • $\begingroup$ Oh, it really wants to minimize the maximum of $x_1$ and $x_2$... $\endgroup$ – Magdiragdag Mar 28 '14 at 18:07
  • $\begingroup$ Did you draw a picture? At least of the area you're optimizing over? $\endgroup$ – Magdiragdag Mar 28 '14 at 18:08
  • $\begingroup$ What is meant by minimize $\max(x_1, x_2)$ and $x_1^2 + 9x_2^2$? Do you mean minimize $\max(x_1, x_2) + x_1^2 + 9x_2^2$? $\endgroup$ – Jared Mar 28 '14 at 18:17
2
$\begingroup$

Let us enter in the Karush–Kuhn–Tucker framework, with $$ f(x,y) = -\max(x,y);\\ g_1(x,y) = 2x+y-1;\\ g_2(x,y) = x+3y-1. $$

The Lagrangian is $$ L(x,y,\lambda) = -\max(x,y) + \lambda\cdot g(x,y) $$

and the solution is, in the region $x\neq y$ (where $L$ is smooth): $$ \begin{cases} 0&=&-1_{x>y} + 2\lambda_1 + \lambda_2 \\ 0&=&-1_{x<y} + \lambda_1 + 3\lambda_2 \\ 0&=&\min(\lambda_{i} , g_{i}(x,y)), & (i=1,2). \end{cases} $$ Hence, both $\lambda_i =0$ and the system has no solution.

In the region $x = y$,

$\max (x,y) = x$. $$L(x,y,\lambda) = -x + \lambda\cdot g(x,y) =: M(x,\lambda). $$The new system for $M$ is:

$$ \begin{cases} 0&=&-1+ 3\lambda_1 +4\lambda_2\\ 0&=&\min(\lambda_{i} , g_{i}(x,x)), & (i=1,2). \end{cases} $$ As we can't have $ g_1(x,x)=0=g_2(x,x), $ either $\lambda_1=0$ or $\lambda_2=0$, then $$ x\in\{1/3, 1/4\}. $$ But if $x=y=1/4$, $2x+y<1$ and the point is not an admissible solution.

Then the solution is $$ x=y=\frac 13;\\ \min_{g_{1,2}(x,y)\ge 0} \max(x,y) = -\max_{g_{1,2}(x,y)\ge 0} (- \max(x,y)) \\ = \max(1/3,1/3) = 1/3. $$


For the second problem, the equations are $$ \begin{cases} 0&=&-2x + 2\lambda_1 + \lambda_2 \\ 0&=&-18y + \lambda_1 + 3\lambda_2 \\ 0&=&\min(\lambda_{i} , g_{i}(x,y)), & (i=1,2), \end{cases} $$ hence $(\lambda_1,\lambda_2)\neq (0,0).$

If $\lambda_2 = 0$:

$$ \begin{cases} 0&=&-2x + 2\lambda_1 \\ 0&=&-18y + \lambda_1 \\ 1 &=& 2x+y \end{cases} $$

then $x=18y, y=1/37, x = 18/37$. Then $x+3y = 21/37<1$: this is not the solution.

The solution is such as $$ \begin{cases} 0&=&-2x + \lambda_2 \\ 0&=&-18y + 3\lambda_2 \\ 1 &=& x+3y \end{cases} $$ then $x=3y, y=1/6, x=1/2$.

$\endgroup$
  • $\begingroup$ For the first solution, I'm not understanding the last equation of the systems, with 0 = min(...). Where did that come from? The others I understand from gradient of the lagrangian $\endgroup$ – JDS Apr 1 '14 at 17:23
  • 1
    $\begingroup$ it means that if $\lambda\neq 0$ then the inequality becomes an equality; and that $\lambda \ge 0$ in general (this is actually more clear in the french version). $\endgroup$ – mookid Apr 1 '14 at 17:26
  • $\begingroup$ Is it still obtained from differentiating the lagrangian with respect to the remaining variables, i.e. lambda 1 and 2? $\endgroup$ – JDS Apr 1 '14 at 17:41
  • $\begingroup$ when you write "Is it still obtained", what is 'it'? $\endgroup$ – mookid Apr 1 '14 at 17:44
  • $\begingroup$ The final equation in the systems, 0 = min(...) $\endgroup$ – JDS Apr 1 '14 at 17:57

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.