The tag has no wiki summary.

learn more… | top users | synonyms

0
votes
1answer
619 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
271 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
151 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
274 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
252 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
166 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
259 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
270 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 ...
1
vote
1answer
461 views

proving the interior of a dual cone is the set of vectors whose inner product is strictly positive on the cone

Apologies for posting such a simple question to mathoverflow. I've have been stuck trying to solve this problem for some time and have posted this same query to math.stackexchange (but have received ...
6
votes
4answers
362 views

Packing and isoperimetrics

Suppose a manufacturer bottles small units of liquid and ships them via very large trucks. If the transportation cost nothing, spherical bottles would minimize the packaging cost (isoperimetric ...
5
votes
1answer
209 views

Convexity of a specific semialgebraic set

I have an engineering problem which maybe resolved with semi-definite programming optimization. I have a set which I would like to know if is convex: Being $m \in \mathbb{R}^+$ a positive real ...
4
votes
1answer
244 views

Deciding the convexity of semialgebraic sets

Given a basic closed semialgebraic set, $S \subset \mathbb{R}^n$, defined by $S = \{ x \in \mathbb{R}^n \mid g_1 (x) \geq 0 \land \dots \land g_m (x) \geq 0\}$ where $m \in \mathbb{N}$ and $g_1, ...
4
votes
4answers
582 views

Is the intersection of boundaries of convex bodies a topological sphere?

Let $K_1, K_2, \ldots K_n$ be convex bodies in $R^d$. Assume that for any index set $I$, $\cap_{i \in I} K_i$ is not empty and is not properly contained in any body $K_i$ for $i\in I$. Is it true ...
13
votes
2answers
437 views

A natural center of a convex weakly compact set in Banach space

Question: Let $S$ be a convex weakly compact set in Banach space $H$. Propose a natural way to define the unique center $O \in S$. Motivation: A lot! For example, in game theory $S$ can be a set of ...
2
votes
1answer
268 views

Quermassintegrals as mean curvature integrals

It is well-known that the quermassintegrals $W_{i}$ of a convex body $K\subset \mathbb{R}^{n}$ can be written as a mean curvature integral $$ W_{i}(K)=n^{-1}\int_{\partial K}H_{i-1} ...
2
votes
2answers
346 views

Does the minima of a sequence of convex convergent functions converge?

Suppose $f_1,f_2,\ldots $ is a sequence of convex functions that converges to a continuous convex $f$. Let $x_1^*,x_2^*$ be their respective (not necessarily unique) minima, and let y be a minima of ...
2
votes
1answer
147 views

Lipshitz Constant of the convex extension of a submodular function

The title says it all :) Given a submodular function (take the rank function of a matroid, for a concrete example) $f:\{0,1\}^n\rightarrow \mathbb{R}$, we can extend it to a convex function ...
0
votes
0answers
196 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
312 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
299 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
278 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
213 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
166 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
965 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
566 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
414 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
470 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
173 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
434 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
284 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
410 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
214 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
105 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
986 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$ ...
22
votes
1answer
442 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
275 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
252 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
155 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
305 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
662 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
414 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
370 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
156 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
123 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
362 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
829 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? ...