The tag has no wiki summary.

learn more… | top users | synonyms

0
votes
0answers
234 views

A question regarding Danskin's theorem

Suppose $\phi({\bf x},{\bf z})$ is a continuous function of two arguments, $\phi: {\mathbb R}^N \times Z \rightarrow {\mathbb R}$, where $Z \subset {\mathbb R}^m$ is a (non-empty) compact convex ...
5
votes
1answer
342 views

Extreme points of a compact convex set are a $G_\delta$?

Dear All, I'm reading a paper (Residuality of Dynamical Morphisms by Burton, Keane and Serafin) that makes a claim that I've been unable to verify or find a reference for. The claim is made that the ...
3
votes
1answer
116 views

Mapping a subset of semi-definite matrices through arcsinus

Hi I am meeting a problem concerning semi-definite positive matrices, and I have no clue concerning them, the classical approaches I know have not given any result, maybe people used to manipulating ...
4
votes
1answer
326 views

Is it possible to extend this inequality about Euclidean distance &Frobenius norm to more general Bregman divergence such as relative entropy & von Neumann divergence?

Motivation- A Special Case Supposing $A,B\in\mathbb{S}^{m\times m}$ are symmetric positive semi-definite (SPD) matrices and $\mathbf{x}\in\mathbb{R}^m$ is a unit vector where $\|\mathbf{x}\|=1$, we ...
9
votes
3answers
1k views

Area Enclosed by the Convex Hull of a Set of Random Points

Consider $n$ points generated randomly and uniformly on a unit square. What is the expected value of the area (as a function of $n$) enclosed by the convex hull of the set of points?
1
vote
1answer
318 views

conjugate function for matrix mixed norm

I am familiar with the conjugate function of the vector norm, which uses the concept of dual norm and is defined as follows: ...
2
votes
1answer
227 views

Generalized unique nearest point problem for a compact, convex set in a strictly convex Banach space.

If $X$ is a Real Banach space with strictly convex norm, it is known that for any non-empty compact, convex set $K$ and point $x_0\notin K$, there exists a unique point $z_0\in K$ minimizing the ...
1
vote
0answers
171 views

Given a jointly convex function $f$, what is the bound of $f\left(\sum_ip_i^2x_i,\sum_jq_j^2y_j\right)$if $\mathbf{p},\mathbf{q}$ are constrained in a manifold?

Suppose there is a jointly convex function $f:\mathbb{R}\times\mathbb{R}\rightarrow\mathbb{R}$, $\mathbf{x},\mathbf{y}\in\mathbb{R}^m$ and ...
2
votes
1answer
1k views

Sufficient conditions for gradient descent convergence

I have an unconstrained optimisation problem with convex objective function $f(x)$. Suppose I have access only to some function of the gradient $\hat{\nabla}= g(\nabla f)$, and I take gradient steps ...
3
votes
2answers
641 views

Computational complexity of unconstrained convex optimisation

What is known about the relationship between unconstrained convex optimisation and computational complexity? For example, for which optimisation problems and which gradient descent algorithms is one ...
13
votes
2answers
453 views

Extreme points of unit ball in tensor product of spaces

Let $B_1, B_2$ be unit balls in finite-dimensional normed spaces $X_1, X_2$ respectively. Let $e(B_1), e(B_2)$ be corresponding extreme points sets. Consider the unit ball $B$ in tensor product ...
2
votes
1answer
513 views

Local strong convexity of a strictly convex function

Is there a formal way to characterise strong convexity about the optimum value of a strictly convex function? I have an objective that looks something like this: $J(p,q) = ...
0
votes
0answers
185 views

lipschitz property of the derivative of a convex function

Let $f\in C^1(\mathbb R^n\to \mathbb R)$ be a convex function. Suppose the equation $$f(x+\Delta x)-f(x)-(f'(x),\Delta x) \leq A|\Delta x|^2$$ holds for some constant $A>0$, any $x\in \mathbb ...
3
votes
3answers
470 views

Inequalities for uniformly convex normed spaces

When reading "Chebyshev centers and uniform convexity" by Dan Amir I encountered the following result which is apparently "known and easy to prove". I'm sure it is, but I can't find a proof and am ...
8
votes
0answers
296 views

What is the “positive part” of the unit ball in $M_n(R)$ ?

In ${\bf M}_n(\mathbb R)$, let us consider the usual operator norm $$\|A\|=\sup\frac{\|Ax\|}{\|x\|},$$ where $\|x\|$ is the Euclidian norm. The closed unit ball $B$ is the set of contractions (in the ...
3
votes
1answer
429 views

Tverberg partitions with less than (r-1)(d+1)+1 points

The Tverberg Theorem states the following: Let $x_1,x_2,\dots, x_m$ be points in $R^d$ with $m \ge (r-1)(d+1)+1$. Then there is a partition $S_1,S_2,\dots, S_r$ of $\{1,2,\dots,m\}$ such that $\cap ...
2
votes
0answers
235 views

Erdős-Szekeres empty pseudoconvex $k$-gons

I am wondering if the Erdős-Szekeres empty convex $k$-gon question has a different answer if convexity is replaced by a pseudoline-version of convexity. The empty convex $k$-gon question is a variant ...
1
vote
0answers
106 views

Mappings preserving convex compactness

Let $H$ be a Hilbert space. How can one describe continuous mappings $F:H \to H$ that satisfy the following condition: There exist two elements $c$, $F(c) \neq c$ and a convex compact $M$ containing ...
5
votes
3answers
1k views

A criterion for the sum of two closed sets to be closed ?

Let $V$ and $I$ be two closed subsets of a Banach space $A$. The set $V$ is a convex cone, and $I$ is a linear subspace of $A$. I also know that $V\cap I=\{0\}$. I would like to know whether $I+V$ ...
21
votes
1answer
466 views

The maximal “nearly convex” function

The following problem is only tangently related to my present work, and I do not have any applications. However, I am curious to know the solution -- or even to see a lack thereof, indicating that the ...
4
votes
1answer
304 views

Generalized widths and reverse Urysohn inequalities

This question is inspired by the discussion in MO questions "Local minimum from directional derivatives in the space of convex bodies" and "Bodies of constant width?" about generalized notions of ...
5
votes
0answers
260 views

Local minimum from directional derivatives in the space of convex bodies

I have a function $f(K)$ defined on the space of three-dimensional convex bodies for which I want to show that the unit ball $B$ is a local minimum. I have been able to show if $K$ is not homothetic ...
3
votes
0answers
158 views

Characterizing curves that bound strictly convex regions

Consider a closed curve on the plane so that if we perform any translation and dilation on it, the resulting curve intersects the original curve at most twice. Does this property characterize the ...
6
votes
2answers
312 views

Volume inequality between projections of a convex symmetric set in $\mathbb R^3$

Let $K$ be a centrally symmetric convex body in $\mathbb R^3$ with volume ${\rm vol}(K)=1$. For any subset $F \subset \lbrace1,2,3\rbrace$, let $K_F$ be the projection of $K$ in $\mathbb R^F$. ...
8
votes
1answer
786 views

Extreme points of a set of probability measures

Consider the set of Borel-measurable probability measures over the interval $[0,1]$ with a given mean, say 1/2. To be precise, I'm talking about the following set $$M=\left(\mu\in \Delta([0,1]):\int ...
1
vote
1answer
474 views

Shift invariant measures that are(n't) convex combinations of ergodic measures

Let $X=2^\omega = \lbrace 0,1 \rbrace^{\mathbb{N}}$ and $T\colon X \to X$ the (left) shift map. The space $\mathcal{M}$ of $T$-invariant Borel probability measures is convex with $\mathcal{M}^e$, the ...
2
votes
1answer
399 views

minimizing functions over simple matrix inequalities

I'm wondering if anything is known about minimizing convex, not necessarily linear functions subject to "simple" matrix equalities. To be precise, consider the following example: $min \Sigma x_i ln ...
4
votes
0answers
161 views

Is it possible to solve the argument maximization problem $\arg\max_x \langle x,l \rangle −f_1(x)−f_2(x)$ via convex duality?

I am attempting to solve the argument maximization problem $$\arg\sup_x \{ \langle x,l \rangle − f_1(x)−f_2(x) \} \ \ \ \ \ \ \ \ \ \ (1)$$ where the functions $f_1$ and $f_2$ are concave but ...
2
votes
1answer
125 views

Spline fit with bounded derivations

How can I do a Spline Fit with bounds on some derivations? Problem Given: Set of data points $t_k, x_k$ Set of nodes $n_i$ order $D$ of the spline (in my case $D=5$) lower and upper bounds ...
10
votes
1answer
370 views

convexity of images of space-filling curves

Suppose $f:[0,1]\to[0,1]^2$ is continuous and for each $t\in[0,1]$, the area of $\lbrace f(s) : 0\le s\le t \rbrace$ is $t$. For what sets of values of $t\in[0,1]$ can $\lbrace f(s) : 0\le s\le t ...
8
votes
2answers
857 views

Does a notion of convex graph make sense?

Let $X=(V,E)$ be a finite connected graph. I would be interested in some notion of convexity. General question: Is there a notion of convexity for finite connected graphs? How does it look like? ...
3
votes
1answer
466 views

Java library for SDP [closed]

People who frequently code semi definite programs, is there any java library for solving sdps? I have tried my luck but all I can find is C/C++ libraries or matlab toolboxes. I can write wrappers to ...
4
votes
2answers
625 views

gradient of convex functions

Hello. Can somebody help me with the following question that I have thought over for quite some time, to no avail? Let $f$ be a smooth function (class $\mathrm{C}^{\infty}$), $f:\mathbb{R}^n ...
11
votes
2answers
2k views

Weighted area of a Voronoi cell

Let $X = \{ x_1,\dots,x_n\} $ denote a set of $n$ points in the unit square $S = [0,1]\times[0,1]$, and let $w = \{w_1,\dots,w_n\}$ denote a set of weights corresponding to the $n$ points in $X$. ...
3
votes
1answer
221 views

Signed measure that is positive over convex sets

I have a signed measure $\mu$ on a convex subset $C\subset \mathbb{R}^n$, and I want to prove that $\mu$ is a probability measure, most importantly that it is positive everywhere. I do know that ...
2
votes
0answers
138 views

Minimally 6-connected 3D discrete lines that are convex lattice sets

There are several definitions of 3D discrete lines, e.g. http://diwww.epfl.ch/w3lsp/publications/discretegeo/nratddl.html , http://dx.doi.org/10.1007/978-3-642-19867-0_4 . However, I know of none that ...
3
votes
2answers
200 views

Does the automorphism group of a cone determine the cone?

A cone is a $R_+$-module. That is, a cone is an abelian monoid that is closed under nonnegative real scalar multiplication. An automorphism of a cone is a bijective $R_+$-linear map. That is a map ...
2
votes
1answer
246 views

Linear and Isometric Automorphism Groups of the PSD Cone

Let $S_+$ be the cone of psd matrices ($n\times n$ real symmetric positive semidefinite matrices). This cone is a metric space induced from the inner product $\langle A,B\rangle = tr (AB)=tr(BA)$. ...
11
votes
1answer
419 views

Status of the compact AR problem?

The so-called "compact AR Problem" reads: Is every compact convex set in a metrizable topological vector space an absolute retract? It is open according to the chapter by T. Banakh, R. Cauty ...
2
votes
2answers
481 views

Finding smallest ellipsoid that circumscribes over intersection of two ellipsoids that do not have common center

Does this already exist in literature? The closest Ive been able to find is circumscribe intersection of two ellipsoids with a common center by W. Kahan ...
2
votes
1answer
737 views

How do I optimize over (or take derivative wrt) a square diagonal matrix?

Hello. I'd like to solve the following optimization problem. $P_i$ is a 6x6 matrix $X$, $Y$ is a 6xk matrix $w_i$ is a kx1 vector $diag(w_i)$ is a square diagonal matrix with diagonal entries equal ...
0
votes
1answer
154 views

Can extremal matrices of subcones of psd matrices have low rank?

Let $S$ be the cone of positive semidefinite symmetric real matrices of size $n\times n$. The cone $S$ spans a $d:=n(n+1)/2$ dimensional vector space. Let $C\subset S$ be a subcone formed by ...
3
votes
2answers
414 views

Is a solution of a linear system of semidefinite matrices a convex combination of rank 1 solutions?

The cone of symmetric positive semidefinite $n\times n$ matrices is the convex hull of rank $1$ matrices. That is, every symmetric positive semidefinite matrix is a convex combination of rank 1 ...
7
votes
0answers
218 views

Are plactic classes convex under the right weak Bruhat order?

For those who are unfamiliar with the terminology, I'll explain a little. The symmetric group $S_n$, as a type A Coxeter group, has generators $\{s_1,\ldots,s_{n-1}\}$ with relations (1) $s_i^2$ for ...
3
votes
2answers
443 views

Surface fitting with convexity requirement

Hi all, Consider a cloud of points in 3D space (x,y,z). The data is well-behaved, once plotted the surface looks like some sort of spheroid. I assumed a form for the fitting function f(x,y,z) = c1 ...
1
vote
0answers
251 views

Computing the intersection of dual affine subspaces

Suppose we have a convex function , $\phi(x): R^d \to R$. It is well known that the Legendre transform of $\phi$ is also a convex function, and can (loosely) be thought of as the dual or derivative ...
1
vote
0answers
179 views

Joint Convexity of Spectral functions of several matrices

$\{A_1 \ldots A_K \}$ is a set of matrices in $\mathbb{R}^{m \times n}$. Let $f (A_1,\ldots,A_K)$ be a function of the singular values of all matrices. For e.g., $f$ is just summation of singular ...
0
votes
0answers
320 views

Global index of convexity/concavity of a function

We are looking for a global index of the convexity/concavity of a function. For concreteness, how can I formalize the intuitive notion that a function $f$ is more convex than $g$ where ...
13
votes
2answers
563 views

Do the elementary properties of mixed volume characterize it uniquely?

Background Take 2 convex sets in $\mathbb{R}^2$, or 3 convex sets in $\mathbb{R}^3$, or generally, $n$ convex sets in $\mathbb{R}^n$. "Mixed volume" assigns to such a family $A_1, \ldots, A_n$ a ...