Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
add comment

1 Answer

up vote 4 down vote accepted

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

share|improve this answer
    
Thank you! I was concerned this was a bit too good to be true. (My reasoning was that were this true, one could solve any (nonlinear) strictly convex program over a polytope by first solving the unconstrained program to find the minimum, then a single quadratic program to determine the "active facet", and then the original convex program with a single linear equality constraint (that the solution be on the active facet.) Having said that - is there a name for cases where this is true? (Perhaps it is true for the standard simplices?) –  Fumiyo Eda Nov 23 '11 at 5:36
    
@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. –  Mike Spivey Nov 23 '11 at 5:41
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.