Given a set $S = \{x_1,\dotsc,x_n\} \subset \mathbb{R}$, is the function

\begin{align} f&: (0,\infty) \to \mathbb{R} \\ f&(p) = 2p^2 + \frac{1}{n}\sum_{i=1}^n \max(0, -p^2-x_i) \end{align}

strongly convex? (What if $f: \mathbb{R} \to \mathbb{R}$?)

I know $p^2$ is strongly convex. Let $P = \{x_i \in S : x_i + p^2 \geq 0\}$ and $N = S\setminus P$ then

\begin{align} f(p) = \begin{cases} 2p^2 & \text{ for all } x_i \in P \\ 2p^2 - \frac{1}{|N|}\sum_{i=1}^{|N|} -p^2 -\frac{1}{|N|}\sum_{i=1}^{|N|}x_i & \text{ for all } x_i \in N \end{cases} \end{align} so in both cases $f$ is strongly convex. Is this argumentation valid?

  • $\begingroup$ Could you please specify the sign of the $x_i$'s and $p$? Is $p$ a continuous variable? $\endgroup$ – AndreaCassioli Jul 15 '14 at 16:37
  • $\begingroup$ The $x_i$ are $p$ real numbers and $p>0$ if necessary. Why could the sign of $x_i$ play a role? They are constants. $\endgroup$ – Manuel Schmidt Jul 15 '14 at 17:47

First we can assume $x_i<0,\forall i$. We can write

$f(p) = \frac{1}{N} \sum_i^N ( p^2+\max\{0, -p^2-x_i\} )= \frac{1}{2}\sum_i^n \phi(p)_i,$

Then it is easy to see that $\phi(p)_i = -x_i$ for $p\in [-\sqrt x_i,\sqrt x_i]$, while $\phi(p)_i= p^2 $ otherwise. This is strictly convex. Each $\phi(p)_i$ is known as Huber penalty function (see http://web.stanford.edu/~boyd/cvxbook/ pag 299).

The $f(p)$ function is then the sum of strictly convex functions, and therefore strictly convex.

  • $\begingroup$ I think in a special case I a can add a convex and a concave function and get a convex function. For example $p^2-p^2$ is constant $0$ and convex. $\endgroup$ – Manuel Schmidt Jul 15 '14 at 19:13
  • $\begingroup$ Even more $2p^2-p^2$ is the sum of a strongly convex and strongly concave function that is strongly convex. $\endgroup$ – Manuel Schmidt Jul 15 '14 at 19:38
  • $\begingroup$ You are right. I update the post. $\endgroup$ – AndreaCassioli Jul 15 '14 at 20:26
  • $\begingroup$ Thanks for your help. Please, note that I am talking about strong not strict convexity. As in my original question your argumentation has to consider two cases. $\endgroup$ – Manuel Schmidt Jul 15 '14 at 20:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.