If S is a convex polyhedron in a euclidean vector space U, and f:S->R is a convex function, then does f necessarily attain a maximum on S? and how would i prove it?
Consider any line segment $\displaystyle \lambda \bold{x}+(1-\lambda)\bold{y}$, $\displaystyle \lambda \in [0,1]$ which passes through the maximum of $\displaystyle f $,where $\displaystyle \bold{x}$ and $\displaystyle \bold{y}$ on $\displaystyle S$.
Because the polyhedron is convex the line segment has its end points on $\displaystyle S$ and is otherwise inside or on the poyhedron. But because $\displaystyle f$ is convex we have:
$\displaystyle
f(\lambda \bold{x}+(1-\lambda)\bold{y})\le \lambda f(\bold{x})+(1-\lambda)f(\bold{y}) \le \max(f(\bold{x}),f(\bold{y}))
$
Which proves that one of the end points is the maximum.
RonL
i was thinking about this problem, and what about the theorem that says if C is a convex set and f is a convex function on C, and if f attains its maximum on C at an interior point of C, then f is constant on C ?(proof can be found here on pg. 194: Topological Spaces: Including a ... - Google Book Search)
then wouldnt f attaining its maximum at an interior point of the set imply that there is no maximum? (since f is constant)
If f is a constant then every point is a maximum including the boundary, so no problem there.
In fact in my earlier post I did not clain (nor wish to imply) that the maximum at an endpoit of the line segment was unique.
We have the situation that you mention of the function being a constant, it is also posible if the function is linear for all the points on a face or edge etc to be maxima.
RonL
what if we consider in R^2 the convex function f(x,y)=x on the set S={f(x,y) such that y>=0}? then it does not attain its maximum on S even though y>=0 is a convex polyhedron and f is a convex function. wouldn't this be a counterexample to what we are trying to prove?
ok sorry for not stating the definition of polyhedron that i am using. basically the definition im working with is "the intersection of finitely many closed halfspaces is called a polyhedron." a closed and bounded polyhedron is called a polytope.
so under this definition, would my counterexample suffice? (i.e. would the restrictions given in the problem permit my counterexample to work?)
this is a different example. i'm asking if we have such a function that f(x,y)=x, and S is the set of all the values f(x,y) can take such that y is greater than or equal to zero, then do we have a convex polyhedron with a convex function mapping from S to R such that the maximum is not attained on S? (under the definition of polyhedron i gave)