6
$\begingroup$

Suppose one has a convex, bounded polytope P $\subset R^n$ and a strictly convex function $f$ defined everywhere on $R^n$. $f$ has a unique minimum; and suppose this minimum occurs somewhere strictly outside P, at a point x $\in R^n$.

Let's define two points on the boundary of P, which are in general distinct.

The first point, N, is the projection of x onto P, by which I mean that N is a point on P's boundary which minimizes the distance (in any norm, but say $l_2$) to x.

The second point, M, is the point on P's boundary which minimizes the function $f$ when restricted to P.

I think that N and M are always on the same facet of P. (By "on a facet" I include the (lower dimensional) "edges" of the facet.) My question is: is this true in general?

Here is an illustration of the following concrete example. Suppose we are in $R^2$, with $f(a,b) = a^2 + 4(b-4)^2$. Suppose that P is given by the four half-planes $a+b \le 7$, $2b-a \le 4$, $a \gt 0$, $b \gt 0$. This looks like:

Here's a picture of this situation:

http://imgur.com/tQ6Rp.png

The minimum of $f$ occurs at x = (0,4). In this case, we see that N and M are indeed on the same facet of P. Is this relationship true in general?

1 Answers 1

4

It's false. To see that, introduce the new constraint $10b - 7a \leq 17$ to your example to create a new polytope $P'$. This constraint cuts off the point $N$ but keeps $M$ in $P'$. Thus $M$ minimizes $f$ over $P'$. The closest point to $x$ on $M$'s facet is now $(1.5, 2.75)$, which is the intersection of the lines $10b-7a=17$ and $2b-a=4$. However, the point $(1,2.4)$, which is on the new facet defined by $10b-7a=17$, is closer to $x = (0,4)$ than is $(1.5, 2.75)$ (a distance of $\approx 1.89$ vs. $\approx 1.95$).

For example, the image below shows the new polytope $P'$. The minimizer of $f$ over $P$ is $M$, which is in blue. The point $(1,2.4)$, in black, is closer to $(0,4)$, in red, than is any point on $M$'s facet.

enter image description here

  • 0
    @Fumiyo Eda: That would be nice - and, as you say, too good to be true. :) Perhaps another way to think about this is that $M$ and the closest point in $P$ to $x$ are the solutions to two *different* optimization problems. From that point of view maybe it's not surprising that if you look hard enough you can find an example in which they're not on the same facet. I'm not sure about a name for cases in which this does hold true. Characterizing those cases might make for an interesting problem, though.2011-11-23