New answers tagged

1 vote
Accepted

if $A$ is positive semi-definite, is $A-cI$ positive semi-definite for some small $c$?

A matrix $A$ $\big($over $\mathbb C$ or over $\mathbb R\big)$ is positive-definite if it is Hermitian or symmetric, and its smallest eigenvalue satisfies $\lambda >0\,$. Then you find some $\,\...
  • 5,023
0 votes

Sum of convex functions is convex?

The answer is yes it is convex. I will give you a proof for the case of two functions. I think you can do it for $n$ function using induction. Let $f(x,y,z)=g(x,y)+h(y,z)$. we have that( $0\leq\,a\,\...
6 votes

Is the minization of a strictly convex function still strictly convex?

As demonstrated in the other answers, $g$ need not be strictly convex. However, under the additional assumption that the infimum is attained, i.e. $g(x) = \min_y f(x, y)$ for all $x$, one can show ...
  • 90k
1 vote

Is the minization of a strictly convex function still strictly convex?

Let $$ f(x,y)=e^{x^2-y}\,. $$ The gradient and Hessian of this function are $$ \nabla f=\begin{pmatrix}2x\\-1 \end{pmatrix}e^{x^2-y}\,,\quad\nabla^2f=\begin{pmatrix}2+4x^2&-2x\\-2x&1\end{...
  • 5,051
5 votes

Is the minization of a strictly convex function still strictly convex?

The function $f \colon \mathbb R^2 \to \mathbb R$ given by $$ f(x,y) = \exp(y) + \exp(x+y) $$ is a counterexample, since $g(x) = 0$.
  • 28.3k
0 votes
Accepted

Asymptotic Cone of Product Sets

Lemma: $x \in A(S)$ if and only if there exists a sequence $s_k \in S$ and $\lambda_k \in [0, \infty)$, converging to $0$, such that $x = \lim_{k \to \infty} \lambda_k s_k$. Proof. Suppose $x \in A(S)$...
  • 45.1k
1 vote
Accepted

For concave functions $f(y)≤f(x)+f′(x)(y−x),∀x,y$ but..

Yes the second inequality is only applicable with $y> x$. For $y< x$, the inequality is reversed, $f'(x)\leq (f(y) - f(x))/(y-x)$ as when you divide the $(y-x)$ from both sides to get the ...
  • 175
1 vote
Accepted

For concave functions $f(y) \le f(x) + f'(x)(y − x), ∀x, y$ but....

You are right that this is only applicable in the case you mention. If $y-x$ is negative (which it is if $y<x$), you have to flip the $\leq$-sign when dividing by $y-x$. So in this case you get $f'(...
0 votes

How can we prove equation of sub-gradient and conjugate?

$$ f(x)+f^{*}(-M^Tp)=\langle x,-M^Tp\rangle $$ $$ f^{**}(x)=\langle x,-M^Tp\rangle - f^{*}(-M^Tp) $$ $$ \langle x,-M^Tp\rangle - f^*(-M^Tp)\geq \langle x,-M^Tq \rangle - f^{*}(-M^Tq) , \ \ \forall q $$...
1 vote

Strictly convex function, implies that translation is strictly convex.

If we have a strict convex function $f$, you can prove strict convexity of translation by doing something like \begin{align*} &f(tx + (1-t)y - a) \\ &= f(tx + (1-t)y - ta - (1-t)a) \\ &= f(...
  • 192
0 votes

If $f$ is log-convex then $f$ is convex

The generalized Arithmetic-Geometric inequality says that $ax+by \geq x^a y^b$, so you can get $ f(x)^{\lambda}f(y)^{(1-\lambda)} \leq \lambda f(x)+(1-\lambda)f(y) $.
0 votes

Convexity of a function with log and det

I think the function is convex over $\mathcal{S}_{++}^n\times\mathcal{R}_{++}$. The proof has three steps: Show the function $g(X)=-\log{\det{X}}$ is a convex function in $X\in \mathcal{S}_{++}^n$. (...
1 vote
Accepted

Is a perspective of a quasiconvex function still a quasiconvex function?

Not true. Let $f(x) = \sqrt{|x|}$. Its perspective is $$ g(x,t) = \sqrt{|x|}\sqrt t, $$ which is not quasiconvex as $$1=g(1,1) > \max (g(2,0),g(0,2)) = 0.$$
  • 43.3k
1 vote

Counterexample for intersection of polar sets is not the closed convex hill of union of polar sets?

I don't know anything about this construction a priori, but if I understand it correctly then you can take singleton sets $A=\{(0,1)\}$ and $B=\{(0,2)\}$ in $\mathbb{R^2}$. The polar set of $A \cap B=\...
  • 1,998
1 vote
Accepted

Is this Kullback-Leibler divergence between positive semidefinite matrices always well-defined?

It appears to be a mistake in the paper. They probably meant to set $$\text{tr}(P \log(Q)) = -\infty \tag{1}$$ when $\ker(Q) \not \subset \ker{P}$. While they talk about extending the function $(P,Q) \...
  • 2,875
0 votes

Question about growth of a convex function

If a function is convex then $$f(ta+(1-t)b)\leq tf(a)+(1-t)f(b)$$ for all $b>a$, $t\in[0,1]$, so setting $a=0$, $b=2x$, and $t=\frac12$ we have $f(x)\leq\frac12(f(0)+f(2x))=\frac12f(2x)$ since $f(0)...
  • 10.3k
0 votes

convolution with heat kernel uniformly increases convexity?

It seems that the answer is yes and it can be deduced from the identities: $$\frac12(f(x+\epsilon)+f(x-\epsilon)) -f(x) = \int_\Bbb R f’’(x-u)\max\{0,\epsilon-|u|\}du$$ $$p_t*f(x)-f(x) =\int_\Bbb R f’’...
  • 12.7k
0 votes

Can someone give an example which satisfies the following conditions.

Examples are \begin{equation} f(x) = x - \log(x+1) \end{equation} or \begin{equation} g(x) = x + e^{-x} - 1 \end{equation}
  • 12.5k
0 votes

Is the non-negative orthant a closed convex set?

The non-negative orthant can be defined by a conjunction of (strict) linear inequalities of the form $ {\bf A} {\bf x} \leq {\bf b}$, where ${\bf A} = - {\bf I}$ and ${\bf b} = {\bf 0}$, and, thus, is ...
0 votes

Is the non-negative orthant a closed convex set?

The non-negative orthant can be defined by the following linear matrix inequality (LMI) $$ \begin{bmatrix} x_1 & 0 & 0 & \dots & 0\\ 0 & x_2 & 0 & \dots & 0\\ 0 & 0 ...
0 votes

Question about integral representation of Convex function

If $\phi$ is continuous then $\Phi$ is a $C^{1}$ function. But this is not always true for a convex function. For example, $\Phi (x)=|x|$ is a convex function which is not continuously differentiable.
  • 8,896
1 vote
Accepted

Strict convexity of log-sum-exp function

For this answer, I'll be thinking of $f \colon \mathbf{R}^{n+1} \rightarrow \mathbf{R}$ and $g \colon \mathbf{R}^{n} \rightarrow \mathbf{R}$ so that we can consider $g$ to be $f$, just with the first ...
0 votes

Is the non-negative orthant a closed convex set?

HINT: You know $\Bbb R^n_+$ is convex, so for $\forall x,y \in \Bbb R^n_+$ we have $\lambda x + (1-\lambda)y \in \Bbb R^n_+,\forall \lambda \in [0,1]$. Therefore, any $x,y \in \Bbb R^n_+$ is also a ...
  • 4,287
1 vote

Question about fixed point of a convex function

Of course $0$ is one fixed point. The second one exists by the Intermediate Value Theorem because (4) implies $\Phi(x) < x$ for $x$ near $0$ and (5) implies $\Phi(x) > x$ for large $x$. There ...
0 votes

How to calculate the supremum of the following function

Ok, since $x \geq 0$ we have $|x| = x$ and hence $$ \sup\limits_{x\geq 0}\{x|y|-|x|^p\} = \sup\limits_{x\geq 0}\{x|y|-x^p\}. $$ If $p>1$, the expression under the supremum decreases unboundedly if $...
  • 34.4k
1 vote
Accepted

Number of solutions of $f(x)=ax+b$ for a strictly convex real function $f$.

A number of reasons could explain why no reference is available: The problem (hypotheses and results) is quite intricate. It can be simplified by posing $g(x)=f(x)-ax$. There are more general results ...
1 vote

Properties of space of bounded probability density functions

For simplicity, let us consider $G = [0,1] \subset \mathbb R$ and $(a+b)/2 = 1$. Let us consider the sequence $(h_k)$ defined via $$ h_k(x) = \begin{cases} a & \text{if } x \in [2n/2^k, (2n+1)/2^k]...
  • 28.3k
3 votes
Accepted

Linear Image of Extreme Points

This is true and $L$ is not required to be surjective. A convex compact subset of $\mathbb{R}^n$ is the convex hull of its extreme points. Now suppose $y$ is an extreme point of $L(C)$. Take any $x\in ...
1 vote

Why do linear constraints always form a convex set?

If $Ax_1 = b, Ax_2 =b$ i.e $x_1,x_2$ belongs to the set then for $0<=k<=1$ $kAx_1 + (1-k)Ax_2 = kb + (1-k)b$ or $A(kx_1 + (1-k)x_2) = b$ i.e $kx_1 + (1-k)x_2 $ also belongs to the set. Therefore ...
2 votes
Accepted

$A$ closed, strictly convex set, $\mu$ non-degenerate probability measure on $\partial A$ $\Rightarrow$ $\int_{\partial A}x\mu(dx) \in A^°$

Yes, it is true. Let $f$ be a nonzero linear functional on $\mathbb R^n$ such that $f(x) \le b$ for all $x \in A$. Then $$ f\left(\int_{\partial A} x\; \mu(dx)\right) = \int_{\partial A} f(x)\; \mu(...
0 votes

Existence of minimizer for strongly convex function on closed, convex set

As pointed out by David Pal, imposing only strong convexity (without lower-semi continuous) is not sufficient to ensure the existence of the minimizer. I therefore provide here a very general Lemma (...
  • 1,190
2 votes
Accepted

Union of a convex domain with closure of a component is open?

No. As a counterexample, consider in $\mathbb{R}^2$ $$ \Omega = \left\{(x,y) \in \mathbb{R}^2 : |x| < |y| \right\} $$ The complement of the closure is $$ (\overline{\Omega})^c = \left\{ (x,y) \in \...
  • 5,994
3 votes

Closed and Bounded set over $2\times 2$ Matrix

The condition for your eigenvalues to be positive is not $x_1-x_1^2-x_2x_3\geq0.25$ and anyway, the positivity of the eigenvalues is not a sufficient condition for the matrix to be PSD. The ...
  • 2,885
1 vote

Strict/Strong convexity of non-Euclidean norm

I hope this answer can be useful, I also gave it as an answer to that question: Strong convexity of squared $\ell_p$ norm in Bregman divergence I think from that paper (not the original reference but ...
0 votes

Strong convexity of squared $\ell_p$ norm in Bregman divergence

In case this can be useful to future readers: I didn't read the other replies, but I think from that paper (not the original reference but they cite the original one) that the answer is positive for $...
1 vote

Proof by contradiction: the intersection of any collection of non-empty convex sets is convex

A proof by contradiction should go as follows. Assume that the intersection is not convex then there exist $x,y \in\,\bigcap\,K_{i}$ such that for some $\lambda$ in $[0,1]\,\,\, \lambda\,x+(1-\lambda)...
3 votes
Accepted

Proof by contradiction: the intersection of any collection of non-empty convex sets is convex

The proof is basically correct, except it is not really a proof by contradiction. It would be more clear if you restated it as a direct proof (that it essentially is). Further, there is an issue in ...
  • 33.4k
1 vote
Accepted

How can I prove the following characterization : $\langle u-\pi_ku,w-\pi_ku\rangle\leq 0$?

See the proof of $(1)\Leftrightarrow(2)$ in the first section of https://fr.wikipedia.org/wiki/Th%C3%A9or%C3%A8me_de_projection_sur_un_convexe_ferm%C3%A9
  • 2,885
0 votes

Multivariable function showing there is at most 1 local optima that is not in the edges - checking each variable on its own

You need two conditions, $$ \dfrac{d^2 f}{d x^2} \; \dfrac{d^2 f}{d y^2} > \left(\frac{d^2 f}{d x d y}\right)^2 $$ and $$ \dfrac{d^2 f}{d x^2} + \dfrac{d^2 f}{d y^2} > 0 $$ (see proof below). ...
  • 1
3 votes
Accepted

Existence of a unique minimizer of a given functional

We have $$J(u) = \frac{1}{2}a(u,u) - L(u)$$ Where $$a(u,v) = 2 \int_\Omega \nabla u(x) \nabla v(x) dx$$ and $$ L(u) = \int_\Omega f(x)dx $$ We can verify these functions fullfill all the Lax-Milgram ...
  • 1,156
0 votes

How to show the maximizer of a convex function lies on the boundary?

Since $f$ is a convex function, $\exists m\in C$ such that $f(m)$ is minimum. Suppose $f$ attains maximum at $M\in C$ such that $M\notin \delta C$. Then $\exists c\in C$ such that the line joining $m$ ...
  • 189
1 vote
Accepted

Lower-bound for $\inf_{x \in \mathbb R^n} \|x-a\|_2 + r\|x\|_1$ as a function of fixed $a \in \mathbb R^n$ and $r \ge 0$.

Notice that evaluating the function in the infinmum with $x=a$ and $x=0$ leads easily to get that \begin{equation}\label{eq}\tag{1} c \leq \min(\|a\|_2,r\,\|a\|_1). \end{equation} But in the ...
  • 7,474
1 vote
Accepted

If two weighted averages (convex combinations) of the same distinct non-zero values are equal, does that make their weights equal?

No, you can not draw this conclusion. For example, let $f_1 = 0$, $f_2 = 1$, $f_3 = 2$. Then $0.5*f_1 + 0*f_2 + 0.5 * f_3 = 1$ Also $0*f_1 +1*f_2 + 0*f_3 = 1$
  • 2,924
0 votes

Black box optimization

A function $f$ is convex if $\forall x_1, x_2$ you have that the following inequality holds for all $\lambda \in [0,1]$: $$ f(\lambda x_1 + (1 - \lambda) x_2) \le \lambda f( x_1 ) + (1 - \lambda ) f( ...
  • 115
1 vote

Is the inverse of a nonnegative convex function being convex/quasi-convex/concave/quasi-concave?

Following Kurt G.'s answer. Here is the proof of the second conjecture. Conjecture $g(x)=\frac{1}{f(x)}$ is quasi-convex if $f:\mathcal{D}\rightarrow\mathbb{R}_+$ is monotonically non-decreasing. ...
0 votes
Accepted

Convexity of composite functions including monotonicity (inner functions are monotonic functions)

I think the statement is not true. Take $g(x)=x^{3}$ convex and increasing for $x>0$ and $f(y)=y^{2}-y+1$ which is convex. Then $f(g(x))=x^{6}-x^{3}+1$ and $f'(x)=6x^{5}-3x^{2}$ and $f''(x)=30x^{4}-...

Top 50 recent answers are included