All Questions
Tagged with convex-optimization convex-analysis
157 questions
2
votes
1
answer
92
views
Does approximately null gradient imply approximately global minimum for convex functions?
Let $f: \mathbb{R}^{n} \rightarrow \mathbb{R}_{+}$ be a non-negative and differentiable convex function which vanishes in a non-empty convex set $\Omega$ - possibly unbounded. Usually, when one ...
- 225
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
2
votes
0
answers
58
views
An s-convex function lying between two convex functions
Let $f: \mathbb R_{+} \to \mathbb R_{+}$ be an $s$-function in the second sense, i.e.,
$$ f(\lambda x +(1-\lambda)y) \leq \lambda^s f(x) +(1-\lambda)^s f(y)$$ for every $\lambda \in (0,1)$. Assume ...
- 55
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
1
vote
0
answers
95
views
Distance between two convex sets
Setting
If $A$ an $B$ are two symmetric matrices, we denote by $A >B$ when the matrice $A-B$ is definite positive.
In $\left(\mathbb{R}^{*}_{+} \right)^4$, consider the convex set $$ \Lambda = \...
- 125
0
votes
1
answer
59
views
Do separable cubic constraint and separable quartic constraint SOCP presentable?
I am an engineer who is doing some network modeling and optimization. During my work, I was running into a case that is quite strange. The problem that I am trying to solve seems to be convex and it ...
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
0
votes
1
answer
104
views
Optimality condition for strongly convex function under sparsity constraint
Let $f: \mathbb{R}^p \to \mathbb{R}$ be a $2s$-sparse strongly smooth, $2s$-sparse strongly convex and twice differentiable function. In other words, there exists positive constants $\alpha, L >0$ ...
- 399
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
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
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
98
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 ...
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
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
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
1
vote
1
answer
55
views
From relative convexity to modulus of continuity estimates for the dual gradient mapping
Let $F: \mathbf{R}^d \to \mathbf{R}$ be a convex function, let $m > 0$, and define $Q_m: \mathbf{R}^d \to \mathbf{R}$ to be the mapping $x \mapsto \frac{m}{2} \| x \|_2^2$. One says that $F$ is $m$-...
- 801
2
votes
1
answer
594
views
Tangent cone of a closed convex cone
Let $K \subset \mathbb{R}^n$ be a closed convex set. Given a point $u \in K$, the tangent cone of $K$ at $u$ is defined as (or characterized by)
$$
T_K(u) := \mathrm{cl}(\left\{ t (v - u) \mid v \in K,...
- 163
4
votes
2
answers
353
views
An upper bound of gradient norm for convex functions near minimizer
Let $f:\mathbb{R}^n\rightarrow\mathbb{R}$ be a convex function. Denote $X^*$ as the set of minimizers of $f$ and assume $X^*$ is unbounded. Is it possible that $\|g_x\|$ is unbounded when $d(x,X^*)$ ...
- 311
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
3
votes
0
answers
109
views
Convex minorants to convex functions, given partial Taylor expansion and smoothness estimate
Let $V$ denote a strictly convex function (in arbitrary dimension) whose Hessian is $L$-Lipschitz. Given only this knowledge, and the values of $\left\{ V \left( x \right), \nabla V \left( x \right), \...
- 801
1
vote
1
answer
1k
views
Is a Lipschitz continuous gradient equivalent to this condition?
I know if a function $f: \mathbb{R}^n \to \mathbb{R}$ is $L$-smooth, i.e. its gradient $\nabla f$ is $L$-Lipschitz continuous, then it satisfies the following inequality for any $x, x_0 \in \mathbb{R}^...
- 163
8
votes
0
answers
459
views
Are there any characterizations of $C^2$ convex functions?
There are several characterizations of convex functions with the Lipschitz continuous gradient. If we already know that the function is of class $C^1$, then we have the following equivalent conditions:...
- 28k
0
votes
1
answer
134
views
Strict inclusion for recession cone of closure of a convex set
Let $C$ be a nonempty closed convex subset of $\mathbb{R}^n$. The recession cone of $C$ is given by
$$R_C=\left\lbrace d\in\mathbb{R}^n:x+td\in C, \forall t>0, \forall x\in C\right\rbrace.$$
It is ...
- 129
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
2
votes
1
answer
119
views
Analytic value of $\alpha := \sup_{(x,y) \in C} ax+by$, where $C := \{(x,y) \in \mathbb R^2 \mid x^2 + y^2 \le 1,\,x^2 + c y^2 \le R^2\}$
Let $a,b \in \mathbb R$, $R \ge 0$, and $c > 0$. Define $C := \{(x,y) \in \mathbb R^2 \mid x^2 + y^2 \le 1,\,x^2 + c y^2 \le R^2\}$, and set
$$
\alpha := \sup_{(x,y) \in C} ax + b y.
$$
Question. ...
- 6,853
0
votes
1
answer
67
views
Analytic formula for minimizer of $f(x) := \sqrt{(x-a)^\top S(x-a)}+ r \|x\|_2$
Let $S$ be a positive-definite $n \times n$ matrix and define $\|z\|_S := \sqrt{x^\top S x}$ for any $x \in \mathbb R^n$. Let $a$ be a fixed vector in $\mathbb R^n$ and $r \ge 0$, and consider the ...
- 6,853
0
votes
0
answers
63
views
Direct (first-order ?) algorithm to minimize $u(x) := \|x-a\|_C + r\|x\|_p$
Fix $a \in \mathbb R^n$, $r \ge 0$, $p \in \{1,2\}$, and a positive-definite matrix $C$ of order $n$. Define $u:\mathbb R^n \to \mathbb R$ by $u(x) := \|x-a\|_C + r\|x\|_p$, where $\|z\|_C := \sqrt{z^\...
- 6,853
2
votes
1
answer
121
views
Can we use the solution to two optimisation problems to solve a third, bigger, one?
Background
Say we have an optimization problem $$\min_x f(x) = g(x) + h(x)$$
where $g$ is differentiable and convex, and $h$ are convex but not necessarily differentiable. If $g$ is the mean squared ...
- 33
7
votes
2
answers
497
views
Proving the set $\left\lbrace \frac{(x + y)^2}{\sqrt{y}} \leq x - y + 5, y > 0 \right\rbrace$ is convex
I have recently picked up a course on Convex Analysis in my spare time, but feel I'm not quite up to speed with the 'tricks' for proving a set is convex.
I have managed to prove this by moving all ...
0
votes
2
answers
630
views
Smooth approximation for non differentiable function
Let $f(t) = \min(\frac{1}{\lvert t\rvert}, 1)$. I would like to find a smooth approximating function $g$ such that $f(t) \leq g(t)$ for all real $t$. Is there a nice function $g$ out there? Any ...
- 3,625
2
votes
0
answers
79
views
Convex optimization over compact sets defined as Aumann set-valued integrals
Let $(X,P)$ be a probability measure space. Let $K$ be a convex compact subset of $\mathbb R^d$ and let $F:X \to 2^{K}$ be a set-valued map. Assume that $F$ is:
closed (i.e $F(x)$ is closed for ...
- 6,853
1
vote
2
answers
270
views
Can we substitute this KKT condition into this optimization problem to reformulate the optimization problem?
Suppose I have the following optimization problem
$$ \min\limits_{\mathbf{x},\mathbf{y}} f(\mathbf{x},\mathbf{y}) \tag{1} $$
It is already known that the target function $f$ is continuous and ...
- 73
0
votes
1
answer
101
views
Estimation via projecting onto a convex body
Assume that $\theta$ is in a convex body $K \in \mathbb{R}^n$ and we observe $y = \theta + z$, where $z$ is a noise term (following, say, the normal distribution). Consider an estimator of $\theta$ by ...
- 773
3
votes
1
answer
179
views
On the convexity of certain set of random vectors
Let ${\cal X}$ be the set of pairs of random variables $(X,Y)$ with finite expectations. For constant $c\in[0,1]$, define set
$$
\{(X,Y)\in{\cal X}:\exists a\geq 0, \, b\geq 0 \text{ such that } E[\...
- 7,182
4
votes
1
answer
336
views
Which set of functions admits the existence of the minimizer?
Let $a,b \in \mathbb R$ and consider the functional $J$ on $X$:
$$J[u] = \int_0^1 \left( (u'(x))^2 -a)^2 + b \ln (1+ u^2(x))\right) dx$$
Providing reasons specify if the $\inf J$ over $X$ is attained ...
- 159
1
vote
0
answers
37
views
Sufficient condition for an $n$-tuple to be a convex conjugate
We say $(f_1,f_2,\dotsc,f_N)$ is a convex conjugate if for any $i=1,2,\dotsc,N$ and any $x_i\in\Bbb R^d$, we have:
$$f_i(x_i)=\sup\left\{\sum_{k=1}^{N}\sum_{j=k+1}^N x_k x_j - \sum_{j=1,j\neq i}^N f_j(...
- 183
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
152
views
A truncated Frobenius norm of a matrix is convex or not?
Given a positive integer $k$ and a matrix $X\in \mathbb{R}^{m\times n}$. A truncated frobenius norm of a matrix $X$ is defined by
$$\Vert X \Vert_{k,F} = \sqrt{\sum_{i=k+1}^{m} \sigma_i^2(X)},$$
where ...
- 143
3
votes
0
answers
97
views
Projection onto level set of convex functional
Fix a probability space $(\Omega,\mathcal{F},\mathbb{P})$ and let $F:L^2_{\mathbb{P}}(\mathcal{F})\rightarrow (-\infty,\infty]$ be bounded-blow, convex, lower semi-continuous, and not identically ...
- 5,405
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
2
votes
1
answer
345
views
Can the subdifferential become unbounded at interior points?
Consider $f: \mathbb{R}^n \to \overline{\mathbb{R}}$ a lower-semicontinuous, proper, closed and convex. My question is, can the subdifferential of $\partial f$ be unbounded in the interior of $\text{...
- 179
0
votes
1
answer
550
views
When is a convex function continuous on its domain?
Consider a lower-semicontinuous convex function $f\colon \mathbb{R}^n \to \mathbb{R}$ with domain $C = \{x \in \mathbb{R}^d: f(x) < \infty\}$. I am interested in understanding under what conditions ...
- 13
2
votes
1
answer
189
views
Analytic expression for the Moreau envelope of $x \mapsto \|Ax\|$
Given an $m \times n$ matrix $A$ and a vector $c \in \mathbb R^n$, define $\eta(A,c) \ge 0$,
$$
\eta(A,c) := \sup_{u \in \mathbb R^n} u^\top c - \frac{1}{2}\|u\|^2 - \|Au\|.
$$
Note that $\eta(A,c) = \...
- 6,853
2
votes
1
answer
252
views
When is a function a convex conjugate?
Let $X$ be a Banach space; $X^*$ be its dual; and $g:X^*\to\mathbb R\cup\{\infty\}$ be a proper, convex, weak${}^*$-lower semicontinuous function with weak${}^*$-compact effective domain.
Question: Is ...
- 537
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
7
votes
1
answer
425
views
Nondifferentiable convex function whose subdifferential admits a continuous selection
Is there a convex function $F$ that is not differentiable, but whose subdifferential admits a continuous selection, i.e. a continuous $g$ with $g(x) \in \partial F(x)$ for all $x$ in the domain?
In ...
- 4,529
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
1
vote
0
answers
89
views
Proximity operator of lower semi-continuous and convex functions pre-composed with norm
Let $\phi:(-\infty,\infty) \rightarrow (-\infty,\infty]$ be a some-where finite, lower semi-continuous, increasing, and convex function. It is easy to verify that the function $\Phi:\mathbb{R}^n\...
