User mark reid - MathOverflow

Solutions to a Monge-Ampère equation on the simplex

2010-02-16T23:35:27Z

Let $\Delta_k$ be the k-simplex and $\mu$ a non-negative measure over $\Delta_k$. I want to know if there exists a function $u : \Delta_k \to \mathbb{R}$ such that $u$ is convex, $u(e_i) = 0$ for all vertices $e_i$ of $\Delta_k$, and $M[u] = \mu$ where $M[u] = \det\left(\frac{\partial^2 u}{\partial x_j \partial x_k}\right)$ is the Monge-Ampère operator. Furthermore, I'd like to know if the solution is unique. Any techniques for how one might solve a specific instance of this problem would be a bonus.

My background is not in PDEs but the closest I've found to an answer seem to be in [1] and [2] where the boundary conditions are more restrictive and the domain is required to be strictly convex for uniqueness.

[1] "On the fundamental solution for the real Monge-Ampère operator", Blocki and Thorbiörnson, Math. Scand. 83, 1998

[2] "The Dirichlet problem for the multidimensional Monge-Ampère equation", Rauch and Taylor, Rocky Mountain Journal of Mathematics, 7(2), 1977.

Any other pointers to solving this type of problem would be greatly appreciated.

Are Bregman divergences quasi-convex?

2010-03-11T00:59:13Z

Given a convex set S ⊂ ℝ^d and an appropriately differentiable convex function f: S → ℝ, a Bregman divergence B_f(x, y) = f (x) - f (y) -⟨x- y , ∇f (y)⟩ for x, y ∈ S.

For any x, consider the function b(y) = B_f(x, y). It is known that this is not always convex (choose f (x) = x³ for S ⊂ ℝ) and I can show that for S ⊂ ℝ it is always quasi-convex (i.e., b(λy+(1-λ)y') ≤ max{ b(y), b(y') } for λ∈[0,1], y, y' ∈ S) but cannot prove or find a counter-example in the general case.

I've done a quick hunt around the literature on Bregman divergences but cannot find an answer either way.

Explicitly describing extreme points of infinite dimensional convex sets

2009-11-19T04:00:50Z

I am currently trying to apply some results from Choquet theory - i.e., the generalisation of results by Minkowski and Krein-Milman for representing points in a compact, convex set C by probability measures over its extreme points, ext C = { x ∈ C : C - { x } is convex }.

My main problem is with explicitly describing the set of extreme points for a particular convex set, namely the set C of concave functions over the k-simplex that vanish at the vertices of the simplex and have sup-norm at most 1. I've convinced myself that this set of functions in compact and convex and so the Choquet's theorem applies. However, apart from the case of the 1-simplex I am struggling to say anything about what the extreme functions might be.

In the case of the 1-simplex, the functions in ext C are "tents" with height 1, that is, functions f that are zero on the boundaries and rise linearly to a single point x where f(x)=1. I suspect that in the case of the 2-simplex the extreme functions are also piece-wise linear concave functions with height 1. I have considered a number of candidates (the functions formed by the taking the minimum of 3 affine functions, each zero on a different vertex) but am having trouble showing that the candidates are actually extreme.

Does anyone know of any techniques for identifying extreme points of convex sets?

Pointers to applications of Choquet's theorem that explicitly construct ext C and the probability measure for a given point in C would also be much appreciated. My reading in this area has only got me as far as Phelps' monograph "Lectures on Choquet Theory" and a survey article by Nina Roy titled "Extreme Points of Convex Sets in Infinite Dimensional Spaces".

Comment by Mark Reid

2010-03-17T23:09:26Z

Thanks for the proof—it's very well written—however, as I stated in my question, I already have a proof (indeed, it is quite similar to your own) of quasi-convexity for the case when S ⊂ ℝ. My real problem is showing it for multi-dimensional functions.

Comment by Mark Reid

2010-03-11T22:49:51Z

I had briefly tried coming at the problem via the dual but didn't get very far. Maybe I'll revisit that approach. Thanks for the suggestion.

Comment by Mark Reid

2010-02-24T05:17:02Z

By a similar degrees of freedom argument I see that specifying exactly where |u(x)|=1 won't help either. My geometric intuition about the problem has completely failed me now. I originally thought that specifying the function's values at the vertices, its "curvature" (roughly speaking) at each point, as well as its height would have determined it. However, your construction shows that there are, in fact, a whole family that satisfy those constraints when M[u] is constant. I suspect M throws away too much information about the function and my intuition is confusing it with the Hessian.

Comment by Mark Reid

2010-02-24T03:17:24Z

Thanks for the demonstration of non-uniqueness. I had already realised that M was invariant under affine transformations which is why I had required u to vanish at the vertices. Another natural constraint in my problem is that $\sup_{x\in{\Delta_k}} |u(x)|=1$. Would that give uniqueness? I suspect, at least, that the construction you give would only satisfy this extra constraint for a single value of $a$. I'll definitely have a look at the book you suggested too.

Comment by Mark Reid

2010-02-17T04:21:57Z

I also found Jerrard's "Some Remarks on Monge-Ampère functions" (2008) useful but not conclusive for my question.

Comment by Mark Reid

2010-02-17T04:15:35Z

Thanks for the pointers. I work in statistical machine learning and have recently been investigating properties of loss functions for probability estimation and their associated entropies. Many properties of losses in the binary case (i.e., k=1) can be explained by the curvature of their entropy function. The question above is an attempt to generalise some results beyond the standard binary prediction problem.

Comment by Mark Reid

2009-12-15T02:46:38Z

I've since found a paper that more or less answers my question. In case anyone else is interested it is "Extremal Convex Functions", Bronshtein, E.M., Sibirskii Matematicheskii Zhurnal, Vol. 19, No 1., 1978 springerlink.com/content/k89m467j865uw7x2

Comment by Mark Reid

2009-11-19T05:07:18Z

I'd also considered these as candidates. Does your argument show that they constitute all of ext C?

Comment by Mark Reid

2009-11-19T05:04:51Z

Regarding compactness, I think you may have a point. Those function would converge to a point that is non-zero over a vertex and thus not in C. I may have to rethink my construction.

Comment by Mark Reid

2009-11-19T05:02:24Z

If I understand your candidates in the case of the 1-simplex, these would be functions over [0,1] that are trapeziums with a flat top over [a,b]? I don't think these are extreme though - an appropriately weighted sum of "tents" plus some proportion of the 0 function (also extreme) would show these are a convex combination of other points in C.