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.
10,118 questions
2
votes
0
answers
19
views
Instances when deciding convexity of degree-four polynomials is in P
I was reading Ahmadi et al.'s paper$\color{\magenta}{^\star}$ on a beautiful proof of the NP-hardness of deciding the convexity of quartic polynomials, including homogenous polynomials. For what class ...
- 101
1
vote
2
answers
137
views
Show that $f$ is strictly increasing on $\mathbb{R}_+.$
Problem statement:
Let $f:\mathbb{R} \to \mathbb{R}$ be defined by
$$
f(x) = a_1^x + a_2^x + \dots + a_n^x,
$$
where $n \in \mathbb{N}, \quad n \ge 3,$ and $a_1, a_2, \dots, a_n > 0,$ all of them ...
- 559
-1
votes
0
answers
35
views
When does an optimization problem that is "worth solving" also satisfy strong duality?
I want some minimalistic/easy to remember statements that relate someone's willingness to solve an optimization problem with the strong duality property of that problem. Of course, you would only want ...
- 8,711
3
votes
3
answers
192
views
The only area–preserving linear symmetry of a strictly convex body fixing a boundary point is the identity?
If $K\subset\mathbb R^2$ is strictly convex, $T\in SL(2,\mathbb R)$ is linear with $T(K)=K$, and $T$ fixes some boundary point $p\in\partial K$, must $T$ be the identity?
Without strict convexity, we ...
- 6,087
7
votes
1
answer
337
views
For which real $\beta$ there exist concave(convex upwards) functions $f, g: (0;1) \to (0;+\infty)$ such that $\frac{f(x)}{g(x)}=(1+x)^\beta$?
For which real $\beta$ there exist strictly concave(convex upwards) functions $f, g: (0;1) \to (0;+\infty)$ such that $\frac{f(x)}{g(x)}=(1+x)^\beta$?
My attempt: if we don't require $f>0$ and $g&...
- 593
0
votes
1
answer
24
views
Does block coordinate descent lead to a constrained critical point?
Let $f:\mathbb{R}^N\to[0, \infty)$ be a non-convex function of $w\in\mathbb{R}^N$ for $N\in\mathbb{N}$. Suppose the entries in $w$ can be partitioned into two vectors $u\in\mathbb{R}^m$ and $v\in\...
1
vote
1
answer
48
views
It seems that the definition of dual problem in Boyd & Vandenberghe does not apply to SVM
In Section 5.2 of Boyd & Vandenberghe's Convex Optimization, the dual problem given a primal problem with only inequality constraint is,
$$ \max \quad g(\alpha) \\ \text{ s. t.} \quad \alpha \...
- 8,711
0
votes
1
answer
55
views
Strict monotonicity of the intrinsic volume $V_{n-1}$
Let $\mathcal{K}^n_n$ denote the set of all compact, convex subsets of $\mathbb{R}^n$ with nonempty interior. I am hoping to show that the intrinsic volume $V_{n-1}$ is strictly monotone, in the sense ...
- 580
0
votes
0
answers
38
views
Domain of the conjugate of a convex and Lipschitz continuous function
High level question: When can we say that $\mathrm{dom}(f^\star) = [L_1, L_2]$ for some $L_1, L_2 \in \mathbb{R}$? That is, when is the domain of conjugate a closed interval.
Detailed question: Let $f:...
2
votes
0
answers
35
views
Understanding changes in a polyhedron structure when there are perturbations on the restrictions vector
I have the polyhedron
$$ P := \left\{ {\bf x} \in \mathbb{R}^{\binom{n}{k}} : {\bf A} {\bf x} = {\bf b} , \hspace{0.3em} {\bf 0} \leq {\bf x} \leq {\bf 1} \right\} $$
where the matrix ${\bf A} \in \...
- 33
1
vote
0
answers
47
views
Convergence of the higher order derivatives of convex functions
Assume that we have non-positive convex functions $f_n:\,[0,1]\to(-\infty,0]$ with $f_n(0)=f_n(1)=0$, $n\in\mathbb{N}$, converging pointwise to a (necessarily convex) function $f$ on $[0,1]$. Moreover,...
- 193
1
vote
1
answer
66
views
Dimension of totally ordered topological vector (or totally ordered normed) spaces?
In the literature, I have only encountered partially ordered topological vector spaces (or partially ordered normed spaces). Therefore, I suspect that requiring a total order is already too ...
- 11
1
vote
0
answers
41
views
Existence of an increasing convex sequence in between of intervals
I am working on a proof for the following fact. I am not sure which exactly field has relevant results, maybe it is something obvious.
Let $x_1<\dots<x_n$ be some points on the real line and ...
- 36.7k
0
votes
0
answers
30
views
Upper bound of the sum of errors for minimizing an L-smooth convex function using gradient descent method
$f(x)$ is an L-smooth convex function, $x_*$ is the minimizer of $f(x)$.
We define $x_{k+1}=x_k-\frac{1}{L}\nabla f(x_k)$.
We can show that $$f(x_0)-f(x_*)\le\frac{L}{2}|x_0-x_*|^2$$ and $$\sum_{k=1}^{...
- 3
1
vote
1
answer
84
views
Show that if $n>1$ and $x,y\in\mathbb{R}^n$ with $B_3(x)\cup B_6(y)$ convex, then $B_3(x)\subseteq B_6(y)$
Problem: Let $n>1$ and let $x,y\in\mathbb{R}^n$ with $B_3(x)\cup B_6(y)$ convex where $B_r(z)$ is the open ball of radius $r$ around the point $z$. Show that $B_3(x)\subseteq B_6(y)$.
First the ...
- 2,262