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

Question

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!

Answer 1

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?

Answer 2

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$.