I was working on the convex optimization MOOC from Stanford and in the geometric problems chapter I was asked to solve the following quiz
Let $P⊂R^n$ be a polyhedron described by a set of linear inequalities, and a $a$ point in $R^n$. Which of the following problems are easy to solve? Check all that apply. (Easy means the solution can be found by solving one or a modest number of convex optimization problems.)
- Find a point in $P$ that is closest to $a$ in Euclidean norm.
- Find a point in $P$ that is closest to $a$ in $l_{\infty}$ norm.
- Find a point in $P$ that is farthest from $a$ in Euclidean norm.
- Find a point in $P$ that is farthest from $a$ in $l_{\infty}$ norm.
Since a polyhedron is described by a set of linear inequalities
$$ Ax \leq b $$
which are convex. And any norm (euclidean or $\infty$) is also a convex function, I believe that the four problems can be expressed as convex problems like:
$$\min_{x}/\max_{x} \quad ||x - a||_{2/ \infty} $$ $$s.t \quad Ax \leq b $$
And therefore all the options should be correct. But to my surprise, finding the point in $P$ that is farthest from $a$ in Euclidean norm was not a correct answer. I don quite get why
Minimizing a convex function over a convex set is easy. Maximizing a concave function over a convex set is easy. Maximizing a convex function over a convex set is not generally easy.
You can maximize the infinity form by solving $2n$ linear programming problems (maximize $x_i−a_i$ or maximize $a_i−x_i$ subject to $Ax \le b$) and taking the largest. If you prefer, think of these as minimizing $-x_i+a_i$ or $-a_i+x_i$ so that these are convex minimization.