The tag has no wiki summary.

learn more… | top users | synonyms

5
votes
1answer
312 views

A question on the Mahler conjecture

In its asymmetric version, the Mahler conjecture states that if $K \subset \mathbb{R^n}$ is a convex body containing the origin as an interior point and $$ K^* := \{y \in \mathbb{R}^n : \langle y, x ...
1
vote
1answer
228 views

When does the finite union of convex sets have a hole in it?

Let $f_1, \dots, f_j$ be convex functions from $\mathbb{R}^n \to \mathbb{R}$. I am trying to develop a test that decides whether or not the set $\{x | f_1(x) \le k_1\} \cup \dots \cup \{x | f_n(x) ...
3
votes
1answer
101 views

What is the doubling dimension of convex functions?

I am interested in the complexity of convex functions, specifically the "doubling dimension" of the class of convex functions defined on a compact subset of Euclidean space, when compared using the ...
3
votes
2answers
356 views

Is Ryser's conjecture on permanent minimizers still open?

Let $A(k,n)$ be the set of $\{0,1\}$ matrices of order $n$ with all their line sums equal to $k$. Conjecture number 5 on the list from Minc's book, attributed to Ryser, says that if $A(k,n)$ ...
3
votes
0answers
84 views

Covering points with a convex hull

Consider a set of $n$ points $x_1,\ldots,x_n \in \mathbb{R}^d$, for some $n \gg d$. Suppose $\{x_1,\ldots,x_n\} \subset C \subset \mathbb{R}^d$. Say that a set of points $y_1,\ldots,y_m \in C$ covers ...
0
votes
1answer
187 views

Extensions of Carathéodory's theorem

We know about the Carathéodory's theorem which is on the convex bodies of $\mathbb{R}^d$. My question is, how far we can extend it? Is it true for say, any convex object of Banach space, or for convex ...
5
votes
1answer
215 views

Monotonicity of Loewner ellipsoid?

Given two $0$-symmetric convex bodies $K \subset L \subset \mathbb{R}^n$, is it true that the Loewner ellipsoid of $K$ is contained in the Loewner ellipsoid of $L$? I have just finished proving a ...
4
votes
1answer
465 views

Why are all these families of polynomials finally log-concave?

This started when I was examining certain families of unimodal polynomials, i.e. $\sum_{k=0}^n a_kx^k$ where $a_0\le a_1\le\cdots \le a_k\ge\cdots \ge a_n$. (Notation: in the following, the $a_k$ ...
3
votes
1answer
306 views

Possible to find a set of log-concave functions with log-concave sums?

While the set of log-convex functions is closed under addition, the set of log-concave functions is not. Yet if $f$ is log-concave, $\ln(k f) = \ln(k)+\ln(f)$, with $k \in \mathbb{R}^+$ constant, is ...
2
votes
0answers
43 views

Conditions under which a set of points have a low weight representation under some basis

Let $S \subset R^d$ be a convex polytope in $d$ dimensional real space. Say that $S$ has weight $w$ if there exists some basis $x_1,\ldots,x_d$ such that for every point $v \in S$, we can write $v = ...
6
votes
2answers
153 views

On the convexity of element-wise norm 1 of the inverse

Question first asked on math.stackexchange here: http://math.stackexchange.com/questions/317209/on-the-convexity-of-element-wise-norm-1-of-the-inverse On the convexity of element-wise norm 1 of the ...
2
votes
0answers
70 views

Fastest 'Oracle' Algorithm for satisfying a single linear constraint on a convex set?

In this paper by Arora, Hazan, and Kale (http://www.cs.princeton.edu/~arora/pubs/MWsurvey.pdf) a method is given for using the Multiplicative Weights Update algorithm to quickly solve Linear Programs ...
5
votes
2answers
285 views

How do you prove that every curve of constant width is convex?

Cross-posted from math.stackexchange: Let C be a simple closed plane curve and let D be its interior. Recall that the width of C in a direction θ is the distance between two supporting lines for D ...
3
votes
1answer
157 views

Support Functions Of 3D Convex Bodies In Spherical Polar Coordinates

What are the known sufficient conditions,analagous to the planar curvature condition, in terms of functions of theta and phi, on the support function h(theta,phi) of a surface in 3D which imply it is ...
1
vote
1answer
212 views

Covering the cone of positive semidefinite matrices by intervals

Is it possible to cover the cone of positive semidefinite matrices by a finite/countable/interesting family of closed intervals of matrices? How about a general convex cone? For the finite case the ...
4
votes
5answers
296 views

Characterizing Convex Configurations of Quadrupels of Coplanar Points via Linear (In-)equalities between Distance Sums or Differences

Given 4 points $A$, $B$, $C$ and $D$ in general position in the euclidean plane, is it possible to determine from the 6 distances $AB$, $BC$, $CD$, $AD$, $AC$ and, $BD$ alone, whether every point is a ...
2
votes
1answer
222 views

another diameter-perimeter-area inequality

Recently I learnt that $$ \inf\frac{diam(C)(per(C)-2diam(C))}{area(C)}=0$$ where the infimum is taken over all plane convex bodies $C$ (say, with non-zero area). In other words, there is no ...
3
votes
2answers
270 views

a diameter-perimeter-area inequality for convex figures

Is the following inequality known? I believe it's true, but I could find no reference. For any convex body $C$ in the plane we have $$\left(4-\frac{8}{\pi}\right)area(C)\leq > ...
4
votes
0answers
158 views

Convex bodies with symmetric shadows.

Theorem. If all orthogonal projections of a convex body $K \subset \mathbb{R}^n$ onto $2$-dimensional subspaces have a center of symmetry, then $K$ has a center of symmetry. This is a classic result ...
0
votes
0answers
76 views

Convexity of a Certain Set of Covariance Matrices

Hello, My question is about a certain set of matrices being convex or not. I'll start with some preliminaries in order to define myself properly. Let $X_1,U,X_2$ be three zero-mean Gaussian random ...
4
votes
1answer
198 views

Extreme rays in the cone of (semi)metrics

How many extreme rays are there on the polytopal cone formed by all semimetrics on a set with $n$ elements? Some background. Given a set $X$ with $n$ elements, the set of all semimetrics $d:X \times ...
0
votes
1answer
142 views

Convex functions: bounding the difference

Suppose you are given a convex function $f: R^d \rightarrow R$. Let us say you are given $x,x' \in R^d$ and $x_1, x_2, \ldots, x_n \in R^d$ such that $$\sum_{i=1}^n (x_i - x') = x - x'.$$ Is it ...
3
votes
1answer
184 views

When are cones of matrices “generated” by vectors?

The cone $P_{n}$ of positive semidefinite matrices of order $n$ can be represented in this form: $P_{n}=\{A|\forall x\geq 0: \langle A,xx^{T}>0 \rangle \}$ with $x$ running over ...
11
votes
2answers
414 views

A problem on convex geometry

Consider a convex body $K \subset \mathbb{R}^n$ containing the origin in its interior. Although the body is not necessarily symmetric, let us say that two points in its boundary $\partial K$ are ...
7
votes
0answers
340 views

Minkowski's Inequality for Integrals in Orlicz spaces

EDIT: I have changed the question to have less parameters, fitting it into the context of Orlicz spaces. Suppose $f:[0,\infty)\to[0,\infty)$ is convex and increasing, ...
11
votes
1answer
387 views

Convex cones and self-duality

Consider the Euclidian space $E_n={\mathbb R}^n$, with standard scalar product $$x\cdot y=x_1y_1+\cdots+x_ny_n.$$ A closed convex cone $\Gamma\subset E_n$ defines an order by $y\ge x$ iff ...
2
votes
2answers
346 views

Convex upper bound on a linear-fractional function

I have a function of the form $f(x,y) = \frac{x}{c+y}$ where $c$ is a positive constant, $c \ge x \ge 0$, and $y \ge 0$. I would like to find a convex upper-bound for this function. Is there a ...
1
vote
1answer
136 views

Smallest Lipschitz constant on non-convex domains

It is well known that if a function $f:U\to \mathbb C^n$, $U\subset \mathbb C^m$ satisfies $\sup_{x\in U}\|Df(x)\|_{\infty} = C < \infty$ uniformly on $U$ and $U$ is compact and convex, then $f$ is ...
2
votes
3answers
391 views

A consequence of convexity

Let $f:\mathbb{R}\to\mathbb{R}$ a convex decreasing function. Let $x_0 < x_1 < x_2$. Studying the behaviour of the difference quotient, it is clear that $$f(x_0)-f(x_2) \leq M (f(x_0)-f(x_1))$$ ...
9
votes
2answers
226 views

Can you see smoothness of the boundary of a convex body from its shadow?

Let $d \geq 3$ and suppose that $K \subset \mathbb{R}^{d}$ is a convex body (compact, convex, non-empty interior). Is the following true? The boundary $\partial K$ is a $C^1$-manifold if and only ...
3
votes
2answers
349 views

Convexity in $\{0,1\}^n$

how is convexity defined in a subset $A \subset \{0,1\}^n$? furthermore, is there any extention of the Brunn-Minkowski inequality for subsets of $\{0,1\}^n$? thanks. Edit (previously posted as an ...
0
votes
0answers
182 views

Geometric Mean of Positive Matrices

Hello all, My question regards the geometric mean (GM) of two positive matrices. The definition of the GM for two positive matrices $(A,B)$ is given by: ...
0
votes
1answer
140 views

necessary and sufficient conditions for a function to be DC

Hi, Does anyone know the necessary and sufficient conditions for a function to be a DC-function? Definition: A function is a DC-function if and only if it can be written as a differnece of 2 convex ...
2
votes
1answer
138 views

When a semigroup extension $S \times A$ of a semigroup $S$ with a commutative group $A$ contains a copy of $S$?

Maybe is a trivial question, but I don't know how to handle it. Setting: Let $S$ be a semigroup (i.e. has an associative operation with neutral element $e$) and let $(A,+)$ be a commutative group ...
8
votes
1answer
597 views

Approximating a convex function by a piecewise linear function

Suppose I have a Lipschitz-continuous convex function $f:\mathbb{R}^n\rightarrow \mathbb{R}$. I wish to approximate it on the unit ball by a piecewise-linear function $g:\mathbb{R}^n\rightarrow ...
2
votes
0answers
134 views

A subclass of log-concave functions satifying a sum inequality

Suppose $f:[0,\infty)\to[0,\infty)$ is continuous and for all positive integers $m$ and real $x\geq0$, $\alpha,\beta>0$: $$ ...
7
votes
0answers
200 views

Is $Q_n(x)=\sigma_{n+1}(x)/\sigma_n(x)$ logarithmically convex on $\mathbf{R}$?

In 1975 J. van de Lune considered the monotony properties of the canonical Riemann Upper and Lower sums for $\int_0^1 t^xdt$, with $x>0$. Writing $\sigma_n(x) := 1^x+2^x+\cdots+n^x$ these sums are ...
7
votes
2answers
269 views

Duality between extremal points and extremal maps

Suppose I have a convex set $C\subset\mathbb{R}^n$ such that $0\in C$ and every Cauchy sequence in $C$ converges in $C$, but $C$ need not be bounded. (Actually I want unbounded $C$). Consider the set ...
0
votes
1answer
103 views

Is these two optimization problems share the same solution?

Hello all, I am dealing with some SDP optimization, and I come across the following problem. The optimization problem is given by \begin{aligned} &\operatorname*{min}_{t_1,\ldots,t_m,X}\ \sum ...
6
votes
1answer
3k views

Eigenvalues of product of two symmetric matrices

This is mostly a reference request, as this must be well known! Let $A$ and $B$ be two real symmetric matrices, one of which is positive definite. Then it is easy to see that the product $AB$ (or ...
1
vote
1answer
321 views

Question regard checking convexity by “restriction to any line that intersects the function domain”

Hello all, I have a question (probably stupid one) about the fact that " A function is convex if and only if it is convex when restricted to any line that intersects its domain". In Stephen Boyd and ...
0
votes
1answer
798 views

Is a jointly convex function of x and y convex as a function of x when y=z(x)?

Hi, Suppose that $x \in R^m, y \in R^n, z(x) \in R^n$, and $f(x,y)$ is convex in $(x,y)$. Is $f(x,z(x))$ a convex function in $x$ for arbitrary continuous functions $z(x)$? Thanks!
1
vote
2answers
283 views

non convex optimization

Hi there, In my studies I come up with this nonconvex optimization problem argmin |Ax|_2+lamda*|x|_1 subject to x'x=1 where cost function is nonsmooth but convex and the constrant in nonconvex. I ...
0
votes
1answer
160 views

(probably simple) optimization question

Suppose you have a concave function defined over a non-polyhedral convex cone and you are interested in the infimum. What would be standard approaches to tackle the question? (The cone is actually PSD ...
2
votes
1answer
388 views

Proving that a specific function is quasiconvex

Hello all, Assume we have a sequence of quasiconcave functions (in $X$) denoted by $f_{i,j}(X)$ for $i,j = 1,\ldots,n$. Denote by $F(X)$ the $n\times n$ matrix whose $(i,j)$ entry is the function ...
1
vote
1answer
255 views

Conjecture that two nested convex curves have a point with the same slope

I'm trying to prove a conjecture and need some help. Consider a continuous, twice differentiable function $p(a)$ such that $p(0) = 0$ and $\forall a$, $p'(a) > 0$ and $p''(a) < 0$ and $p$ is ...
3
votes
1answer
168 views

Are faces of a compact, convex body “opposed” iff their extreme points are pairwise “opposed”?

Let $P$ be a compact, convex subset of $\mathbb{R}^n$ (infinite-dimensional generalisations welcome, but not necessary). Let's say that disjoint subsets $W_1$, $W_2$ $\subset P$ are opposed if there ...
7
votes
3answers
273 views

Characterising semi-definite positiveness on vectors with non-negative entries

My problem is to characterise (or find useful information on) the cone $C$ of $N\times N$ matrices $M$ ($N\geq 1$) such that $$V^t M V\geq 0$$ for every vector $V $ with non-negative entries. Is this ...
20
votes
1answer
1k views

A Weak Form of Borsuk's Conjecture

Problem: Let P be a d-dimensional polytope with n facets. Is it always true that P can be covered by n sets of smaller diameter? Background and motivation The Borsuk conjecture (disproved in ...
4
votes
1answer
277 views

Going in the direction of the gradient

First, a motivating example. Suppose $f(x)$ is convex, differentiable, with a single minimum $x^*$. Then the differential equation $$\dot{x}(t) = -\nabla f(x(t))$$ drives $x(t)$ to $x^*$. Now my ...