I'm currently working on a problem involving convexity of a function:
$f(x_1,x_2)=0.5(x_2^2 +x_1^2) -x_1x_2$ We are also given a constraint:
$g(x_1,x_2) = x_1+x_2 \leq -1$
I know graphically this is convex, but I'm required to use two tools to show $f(x_1,x_2)$ is convex:
- The sum of two convex functions is convex.
- If $h$ is convex on $\mathbb{R}$ and $l$ is linear from $\mathbb{R}^n$ to $\mathbb{R}$, then $h\circ l$ is convex on $\mathbb{R}^n$
From tool 1, if we treat $f_1(x_1,x_2)=0.5(x_2^2 +x_1^2)$ and $f_2(x_1,x_2)=-x_1x_2$:
- $f_1(x_1,x_2)$ is convex because its hessian is positive definite at the stationary point (0,0) and the this is essentially summing two parabolas (satisfying tool 1).
- $f_2(x_1,x_2)$ is a saddle point at (0,0) because the hessian for $f_2$ is $\nabla^2(f_2)(0,0) = -1 <0$ which is indefinite but if we take $-f_2$; the hessian becomes: $\nabla^2(-f_2)(0,0) = -1 <0$ indicating a saddle point. Maybe this becomes convex within the feasible region?
So I'm assuming tool 2 interacts with $f_2$ somehow, but I don't really know what tool 2 is asking. I can kind of understand, and I know that $f:\mathbb{R}^n \to \mathbb{R}$ is saying "a function when given a Real numbered input vector of length n; it outputs a single real number". I just don't know how to use tool 2 to my advantage. My suspicion is that it involves drawing a line from one point to another and using that information to show convexity.
Thanks for reading!
You can rewrite your function in the form $$ f(x_1,x_2)=\frac 1{2}(x_1-x_2)^2. $$ This is a composition of $r\to\frac 1{2}r^2$ (clearly convex) with the linear function $(x_1,x_2)\to x_1-x_2$. So it is convex. Your constraint is a half-plane, hence a convex set. Conclusion: your function is convex.