The tag has no usage guidance.

learn more… | top users | synonyms

12
votes
0answers
208 views

How large are the smallest-area projections of a high-dimensional convex body?

Let $B$ be a convex body in $\mathbb{R}^d$, equipped with its standard Euclidean form, and assume that $$\intop_B x \, dx = 0$$ $$\frac{1}{|B|_d} \intop_B x_i x_j \, dx = \delta_{ij},$$ a ...
7
votes
0answers
293 views

Strong convexity of the trace of the square root of a matrix function

Any clues about how to prove that the following function is strongly-concave in $x$? (We conjecture it is $2$-strongly concave but cannot prove it. We have already proved strict concavity through ...
6
votes
0answers
94 views

orthogonal projector onto the set of convex functions

Let $\Omega\subset \mathbb R^d$ be an open, convex domain, and consider the Hilbert space $L^2(\Omega)$. Each sum of convex functions is convex, hence the subset $Conv(\Omega)$ of all convex functions ...
5
votes
0answers
72 views

Concavity of mixed volumes and mixed discriminants

For $n\times n$ symmetric matrices $A_1, \ldots, A_n$, the mixed discriminant $D(A_1, \ldots, A_n)$ can be defined as $1/n!$ times the coefficient of $t_1\ldots t_n$ in the homogeneous polynomial $\...
5
votes
0answers
456 views

An intuition for three different types of subgradients (proximal, regular, limiting)

I'm having a bit of difficulty getting my head around the different types of subgradients we're currently covering in a nonsmooth optimisation class I'm taking. These subgradients are (assume $x \in$ ...
4
votes
0answers
105 views

Dimension reduction for low-order moments of Rademacher-weighted sums of vectors

Let $x_1,\dots,x_n$ be vectors in a Euclidean space $H$. Let $\varepsilon_1,\dots,\varepsilon_n$ be independent Rademacher random variables (r.v.'s), so that $P(\varepsilon_i=\pm1)=1/2$ for all $i$. ...
4
votes
0answers
77 views

Linear projections of convex sets with unique preimages of boundary points

Fix a compact convex subset $C \subset \mathbb{R}^n$ with nonempty interior. For any subspace $S \subset \mathbb{R}^n$, let $P_S$ denote the orthogonal linear projection onto $S$. I'd like to claim ...
3
votes
0answers
211 views

Area defined with $\pm$ closedness

Denote $B_n\subset\Bbb R^n$ to be unit ball at origin. Denote $S\subset B_n$ to region of type $\mathsf I$ if it satisfies $$s\in S\iff\forall t\in S, s+t\in S\mbox{ or }s-t\in S$$ I am convinced $\...
3
votes
0answers
113 views

error estimate of linear interpolation in high dimension

Consider convex functions $f,g$ on $[0,1]^d$. Let $x_1,\cdots,x_n$ be $n\geq d+1$ fixed point in $[0,1]^d$ that is equally 'distributed' in the sense that $$c_1\leq \frac{n\mathrm{vol}(K)}{\mathrm{...
3
votes
0answers
262 views

Decreasing sequence of closed convex sets in a Banach space

Let $(C_n)$ be a decreasing sequence of closed convex subsets in a Banach space $(E,\Vert \cdot \Vert)$. The question I have is about the content of $C=\bigcap_{n=0}^\infty C_n$. If the $C_n$ are ...
3
votes
0answers
57 views

Minimax-like theorems involving union and intersection of regions in $\mathbb R^d$

From Minimax theorems, we roughly know that if $f(x,y)$ is convex on $X$ and concave $Y$ for both compact $X,Y$, then: $$ \max_{x\in X}\min_{y\in Y} f(x,y)=\min_{y\in Y}\max_{x\in X} f(x,y). $$ We can ...
3
votes
0answers
192 views

Ways to establish equality of measures on locally compact spaces

Let $M$ be a locally compact space and $\mu$ be some probability measure on $M$. Let $y^\ast \in M$, $f(x,y)$ be a real continuous bounded function $M \times M \to \mathbb{R}$. Consider an equality $$ ...
2
votes
0answers
64 views

A convex analysis theorem improvement

John's theorem states that to any full-dimensional symmetric convex set $K\subseteq R^n$ and any Ellipsoid $E\subseteq R^n$ that is centered at origin, there exists an invertible linear map $T$ so ...
2
votes
0answers
339 views

On increasing the penalty term in convex optimization with regularization

Given the two strictly convex (unique solution) optimization problems as: $$Problem\:1:\min_{X} f(X)+\|X\|_{F}^2 \hspace{2cm}Problem \:2:\min_{X}f(X)+n\|X\|_2^2$$ where $X\in\mathbf{S}_{++}^{n}$ (...
2
votes
0answers
143 views

Lower convex envelope of a function involving entropy

Suppose two discrete random variables $X$ and $Y$ defined on finite sets $\mathcal{X}$ and $\mathcal{Y}$ are given and also suppose the conditional distribution $P_{Y|X}$ (i.e, channel) is fixed. We ...
2
votes
0answers
171 views

Showing $\langle \frac{\partial b(v)}{\partial t}, v \rangle_{H^{-1}(\Omega), H^1(\Omega)} = \frac{d}{dt}\int_{\Omega}\Psi^*(b(v))$

Let $b$ be continuous and increasing with $b(0) = 0$. Define $\Psi(t) = \int_0^t b(s)\;ds$ and $\Psi^*(s) = \sup_{r \in \mathbb{R}} (sr-\Psi(r))$. (Note $\Psi^*(b(s)) + \Psi(s) = sb(s)$). Let $v \...
2
votes
0answers
183 views

Convex functions with non-singular hessian measure are continuously differentiable?

It is known that every convex function $f: \Omega\to \mathbb{R}$, $\Omega$ convex subset of $\mathbb{R}^n$, has a weak derivative of bounded variation $Df\in BV_{loc}(\mathbb{R}^n)$ (e.g. Evans and ...
2
votes
0answers
90 views

How to prove convexity for a complex integral including the variable in both limits and integrand?

During my research [on inventory management policies, i.e., something really applied ;-) ] I stumbled on integrals of the following type and I'm curious under which circumstances there are convex. ...
2
votes
0answers
124 views

Concavity of a ratio of Kullback-Leibler divergences

For $0\leq r\leq 1$ and $0 < p < 1$, define the Kullback-Leibler divergence between the Bernoulli(r) and Bernoulli(p) distributions as: $D(r||p) := r\log\frac{r}{p} + \bar{r}\log\frac{\bar{r}}{\...
2
votes
0answers
628 views

Definition and Convergence of Iteratively Reweighted Least Squares

I've been using iteratively reweighted least squares (IRLS) to minimize functions of the following form, $J(m) = \sum_{i=1}^{N} \rho \left(\left| x_i - m \right|\right)$ where $N$ is the number of ...
1
vote
0answers
73 views

Projecting on a a special polyhedron

Let $X$ be an $n$-by-$p$ matrix and consider the closed convex polyhedron $$\mathcal P_X := \{y \in \mathbb R^n | \|X^Ty\|_\infty \le 1\}.$$ Notice that $\mathcal P_X$ is symmetric about the origin. ...
1
vote
0answers
45 views

Projecting on a convex compact polytope with special form

Let $E$ be a large sparse $l$-by-$n$ matrix ($l$ and $n$ can be in the billions...) with coefficients in $\{-1, 0, 1\}$: the first row of $E$ is the vector $(1,0,0,\ldots,0) \in \mathbb R^n$, and ...
1
vote
0answers
51 views

Derivatives of Minkowski function?

Let $A\subset \mathbb R^n$ and $M$ be the convex hull of the set $A$, e.g., $M:=Conv(A)$. The Minkowski function on $M$ is defined as follows \begin{align*} &f: \mathbb R^n \to \mathbb R\\ &f(...
1
vote
0answers
62 views

concavity of a vector function

I'm given a function $g:\mathbb{R}^n \mapsto \mathbb{R}$, $g(y) = \prod_{i\in[n]} (1+y_i\cdot c_i)$, where $c_i>0$. Let $e_a,e_b$ be two arbitrary standard vectors. It is easy to show that for any ...
1
vote
0answers
74 views

A version of isotone projection cones

We write $a \succeq b$, where both $a, b \in \mathbb{R}^n$, as a shorthand for $a_i \ge b_i$ for all $1 \le i \le n$. Let $C$ be a closed convex cone in the first orthant of $\mathbb{R}^n$ and denote ...
1
vote
0answers
50 views

Uniqueness of (generalized) Moreau decomposition

Let $H$ be some Hilbert space, which we can take to be the usual finite-dimensional Euclidean space if needed. For a function $f : H \to \mathbb{R}$, let $f^* : H \to \mathbb{R}$ be its conjugate dual,...
1
vote
0answers
129 views

Proximal mapping of composition with linear operator

Let $A$ be an orthogonal matrix. Then the proximal mapping $prox_{f \circ A}(x)$ can be evaluated efficiently by $$ (I + \partial (f \circ A))^{-1}(x) = prox_{f \circ A}(x) = A^T prox_{f}(A x), $$ as ...
1
vote
0answers
178 views

Restricted strong convexity for biconvex functions

Recently, it has been shown (arxiv paper) that non-convex functions with the restricted strong convexity (RSC) property has the interesting property that their local minima lie within a small ball of ...
1
vote
0answers
96 views

Convex Optimization related problem

Suppose two non-negative convex functions $f$ and $g$ be given. We want to solve the following optimization $$\max_{g\leq\epsilon}f.$$ Now suppose that both $f$ and $g$ can be upper-bounded by a ...
1
vote
0answers
126 views

convergence of supergradient

Let $\{g_n\}$ be a sequence of concave functions defined on $\mathbb{R}$ and set $$\lambda_n(x)=\lim_{\Delta x\to 0+}\frac{g_n(x+\Delta x)-g_n(x)}{\Delta x}$$ Assume there exists a concave function ...
1
vote
0answers
90 views

Directional derivates and unique subgradients

I have a question about the fine structure of convex functions. Convex functions behave very regular in the interior of their domain of definition (e.g. they are locally Lipschitz continuous there) ...
1
vote
0answers
265 views

Lipschitz continuity of solution set mapping of a parametric convex optimization problem

I have a parametric convex optimization problem: \begin{array}{cl} \underset{x}{\text{minimize}} & f\left(x,z\right)\\ \text{subject to} & g\left(x\right)\leq0 \end{array} where $x$ is the ...
1
vote
0answers
113 views

Linearization of cones

Suppose that $K$ is a closed convex cone in $R^{n}$. Is there a "nice" function $f:R^{n} \rightarrow R^{m}$ so that $f(K)$ is a subspace? What about an approximate subspace?
1
vote
0answers
181 views

Optimize a convex hull on a 2D histogram so the selected points match a target shape

I have an image (can be 2D or 3D), and compute a 2D histogram of the image (for example, the pixel intensity and gradient along certain direction). There is a known target region $R^*$ in the image. I ...
1
vote
0answers
143 views

variational problem under convexity constraints

I wonder if there is any method to compute variational problems subject to certain shape constraints (e.g., convexity, monotonicity, etc.). The literature I found on this topic (which I am no expert ...
0
votes
0answers
15 views

Are there examples of functions with Nesterov's convergence bound between convex quadratic and strongly convex cases?

Are there examples of simple and strongly convex functions for which the convergence bound of Nesterov’s Accelerated Gradient Method is better than Nesterov’s bound for strongly convex case ($\sqrt{1 -...
0
votes
0answers
36 views

L-natural convex optimal criterion

Let $g: \mathbb{Z}^V \to \mathbb{R} \cup \{+\infty\}$ be L-natural convex function. I know that this is equivalent to the following statement: $\forall p, q \in \mathbb{Z}^V, \forall \alpha \in \...
0
votes
0answers
72 views

Differntiability of Distance to a CLosed Convex Set

Let $A$ be a closed convex set in Banach space $( \mathbb{R}^n, \| \cdot\| )$. For any $\mathbf{x} \in \mathbb{R}^n$, define $$P_{A}(\mathbf{x}) = \arg\min_{\mathbf{y}\in A} \| \mathbf{x} - \mathbf{y} ...
0
votes
0answers
37 views

Bounds on the curvature of a sequence of convex functions

Let $\{f_n\}$ be a sequence of (real-valued) smooth convex functions on $[0,1]$, with $f_n(0) = f_n(1) = 0$ for all $n$. Let $t_n \in [0,1]$ be the minimizer of $f_n$ and assume that $M_n:= f_n(t_n) ...
0
votes
0answers
65 views

Maximum value of linear function on the intersection of a parametrized family of balls

Let $C$ be a (nonempty) closed convex subset of $\mathbb{R}^n$ and $a, b \in \mathbb{R}^n$. Using the normal cone characterization of the euclidean projection operator $\mathrm{proj}_C$ (recall that $\...
0
votes
0answers
57 views

A question about the approximation of convex cones

I have the following question which maybe is too naive. Let $K$ be a convex cone on $\mathbf{R}^n$. Can we approximate $K$ by a sequence of polyhedral convex cone $K_i$ such that for any compactly ...
0
votes
0answers
86 views

Largest ball with fixed center in a a convex region

Let $x_0$ be a point contained inside a compact, convex set $C\subset\mathbb{R}^d$, which is of the form $C=\{x:f(x)\leq0\}$ for some explicit convex function $f$. Is there a computationally ...
0
votes
0answers
31 views

Looking for a homogeneous function with some properties

I'm looking for a 1-homogeneous function $\pi \colon \mathbb{R}^n_{\geq 0} \to \mathbb{R}$ satisfying the following properties: 1) $\pi$ is not concave. This is equivalent to the fact that there ...
0
votes
0answers
90 views

convergence of concave envelope

Let $\{f_n\}$ be a sequence of uniformly upper bounded functions defined on $\mathbb{R}$ s.t. for every $x\in\mathbb{R}$ $$f_n(x)\to f(x),~ n\to\infty$$ Define $g_n$ and $g$ as the concave envelope ...
0
votes
0answers
120 views

Min of a real-valued Fourier transform

Let $P$ be a compact, convex, symmetric, $d$-dimensional body in $\mathbb R^d$, and let $\mu$ be a (necessarily) symmetric probability measure on $P$, so that $\mu_P(x) = \mu_P(-x)$, for all $x \in \...
0
votes
0answers
58 views

convexity of two linear spaces connected by convex nonlinear equality constraints

If there are two sets of linear constraints in different variables, Ax <= b with x_l <= x <= x_u and Cy <= d with y_l <= y <= y_u, and a set of equality constraints of a specific non-...
0
votes
0answers
173 views

On the remarkable property of the concave function's level sets

Consider a smooth function $f(x) \colon \mathbb{R}^2_+ \to \mathbb{R}_+$ such that $f$ is concave and positively homogeneous of order one. Consider a linear transform $P$ given by matrix $$ P = \...