All Questions
Tagged with convex-optimization fa.functional-analysis
93 questions
1
vote
0
answers
48
views
What makes the generalized projection different than metric on a Banach space?
I have came across the notion of generalized projection in Banach spaces, introduced by Ya. Alber and has seen many iterative algorithms being solved by using this projection. It helps in finding the ...
- 85
7
votes
0
answers
249
views
Proving this function is convex
Let $C$ be a symmetric positive definite matrix such that $0\leq c_{ij} \leq 1$, $c_{ii}=1$, and define $f$ as $$f(x)=\sum_{i}x_{i}\log(\sum_{j}c_{ij}x_{j})$$ for positive vectors $x$ (in fact let's ...
- 4,049
1
vote
0
answers
73
views
Convexity and subdifferential monotonicity
Do you know any reference where I can find some results in this sense:
Consider $W:K\to [0,\infty)$ is a functional defined on a convex cone $K\subset X$, where $X$ is a Banach space. Then the ...
- 1,759
0
votes
1
answer
150
views
When are infimal convolutions contractions?
Let $X$ be a separable Fréchet space and $\varphi,\psi:X\to \mathbb{R}$ be a lower semi-continuous and convex function with $\psi$ bounded below and coercive. Consider the infimal convolution
$$
\...
- 364
7
votes
2
answers
178
views
Separating domains in $\mathbb{R}^{2n}$ by a real algebraic variety
Suppose $\Omega_1$ and $\Omega_2$ are two disjoint unbounded domains in $\mathbb{R}^{2n}$, $n \in \mathbb{N}$. Can there be conditions on $\Omega_1$ and $\Omega_2$ so that these two domains can be ...
- 171
0
votes
0
answers
40
views
Iterating partially-unconstrained optimization with projection
Let $f:H\to \mathbb{R}$ be a strictly convex Fréchet differentiable, coercive function on a separable Hilbert space $H$ and let $C_1,C_2\subseteq H$ be closed and convex.
I want to optimize
$$
\tag{(A)...
- 5,405
3
votes
0
answers
281
views
Interchange limit and supremum of functionals over a bounded convex set
Let $(H, \langle\cdot,\cdot\rangle)$ be a separable real Hilbert space and $B\subset H$ be (nonempty) convex and bounded, and suppose that $(\alpha_k)\subset H$ is a sequence for which the limit $\...
- 463
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
0
answers
95
views
Self adjoint operators from energy functionals
It is known that the equation
$$
\Delta f = 0
$$
on some bounded domain $\Omega$ on $\mathbb{R}^n$ subjected to certain boundary conditions can be derived through the minimization of the Dirichlet ...
- 115
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
1
vote
1
answer
176
views
Maximization of $\ell^2$-norm
Consider for $r,c>0$ the set
$$X_{r,c}=\{x \in \ell^1(\mathbb{N}) \mid \|x\|_1=r,\, \forall i \in \mathbb{N}: |x_i|<c\}.$$
Then I can show that $\inf_{x \in X_{r,c}} \|x\|_2 = 0.$
But is it ...
- 11
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
1
answer
84
views
optimization over moving domains
Let $A, B$ be Banach spaces, and for any $a\in A$, $B_a\in B$ is a measurable subset. Consider the following optimization problem:
$$L(a)=\inf_{b\in B_a}\ell(b),$$
where $\ell(b)$ is a infinite-times ...
- 87
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
0
votes
2
answers
197
views
Convergence of the infima of convex functions on $\mathbb{R}^m$
Any thoughts on proving the following statement, which is a generalization of the result in convergence of the infima of convex functions from domain $\mathbb{R}$ to $\mathbb{R}^m$ and also Theorem 1 ...
0
votes
1
answer
44
views
Identify maxima for 2-Dimensional Function without knowing cross-derivative
I am trying to proof the uniqueness of a maximum for a two-dimensional function (well behaved, twice differentiable, domain $R^2$, etc.), yet cannot compute the exact derivatives or the Hessian.
I ...
- 103
2
votes
0
answers
56
views
Whether $d_x(t) := \|P_t(x)-x\|_H$ is increasing in $t$ where $P_t:H \to H$ is the proximal operator of a convex function
Let $H$ be a Hilbert space (e.g Euclidean $\mathbb R^n$), and fix a proper convex function $f:H \to (-\infty,+\infty]$. Given any $t \ge 0$, let $P_t:H \to H$ be the proximal operator of $f$ at level $...
- 6,853
1
vote
0
answers
96
views
Dynamical formulation of the 2-Wasserstein distance for *discrete* matrix-valued measures
TL;DR: I want to find a definition generalizing "$t \mapsto \frac{1}{m} \sum_{k = 1}^{m} \delta_{x_k(t)}$ is a Wasserstein gradient flow" to matrix-valued probability measures.
Let $(X, d)$ ...
- 67
0
votes
1
answer
88
views
Is the mapping $F(a):= \arg\min_{x \in \mathbb R^n} \|x-a\|_2 + \|x\|_1$ non-expansive?
Fix $a \in \mathbb R^n$ and let $\|\cdot\|$ be any norm on $\mathbb R$ (e.g $\ell_1$ norm). For any $a \in \mathbb R^n$, it is clear that the function $f_a(x) := \|x-a\|_2 + \|x\|$ is strictly convex ...
- 6,853
5
votes
1
answer
355
views
Are the polyhedral cones the only examples of cones that remains closed when they are added to vector subspaces?
Let $C \subset \mathbb{R}^{n}$ be a closed convex cone. If one wants to know whether the linear map $T:\mathbb{R}^{n} \to\mathbb{R}^m$ sends the closed set $C$ to another closed one, $T(C)$, it is ...
- 225
4
votes
0
answers
622
views
Simple constructive proof for the hyperplane separating theorem (HST)?
The Hyperplane Separation Theorem (HST) is usually proved through the existence of a unique minimum-norm vector in a nonempty closed convex set. I think this is an existential proof which applies to ...
- 599
0
votes
0
answers
143
views
Minimax problem : uniqueness of a solution
Let $n\geq2$. Is it true that the minimax problem:
$$
\min_{p\in\mathcal{P}}\max_{H\in\mathcal H}p^tH\bar{p},
$$
where
$\mathcal H\subset\mathcal{M}(n)$ is a strictly convex bounded subset of ...
- 4,034
2
votes
1
answer
399
views
Smoothness of Minkowski functional is equivalent to smoothness of boundary
Let $C\subseteq \mathbb{R}^n$ be a convex body containing $0$ in its interior. I recently read that Minkowski functional of $C$,
$$
f_C(x):=\inf\Big\{t>0:\frac1{t}\cdot x\in C\Big\},
$$
is $C^1$ ...
- 5,405
2
votes
0
answers
56
views
A variant of the elliptope relaxation
Given a p.s.d. matrix $A$, one may want to find:
$$
\max_x x^t A x \mbox{ such that } x \mbox{ has entries }1 \mbox{ or } {-1}.
$$
This hard problem has a well known relaxation based on the so called ...
- 2,772
4
votes
1
answer
210
views
On some convergence theorems by Felix E. Browder (1967)
I have been reading Felix E. Browder's Convergence Theorems for Sequence of Nonlinear Operators in Banach Space and I was hoping I could find answers to a couple of questions I have about the paper. ...
user452741
3
votes
1
answer
621
views
Strong convexity inequality w.r.t. infinity norm $\lVert\cdot\rVert_{\infty}$
Consider a twice differentiable 1-strongly convex function $f:\mathbb{R}^n \to \mathbb{R}$.
Is it true that there exists $\alpha>0$ independent of $n$ such that, for all $x \in \mathbb{R}^n$:
\...
- 33
2
votes
0
answers
141
views
Optimization of functionals with constraints
I have a minimization problem as follows:
$\min\left( \int_0^1\int_0^1\beta(t)\beta(s)G_1(t, s)dtds\right)^{1/2}+\left( \int_0^1\int_0^1\beta(t)\beta(s)G_2(t, s)dtds\right)^{1/2} $
$\texttt{s.t.}\;\;\;...
4
votes
1
answer
366
views
Example of empty projection in strictly convex Banach space
Let $X$ be a strictly convex Banach space, let $C\subseteq X$ be a nonempty closed convex set, and let $P_C$ be the set-valued metric projection
$$P_C(x) = \{y\in C : \|x-y\| = d(x,C)\} . $$
We know ...
- 267
4
votes
0
answers
140
views
A convex function is "usually" subdifferentiable
Let $X$ be a locally convex topological vector space, and let $f:X\to\mathbb R\cup\{\infty\}$ be a proper, convex, lower semicontinuous function, whose effective domain $D:=f^{-1}(\mathbb R)$ is ...
- 537
2
votes
0
answers
51
views
Conjugate of composition in Bochner spaces
Let $H$ be a separable Hilbert space (of non-zero dimension), let $(\Omega,\Sigma,\mu)$ be a finite measure space, and let $L^2(\mu;H)$ be the Bochner-space $\mu$-integrable $H$-valued functions. ...
0
votes
0
answers
44
views
Let $A,B,C$ be centrally-symmetric convex bodies. What is this function $G(x,y) := \sup_{b \in B}\inf_{a \in A} a^T x - b^T y + \|a-b\|_C$?
Let $A$, $B$, and $C$ be centrally-symmeric convex bodies in $\mathbb R^n$. Note that any such set can such set induces a norm $\|\cdot\|_C$ on $\mathbb R^n$ defined by $\|x\|_C := \sup_{c \in C}c^\...
- 6,853
0
votes
1
answer
279
views
When does strict inclusion holds for the domain of subdifferential?
Recall that, given an extended real-valued function $f: \mathbb{R}^n \to (-\infty, \infty]$
Its effective domain is,
$$\text{dom}(f) = \{x \in \mathbb{R}^n : f(x) < +\infty\}$$
The subdifferential ...
- 103
1
vote
1
answer
173
views
Taut string algorithm and TV-minimization equivalence
Given real numbers $y_i's$, consider the following convex optimization problem:
$$
\min_{x_i's} \sum_{i=1}^N(y_i-x_i)^2 + \lambda\sum_{i=1}^{N-1}|x_{i+1}-x_{i}|.
$$
The paper A Direct Algorithm for 1D ...
- 1,216
0
votes
0
answers
144
views
Optimization over the set of all bounded probability measures
Given $X$ finite, fix a continuous function $\theta \in \Delta^+ (X) \to [0,1]$, fix a probability measure $\mu^*$, and a $\varepsilon > 0$. Consider:
$$
\max_{\mu \in \Delta^+ (X)} \theta (\mu), \...
- 67
5
votes
1
answer
309
views
Find a combination of convex function so that it is positive
A student in my class asked me the following question, I did know what tools will be needed to attack it. But I found it is an interesting question.
Let $f_1,f_2$ be two convex functions on $[0,1]$ ...
- 425
9
votes
1
answer
333
views
Closedness of linear image of positive L1 functions
Let $\mathcal X$ be the Banach space of $L^1$ functions on some probability space, $\mathcal Y$ be some other Banach space, $T:\mathcal X\to \mathcal Y$ be some surjective continuous linear map, $\...
- 537
0
votes
1
answer
481
views
Is it true that every uniformly continuous strictly convex function on convex compact subset of a finite-dim normed vector space has unique minimizer? [closed]
Let $C$ be a convex compact subset of a finite-dimensional normed vector space and let $f:C \to \mathbb R$ be strictly convex and uniformly continuous function (e.g it is sufficient that $f$ be ...
- 6,853
2
votes
0
answers
110
views
A strong duality for convex functional optimization that admits Lipschitz continuity constraints?
Problem Statement
I am looking for formal proof---hopefully textbook material---of two items:
an analogue to Slater's condition [1] that obtains strong duality for optimization of convex functionals; ...
4
votes
0
answers
252
views
Can this function be minimized?
Let $X$ be a locally convex TVS, and let $A$ and $B$ be convex and compact subsets of $X$ with $A \subset B$.
Let $f: A \times B \to [0,\infty]$ have the following properties:
(1) For all $b \in B$, $...
- 869
5
votes
0
answers
252
views
Generalized convexity
Let $X$ be a vector space. The positive-homogeneous function $\|\cdot\|$ is said to be a quasinorm
if $\|x+y\|\le K(\|x\|+\|y\|)$, for some $K\ge1$; it is a norm if $K=1$.
Question: 1. (terminology) ...
- 6,541
5
votes
4
answers
613
views
Optimizing the gradient norm on the unit sphere
Let $ \Bbb S^{d-1}=\{(x_1,\cdots ,x_d): x_1^2+ \cdots +x_d^2=1\}\subset \Bbb R^d$ be the unit
sphere. Let $\nabla u= (\partial_{x_1}u,\cdots, \partial_{x_d}u)$ be the gradient of a function $u\in C_c^\...
- 1,101
1
vote
0
answers
40
views
Minimax theorems in nonconvex setting
Let $X$ be a topological space, $Z$ be a compact convex subset of $\mathbb R^m$, and let $f:X \times Z \to \mathbb R$ be a continuous function (w.r.t the product topology on $X \times Z$).
Question. ...
- 6,853
1
vote
1
answer
80
views
How to compare the minimums of two discrete convex functions?
I have a question that troubled me for a long time.
If I have two convex discrete function $f(·)$ and $g(·)$ such that $f(·) \ge g(·)$. (may be not necessary?)
Let $x_1 = \text{argmin } f(·)$, ...
- 13
1
vote
0
answers
103
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
4
votes
1
answer
254
views
Max-norm projection of a Hermitian matrix onto the set of positive semidefinite matrices
For a given Hermitian matrix $A$ (i.e. complex matrix with $A_{ij}^{\ast}=A_{ji}$) find its max-norm projection onto the set of complex positive semi-definite matrices:
$$\Pi(A)=\mathrm{argmin}_{M\...
- 41
2
votes
0
answers
66
views
Proving the existence of a dual for an infinite linear program
I am concerned with proving the existence of the dual of an infinite linear program. In addition to the writings of Rockafellar, Luenberger, and Boyd & Vandenberghe on: subdifferentials, Legendre-...
- 121
5
votes
1
answer
281
views
Generalization of minimal selection theorem
Consider a metric space $X$ and a set-valued map $F : X \to \mathbb{R}^{n}$. We define the minimal selection
\begin{equation*}
m(F(x)) := \arg\min \big\{ \lvert u \rvert : u \in F(x) \big\},
\end{...
- 351
3
votes
0
answers
255
views
How can we solve this kind of saddle point problem?
I'm trying to solve a saddle point problem of the following form: Let
$(E,\mathcal E,\lambda)$ be a measure space;
$p$ be a probability density on $(E,\mathcal E,\lambda)$ and $\mu:=p\lambda$
$W$ be ...
- 167
0
votes
1
answer
65
views
Is there a general guideline for minimizing $\sup_{y\in H}F(\;\cdot\;,y)$?
Let $H$ be a $\mathbb R$-Hilbert space and $F:H^2\to\mathbb R$. Is there a general guideline for minimizing $\sup_{y\in H}F(\;\cdot\;,y)$?
Since the question is rather abstract, feel free to impose ...
- 167
1
vote
0
answers
79
views
Minimization of a smooth integral functional over a closed convex set
Let $(E,\mathcal E,\mu)$ be a probability space, $I$ be a finite nonempty set, $\gamma:(E\times I)^2\to[0,\infty)$ be measurable, $$F_1(g,w):=\sum_{i\in I}\int\mu({\rm d}x)w_i(x)g(x)\sum_{j\in I}\int\...
- 167