Strictly convex function proof

Question

Is the following function strongly convex for $x\succeq 0: \sum_{i} x_i = 1$ and $c_i > 0$ for $i\neq 1$? $$ f(x) = \max_{i\neq 1}f_i(x) = \max_{i\neq 1}\frac{\frac{1}{x_1} + \frac{1}{x_i}}{c_i}. $$ What I have tried: based on this reply, the pointwise maximum of strictly convex functions is strictly convex. Hence, it suffices to prove that $\forall i \neq 1$,$f_i(x)$ is strictly convex.

The hessian of $f_i$ is $H_i = \text{diag}(\frac{2}{c_1x_1^3}, 0,\frac{2}{c_ix_i^3}, \dots, 0)$, which for $x\succeq 0$ is positive semi-definite. Is this, in combination with the previous result on pointwise maximum of strictly convex function enough to prove that $f(x)$ is strictly convex?

The matrix $H_i$ is positive semi-definite, but not positive definite. — Martin R, Apr 18 '22 at 08:32
Indeed. (You probably want the $c_i$ and $x_i$ to be strictly positive to make everything well-defined.) — Martin R, Apr 18 '22 at 08:53

Martin R · Accepted Answer · 2022-04-18T11:43:01.680

Your argument works to show that $f$ is (weakly) convex, but the function is not strictly convex if the domain is $\Bbb R_+^n$ with $n \ge 4$.

Without loss of generality we may assume that $c_2 \ge c_3 \ge \cdots \ge c_n$. Now fix $x_4 = \cdots = x_n = \frac{1}{3(n-2)}$ and consider $f$ as a function of two variables $x_2, x_3$ with $\frac 16 \le x_2, x_3 \le 1$, $x_1 + x_2 = \frac 23$.

Then $$ \frac{\frac{1}{x_1} + \frac{1}{x_k}}{c_k} \le \frac{\frac{1}{x_1} + \frac{1}{x_k}}{c_j} \le \frac{\frac{1}{x_1} + \frac{1}{x_j}}{c_j} $$ for all $k=2, 3$ and $j \ge 4$, so that $$ h(x_2, x_3) = f(x_2, x_3, \frac{1}{3(n-2)}, \ldots, \frac{1}{3(n-2)}) $$ is constant for $\frac 16 \le x_2, x_3 \le 1$, $x_1 + x_2 = \frac 23$.

In particular is $h(1/6, 1/2) = h(1/3, 1/3) = h(1/2, 1/6)$, which shows that $h$ (and therefore $f$) is not strictly convex.

@Apprentice: I have updated the answer. – Martin R Apr 18 '22 at 11:34 — Martin R, Apr 18 '22 at 11:34

score 0 · Answer 2 · answered Apr 18 '22 at 08:40

It will not be strictly convex.

Assume you are at a point $x$ such that the maximum defining $f$ is attained for a given unique $i$ (i.e. for any $j \neq i$, $f_j(x) < f_i(x)$). (This depends on the $c_i$ but can clearly be made by fixing all the other $x_j$ and choosing $x_i$ close to $0$.)

Then, by continuity, moving any $x_j$ for $j \neq i$ (and $j \neq 1$) will not change the value of $f$ (at least locally). Since $f$ is therefore constant on such lines, it cannot be strictly convex.

Strictly convex function proof

2 Answers2