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.

Filter by
Sorted by
Tagged with
1
vote
1answer
21 views

The generalized Pythagorean property of Bregman divergence

So suppose a function $f$ is strictly convex and continuously differentiable. The Bregman divergence associated with $f$ is \begin{equation} D_f(x,y) = f(x) - f(y) - \nabla f(y)^{T}(x-y), \forall x,y\...
2
votes
1answer
79 views

Minimization of $\log \det$ plus $\| \cdot \|_1$

Given fat matrices ${\bf A} \in \mathbb{R}^{m\times n}$ (where $m < n$) and ${\bf B}\in \mathbb{R}^{p\times n}$ (where $p < n$ and $\mbox{rank}({\bf B}) = p$), and $m \times m$ symmetric ...
0
votes
0answers
14 views

A condition for global convexity

Let us consider four real numbers $-\infty<a < b < c < d<\infty$. Let us suppose that a function $f:(a,d) \to \mathbb R$ is convex on $(a,c)$ and $(b,d)$. Is it true that $f$ is convex ...
1
vote
1answer
40 views

A problem about convex sets

Let $A,C_1,\dots,C_m$ be convex sets in $\mathbb{R}^n$ (Let's say $m \gg n$). Suppose that for any triple $(C_i,C_j,C_k)$ we always have a translation of $A$ such that $A\cap C_i\ne \emptyset, A\cap ...
0
votes
1answer
33 views

Sum of restricted strictly convex functions

Suppose that $\boldsymbol{x}\in\mathbb{R}^p$. Also, assume $\Omega\subseteq \{1,2,\ldots,p\}$ is a subset of the indices, and $\Omega^c$ denotes the complement of $\Omega$. The notation $\boldsymbol{x}...
0
votes
1answer
62 views

Can we tell if ANY Function is Convex or Non-Convex?

Reading the mathematical definition of convexity (https://en.wikipedia.org/wiki/Convex_function), it seems that there is a relatively clear definition as to what makes a function "convex": ...
1
vote
2answers
90 views

Real functions with the property: $\ f(x_1)f(x_2) = f\left( \frac{x_1+x_2}{2} \right)^2 $ for all $\ x_1,\ x_2\in\mathbb{R}.\ $

Suppose $\ f:\mathbb{R}\to\mathbb{R}\ $ has the property:$\ f(x_1)f(x_2) = f\left( \frac{x_1+x_2}{2} \right)^2\ $ for all $\ x_1,\ x_2\in\mathbb{R}$. I made some educated guesses and stumbled upon the ...
5
votes
1answer
100 views

Do we have any way of knowing if natural phenomena in the real world follow the "Lipschitz Condition"?

Recently, I keep coming across terms containing "Lipschitz" pertaining to statistical models and machine learning. This includes terms such as "p-lipschitz (rho), lipschitz convexity, ...
0
votes
1answer
40 views

Strictly convex function and second derivative [closed]

Let $f(x)=x^2+e^x$ since $f''(x)=2+e^x>0$ always, can I say that the function is strictly convex?
0
votes
0answers
17 views

Conjugate function of maximum eigenvalue of symmetric matrix

Let $X \in S^n$ be an $n \times n$ symmetric real matrix,and $\lambda_{\max}(X)$ be the largst eigenvalue of X. Then, $\lambda_{\max}:S^n:\to \mathbb{R}$ is a convex function with its conjugate $\...
3
votes
1answer
40 views

Proof that $\left(\frac{1}{x}, \frac{1}{y}\right)$ is a convex region if $(x, y)$ is

I'm trying to convince (prove) myself that if a set $S \subset \mathbb{({R^+})^2}$ is a convex region, then $S' := \left\{ \left(\frac1{x}, \frac1{y}\right) ; (x, y)\in S \right\}$ is also a convex ...
4
votes
0answers
56 views

Is $f^{-1}\big( \sqrt{xf(x)} \big)$ convex when $f(x) \leq x$ is concave and strictly increasing?

Question Suppose $f : \mathbb R_+ \to \mathbb R_+$ is a strictly increasing, concave function such that $f(x) = o(x)$ for $x \to \infty$. Define $g(x):= f^{-1}([xf(x)]^{1/2})$, $x \in \mathbb R$. Does ...
1
vote
0answers
14 views

Convexity of KL divergence for channel setting

I have seen an excellent proof of what I am trying to learn in Cover and Thomas or here but I am trying to clear my understanding if I try to prove it another way. Given a probability distribution $...
0
votes
0answers
24 views

Proving convexity/concavity of a function

The given function is $$f(P) = y^T(APA^T)^{-1}y$$ It is given that $P$ is a diagonal matrix made of elements of the vector $p$, and the elements of $P$ are strictly positive. My attempt : Since $P$ is ...
1
vote
0answers
44 views

Composition of two convex functions, where one of them is increasing

First a definition of convexity is defined as follows: Given a function $f:A\to \mathbb{R}$, where $A$ is an interval in $\mathbb{R}$, and given distinct $x_1,x_2\in A$, define $$ \varphi(x_1,x_2)=\...
1
vote
0answers
37 views

Pointwise supremum [closed]

Suppose the set $\mathcal{A}{\color{red}{(x)}}$ is a convex set (of the variable $y$) for every $x$. Also, suppose that $f(x, y)$ is convex in $x$ for every $y \in \mathcal{A}{\color{red}{(x)}}$. Then ...
1
vote
0answers
31 views

Convexity and sum of variables

I have a sequence of vector $x^k = \frac{1}{N} \sum_{i=1}^N x_i^k$, and a set of functions $\{f_i\}_{i=1}^N$ convex functions. From the convexity of $f_i$, I know that $\langle \nabla f_i(x_i^{k+1}) - ...
0
votes
1answer
38 views

Prove convex hull is a compact set

Let $\mathbf{v}_1,\dots,\mathbf{v}_r$ be vectors in a Euclidean space $\mathbf{V}$. Prove that the convex hull $\mathrm{Conv}(\mathbf{v}_1,\dots,\mathbf{v}_r)$ is a compact set. I believe the convex ...
2
votes
0answers
19 views

Sufficient condition for convex conjugates (does one imply the other?)

We say $(f_1,f_2,\cdots,f_N)$ a convex conjugate if for any $i=1,2,\cdots,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(...
1
vote
1answer
57 views

Show that if $f$ is convex, differentiable and $f(0)=0$ then $f(x) \le xf'(x)$

Show that if $f:\mathbb{R} \to \mathbb{R}$ is convex, differentiable and such that $f(0)=0$, then $$f(x) \le xf'(x), \ \forall x\in\mathbb{R}$$ My try: if $x=0$, then since by hypothesis $f(0)=0$ and $...
2
votes
1answer
44 views

If $f$ is midpoint-convex and $f$ is a Baire function (Borel measurable) then $f$ is convex

Suppose $f$ is a function defined on some interval $\mathrm{J}$ such that $$ f \left( \dfrac{t_1 + t_2}{2} \right) \leq \dfrac{f(t_1) + f(t_2)}{2}, $$ for all pairs $t_1, t_2$ in $\mathrm{J};$ this is ...
1
vote
1answer
31 views

Strict concavity and convexity when there is an inflection

$f(x)=xe^x$ is such that $f'(x)=e^x+xe^x$ and so $f''(x)=(2+x)e^x$. I know that $f''(x)>0\iff x>-2$ and $f''(x)<0\iff x<-2$, while $x=-2$ is an inflection point. Can I say that in $(-\...
1
vote
1answer
26 views

How to prove that Squared Error Loss is convex

I have the squared loss given by: $L(z;\textbf{y}) = \frac{1}{2}\left\| z-\textbf{y} \right\|^{2}_{2} = \frac{1}{2}(z-\textbf{y})^{T}(z-\textbf{y})$ where $z=\textbf{W}^{T}\phi(x)+\textbf{b}$. I need ...
0
votes
0answers
22 views

The monotonicity or convexity of an ODE regard to its coefficient

I am trying get some ideas on how to prove that the solution of the following ODE is monotone or convex in the constant $k$: $$f(x)-x(f'(x))^2+k(x-x^2)f'(x)+(x-x^2)f''(x)=0$$ where $k\in(0,1)$ and the ...
2
votes
2answers
81 views

$\{(x,y)\in \mathbb{R}^2: |x|+|y|^{1/2}<1\}$ is convex

How to prove that $A=\{(x,y)\in \mathbb{R}^2: |x|+|y|^{1/2}<1\}$ is convex? I tried using the definition but couldn’t go far, since the second component involves square root(tried squaring, that ...
0
votes
0answers
29 views

General optimization problem

I've tried many efforts on this optimization problem but don't find any idea how to continue: Let $n \geq 2$ be an integer, and $J: \mathbf{R}^{n} \longrightarrow \mathbf{R}$ a continuous, coercive ...
0
votes
0answers
23 views

Convexity w.r.t. two functions?

I recently read about convexity with respect two functions $u, v$. I tried to look up for some definition, but I failed. That is why I am asking it here. What does it mean a function $f$ is convex ...
1
vote
0answers
26 views

Calculus on the half positive space

Let $n \geq 2$ be an integer, and $J: \mathbf{R}^{n} \longrightarrow \mathbf{R}$ a continuous, coercive and strictly convex fonction. For any real $\delta \geq 0$, we denote by $U_{\delta}=\mathbf{R}^{...
1
vote
1answer
26 views

If $f$ is convex and $t$ is greater or equal to 1, is f(tx) greater or equal to $tf(x)$?

I'm interested in the following question: If $f$ is a convex function and $t\geq 1$, can we show that $f(tx) \geq tf(x)$? Apparently this is supposed to be a direct consequence of (one of) the ...
1
vote
1answer
38 views

Inflection points and the second derivative

I have a doubt about the classification of a point as an inflection point. I know that if a function $f$ is twice differentiable at $x_0$ and if $x_0$ is an inflection point then $f''(x_0)=0$. My ...
6
votes
0answers
104 views

Distance between point and convex hull in high dimensions

I am trying to develop an intuition for the properties of the convex hull of a set of points in high ($d>20$) dimensions. Consider a set of $n$ data points which are iid distributed according to ...
1
vote
0answers
26 views

Name for class of (almost) convex functions

Is there a name for the class of functions $\newcommand{\R}{\mathbb{R}}$ $f:\R^n \to \R$ such that for each $f$, there exists an $\alpha > 0$ such that $$f(x) + \frac{\alpha}{2} \Vert x \Vert^2$$ ...
0
votes
0answers
35 views

Convexity on an open set implies whole set

If $A\subseteq \mathbb{R}$ is an interval, and $f:A\to \mathbb{R}$ is convex on the interior $A^\circ$ of $A$. Can $f$ then be convex on whole $A$? If not, which condition does $f$ need to make this ...
1
vote
1answer
50 views

Checking Convexity of a function?

I want to check if the following function is convex with respect to the vector variable $x$. $$ R(x) = \log_2 \left( \sum_{i=1}^M {\frac{p}{((x_i-\gamma)^2 + (y_i-\beta)^2 +(z_i-\rho)^2)^\alpha}+\...
2
votes
1answer
29 views

Fenchel conjugate of least squares in a Banach case

I can't wrap my head around this question: let $\mathcal{X}$ be a Banach space, let $\mathcal{X}^*$ be its dual and $\mathcal{H}$ be a Hilbert space (such as $L^2$). Define the linear mapping $\Phi : \...
1
vote
0answers
12 views

Analytic formula for Huber-like function $f(x) := \sup_{|y| \le r}xy - \frac{1}{p}|y|^p$, where $p \ge 1$ and $r>0$ are fixedreal

Let $x \in \mathbb R$, $r>0$, and $p \ge 1$. Question. What is the analytic formula for $f_p(x;r) := \sup_{|y| \le r}xy - \frac{1}{p}|y|^p$ ? N.B. I'm particularly interested in the case $p \in [...
1
vote
1answer
33 views

Does convex functios $f$ always achieves a minimum on closed convex sets whenever the $f$ have an unconstrained minimum?

I have a convex function $f: \mathbb{R}^{n}\rightarrow \mathbb{R}$ that achieves minimum at some point of $\mathbb{R}^{n}$. I want to know if the problem \begin{equation*} \begin{array}{c c} \text{...
0
votes
1answer
32 views

Convex hull of less than 3 points

Convex hull $H$, of set of points $P=\{p_i: p_i \in R^2\}$, always exists if $|P|\ge3$. I wanted to know if the convex hull of an empty set, one-point set, or a two-point set is the set itself? i.e., $...
0
votes
0answers
14 views

How do you solve a convex minimization problem with affine linear constraints?

I am studying KKT conditions and I got a bit confused about how to solve the following problem: \begin{align*}&\min f(x) \\ s.t. &l \leq x_i \leq u \qquad \forall i=1, \dots n\\ &c^Tx \leq ...
2
votes
1answer
20 views

Second Derivative of Lipchitz Concave Curve is infinite at only finite points

Suppose $Q(x):[0,1]\to[0,1]$ is a segment of a convex set which is concave downwards and locally Lipchitz and differentiable a.e. such that $Q(0)=Q(1)=0$ Is $Q''(x)$ going to be tending to $-\infty$ ...
1
vote
0answers
55 views

Prove or disprove a version of the open mapping theorem for sublinear maps.

Let $ T: R^n \to R^m $ be a surjective sublinear map. Prove or disprove that : there exists a $ \kappa >0 $ such that for all $v \in R^m $ we have $$ \inf_{\|w\|=1}\langle T(w)~,~ v \rangle \leq ...
0
votes
0answers
20 views

Successive Convex Approximation and first order Taylor approximation [closed]

I am solving an optimization problem that maximizes a convex function with respect to a variable, and it is solved via successive convex approximation after using the first order Taylor's ...
1
vote
0answers
17 views

Visualise Gradient Condition for Convex Function.

Let $f:\mathbb{R}^n\to\mathbb{R}$ be a convex differentiable function. What is the best visual justification for the condition $$f(x)\geq f(y)+\nabla f(y)\cdot(x-y),~~\forall x,y\in\mathbb{R}^n.$$ Any ...
3
votes
2answers
63 views

Inequality involving $p$-norm of particular vectors for $1<p<2$.

While investigating counterexamples for certain conjectures in matrix analysis, I stumbled across the following calculus problem. I need to show (rigorously) that for $1<p<2$, $$\left\lVert\...
0
votes
0answers
16 views

Characterization of subsets $C$ of $R^n$ for which $\inf_{x \in C}\sup\{r \ge 0\mid B = B_n(y,r) \subseteq C,\,y \in R^n,\,d(x,B) = d(x,C)\} \ge r_0$

Let $C$ be a closed subset of $\mathbb R^n$. For any $x \in \mathbb R^n$, define $$ k(x) := \sup\{r \ge 0\mid B = B_n(y,r) \subseteq C,\,y \in \mathbb R^n,\,\mbox{dist}(x,B) = \mbox{dist}(x,C)\}, $$ ...
0
votes
0answers
20 views

Distance to Convex Set and Local Minima

Let $C \in \mathbb{R}^n$ be a convex set, and consider a fixed point $y \in \mathbb{R}^n$. Suppose we define the distance function to any point $x \in C$, $f(x) = ||x - y ||$. I am wondering if $f(x)$ ...
0
votes
0answers
23 views

Problem on duality simplex algorithm

Consider the linear programming $\{cx|Ax=b,x\geq 0\}$, We say a basis of $A$ is dual feasible basis if $c-c_BB^{-1}A \geq 0$. Then, I want to show that the dual feasible basis exists if and only if ...
2
votes
1answer
93 views

Finding a strictly positive “good” permutation in a doubly stochastic matrix

Let $n$ be a positive integer and $\mathbf X\equiv[x_{ij}]_{i=1,j=1}^{i=n,j=n}$ a doubly stochastic matrix; that is, a matrix with non-negative elements such that the sum of every row and the sum of ...
1
vote
1answer
51 views

Is $q(x) = \frac{1}{2} x^T H x - g^T x$ strongly convex?

Let $$q(x) := \frac{1}{2} x^T H x - g^T x$$ where matrix $H$ is symmetric positive definite and $g \in \mathbb{R}^n$. Clearly, the function is strictly convex, but why is it strongly convex?

1
2 3 4 5
167