Questions tagged [convex-analysis]
Convex analysis is the study of properties of convex sets and convex functions. For questions about optimization of convex functions over convex sets, please use the (convex-optimization) tag.
9,373
questions
1
vote
1
answer
15
views
Strong Convexity Inequality with Minimizer
I was reading "Primal-dual subgradient methods for convex problems" by Nesterov, and in the appendix, he proves that if $d(x)$ is $\sigma$-strongly convex, then it has a minimizer $x'$, and ...
3
votes
2
answers
76
views
Can a point be closer to all the vertices of a convex polytope than another point inside that polytope?
Consider a set $X = \{x_i \in \mathbb{R}^n\}$ and denote its convex hull
$$
C \equiv \bigg\{ \sum_i \lambda_i x_i : \lambda_i \geq 0 \text{ for all } i \text{ and } \sum_i \lambda_i = 1 \bigg\}.
$$
I ...
- 33
0
votes
0
answers
17
views
Construction of largest convex minorant of a sequence
Given a sequence $a_n$, construct the largest minorant $b_n$, i.e. $b_n \leq a_n$, that is convex.
A natural candidate is
$$
b_n = \inf \left\{\frac{(r-n)a_l + (n-l)a_r}{r-l} \mid l \leq n < r\...
- 13
0
votes
0
answers
20
views
Geometric intuition of the graph of Fenchel conjugate function
The fenchel conjugate as described in detail here is
$$f^*(y)= \sup_{x \in \operatorname{dom} f } (y^Tx-f(x))$$
The above post linked some intuitions on what values the Fenchel conjugate obtains at ...
- 1,104
0
votes
0
answers
31
views
convex function in convex domain has its minimum (or bounded from below)
Prove or disprove the following statement.
Suppose that $E$ is a convex subset of $\mathbb R^n$ and that
$f:E\to\mathbb R$ is a convex function. Then $f$ has its minimum. (Or
$f$ is bounded from ...
- 87
2
votes
1
answer
51
views
The sufficient condition for a function to be convex on the interval $[a;b]$
When I read about convex functions, I often encounter theorems of the following form: For a continuous function $f$ on the interval $[a;b]$ satisfying $f''(x) \geq 0$ for all $x \in [a;b]$, then $f$ ...
- 381
0
votes
0
answers
17
views
Can all quasiconvex functions be represented as a ratio of a convex function and a concave function?
My optimization algorithms teacher raised this conjecture:
$\forall f:D\subset\mathbb{R}^n\rightarrow \mathbb{R}$ quasiconvex $\exists (p, q)$ where
$p:D\rightarrow \mathbb{R}$ convex,
$q:D\rightarrow ...
- 151
2
votes
0
answers
12
views
Sobolev Regularity of Convex Envelope
Suppose I know the function $f \in W^{2,p}$ for some $p>p*$ where p* is the Sobolev exponent needed in order for f to embed into $C^{1,\alpha}$. Then classical regularity theory for convex ...
0
votes
0
answers
28
views
Proving that any convex function on $\mathbb{R}$ is bounded above, then any subharmonic function bounded above on $\mathbb{C}$ is constant
The following question arises from another exercise of Ransford's book.
Let $-\infty\leq a<b\leq+\infty$ and $f\colon(a,b)\rightarrow\mathbb{R}$. We say that $f$ is convex if for
$$c=(1-\lambda)x+\...
2
votes
0
answers
42
views
Simple question on the gauge function
Suppose that $X$ is a real vector space and $K$ is a convex subset of $X$ that contains the origin as an interior point of $K$, i.e., if $y\in X$, then there exists an $\epsilon_{y} >0$ such that
\...
- 175
0
votes
0
answers
21
views
Question about proper separation of two convex sets
I would like you to give me some advice on how I can use the advice that this problem gives me, I managed to solve the problem using only properties but I did not use the suggestion.
Let $C, D \subset ...
- 35
1
vote
2
answers
37
views
Can a closed convex cone not containing a line passing through the origin contain a line?
Suppose that $K$ is a closed convex cone in $\mathbb{R}^n$. We know that $K$ does not contain any line passing through the origin; that is, $K \cap -K = \{0\} $. Does it imply that $K$ does not ...
- 143
2
votes
1
answer
97
views
Compute the complexity of the gradient descent.
Let $f$ be a $L$-smooth and convex function. We denote $\|\cdot\|$ to be the $\ell_{2}$-norm on $\mathbb{R}^{n}$. The definition of $f$ being $L$-smooth is the following $$f(x)\leq f(y)+\langle \nabla ...
- 5,383
1
vote
1
answer
43
views
How to use co-coercity property to prove $\|x_k - x^* \|\leq (\frac{L-m}{L+m})^k \|x_0 - x^*\|$ for steepest descent with $\alpha = \frac{2}{L+m}$?
I am trying to solve exercise 3.5 in Optimization for Data Analysis but can't seem to get it quite right.
The exercise is as follows:
Suppose that $f: \mathbb{R}^n \rightarrow \mathbb{R}$ is a ...
- 11
0
votes
0
answers
23
views
How an indicator function can be approximated to a convex one?
I'm reviewing a paper on Schedule Optimization of Electric Vehicles, and they're using a function that I am not familiar with.
They're proposing as one of the objective functions to minimize:
$$ \eta^{...
0
votes
0
answers
18
views
Ratio of two Jensen's Inequality
I have these pair of numbers
$ (a, b) = (\frac{4}{9}, \frac{1}{9}) $ and $(c, d) = (\frac{1}{2}, \frac{1}{6}) $. (Number mean nothing, just for illustration and simplification)
Note that - (a, b) are ...
- 177
1
vote
1
answer
38
views
Optimize ratio of two positive convex functions
I am trying to minimize this function over x. If it is convex -- there should be no problem. But I doubt that it is convex. Any algorithmic thoughts?
$$F(\mathbf{x})= \frac{|\mathbf{a}^T\mathbf{\Sigma}...
- 1,523
0
votes
2
answers
33
views
Is the ratio of two positive (non zero functions) quasiconvex or convex?
I am trying to minimize the below function, can it be considered quasiconvex and/or convex?
$$F(\mathbf{x})= \frac{|\mathbf{a}^T\mathbf{\Sigma}\mathbf{x}|}{\mathbf{x}^T\mathbf{\Sigma}\mathbf{x}}$$
...
- 1,523
3
votes
0
answers
66
views
The inequality of convex function including power function
I want to show the following.
$$ \phi((\lambda g_1 + (1-\lambda)g_2)^k) - (\lambda g_1 + (1-\lambda) g_2)^k \nabla \phi(f^k) \le \lambda \phi(g_1^k) + (1-\lambda)\phi(g_2^k) - (\lambda g_1^k + (1-\...
- 41
0
votes
0
answers
14
views
Proving that the Chebyshev approximation can be written as a linear program
Given the Chebyshev (or minimax) approximation problem:
$\min_\limits{x} ||Ax-b||_\infty, \\
\text{subject to } x \succeq 0$
I want to write it as a linear program in the following manner:
$\min_\...
0
votes
0
answers
36
views
Prove that a functional is $\alpha$ convex and continuous
I have hard time trying to prove this functional is $\alpha$ convex and continuous
$$
J(v) = \frac{1}{2}\int_{0}^{1}\lvert v'(x)\rvert dx - \int_{0}^{1}f(x)v(x)dx
$$
Where $v\in H_{0}^{1}(0,1)$ and $f ...
- 1,108
0
votes
1
answer
40
views
Proving convexity of a second-order cone from basic definition of convexity
I am trying to prove that the second-order cone defined as $C = \{(x,t): || x ||_2 \leq t, t\geq 0\}$ is a cone and is convex. I want to use the definition of convexity. Here is what I have so far:
...
-2
votes
0
answers
44
views
Ratio vs individual numbers vs difference. [closed]
I have these pair of numbers
$ (a, b) = (\frac{4}{9}, \frac{1}{9}) $ and $(c, d) = (\frac{1}{2}, \frac{1}{6}) $.
Note that - (a, b) are pair of numbers which represent $(E^2(e_1), E^2(e_2)) $ and (c, ...
- 177
3
votes
4
answers
109
views
When is $\exp(f(x))$ concave?
I'm interested in the set of twice-differentiable functions $f$ such that $\exp(f(x))$ is concave for $x \in [0,1]$. This is equivalent to asking for the set of functions $f$ such that
$$
\left(\frac{...
- 1,185
1
vote
1
answer
47
views
Prove that alpha convexity implies convexity
I encountered recently the concept of alpha convexity for functionals defined on normed spaces. The definition is as follow
A function $f : K\subset E\to \mathbb{R}$ (where $K$ is a convex subset of $...
- 1,108
1
vote
0
answers
28
views
proving concavity of the trigonometry function
I have a complicated function:
\begin{equation}
F(x,y) = \Big\lvert\cos(\sqrt{x^2 + 1}/2)\cos(\sqrt{y^2 + 1}/2) - \frac{xy + 1}{\sqrt{(x^2 + 1)(y^2+1)}} \sin(\sqrt{x^2 + 1}/2)\sin(\sqrt{y^2 + 1}/2) \...
- 77
-1
votes
1
answer
41
views
For convex functions, how is domain defined?
Often times I see authors having a definition for convex function whereby they say that the domain of $f$ is a convex set.
However, how is the domain of this function defined?
I am asking because in ...
- 7,850
0
votes
0
answers
9
views
Prove that the supremum of a family of affine functional is convex
I would like to show that the supremum of a family $(L_i)_{i\in I}$ of affine functional defined on a topological vector space is convex. Here is my strategy : we will show that the epigraph of $f(x)=\...
- 1,108
0
votes
0
answers
48
views
Is it possible to make a posynomial concave using a change of variables?
Update
This question has an answer here.
Consider the following posynomial with respect to the variables $x_1,\dots,x_n$:
$$
\begin{align}
f(x_1,\dots,x_n) &= \sum_{k=1}^K c_k x_1^{a_{1k}} x_2^{...
- 1,185
-1
votes
0
answers
28
views
Convex combinations in $L^2(-\pi,\pi)$ Rudin
i am having troubles with problem 13 in 3rd chapter of Rudin's functional analysis:
It focuses on sequence in $L^2(-\pi,\pi)$ defined as $f_N(t)=\frac{\sum_{n=1}^{N^2}e^{int}}{N}$.
I should prove ...
- 1
2
votes
2
answers
233
views
Intuition behind the Euclidean orthogonal projection
Let $A$ be a closed and convex set in $\mathbb{R}^{n}$, let $x_{0}\in\mathbb{R}^{n}\setminus A$, and define $f:\mathbb{R}^{n}\longrightarrow (0,\infty)$ by $f(x):=\frac{1}{2}\|x-x_{0}\|^{2},$ where $\|...
- 5,383
2
votes
1
answer
87
views
Can every real continuous function be approximated by either a convex or concave function on an interval?
If $0\leq a < b\leq 1;\ p: [a,b]\to [f(m),f(M)] \subset [0,1],$ where $p(m) = \min_{x\in(a,b)} p(x) $ and $p(M) = \max_{x\in(a,b)} p(x), $ is a non-constant continuous function, then $ h_p(x):[0,1]\...
- 17.8k
1
vote
0
answers
38
views
What is the connection between the gradient acting on the support function in Euclidean space and on a sphere?
The support function defined on the unit sphere can be locally represented as a support function defined in the entire space. This can be achieved by using a mapping
\begin{align}
(x_1,\cdots,x_n)&...
- 23
0
votes
0
answers
38
views
Representation of $L_2$ norm with duality, in a Banach space [closed]
Let $(E,\|\cdot\|,\mathcal{F})$ be a Banach probability space, let $\phi:E\rightarrow\mathbb{R}$ be a lower-
semicontinuous convex function, and let $\phi^*$ be its convex conjugate. For any $x\in E$,...
- 305
0
votes
0
answers
18
views
β-strongly convex property
If $f$ is Gâteaux differentiable, deduce that the following propositions are equivalent, for $\beta>0$:
a) $f$ is $\beta$-strongly convex.
b) For all $\gamma \in( 0, \beta], f$ is $\gamma$-strongly ...
- 351
1
vote
1
answer
22
views
Concavity of a two variables function with zero Hessian
I'm stuck on an exercises that asks me to find all values of $a$ for which the following function is strictly concave in the first quadrant:
$$g(x, y) = \left(\frac{1}{3}x^{-a} + \frac{2}{3}y^{-a}\...
- 2,408
0
votes
1
answer
29
views
Convexity of a bivariate function.
I have a function is two variables, $f(x,y)$. $f$ is twice continuously differentiable and increasing in x and y. I want to say that in definition of $f$, $y$ takes the form $y^\alpha$ where $\alpha&...
- 43
1
vote
0
answers
64
views
Split up $\int_5^ \infty\int_\mathbb{R^{n-1}} e^ {-g(|r+x|)} \ dx dr$
I need help in understanding the following problem:
Let $g$ be an anon-constant, convex increasing, and rotation invariant function and let $|x|^2=\sum_{i=1}^n {|x_i|^2}$. We have:
$\int_5^ \infty\...
- 11
2
votes
1
answer
51
views
Directional derivative of proximal mapping of a convex function
Let $f:\mathbb{R}^n\rightarrow\overline{\mathbb{R}}$ be a proper closed convex function that is locally Lipschitz continuous on its domain $D(f)$. Define the proximal mapping of $f$ to be
$$\textbf{...
- 892
1
vote
0
answers
62
views
If $f(x)$ is strictly convex, then is $g(x,y)=f(x + y)$ also strictly convex?
Assume that function $f: \mathbb{R}^{n} \to \mathbb{R}$ is strictly convex.
Next, let $g(x,y): \mathbb{R}^{2n} \to \mathbb{R}$ be such that $g(x,y) = f(x+y)$.
The question: is $g$ a strictly convex ...
- 85
2
votes
1
answer
40
views
Difference of convex functions with many oscillations (looking for examples)
It is known (see e.g. here [pdf]) that any function $f: \mathbb{R} -> \mathbb{R}$ with locally bounded left- and right derivatives can be represented as a difference of convex functions. ...
- 202
3
votes
1
answer
94
views
How to prove $\mathrm{Vol} \left( \mathcal{K} \cap \{x \in \mathbb{R}^n : x^{\top} w \geq 0\} \right) \geq \frac{1}{e} \mathrm{Vol} (\mathcal{K})$
I read the book Convex Optimization Algorithms and Complexity, The Lemma 2.2:
Let $\mathcal{K}$ be a centered convex set, i.e., $\int_{x \in \mathcal{K}} x dx = 0$, then for any $w \in \mathbb{R}^n, w ...
- 93
0
votes
2
answers
36
views
How to see $\ell_0$-penalty is non-convex function?
$$\hat{\beta}(\lambda) = \arg \min_\beta (|| Y - X\beta ||_2^2 /n + \lambda ||\beta||_0)$$
where the $\ell_0$-penalty is $|| \beta||_0 = \Sigma_{j=1}^p 1(\beta_j \neq 0)$.
The textbook says "...
- 511
1
vote
0
answers
29
views
inflection points of NIG distribution [closed]
With $\beta=0$ in the Wikipedia parameterization of the Normal Inverse Gaussian (NIG) distribution, the density is proportional to
$$
p(x) \sim \frac{K_1\left(\alpha \sqrt{\delta^2 +(x-\mu)^2}\right)}{...
- 19
0
votes
0
answers
32
views
Convex separation and edge intersection [closed]
Let us consider a (bounded) closed convex hull $K$ of a finite number of points in $\mathbb{R}^d$. Let us also consider a bounded open convex set $C$ and its boundary $\partial C$. We suppose that the ...
- 9
0
votes
0
answers
31
views
How to prove: An extreme point of a face of a convex set $K \subseteq \mathbb{R}^n$ is also an extreme point of $K$
How do I prove that An extreme point of a face of a convex set $K \subseteq \mathbb{R}^n$ is also an extreme point of $K$
- 11
1
vote
2
answers
35
views
When is the (Fenchel-Rockafellar) duality gap strictly positive?
In optimization, there is a notion of the duality gap, $\Delta$ which is always positive $\Delta\geq 0$. The condition $\Delta=0$, called strong duality, is sometimes quite convenient in the analysis ...
- 4,118
2
votes
2
answers
87
views
Is $f(x)=\frac{\left(\sum_{k=0}^{K-1}\gamma_k (e^{\zeta_kx}-1)\right)^{\alpha}}{x}$ convex? (with $0\leq\alpha\leq 1$, $x>0,\gamma_k>0,\zeta_k>0$)
Is $f(x)=\frac{\left(\sum_{k=0}^{K-1}\gamma_k (e^{\zeta_kx}-1)\right)^{\alpha}}{x}$ convex? (with $0\leq\alpha\leq 1$, $x>0,\gamma_k>0,\zeta_k>0$)
I am trying to show that the above function ...
- 185
1
vote
1
answer
84
views
Is a posynomial concave under the following conditions?
Consider the following posynomial with respect to the variables $x_1,\dots,x_n$:
\begin{align}
f(x_1,\dots,x_n) &= \sum_{k=1}^K c_k x_1^{a_{1k}} x_2^{a_{2k}} \cdots x_n^{a_{nk}} \\
&= \sum_{k=...
- 1,185
-2
votes
1
answer
41
views
Is the following max-min function convex? [closed]
Suppose $f(x_1,x_2,...,x_n)$ is an affine function, $\mathbb{R}^n\rightarrow\mathbb{R}^m$. Let
$$
g(x_1,x_2,...x_n) = \max\{f(x_1,x_2,...,x_n)\} - \min\{f(x_1,x_2,...,x_n)\}
$$
The max and min ...
- 3