Is the following formula convex or concave?

Question

I have the formula using Frobenius norm as follows:

$1 - \frac{\bigg\|\mathbf{a} - \frac{\sum_{m=1}^M m(x_{m} - x_{m-1})}{\gamma} \mathbf{b}\bigg\|_F}{\|\mathbf{a}\|_F}$,

where $\mathbf{a}, \mathbf{b}, \gamma$ are constants, $x_0 = 0$, and $x_m, \forall m \in \mathcal{M}$ are variables with $x_m \geq x_{m-1}, \forall m \in \{2,\ldots, M\}$.

Is this formula convex or concave? How to prove it?

score 2 · Accepted Answer · answered Mar 11 '20 at 09:35

2

Let $x,y \in \mathbb{R}^m$ satisfying the inequalities and $\lambda \in (0,1)$,

\begin{align} &f(\lambda x + (1-\lambda)y)\\ &=1- \frac{\|a-\frac{\sum_{m=1}^M m\lambda( x_m- x_{m-1})+m(1-\lambda) (y_m - y_{m-1}))}{\gamma}b\|_F}{\|a\|_F} \\ &=1- \frac{\|\lambda a+(1-\lambda)a-\frac{\sum_{m=1}^M m\lambda( x_m- x_{m-1})+m(1-\lambda) (y_m - y_{m-1}))}{\gamma}b\|_F}{\|a\|_F} \\ &\ge 1-\lambda \frac{\|a-\frac{\sum_{m=1}^M m( x_m- x_{m-1})}{\gamma}b\|_F}{\|a\|_F} - (1-\lambda)\frac{\|a-\frac{\sum_{m=1}^M m( y_m- y_{m-1})}{\gamma}b\|_F}{\|a\|_F}\\ &=\lambda + (1-\lambda)-\lambda \frac{\|a-\frac{\sum_{m=1}^M m( x_m- x_{m-1})}{\gamma}b\|_F}{\|a\|_F} - (1-\lambda)\frac{\|a-\frac{\sum_{m=1}^M m( y_m- y_{m-1})}{\gamma}b\|_F}{\|a\|_F}\\ &= \lambda f(x)+(1-\lambda)f(y) \end{align}

where the inequality is due to triangle inequality for Frobenius norm.

Hence it is concave.

answered Mar 11 '20 at 09:35

Siong Thye Goh

149,520
20
88
149

Thank you very much! – bnbfreak Mar 12 '20 at 10:18
If we multiply the formula with a constant $c$ such that $c(.)$, where $(.)$ is the above formula, we still have a concave function, right? – bnbfreak Mar 12 '20 at 10:28
that depends on the sign of $c$, if $c$ is nonnegative, it remains concave, if $c$ is negative, it becomes convex. – Siong Thye Goh Mar 12 '20 at 10:33
Yes, exactly. It is a non-negative constant. Thank you. – bnbfreak Mar 12 '20 at 10:42

Is the following formula convex or concave?

1 Answers1