The convexity tag has no wiki summary.

**1**

vote

**2**answers

211 views

### On a version of gradient descent

I am trying to read this paper and have gotten stuck. The author considers the problem of minimizing a convex function whose gradient has Lipschitz constant $M$ and considers the scheme
$$ x(t+1) = ...

**1**

vote

**1**answer

79 views

### Constrained minimum maximal distance.

Let $C$ and $D$ be two convex sets. And suppose $C\cap D\neq \emptyset$. Let $x^*$ is the solution to the optimization problem:
$$\min_{x\in C} \max_{y \in D} |x-y|^2$$
Is it true that $x^* \in D$. ...

**0**

votes

**2**answers

246 views

### Higher dimensional convex hull

Let $CH(S)$ be a convex hull of a finite set $S$ and denote the set of all the vertices of $CH(S)$ as $Vert(S)$. For a vertex $v \in Vert(S)$, it has an associated set $E(v)$ which is defined as ...

**1**

vote

**1**answer

149 views

### Regularizing a Convex function with itself

Hi,
This is a problem that has being bothering me the last few days.
Assume a convex function $f(x): {\mathbb R}^n \rightarrow {\mathbb R}$ with a unique minimizer $x^{\star}$. Now consider the ...

**2**

votes

**3**answers

244 views

### Measuring the distance of a convex set from a ball (Nikodym distance)

Assume we have a centrally symmetric convex set $K \subset \mathbb{R}^n$ such that Vol(K)=1. In addition, assume that for every direction $u$ we know that $Vol(K \Delta R_u(K)) < \epsilon$, where ...

**1**

vote

**0**answers

60 views

### Which matrix/operator in a cone has the largest negative spectral part?

Background:
Let $\mathcal{K}$ be set (convex cone, if you like) of symmetric matrices of order $n$. Each matrix $A \in \mathcal{K}$ can be decomposed in a unique way as $A=A_{+}-A_{-}$, where ...

**5**

votes

**1**answer

324 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

**1**answer

230 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

**1**answer

105 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

**2**answers

367 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

**0**answers

86 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

**1**answer

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

**1**answer

228 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

**1**answer

493 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

**1**answer

351 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

**0**answers

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

**2**answers

165 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

**1**answer

90 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

**2**answers

291 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

**1**answer

161 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

**1**answer

220 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

**5**answers

305 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

**1**answer

228 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

**2**answers

277 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

**0**answers

161 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

**0**answers

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

**1**answer

202 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

**1**answer

144 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

**1**answer

193 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

**2**answers

415 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

**0**answers

348 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

**1**answer

425 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

**2**answers

365 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

**1**answer

139 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

**3**answers

394 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

**2**answers

232 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

**2**answers

353 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

**0**answers

183 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

**1**answer

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

**1**answer

139 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

**1**answer

619 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

**0**answers

136 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

**0**answers

203 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

**2**answers

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

**1**answer

106 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 ...

**10**

votes

**1**answer

4k 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

**1**answer

347 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

**1**answer

821 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

**2**answers

288 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

**1**answer

161 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 ...