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