1
vote
0answers
73 views

Quickly checking an inequality on a convex region

I previously posted this question to math.sx at: http://math.stackexchange.com/questions/748015/quickly-checking-if-an-inequality-holds-on-a-convex-region but I'm thinking that MO may be more ...
1
vote
0answers
77 views

Maximizing an integral over a convex region

Let $C$ denote a compact, convex region in the plane containing the origin with unit area, and let $f$ be a probability distribution on $C$. Let $f^\ast$ denote the distribution that maximizes the ...
1
vote
2answers
143 views

What is the dual of an semidefinitely representable (SDR) cone?

The Question Let $V\simeq \mathbb{R}^r$ be an $r$-dimensional vector space with the usual Euclidean inner product. Let $\mathcal K\subset V$ be a cone defined as $$ \mathcal K=\Big\{x\in ...
4
votes
0answers
117 views

Convexified threshold of a function

Upd. The question in a nutshell: find convex set on plane which is «closest» to a given non-convex set. It is given integrable function $0\leq f(x,y)\leq 1$ with bounded support: $f(x,y)=0$ when ...
11
votes
3answers
462 views

finding the most-isolated point in a high-dimensional cube

I have a set of points {$x_1,\ldots,x_n$} located in the d-dimensional unit cube $[0,1]^d$. $n$ is about 1000 and $d$ is about 25. I'd like to find $\max_{\omega\in [0,1]^d}\min_{i=1,\ldots,n} ...
2
votes
1answer
356 views

faces of a polytope

Let $a_1,a_2,..,a_n\in\mathbb{R}^m$, $n>m$ and the points are in general position meaning, no hyperplane contains more than $m$ points. Define a polyhedron $$P=\{x\in\mathbb{R}^m:a_1'x\leq0, ...
3
votes
3answers
746 views

Minimum norm of convex hull

Dear all, I am currently stuck at a problem which seems too easy to be stuck at to me... Summary Let $H$ be the convex hull of the points $d_1,\ldots, d_n\in \mathbb{R}^d$. How can one compute ...
2
votes
1answer
350 views

A min-max formula for depth of the origin in a convex set

Depth is defined as the distance to the boundary of a set, i.e., $\operatorname{depth}(x, C) = \operatorname{dist}(x, \mathbb{R}^n \backslash C)$. Let $C$ be a convex set that contains the origin. I ...
0
votes
3answers
514 views

a different algebra/representation for convex sets

Hi, I was dealing with finding a feasible region for a set of norm inequalities and the feasible region is convex. The question is not about how to find the feasible region but how to represent the ...
2
votes
1answer
614 views

Condition number for Ellipsoid method matrix

Hello, When using the ellipsoid method (for solving a linear program for example), the volume of the ellipsoid at each iteration is proven to decrease, and do so by at least a factor of $e^{1/2n}$. ...