How to minimize $\max(x_1, x_2)$ and $x_1^2 + 9x_2^2$ subject to constraints?

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)$.

• Edited question to reflect second objective $f(x_1, x_2)$ function example and fix title. – JDS Mar 28 '14 at 18:05
• @Magdiragdag the question wants to minimize objectives in the form $f(x_1, x_2)$ over the given constraints in R2. – JDS Mar 28 '14 at 18:06
• Oh, it really wants to minimize the maximum of $x_1$ and $x_2$... – Magdiragdag Mar 28 '14 at 18:07
• Did you draw a picture? At least of the area you're optimizing over? – Magdiragdag Mar 28 '14 at 18:08
• 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$? – Jared Mar 28 '14 at 18:17

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$.

• 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 – JDS Apr 1 '14 at 17:23
• 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). – mookid Apr 1 '14 at 17:26
• Is it still obtained from differentiating the lagrangian with respect to the remaining variables, i.e. lambda 1 and 2? – JDS Apr 1 '14 at 17:41
• when you write "Is it still obtained", what is 'it'? – mookid Apr 1 '14 at 17:44
• The final equation in the systems, 0 = min(...) – JDS Apr 1 '14 at 17:57