How can i prove $f(x_1,\ldots,x_n) = \sum x_i\ln x_i - (\sum x_i )\ln(\sum x_i)$ is convex on R++
119828
$$f(x_1,\dots,x_n)=\sum\limits_{i=1}^nx_i\ln x_i-\left(\sum\limits_{i=1}^nx_i\right)\ln\left(\sum\limits_{i=1}^nx_i\right)\rightarrow R_{++}^n$$  How can I prove this is convex on $R_{++}^n$? I tried using the Hessian and couldn't prove it. There is a solution using the gradient and Jensen but very long and complicated.
59814
$\newcommand{\prox}{\operatorname{prox}}$ $\newcommand{\argmin}{\operatorname{argmin}}$ $\newcommand{\dom}{\operatorname{dom}}$  Recall again that the proximal operator for vectors $\prox_{f}: R^n \rightarrow R^n$ of $f$ is defined as:  $\prox_f(v) := \argmin_{x} \left(f(x) +(1/2)\|x-v\|_2^2 \right) $,  where $f: R^n \rightarrow R \cup \infty$ is a closed proper convex function and $\|\cdot \|_2$ is the Euclidean norm. $\prox$ is strongly convex and not everywhere infinite, so there it will have a unique minimizer for every $v \in R^n$  The crucial property of proximal operator is that $x^*$ minimizes $f(x)$ iff $x^* = \prox_f(x^*)$, i.e. $x^*$ is a fixed point of $\prox_f$.  Let us consider the proof of this property. The first part, namely, that if $x^*$ minimizes $f$ then $\prox_f(x^*)=x^*$, is trivial:  $f(x) +(1/2)\|x-x^*\|_2^2 \le f(x^*) = f(x^*) +(1/2)\|x^*-x^*\|_2^2$  The second part uses the notion of subdifferential. In the proof authors say that $\tilde{x}$ minimizes  $f(x) +(1/2)\|x-v\|_2^2$  i.e. $\tilde{x} = \prox_f(v)$ iff $0 \in \partial f(\tilde{x}) + (\tilde{x}-v)$,   where the sum is of a set and a point. Recall the definition of the subdifferential:  $\partial f(x) = \{ y$ |  $ f(z)\le f(x) + y^T(z-x)$ $\forall z \in \dom{f}\}$  Take $\tilde{x}=v=x^*$, it follows that $0 \in \partial f(x^*)$ so $x^*$ minimizes $f$.  Question 1:  Consider proximal operator defined for matrices now:  $\prox_f(Y) := \argmin_{X} \left(f(X) +(1/2)\|X-Y\|^2 \right)$,  where $X$ is some real $m$ by $n$ matrix. What norm function should be taken in the definition of the $\prox$ in this case? Frobenius? Or spectral norm (induced 2nd norm) which is the largest eigenvalue (is spectral norm even differentiable?)? Or something else?  Question 2:   Can the norm for the definition of $\prox$ in case of matrices be chosen in different ways? What conditions does the proof above impose on the norm function?
98609
How would I prove that if $f: \mathbb R^2 \to \mathbb R$ is a function such that  $$\lim_{(x,y)\to(a,b)} f(x,y) = L$$  and for every $y_0 \in \mathbb R$   $$ \lim_{x\to a} f(x,y_0) = L'_{y_0}$$  and for every $x_0 \in \mathbb R$   $$ \lim_{y\to b} f(x_0,y) = L''_{x_0}$$  then  $$ \lim_{x\to a}\left(\lim_{y\to b} f(x,y)\right)  = \lim_{y\to b}\left(\lim_{x\to a} f(x,y)\right) = L$$
16824
How can I prove that $xy\leq x^2+y^2$ for all $x,y\in\mathbb{R}$ ?
116950
Is convex hull of closed set in $\mathbb R^{n}$ closed?
28097
I cannot prove that if $f(x)$ is convex on $[a,b]$ then  $f\Big(\frac{a+b}2\Big) \le \frac1{b-a}\int_a^b f(x)\,dx \le \frac{f(a)+f(b)}2 .$
120022
I know that $p$-norm of $x\in\Bbb{R}^n$ is defined as, for all $p\ge1$,$$\Vert{x}\Vert_p=\left(\sum_{i=1}^{n} \vert{x_i}\vert^p\right)^{1/p}.$$  The textbook refers to "Every norm is convex" for an example of convex functions.  I failed to prove $f(x)=\Vert{x}\Vert_p$ for all $p\ge1$, then tried to find the proof on the internet but I cannot find it.  Can someone let me understand why $p$-norm is convex for all $p\ge1$.
53979
Is the function $\mbox{tr}(XAX')$ convex, where $A$ is a positive semidefinite (PSD) matrix? I know that for a general $A$, the above trace function is not convex. But for a PSD $A$, is the function convex?
97283
Let $T:\mathbb{R}^k\to\mathbb{R}^m$ is additive, i.e. $T(X_1+X_2)=T(X_1)+T(X_2)$. $T$ is locally bounded. Prove that $T$ is a linear transformation.  I know there is a relation between boundedness, convexity and scalar multiplicity. But not sure where to start or how to tie things together.
80609
Let $x = (x_1,\ldots,x_p) \in \mathbb R^p$. I'm solving the constrained optimization problem     $$\begin{align*} \text{min} &amp;\quad \sum_{i=1}^p (y_i-x_i)^2 \\ \text{s.t} &amp;\quad \sum_{i=1}^p y_i - 1 &amp;&amp;=0\\            &amp;\quad\forall  i = \overline{1,p}: -y_i &amp;&amp;\le 0  \end{align*}$$   My attempt:  Let $f(y) = \sum_{i=1}^p (y_i-x_i)^2$, $h(y) = \sum_{i=1}^p y_i - 1$, and $g_i(y) = -y_i$ for all $i = \overline{1,p}$.  We have $f,g_i$ are convex and $h$ is linear. Let $\alpha =(1/p, \cdots, 1/p)$. Then $h(\alpha)=0$ and $g(\alpha) &lt;0$ for all $i = \overline{1,p}$. It follows that Slater's condition is satisfied. By Karush-Kuhn-Tucker conditions, we have $$\begin{aligned} \begin{cases} \forall i = \overline{1,p}:\mu_i &amp;\ge 0 \\ \forall i = \overline{1,p}: g_i(y) &amp;\le 0\\ h(y) &amp;=0 \\ \forall i = \overline{1,p}:\mu_i g_i(y)&amp;=0 \\ \nabla f (y)+ \lambda\nabla h (y)+ \mu_i \nabla g_i (y) &amp;=0 \end{cases} &amp;\iff \begin{cases} \forall i = \overline{1,p}:\mu_i &amp;\ge 0 \\ \forall i = \overline{1,p}:-y_i &amp;\le 0\\ \sum_{i=1}^p y_i - 1&amp;=0 \\ \forall i = \overline{1,p}: -\mu_i y_i &amp;=0 \\ \forall i = \overline{1,p}: 2(y_i - x_i) +\lambda - \mu_i &amp;= 0 \end{cases} \\ \end{aligned}$$  Then I'm stuck at solving the last system of equations.  How can I proceed to solve it? Thank you so much!
29394
Intention  The clear solution is to use the fact that $x^n$ is twice differentiable. But I want a more direct proof. To be clear I want to prove this result without referencing the idea of a derivative.  My work  I decided to start with the inequality I wanted to prove, and work backward to an inequality that is obviously true.  Start with $$(ax+by)^n\leq ax^n+by^n\quad (1)$$  where $a$ and $b$ are positive real numbers such that $a+b=1$. Then (1) can be rewritten as  $$(a-a^n)x^n+(b-b^n)y^n-\bigg(\sum\limits_{k=1}^{n-1}{n\choose k}(ax)^k(by)^{n-k}\bigg)\geq 0$$  I am stuck here.
74663
Let $X_1,X_2,\ldots,X_n$ and $A_1,A_2,\ldots,A_n$ be real numbers taken at random, and $\alpha\gt0$. Show that: $$\sum_{k=1}^n |X_kA_k| \le \frac{1}{\alpha}\sum_{i=1}^n X_k^2 + \frac{\alpha}{4}\sum_{k=1}^n A_k^2$$
81678
I noticed many identical questions on this site relating to equivalent definitions of convexity, see for example , , , , , ,  and there might be more. So I wanted to create a &quot;big list&quot; of equivalent definitions of convex functions, I will start with some equivalent definitions and post my proofs in my answer below. Feel free to add any other equivalent definitions. This question can then serve as an abstract duplicate. Claim. Let $n\in\mathbb N$ and $f\in\mathcal C^1(\mathbb R^n)$. Then the following are equivalent:  $f$ is convex, i.e. $f(\lambda x_1 + (1-\lambda x_2))\le\lambda f(x_1)+(1-\lambda)f(x_2)$ for all $\lambda\in[0,1]$ and $x_1,x_2\in\mathbb R^n$. For all $x,y\in\mathbb R^n$, $\langle\nabla f(x)-\nabla f(y),x-y\rangle\geq0$. For every $x,y\in\mathbb R^n$, $f(y)\geq f(x)+\langle y-x,\nabla f(x)\rangle$.
40731
I have a function $f:\mathbb{R}^p\rightarrow\mathbb{R}$. For the purposes of illustration let's say that $p=2$. I want to prove that $f$ is convex. Suppose I can show that both  $f(\alpha x_1 + (1-\alpha)x_2,y)\leq\alpha f(x_1,y)+(1-\alpha)f(x_2,y) \quad \forall y \in \mathbb{R}$  and  $f(x,\alpha y_1 + (1-\alpha)y_2)\leq\alpha f(x,y_1)+(1-\alpha)f(x,y_2) \quad \forall x \in \mathbb{R}$  is true, i.e. I can show that the resulting univariate functions obtained by holding all but one of the arguments fixed is convex.  Is this sufficient to prove that $f$ is convex in $x$ and $y$? Namely  $f(\alpha x_1 + (1-\alpha)x_2,\alpha y_1 + (1-\alpha)y_2)\leq \alpha f(x_1,y_1) + (1-\alpha)f(x_2,y_2)$.  I am looking for a proof or counter example.   Merely applying each conditional inequality sequentially gives $f(\alpha x_1 + (1-\alpha)x_2,\alpha y_1 + (1-\alpha)y_2)\leq \alpha^2 f(x_1,y_1) + \alpha (1-\alpha) f(x_1,y_2) + \alpha (1-\alpha) f(x_2,y_1) + (1-\alpha)^2 f(x_2,y_2)$  If $f$ is a convex function, this implies the first two univariate inequalities of this post. This post is asking if the reverse direction holds.
32998
Let $f$ be an increasing function defined on $[a,b]$ and let $x_1 &lt; x_2 &lt; \dotsb &lt; x_n$ be $n$ points in the interior of $[a,b]$. Show that $\sum_{k = 1}^n [f(x_k^+) - f(x_k^-)]\leq f(b^-) - f(a^+)$.   The proof I have is very wordy and sketchy. I know it would be easier if I could find a telescoping sum but I've got a road block in my mind. :/
34793
In Section 2.5.2 of the book Convex Optimization by Boyd and Vandenberghe, the authors mentioned without proving that "a convex set in $\mathbb{R}^n$ with empty interior must lie in an affine set of dimension less than $n$." While I can intuitively understand this result, I was wondering how it can be proved formally?
51589
Let $f_1,f_2,f_3:\mathbb{R}^2\to\mathbb{R}_{\ge 0}$ be measurable, bounded, and compactly supported. Prove that  $$\int_{\mathbb{R}^3}f_1(y,z)f_2(x,z)f_3(x,y)d(x,y,z)\le\lVert f_1\rVert_{L^2(\mathbb{R}^2)}\lVert f_2\rVert_{L^2(\mathbb{R}^2)}\lVert f_3\rVert_{L^2(\mathbb{R}^2)}$$ By Tonelli's Theorem and Cauchy, \begin{align} \int_{\mathbb{R}^3}f_1(y,z)f_2(x,z)f_3(x,y)d(x,y,z) &amp;=\int_{\mathbb{R}^2}\left(f_1(y,z)\int_{\mathbb{R}}f_2(x,z)f_3(x,y)dx\right)d(y,z)\\ &amp;\le\sqrt{\int_{\mathbb{R}^2}f_1^2(y,z)d(y,z)\int_{\mathbb{R}^2}\left(\int_{\mathbb{R}}f_2(x,z)f_3(x,y)dx\right)^2d(y,z)} \\ &amp;\le\lVert f_1\rVert_{L^2(\mathbb{R}^2)}\sqrt{\int_{\mathbb{R}^2}\left(\int_{\mathbb{R}}f_2^2(x,z)f_3^2(x,y)dx\right)d(y,z)} \\ &amp;=\Vert f_1\Vert_{L^2(\mathbb{R}^2)}\sqrt{\int_{\mathbb{R}^3}f_2^2(x,z)f_3^2(x,y)d(x,y,z)} \\ &amp;=\lVert f_1\rVert_{L^2(\mathbb{R}^2)}\sqrt{\int_{\mathbb{R}^2}\left(f_2^2(x,z)\int_{\mathbb{R}}f_3^2(x,y)dy\right)d(x,z)} \\ &amp;\le\lVert f_1\rVert_{L^2(\mathbb{R}^2)}\sqrt[4]{\int_{\mathbb{R}^2}f_2^4(x,z)d(x,z)\int_{\mathbb{R}^2}\left(\int_{\mathbb{R}}f_3^2(x,y)dy\right)^2d(x,z)} \end{align}  As you can see, this doesn't seem to be going anywhere.