5
$\begingroup$

In convex optimization it is often convenient to use the following smooth approximation to $\max\{x_1, \ldots, x_n\}$:

$$ f_\lambda(x_1, \ldots, x_n) = \frac{1}{\lambda}\log \sum_{i = 1}^n{e^{\lambda x_i}}. $$

Above $\lambda > 0$ is a parameter. It's easy to see that

$$ \max\{x_1, \ldots, x_n\} \leq f_\lambda(x_1, \ldots, x_n) \leq \max\{x_1, \ldots, x_n\} + \frac{1}{\lambda}\log n. $$

It is also easy to verify that $f_\lambda(x_1, \ldots, x_n)$ is convex. For example, the second derivative at $x = (x_1, \ldots, x_n)$ in the direction of $y = (y_1, \ldots, y_n)$ is

$$ \left(\frac{d^2}{(dt)^2}f_\lambda(x + ty)\right)_{t = 0} = \lambda \left(\frac{\sum_i{e^{\lambda x_i}y_i^2}}{\sum_i{e^{\lambda x_i}}} - \frac{(\sum_i{e^{\lambda x_i}y_i})^2}{(\sum_i{e^{\lambda x_i)}})^2} \right) \ge 0, $$ for $\lambda > 0$, by Cauchy-Schwarz (notice this is the variance of a random variable that takes value $y_i$ with probability proportional to $e^{\lambda x_i})$.

There is a natural matrix equivalent to the soft max which is an approximation of the largest eigenvalue of a real symmetric matrix $X$:

$$ g_\lambda(X) = \frac{1}{\lambda}\log \mathrm{tr\ } e^{\lambda X}. $$

Let's assume that $X$ is real symmetric $n\times n$ matrix, with eigenvalues $\mu_1 \geq \mu_2 \ldots \ge \mu_n$. The matrix exponential is, as usual, $e^M = \sum_{i = 0}^\infty{\frac{1}{i!}M^i}$. Then, $\mu_1 \leq g_\lambda(X) \leq \mu_1 + \frac{1}{\lambda}\log n$.

Is $g_\lambda(X)$ convex over real symmetric $X$, for $\lambda > 0$? What's an easy proof?

The proof of convexity for $f_\lambda$ does not adapt easily, because of commutativity issues.

$\endgroup$
6
$\begingroup$

$ \DeclareMathOperator{\tr}{tr}$ You can get some information using the concepts of Schur-convexity and majorization:

Let $X$ be an $n \times n$ real symmetric matrix, with spectral decomposition $ X = U \Lambda U^T$, $U$ is an orthogonal matrix, $\Lambda$ is diagonal with the eigenvalues. Then your function is $$ g_\lambda(X)= \frac{1}{\lambda} \log \tr e^{\lambda X} = \frac{1}{\lambda} \log\sum_{k=1}^n e^{\lambda \lambda_k}. $$ (the matrix exponential function)

Now, $g_\lambda$ is a Schur-convex function (the proof is easy), the proof method given in the wikipedia article works. And, if now $X$ and $Y$ are two real symmetric matrices as above, then, if the eigenvalues of $X$ are $\lambda_i$ and the eigenvalues of $Y$ is $\omega_i$, we have the majorization result that the vector of eigenvalues of $\mu X + (1-\mu) Y$ $(0 \le \mu \le 1)$ is majorized by the vector $\mu \lambda + (1-\mu) \omega$. This gives the result that $$ g_\lambda(\mu X + (1-\mu) Y) \le \frac{1}{\lambda} \log \sum_{k=1}^n e^{\lambda(\mu \lambda_k + (1-\mu) \omega_k)} $$ which might be of some help in further analysis.

EDIT The following paper seems to give an answer: http://people.orie.cornell.edu/aslewis/publications/96-convex.pdf

Your function is convex. The result proved there is that a spectral matrix function (of Hermitian or real symmetric argument) ($g_\lambda$ is spectral, meaning that it depends only on the eigenvalues of the matrix argument): convex spectral functions can be characterized as symmetric convex functions of the eigenvalues. $g_\lambda$ is clearly symmetric, and you proved yourself it is convex. That is all which is needed (after reading that paper above).

$\endgroup$
  • 1
    $\begingroup$ Terrific, thank you! It seems the original result is due to von Neumann, by the way. $\endgroup$ – Sasho Nikolov Jan 25 '14 at 16:53
  • 1
    $\begingroup$ Kjetil, I looked again at this, and you have essentially proven convexity for $g_\lambda$. It follows directly from the inequality you derived for $g_\lambda$ and from the convexity of $f_\lambda$. $\endgroup$ – Sasho Nikolov Feb 5 '14 at 0:09

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.