MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Assume that $u$ is a function in some domain $\Omega$ in $\mathbb{R}^d$ satisfying restrictions like $u(0)=0$ and $\nabla u\in P$ in any point, where $P$ is a given polytope (for example, constraints are $\partial u/\partial x_i\in [0,1]$ and $\sum \partial u/\partial x_i\leq 2$ or like so). We have to minimize the integral functional like $\int_{\Omega} \langle\nabla u(x),F(x)\rangle dx$ with some function $F$, which may change sign and so on. A priori minimum should be attained in an extreme point of the convex set of our admissible functions $u$. But is there any nice description of the set of extreme points? Clearly, in any inner point of $\Omega$ the gradient must lie on the boundary of $P$, because else we may vary $u$ by a small function supported in the small neighborhood of such a point. But this looks like not sufficient at all, because one equality like $\partial u/\partial x_1=0$ still leaves many degrees of freedom for possible variations, the problem is that they are no longer local.

share|cite|improve this question
I think the answer depends a lot on the acutal polytope. If this is formulated by $A\nabla u(x)\leq b$ then you should look closer on the set of $A\nabla u(x)\leq 0$. – Dirk Feb 17 '12 at 7:54
The polytope is described as $\{(p_1 ,\dots,p_d): 0\leq p_i\leq 1,\sum p_i\leq k\}$ for some fixed k∈[0,d]. It may be described in such a way for natural matrix $A$ with $2d+1$ rows. – Fedor Petrov Feb 17 '12 at 12:57

Your Answer


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

Browse other questions tagged or ask your own question.