0
$\begingroup$

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:

  1. The sum of two convex functions is convex.
  2. 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$:

  1. $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).
  2. $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!

$\endgroup$

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Oh, it was as simple as examining the parabolic properties. Awesome that makes total sense. Thank you for helping me! $\endgroup$
    – Sprawk48
    Commented Oct 10, 2021 at 1:18
  • $\begingroup$ One other thing< let's say that the function changes from $f(x_1,x_2)=0.5(x_2^2 +x_1^2) -x_1x_2$ to $f(x_1,x_2)=0.5(2x_2^2 +x_1^2) -x_1x_2$ how does this affect the intuition? $\endgroup$
    – Sprawk48
    Commented Oct 10, 2021 at 3:56

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .