0

I think this function is strictly convex in the vector ${\bf x} = (x_1,x_2,x_3,x_4)$ but the fact that some terms are zero when variables take on the same values leaves me uncertain, i.e. when $x_1=x_2$ and $x_1=x_3$ then the argument of $c_1$ is zero.

$C({\bf x}) = c_0(a_0x_1^2)+c_1\left(a_1(x_1-x_2)^2+b_1(x_1-x_3)^2\right) + c_2\left(a_2(x_2-x_1)^2+b_2(x_2-x_4)^2\right)$

where each $c_i$ is strictly increasing and strictly convex, $c_i(0) =0 $ and all $a_i,b_i>0$. What is throwing me off is the fact that a function like $f(x,y) = (x-y)^2$ is weakly convex.

Thank you

jonem
  • 383
  • 1
    Yes, but your function is more like $f(x,y) = x^2 + (x-y)^2$. – Stephen Montgomery-Smith Mar 21 '14 at 02:46
  • Thanks, what is the reasoning? The second and third terms have weakly convex arguments, so the composition with a strictly convex function is still weakly convex. Is strict convexity all due to the first term? But it is only strictly convex in $x_1$, not ${\bf x}$. Sorry for all the questions. – jonem Mar 21 '14 at 02:49
  • 1
    If you are allowed to assume that your functions are twice differentiable, I would prove that the Hessian is positive definite. – Stephen Montgomery-Smith Mar 21 '14 at 02:52
  • Thanks. If the function was just $c_1\left(a_1(x_1-x_2)^2+b_1(x_1-x_3)^2\right) + c_2\left(a_2(x_2-x_1)^2+b_2(x_2-x_4)^2\right)$ would it still be strictly convex? – jonem Mar 21 '14 at 03:06
  • 1
    No. For exactly the kind of reason you stated. It would be constant along the ray $(x_1,x_2,x_3,x_4) = (t,t,t,t)$. – Stephen Montgomery-Smith Mar 21 '14 at 03:08
  • Great, that makes things much clearer, much appreciated. – jonem Mar 21 '14 at 03:10

1 Answers1

1

First note a result which is straightforward to verify: Suppose $f$ is convex and $\phi: \mathbb{R} \to \mathbb{R}$ is convex and non-decreasing, then $\phi \circ f$ is convex. In addition, if $f$ is strictly convex, and $\phi$ is strictly increasing, then $\phi \circ f$ is strictly convex.

Let $A = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 1 & -1 & 0 & 0 \\ 1 & 0 & -1 & 0 \\ 0 & 1 & 0 & -1 \end{bmatrix}$, and note that $\det A = 1$.

Then $C = \kappa \circ A$, where $\kappa(y) = c_0(a_0 y_1^2)+c_1\left(a_1y_2^2+b_1 y_3^2\right) + c_2\left(a_2 y_2^2+b_2 y_4 ^2\right)$, and I am abusing notation slightly by using $A$ to represent the map $x \mapsto Ax$.

Since $A$ is an invertible linear map, we see that $C$ is strictly convex iff $\kappa$ is.

Let $f_0(y) = c_0(a_0 y_1^2)$, $f_1(x) = c_1\left(a_1y_2^2+b_1 y_3^2\right)$, $f_2(y) = c_2\left(a_2 y_2^2+b_2 y_4 ^2\right)$, and note that from the hypotheses, the $f_k$ are all convex. Also note that by the above result, the restricted maps $y_1 \mapsto c_0(a_0 y_1^2)$, $(y_2,y_3) \mapsto c_1\left(a_1y_2^2+b_1 y_3^2\right)$, $(y_2,y_4) \mapsto c_2\left(a_2 y_2^2+b_2 y_4 ^2\right)$ are strictly convex.

We have $\kappa = f_1+f_1+f_2$, and if $\lambda \in [0,1]$, we have $f_k(\lambda x + (1-\lambda ) y) \le \lambda f_k(x) + (1-\lambda) f_k (y) $, for each $k$, and so we see that $\kappa$ is convex. Furthermore, note that at any particular $x,y,\lambda$, if the inequality is strict for any of the $f_k$, then the inequality is strict for $\kappa$.

Now suppose $x\neq y$ and $\lambda \in (0,1)$. Then, since $x_i \neq y_i$ for at least one $i$, we see that the inequality is strict for at least one $f_k$, hence $\kappa$ is strictly convex.

Note that strict convexity depends on the domain in the sense that if you extend a strictly convex function to a larger domain, it may no longer be strictly convex. For example, the function $x_1 \mapsto x_1^2$ is strictly convex, but the function $(x_1 , x_2) \mapsto x_1^2$ is not.

copper.hat
  • 172,524
  • Thanks for your help! It seems establishing strict convexity is much trickier than convexity at times. I'll push my luck and try to ask you one question related to the above. If I were to have another term, say $c_3(a_3(x_3-x_1)^2 + b_3(x_3-x_4)^2)$, would the function still be strictly convex? This would add another row to $A$ so the determinant would not be defined (since $A$ is non-square) but I'm thinking we could take the same $A$ to establish st. convexity, and the additional term would just be a convex term added. If this changes the proof significantly then don't worry about it! – jonem Apr 03 '14 at 17:53
  • If $f$ is strictly convex and $g$ is convex, then $f+g$ is strictly convex. This follows directly from the (functional) definition of convexity and strict convexity. – copper.hat Apr 03 '14 at 17:57
  • Can you elaborate a bit on the statement "since $x_i \neq y_i$ for at least one $i$, we see that the inequality is strict for at least one $f_k$," I don't see why this is true. – jonem Apr 04 '14 at 03:45
  • Note that the maps $f_k$ above are strictly convex when restricted to the appropriate subspace. If $y_1 \neq x_1$ then $f_0$ is strictly convex, if $y_2 \neq x_2$ or $y_3 \neq x_3$ then $f_1$ is strictly convex, and similarly (with appropriate changes) $f_2$ is strictly convex... – copper.hat Apr 04 '14 at 03:50