Questions tagged [convexity]
For questions involving the concept of convexity
189 questions with no upvoted or accepted answers
2
votes
0
answers
240
views
Radon transform and Log-concavity
This question is related to (but different from) that of Darsh Ranjan.
Is there a characterization of the functions $f:\mathbb R^n\rightarrow\mathbb R_{\ge0}$ whose Radon transform $\hat f(\omega,t)$...
- 52.3k
1
vote
0
answers
30
views
Generalization of subadditivity analogous to quasiconvexity, and variants
I am curious if there are natural generalizations of subadditivity which have been studied in the past or have been stated in the literature? I (and people that I have talked to) have not had much ...
- 21
1
vote
0
answers
30
views
Finite right-triple convex sets in planes
Let $\mathcal{S}$ be a set of points in $\mathbb{R}^2$. We say that $\mathcal{S}$ is right-angle convex, if for any two distinct points $P,Q\in \mathcal{S}$ there always exists another point $R\in \...
- 123
1
vote
0
answers
95
views
Detecting points inside the convex hull with inner products
Given a finite set $P$ of $n\gt d+1$ points in $d$-dimensional euclidean space.
Under the assumption that the points of $P$ are in general position in the sense that $\lbrace p_{i_1},\dots,p_{i_d}\...
- 13.2k
1
vote
1
answer
191
views
Comparison of solutions of Hamilton-Jacobi equations with different initial conditions
Consider a Hamilton-Jacobi equation:
$$u_{t} + f(u_{x}) = 0 \quad (x,t) \in \mathbb{R}\times [0,+\infty)$$
with two possible initial conditions $u(x,0) = g_{i}(x)$ for $x \in \mathbb{R}$ and $i=1,2$. ...
- 3,515
1
vote
0
answers
195
views
The image of zero-measure set under normal mapping is Lebesgue measurable
Let $u$ be a convex function defined on a bounded open set $\Omega$ in $\mathbb{R}^n$. Then $u$ is twice differentiable a.e. Let $E_u$ be the set on which $u$ is not twice differentiable. Then $E_u$ ...
- 11
1
vote
0
answers
271
views
Starlike sets in $\mathbb{C}^n$
Let $S$ be a bounded domain in $\mathbb{C}^n$. $S$ is called starlike about the point $x_0\in S$ if for every point of $S$, the segment of the straight line from the point to $x_0$ lies in $S$. If $S$ ...
- 61
1
vote
0
answers
65
views
Minimum bounding rectangle of symmetric convex bodies in the plane : is the ball the worst case
The minimal rectangle containing the euclidean ball in the plane is the standard cube $B_\infty = [-1;1]^2$. I would like to know if the euclidean ball is the worst symmetric convex body to be ...
- 245
1
vote
0
answers
82
views
Maximal geodesically convex function interpolating three points on the hyperbolic plane
Crossposted on MSE: https://math.stackexchange.com/questions/4282998/maximal-geodesically-convex-function-interpolating-three-points-on-the-hyperboli
Let $M$ be a two-dimensional Hadamard manifold. ...
- 637
1
vote
0
answers
115
views
How to prove the inequality $\ln\frac{1+e^{-y}}{1+e^{-x}}+\frac{1}{1+e^x}(y-x)\geq 0$?
I am trying to prove that $\ell(\beta) = \sum_{i=1}^n \left (-y_i \beta^{\top}x_i + \ln \left (1 + e^{\beta^{\top}x_i }\right )\right )$ is a convex function. I follow the following steps:
Let $\...
- 19
1
vote
1
answer
350
views
How to prove the convexity of a simple function involving a ratio of two polygamma functions?
Let
\begin{equation*}
\Gamma(z)=\int_0^{\infty}t^{z-1}\textrm{e}^{-t}\textrm{d}t, \quad \Re(z)>0
\end{equation*}
and
$$
\psi(z)=[\ln\Gamma(z)]'=\frac{\Gamma'(z)}{\Gamma(z)}.
$$
In the literature, ...
- 1,091
1
vote
0
answers
864
views
The "interior" of a convex set?
Consider any compact metric space $S$ which is a convex subset of a vector space. I am trying to see if the following definition is equivalent/close to some well-known definitions.
Consider a convex ...
- 157
1
vote
0
answers
121
views
Relation satisfied by a Gaussian random variable
I want to prove the following relation for $X\sim \mathcal{N}(0,1)$, $x\in \mathbb{R}$ and $f(x)=\mathbb{E}[\max(X,x)]$:
$$f(\frac{f(x+1)+f(x-1)}{2})\leq \frac{f(f(x)-1)+f(f(x)+1)}{2}$$
It seems that ...
- 171
1
vote
0
answers
213
views
Stationary distributions of convex combination of stochastic matrices
Consider two irreducible finite state Markov chains with transition matrices $A,B\in\mathbb{R}^{n\times n}$.
Let $x$ and $y$ be the unique stationary distributions of $A$ and $B$, respectively.
Now ...
- 179
1
vote
0
answers
323
views
Decomposition of Polyhedral - An example
There is no doubt that clear examples consolidate the understanding of concepts being learnt. I am new to finding the structure and decomposition of a polyhedra. Suppose that we have the system
$$ \...
- 111
1
vote
0
answers
151
views
Log-concavity inequality
Let $x,y,$ and $t$ be fixed real numbers, $1<x<y$, $0<t<1$. Does the following inequality hold for some $c$
$$\frac{\log{(tx+(1-t)y)}}{\log^t{x}\log^{(1-t)}{y}}>\frac{\log{(sw+(1-s)z)}}{...
- 3,209
1
vote
0
answers
36
views
Does a total preorder on lotteries that preserves countable mixtures preserve arbitrary mixtures?
Let $X$ be a countable set. A lottery on $X$ is a function $\lambda: X \to [0,1]$ such that $\sum_x \lambda(x) = 1$. Let $\Delta X$ be the set of lotteries on $X$.
A total preorder $\preceq$ on $\...
- 869
1
vote
0
answers
106
views
strict convexity of the Legendre-Fenchel transform
Let $d$ be a positive integer.
Let $L:\mathbb{R}^d\to\mathbb{R}$ be a differentiable function with continuous derivatives.
Assume that the Legendre-Fenchel transform of $L$ exists everywhere, is ...
- 11
1
vote
0
answers
135
views
Linearly independent support vectors of a convex set
Let $\Omega\subset\mathbb{R}^n$ a compact strictly convex set containing $0$ in its interior and let $k\leq n$.
Given a vector $x\neq 0$ in $\mathbb{R}^n$ a supporting vector $\xi_x$ in the ...
- 11
1
vote
0
answers
83
views
Convexity of conditional relative entropy for Markov distributions
Consider two Markov processes $p$ and $q$. The conditional relative entropy between them is
\begin{align}
D(p\parallel q)& =\sum_a p(a)\sum_b p(b\mid a)\log\frac{p(b\mid a)}{q(b\mid a)}\\
& =\...
- 11
1
vote
0
answers
35
views
Modelling exact unions of polytopes in homogeneous case?
We can model disjunctions (note I am not looking for convex hull) of $t$ unbounded convex polyhedra given by $A^{(1)}x^{(1)}\leq b^{(1)}$,$\dots$,$A^{(t)}x^{(t)}\leq b^{(t)}$ exactly with a mixed ...
- 1,826
1
vote
0
answers
120
views
John's ellipsoid of a polytope
Suppose that $X$ is $\mathbb R^n$ with some polyhedral norm, that is, the unit ball of $X$ is an $n$-dimensional polytope. Assume that the John ellipsoid of $X$ is an Euclidean ball that touches every ...
- 113
1
vote
0
answers
389
views
The perturbation of a convex function can also be convex?
$ W^{1,\infty}(D)\ni f:D\to\mathbb R, (x,y)\mapsto f(x,y)$, is a strictly increasing on both dimensions (i.e. if $x_1>x_2$ then $f(x_1,y)>f(x_2,y)$), lipschitz continuous function defined on a ...
- 263
1
vote
0
answers
616
views
Convexity of the variance of a function depending on random variables
here is my question:
I have a function $f(x,\epsilon_1, \dots, \epsilon_n)$ that depends on a decision $x$ I make and a certain amount of random variables $\epsilon_i$.
I define the two following ...
- 11
1
vote
0
answers
60
views
Condition on $f := (I-\delta P)^{-1}g$ to ensure convexity of $f$?
Consider the following extension of the notion of convexity of continuous functions to functions defined over $\mathcal{I} = \{0,\ldots,n \}$ — that is, to vectors: $f$ is convex if for any $\alpha \...
- 133
1
vote
0
answers
676
views
Are Outer Products of Sub-Gaussian Vectors Sub-Exponential?
$\newcommand\xx{\mathbf{x}}\newcommand\yy{\mathbf{y}}\newcommand\A{\mathbf{A}}\newcommand\aalpha{\boldsymbol{\alpha}}\newcommand\bbeta{\boldsymbol{\beta}}\newcommand\E{\mathbb{E}}\newcommand\inner[1]{\...
- 153
1
vote
0
answers
88
views
On convex quadratic programming clarification
We know convex quadratic programming is in $P$.
Is it also in $P$ if the function of interest is only convex in the domain of interest?
- 13.9k
1
vote
0
answers
149
views
Coordinate descent conditions
The following is quoted from "Bertsekas, D. P. (1999). Nonlinear programming (p. 794). Belmont: Athena scientific".
Convergence of Coordinate Descent: Suppose a function $f$ is continuously ...
- 133
1
vote
0
answers
180
views
Continuity of a convex function on a vector bundle
Consider the rank-${n \choose m}$ vector bundle $\pi\colon E:=\bigwedge^m(TN)\to N$ over a smooth Finsler manifold $N$ and equip each fibre $E_q := \pi^{-1}(q)$ with a norm that depends smoothly on $q\...
- 193
1
vote
0
answers
181
views
Stochastic increasing convex ordering
Consider $n \geq 2$ and the simplex
\begin{equation}
\Delta=\{(p_1,\cdots,p_n) \in \mathbb{R}^{n} \mid \forall i, p_i \geq 0 \text{ and } \sum_{i=1}^{n}{p_i}=1\}
\end{equation}
Suppose that $\Delta$ ...
- 111
1
vote
0
answers
368
views
Convex hull of the intersection of nonconvex sets
I have a set $D$ in $\mathbb{R}^{d+1}$ which is the intersection of $d$ domains $D_i$ given by $f(x_{i}) \leq x_{i+1} \leq g(x_{i})$ for two functions $f$ and $g$.
I want to find the convex hull of $...
- 31
1
vote
0
answers
447
views
Largest possible variance for log-concave distributions on a bounded interval
Let $f$ be the density of a log-concave probability distribution on the interval $[0,1]$ (with respect to Lebesgue measure). To be concrete, suppose that $f(x) = \exp( - \varphi(x))$, for some convex ...
- 251
1
vote
0
answers
232
views
Semi-convex problem and almost convex problem
I have a target function, I've computed its Hessian to check convexity, it has a positive-definite sub-matrix and small negative-definite sub-matrix and a kernel. Sometimes it is even better -- the ...
- 355
1
vote
0
answers
66
views
Comparison inequalities for Hamiltonian mechanics with convex potential - analogue to Rauch's theorem?
I'm asking about an area (Hamiltonian mechanics) that I don't know at all well; thus, I keep the question somewhat vague.
In differential geometry, there are a number of results saying that geodesics ...
- 11
1
vote
0
answers
59
views
Conditions on probability measure that generates non-void random polytope
Let $C$ be a non-void compact convex set in $\mathbb{R}^d$, and $\nu$ a probability measure on $C$. Then under what conditions on $C$ and $\nu$, the following statement is true: If $X_1,\cdots,X_{d+1}$...
- 599
1
vote
0
answers
139
views
Can we define log-convex operators?
Let $I\subset\mathbb{R}$. A function $f:I\rightarrow\mathbb{R}$, is said to be log-convex if $\log f$ is convex or equivalently for all $x,y\in I$ and $\alpha\in [0,1]$
$$f(\alpha x+(1-\alpha)y)\leq [...
- 55
1
vote
0
answers
126
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,109
1
vote
0
answers
100
views
Changing a nonlinear equality constraint into some conic inequality plus rank constraint
If we have a constraint optimization problem in which one of our constraint is $\prod\limits_{k = 1}^N {\left( {x - {a_k}} \right) = 0} $ . How could this nonlinear equality condition be changed into ...
- 33
1
vote
0
answers
298
views
Proving solution to linear parabolic PDE is convex with negative third derivative
I have a PDE in $g(y,t)$ of the form
\begin{equation}
a\frac{\partial^2g}{\partial y^2}y^2-b\frac{\partial g}{\partial y}y -rg + \frac{\partial g}{\partial t} - c = 0
\end{equation}
in which $a$, $b$, ...
- 19
1
vote
0
answers
291
views
Proof of an inequality for a linear combination of three trigonometric functions
Given a function $$f(t) = k_{1} \sin(t+\alpha) + k_{3} \sin(3t+\beta) + k_{5} \sin(5t+\gamma)$$
where $k_{1}, k_{3}$ and $k_{5}$ are all positive parameters, and the three phase angles, $ 0<\alpha&...
- 29
1
vote
0
answers
324
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?
- 6,962
1
vote
0
answers
81
views
Reference request: Compact metrizable semilattices with small connected semilattices are absolute retracts
Let $X$ be a compact metrizable topological semilattice with a neighbourhood base of sub-semilattices that are path-connected. I need a reference for a proof that $X$ is an absolute retract.
Here is ...
- 900
1
vote
0
answers
79
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 $A_{+}$ ...
- 6,962
1
vote
0
answers
285
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 $\mathbf{p}=[p_1\;\ldots\;p_m]^\top,\mathbf{q}=[q_1\;\ldots\;...
- 607
1
vote
0
answers
360
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 R^...
- 11
1
vote
0
answers
114
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 ...
- 11
1
vote
0
answers
552
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 ...
- 111
1
vote
0
answers
227
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 ...
- 519
1
vote
0
answers
236
views
Convexity of a constrained optimization problem
Hi, this is a continuation of a previous question I asked about the convexity of an optimization problem I am working with.
Consider the function
\begin{multline}
B_i(a_0,\mathbf{p}) \equiv B(\vec{x}...
- 73
1
vote
0
answers
466
views
Bounding point-wise maximum of the absolute difference of two convex functions
Let $\Delta: R \times R \rightarrow R_{+}$ be a positive and convex function (convex in, say, both the arguments) called the loss function.
Let $x \in R^d$. Moreover, let $H_1,...,H_r$ be sets of ...
- 11