All Questions
1,018 questions
5
votes
2
answers
447
views
Extending a convex function to a higher dimensional domain
Let $D\subset{\mathbb R}^2$ be the unit disk, and $I=(-1,1)$.
Let $v\in C^2(\bar I)$ be a convex function.
Does there exist a convex function $u\in C^2(\bar D)$, such that on the one hand $u(\cdot,0)=...
- 52.3k
1
vote
1
answer
185
views
Derivative of Moreau envelope in Hilbert space with respect to regularization parameter $\lambda$ using Hopf-Lax formula?
Let $\mathcal H$ be a Hilbert space, $f \colon \mathcal H \to (- \infty, \infty]$ a proper, convex, lower semi-continuous function and $\lambda > 0$.
The $\lambda$-Moreau envelope of $f$ is
$$
f_{\...
- 67
3
votes
0
answers
87
views
Instances of c-concavity outside of optimal transport?
Let $X$ and $Y$ be metric spaces, and let $c:X\times Y\rightarrow \mathbb{R}$ be a nonnegative function which we refer to as a cost. For any $\phi:X\rightarrow \mathbb{R}$ and $\psi:Y\rightarrow \...
- 232
2
votes
1
answer
213
views
Is matrix B obtained from matrix A?
Assuming a matrix $\mathbf{A} \in \mathbb{R}^{4096 \times 4096}$ sampled from a standard normal distribution $N(0, 1)$, and another matrix $\mathbf{B} \in \mathbb{R}^{4096 \times 4096}$ either sampled ...
- 49
0
votes
0
answers
81
views
Is a bounded measurable convex function above its interior lower semi-continuous convex envelope?
Let $E$ be a locally convex topological vector space, let $C$ be a convex set which matches the closure of its relative interior $\mathring C=\{ x\in C : \forall y\in C,\exists z\in C,~x\in\mathopen]y,...
- 204
0
votes
0
answers
43
views
For a convex body $K\subset R^n$, does the quantity $\min_{t>0} E[t^{-1} \|tg - \pi_K( t g)\|_2]$ have a name? Where has it been studied?
Consider a convex compact set $K\subset R^n$ (with non-empty interior if that helps).
Let $\Pi_K:R^n\to K$ be the projection onto $K$, defined as
$$
\Pi_K(x) = \operatorname{argmin}_{k\in K} \|k-x\|
$$...
- 1,724
-1
votes
1
answer
80
views
Regions when a concave function is smaller than another concave function
Let $f_1,f_2:[0,1]\mapsto\mathbb{R}$ be two bounded and concave functions. Assume $f_1(0)<f_2(0)$ and $f_1(1)<f_2(1)$. I want to investigate the set $\mathcal{X}\triangleq\{x\in[0,1]: f_1(x)>...
- 53
0
votes
0
answers
36
views
ILPs with square constraint matrix
Given the Integer Linear Programming ($\text{ILP}$) problem
\begin{array}{ll}
\text{minimize} & c^T x \\
\text{subject to}& \mathbf{A}^T x \ge b \\
\text{where}&c,x,b\in\mathbb{N}_0^n,\\ &...
- 13.2k
1
vote
1
answer
128
views
Is a bounded convex function $g$ that is non-negative on this particular convex set also non-negative on the its closure?
Setup :
Let $S$ be the simplex on $\mathbb N$, i.e. the set of probability distribution on the natural numbers. Suppose we have $p\in S$ such that, for all $n\geq 1$, $p_n > 0$. For any $\emptyset\...
- 204
1
vote
1
answer
123
views
Properties of the relatively bounded probability distributions on the simplex over the natural numbers
Setup :
Let $S$ be the simplex over $\mathbb N$, i.e. the set of probability distribution over $\mathbb N$. Let $p\in S$ be such that $0 < p_n$ for all $n\in \mathbb N$. Let $H$ be the Hilbert ...
- 204
0
votes
0
answers
26
views
Monotony of enforced subtour merging
Is it true that for a symmetric TSP instance in the sequence of edges generated by successively:
calculating the optimal 2-factor
adding cardinality constraints on the edgesets of the 2-factor's ...
- 13.2k
0
votes
0
answers
171
views
Solve NP-hard type problems with linear programming
I would like to know if there is any way to solve an NP-hard type problem, for example, the TSP, sum of subsets or knapsack problem, by using linear programming and not by brute force.
I ask this ...
0
votes
0
answers
64
views
Alternatives to McCormick Envelope
I have an optimization problem for which I have the optimal solution obtained by the ILP.
However, when I introduced the McCormick Envelope to replace the product of a bi-linear term in its LP ...
- 3
2
votes
0
answers
119
views
Seeking insights on bounded set positive solutions for a set of linear systems in $\mathbb{R}^n$
Before delving into my query, I'd like to provide some context. Consider a continuous function $f:\mathbb{R}^{k}\rightarrow\mathbb{R}^{m}$ and a compact set $\mathcal{B}\subset \mathbb{R}^{k}$ (...
1
vote
1
answer
209
views
Does an uncountable convex combination of elements of a set lie in the convex hull of the set in finite dimension?
Suppose that $\mathcal{F}$ is a finite-dimensional vector space and that $C\subseteq\mathcal{F}$ is a convex subset of $\mathcal{F}$.
Is it true that an uncountable convex-combination of elements of $...
- 199
3
votes
0
answers
65
views
Convex combination of cyclically monotone sets
I want to show the following statement, but I am not sure how.
Proposition(?):
Let $C \in \mathbb{R}^d$ be a compact convex set, and let $u, v : C \to \mathbb{R}$ be smooth convex functions.
Suppose
$$...
- 51
0
votes
0
answers
129
views
Primal optimal attained implies dual optimal attained
Given some optimization problem
$$\min_{x \in S \subset \mathbb{R}^n} f_0(x) \quad \text{s.t.} \quad f_i(x) \leq 0, \quad 1\leq i\leq m$$
we can find the dual problem
$$\max_{\lambda\in\mathbb{R}^m} g(...
- 275
0
votes
1
answer
169
views
How to integrate an indicator function/constraint into the cost function of a linear program?
I have a mathematical model $P$ for which I optimize two cost functions say $F_1$ and $F_2$ subject to a set of constraints $C1$–$C10$.
In $F_2$, I want it to be included only when its expression ...
- 3
1
vote
1
answer
156
views
On the additive property of the subdifferential of lower semicontinuous functions
Let $f:\mathbb R\to\mathbb R$ be a lower semicontinuous function, we define the Fréchet subdifferential of $f$ at $x\in\mathbb R$ by
$$\partial^F f(x):=\left\{L\in\mathbb R: \liminf_{v\to0}\frac{f(x+v)...
- 299
4
votes
1
answer
186
views
Convex hull of 3 points in Cartan-Hadamard manifolds
Can the convex hull of $3$ points in a Cartan-Hadamard manifold be smooth?
A Cartan-Hadamard manifold $M$ is a complete simply connected manifold with nonpositive curvature (so it includes the ...
- 7,149
0
votes
0
answers
164
views
Inf-convolution of norm 1 and norm 2 square
The inf-convolution of the functions $f$ and $g$ defined on $\mathbb{R}^n$ is
$$
h(x)=\inf _{y \in \mathbb{R}^n} f(y)+g(x-y) .
$$
We can prove that if $f,g$ are convex functions, then $h$ is convex.
...
- 129
1
vote
1
answer
72
views
Is this notion of being "fully" convex closed under set addition?
While reading through "Linear Operators: General theory" by "Jacob T. Schwartz", reading the corollary to II.10.1 which states that for a compact convex subset $C$ of some ...
- 204
1
vote
1
answer
96
views
If $|P|<\infty$ and $C=P\cap\partial(\textrm{Conv}(P))$, then $P\subset\textrm{Conv}(C)$?
That is, if $P$ is a finite set, and $C$ is the set of points in $P$ which lie on the boundary of the convex hull of $P$, then is $P$ contained in the convex hull of $C$?
It seems true intuitively. In ...
0
votes
1
answer
28
views
Calculating vertex potentials from optimal matchings
Question:
can the solution to the dual of a Linear Program be calculated directly from the solution of the primal Linear Program?
If yes, what are known algorithms and their bounds on complexity.
As ...
- 13.2k
2
votes
1
answer
183
views
Lipschitz smooth convex extension
Assume that convex $f: S \to \mathbb{R}$ with $L$-Lipschitz continuous gradient on some convex compact $S \subset \mathbb{R}^d$ is given. It would be very helpful if there existed function $F$ such ...
3
votes
1
answer
155
views
Is a compact set of extreme points contained in a compact face?
I have run into the following question in convex analysis, which I haven't found answered in the literature:
Suppose that $K$ is a "nice-enough" non-compact convex subset of a Hausdorff ...
- 135
2
votes
1
answer
225
views
Boundary points in $\overline{\operatorname{conv}\{z_i\}_{i\in I}}$
Let $X$ be an infinitely-dimensional Banach space and $\{z_i\}_{i\in I}$ be a set of linearly independent points in $X_{\leq 1}$, the closed unit ball of $X$. $I$ the index set is not necessarily ...
- 307
1
vote
0
answers
94
views
Linear Program Optimal Value
If $f(A,b,c)$ is the optimal value of a linear program
$\min c.x$
subject to $A.x \leq b ; x \geq 0.$
Does $f(A,b,c)$ have a piecewise polynomial/rational upper bound in $(A,b,c)$ on the domain of ...
0
votes
1
answer
114
views
Mixed integer program and continuous Diophantine approximation
Let $n\in\mathbb{N}$ such that $n\geq 2$ and let $0<r<1$ be a real number. We wish to solve the following problem.
$$\min_{(t,(z_j)_{j=2}^n) \in \mathbb{R}\times \mathbb{Z}^{n-1}} t$$
subject to ...
5
votes
1
answer
455
views
Is there a Borel measurable $f:\mathbb{R}^d \to \mathbb{R}^d$ such that $f(x) \in \partial \varphi (x)$ for all $x$?
Let $\varphi: \mathbb{R}^d \to \mathbb{R}$ be a convex function. The subdifferential of $f$ at $x$ is defined as
$$
\partial \varphi (x) := \{z \in \mathbb{R}^d : \varphi(y) \geq \varphi(x) + \langle ...
- 835
0
votes
0
answers
56
views
Zero flux along lines
I am considering the $L^1$ ball in $\mathbb{R}^d$, and a conservative vector field $V$ on it, which arises as the gradient of a bounded, almost-everywhere Lipchitz-function. Denoting by $e_i$ as the i’...
- 232
2
votes
1
answer
151
views
Distance between convex hulls in a bounded closed convex set
Let $X$ be an infinite-dimensional Banach space and $C\subseteq X$ be a bounded closed convex subset. Let $\{z_i\}_{i\in\mathbb{N}}$ be a sequence of linearly independent points in $C$ and for each $n\...
- 307
1
vote
0
answers
166
views
Monotone likelihood ratio of convolved power function kernel, $p\ge 3$
It was shown in a previous answer that for: $f(x)=|x|^p$, $\;x\in \mathbb{R}$, $\;p>2$, defining the density:
$$p(\phi;\theta) = \Big(f\big(\hspace{-1pt}\cos(\phi-\theta)\big) - f\big(
\hspace{-1pt}...
- 391
2
votes
1
answer
240
views
Is the problem of vertex enumeration from an H-representation of a polytope NP-hard?
According to the Wikipedia page on the issue, the vertex enumeration problem is NP-hard.
However, double description and reverse linear search are algorithms listed to solve the problem. Moreover, ...
- 123
3
votes
1
answer
42
views
A converse question about the polyhedrality under linear mapping
It is quite well known that for any polyhedral set $K$ and any linear mapping $A$, the set $AK$ is polyhedral and hence closed. I am more curious about the converse problem, namely:
Suppose $K$ is a ...
- 300
2
votes
0
answers
58
views
Extension of averaged nonexpansiveness for mappings that are not self maps
Let $\mathcal{H}$ be a Hilbert space and let $\alpha \in (0,1)$. We say that an operator $f:\mathcal{H} \rightarrow \mathcal{H}$ is
Nonexpansive if $\|f(x)-f(y)\|_{\mathcal{H}} \le \|x - y\|_{\...
- 21
2
votes
1
answer
170
views
Log-concavity of the difference of the second anti-derivative of Gaussians
I would like to prove the following but I couldn't manage to do it. Let $a>b>0$ be two real numbers. Let $f$ be the function defined as:
$$\forall \sigma>0, ~\forall x\in\mathbb{R},~f_\sigma(...
- 393
1
vote
0
answers
269
views
Monotone likelihood ratio of a kernel based on $\log(\cosh(x))$
Let $f(x) = \log(\cosh(x))$, and define the kernel density:
$$p_r(\phi;\theta) = \Big(f\big(r\cos(\phi-\theta)\big) - f\big(r\cos(\phi+\theta)\big) \Big)\hspace{0.5pt} \frac{\sin(2\phi)}{\sin(2\theta)}...
- 391
1
vote
1
answer
151
views
Monotone likelihood ratio of densities based on power function
Given $p,\phi,\theta \in \mathbb{R}$ such that $p>2$ and $0 \le \phi,\theta\le \pi/2$ define the density function:
$$f(\phi;\theta) =
\mbox{$\Large\frac{1}{p B\big(\hspace{-1pt}\frac{3}{2},\frac{p+...
- 391
0
votes
1
answer
33
views
Sign Regularity of a Density Kernel with Convexity Properties
(Asking a final time in a new question because the previous version had insufficient conditions, as pointed out in the answer there.)
Define the densities:
$$p(\phi;\theta,r) = \Big(f\big(r\cos(\phi-\...
- 391
1
vote
1
answer
109
views
Monotone likelihood ratio of a family of densities with convexity property
(Asking again in a new question because the previous version had insufficient conditions, as pointed out in the answer there.)
Define the densities:
$$p(\phi;\theta,r) = \Big(f\big(r\cos(\phi-\theta)\...
- 391
1
vote
1
answer
133
views
Monotone likelihood ratio of a family of densities with compact support
Define the family of densities:
$$p(\phi;\theta) = \Big(f\big(\hspace{-1pt}\cos(\phi-\theta)\big) - f\big(\hspace{-1pt}\cos(\phi+\theta)\big)\Big)\hspace{0.5pt} \frac{\sin(2\phi)}{\sin(2\theta)}, \...
- 391
2
votes
2
answers
191
views
Log convexity of hypergeometric function for $a,b,c>0$
Prove that:
$$ f(x) = \log\big(
{}_2F_1(a,\,b\,;\,c\,;\,x^{-1})\big),\;\;a,b,c>0
$$
is convex (and decreasing) on $(1,\infty)$.
It actually seems that the stronger result that $f\big((x+1)^{\beta}\...
- 391
0
votes
0
answers
55
views
Relationship of optimal solutions between the total function and the sub function
This is an unconstrained convex optimization problem. Let $\mathcal{N}=\left\{1,\ldots,n\right\}$, $2\leq n<\infty$. Suppose there are many strongly convex functions $f_i(x)$, where $x\in\mathbb{R}^...
- 1
0
votes
0
answers
85
views
Show that $\max_{P_X : X\in (0,1) } \left| \frac{\mathbb{E} [ f'(X) ]}{ \mathbb{E} [ f(X) ] } \right|$ is maximized by at most two mass points
Let $f$ be some given well-behaved function. Consider the following optimization problem overall probability distribution on $[0,1]$
\begin{align}
\max_{P_X : X\in [0,1] } \left| \frac{\mathbb{E} [ ...
- 671
1
vote
1
answer
69
views
$A^*$ algorithm to find shortest path when weights in my graph are the inverse of distance
Given a graph G=(V,E) where the weights on my edges are inverse of Euclidian distance between nodes, I want to know if I can use A* algorithm to find the shortest path. How I need to modify the ...
- 111
4
votes
1
answer
162
views
Uniqueness of critical points for Lipschitz perturbations of uniformly convex Hamiltonians
Consider a macroscopic free energy functional of the form
$$\mathcal{F}_\beta(\mu):= \frac{1}{\beta}\int_{\mathbb{R}^d}\log(\mu)\mu dx + \int_{\mathbb{R}^d}V(x)\mu(x)dx + \iint_{(\mathbb{R}^d)^2}g(x-y)...
- 873
1
vote
1
answer
72
views
Generalised Lebesgue transform continuous wrt. strict topology?
Let $X$ and $Y$ be $\sigma$-compact spaces, and $\mu$ [resp. $\nu$] be a regular Borel probability measure on $X$ [resp. $Y$].
For a bounded continuous $c:X\times Y\rightarrow\mathbb{R}$, consider the ...
- 463
0
votes
1
answer
93
views
Continuity of generalised Legendre transform
Let $X$ and $Y$ be $\sigma$-compact spaces, and $\mu$ [resp. $\nu$] be a regular Borel probability measure on $X$ [resp. $Y$].
For a bounded continuous $c:X\times Y\rightarrow\mathbb{R}$, we consider ...
- 463
1
vote
1
answer
209
views
Does the value function of a quadratic program stay convex when adding constraints?
I am interested in the value function of a quadratic program of the form
$$
v(y)=\min_x \frac{1}{2} x^\top Q(y) x,
$$
subject to a linear equality constraint
$$
E(y)x=d(y),
$$
and a linear inequality ...
- 379