Lagrange multipliers - hard one

Question

Given set $D=\{x\in\mathbb{R}^2:x_1^2+44x_2^2\le5\}$ and function $f:D\rightarrow\mathbb{R}$ given us $f(x)=13x_1-22x_2$. I have to find supremum and infimum of $f$ and tell whether they are reached by $f$ in $D$ and in any interior point of D. When we focus only on $D'=\{x\in\mathbb{R}^2:x_1^2+44x_2^2=5\}$ we can use Lagrange multipliers but the original problem is much harder. How to solve this?

Answer 1

The theory of inequality-constrained optimization is very well-developed (particularly for convex problems such as yours). However you can solve your particular problem with the following elementary observation: every extremum of $f$ is either

1. on the active set $\partial D$ (which you say you know how to solve), or
2. on the interior of the feasible set.

Do you see why $f$ can't possibly have extrema on the interior of $D$?

---

Here's a bit more explanation. Suppose you are trying to solve

$$\min_x f(x)\quad \textrm{s.t.}\quad g(x) \geq 0.$$

A (local) solution to this optimization problem must be of one of the two following types:

1. A critical point of $f$ inside the feasible region, i.e. $$\nabla f = 0, \quad g > 0.$$
2. A point on the boundary of the feasible region, but where the function $f$ cannot decrease further without leaving the feasible region because its negative gradient points straight out of the feasible region. Since $\nabla g$ is perpendicular to level sets of $g$, a convenient way of encoding this condition -- that $f$'s gradient is perpendicular to the boundary -- is that $\nabla f = \lambda \nabla g$ for some $\lambda \geq 0$. So in other words, the conditions for this case being true are that $$g = 0, \quad \nabla f = \lambda \nabla g, \quad \lambda \geq 0$$ for some $\lambda.$

Finally notice that both conditions can be encoded simultaneously by the variational problem $$\underset{x, \lambda}{\operatorname{ext}} f(x) - \lambda g(x) \quad \textrm{s.t.} \quad \lambda \geq 0,$$ and this is the extension of the method of Lagrange multipliers to inequality constraints. However, the variational problem merely encodes the same information as in the two cases analyzed above; and in your case it is very easy to treat these two cases directly. The method of Lagrange multipliers in the form I've written above is mostly useful for problems with very large numbers $m$ of constraints, where directly checking all $2^m$ possible active sets is intractable.