# How to efficently solve a convex optimization problem with positive semi-definite Hessian matrix?

Consider the following optimization: $$f(x)= \min \sum_{i=1}^n \left(x_i-\sum_{j=1}^n x_j\right)^2$$

Let $g_i(x)=x_i-\sum_{j=1}^n x_j$ , then

$$f(x)= \min \sum_{i=1}^n g_i(x)^2$$

The determinant of Hessain matrix of $g_i(x)$ for all $i$ is zero; therefore, the Hessian matrices are positive semi-definite, and $g_i(x)$ is convex. We know that one of the eigenvalues is equal to zero as well.

To solve this quadretic optimization problem, Cplex/OPL can be used, but I am looking for a theorem or property that specifically uses for this type of optimizatin programming (determinant of Hessain matrix equal to zero, positive semi-definite, and convex).

Is there any theorem or property that can simplify optimization of this function?

Thank you very much!

• You say $g_i(x) \in S \subseteq \mathbb R^n$, and so $g_i(x)$ must be a vector in $\mathbb R^n$. So $g_i(x)^2$ makes no sense (except if $n = 1$) ! – dohmatob Dec 31 '15 at 13:54
• @dohmatob, you are right. I just wanted to mention that $g_i(x)$ are convex for all $i$. – rezzz Dec 31 '15 at 16:01

For an appropriate $n$-by-$n$ positive semidefine matrix $A$ and an approriate vector $b \in \mathbb{R}^n$, your problem is equivalent to minimizing the quadratic functional (as an easy exercise, determine $A$ and $b$ in problem) $$x \mapsto \frac{1}{2}x^TAx + b^Tx,\; x \in \mathbb R^n.$$

One can show (see Proposition 12.5 this manuscript, for example) that the above problem is solvable iff

$$b \in \ker I - AA^+.$$ where $A^+$ denotes the Moore-Penrose pseudo-inverse of $A$. In this case, the optimal minimal value of the objective is

$$p^* = -\frac{1}{2}b^TA^+b,$$ and the set of minimizers is $$\mathcal S := \{-A^+b + U[0\hspace{.5em}z]^T | z \in \mathbb R^{n-r}\},$$

where $r:=\text{rank }A$, and $A = U\Sigma U^T$, is the SVD decomposition of $A$.

• This is the correct answer. It should not have been downvoted. – Nick Alger Dec 31 '15 at 21:36
• Sorry I did that by accident. How can I fix that? – Erwin Kalvelagen Dec 31 '15 at 22:11

You write $g_i$ as a function. Can we not just use additional variables $y$ and $s$ and write the following linear equations plus convex objective:

$$\begin{array}{l} s = \sum_i x_i \\ y_i = x_i - s\\ \min \sum_i y^2_i \end{array}$$

This can be solved straightforwardly and efficiently with Cplex/OPL (the Q matrix is now positive definite). This formulation is somewhat optimized to make things as linear as possible and to minimize the number of nonzero elements in the constraint matrix.

Am I missing something?

• @ Erwin, I think we cannot write it as a linear function! – rezzz Dec 31 '15 at 13:24
• I am not using a function but rather simultaneous equations. These equations must hold at the same time. Exactly what a QP solver does for us. – Erwin Kalvelagen Dec 31 '15 at 14:01