2
$\begingroup$

I'm currently taking a convex optimization class and we're using the textbook by Boyd & Vandenberghe. I was solving an exercise problem when I came across a question (for anybody curious the problem is Exercise 9.1). I have two questions in total regarding the same problem. One about a detail within the problem and one regarding the solving itself. Here's the problem:

Consider the problem of minimizing a quadratic function:

$$\text{minimize}\quad f(x) = \frac{1}{2}x^T P x + q^T x + r$$

where $P \in S^n$ (i.e. an $n \times n$ symmetric matrix) but we do not assume $P$ is positive semidefinite.

Show that if $P$ is not positive semidefinite (and therefore objective function $f$ is not convex) then the problem is unbounded below.

My approach

By definition if a matrix is not positive semidefinite then that means there exists some $z$ such that

$$z^TPz \lt 0$$

Following this logic we could say that $x = \alpha z$ with $x, z \in \Bbb{R}^n$ and $\alpha \in \Bbb{R}$. The objective function changes to

$$f(x) = \frac{1}{2}\alpha^2 (z^TPz) + q^T(\alpha z) + r$$

This is where I get stuck. According to the solution manual, it states that if $\alpha$ becomes large then $f \rightarrow -\infty$ and we can therefore conclude that the function is unbounded below.

My two questions are as follows:

  1. Why does the matrix not being positive semidefinite imply the function is not convex?

  2. How was the conclusion drawn that if $\alpha$ becomes large then the function diverges to $-\infty$?

Thank you.

$\endgroup$
1
$\begingroup$

To answer your first question,

The definition of a convex function (in the context of twice continuously differentiable functions) is that the Hessian is positive semidefinite, and the Hessian of $f$ in this case is $P$.

As for your second question,

Since you've now fixed $z$, the expression $\frac{1}{2}z^TPz\alpha^2 + q^Tz\alpha+r$ is just a quadratic equation with variable $\alpha$, and if the second order term of a quadratic equation is negative then we know its parabola faces downwards.

$\endgroup$

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.