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!

  • $\begingroup$ 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$) ! $\endgroup$ – dohmatob Dec 31 '15 at 13:54
  • $\begingroup$ @dohmatob, you are right. I just wanted to mention that $g_i(x)$ are convex for all $i$. $\endgroup$ – 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$.

  • $\begingroup$ This is the correct answer. It should not have been downvoted. $\endgroup$ – Nick Alger Dec 31 '15 at 21:36
  • $\begingroup$ Sorry I did that by accident. How can I fix that? $\endgroup$ – 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?

  • $\begingroup$ @ Erwin, I think we cannot write it as a linear function! $\endgroup$ – rezzz Dec 31 '15 at 13:24
  • $\begingroup$ 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. $\endgroup$ – Erwin Kalvelagen Dec 31 '15 at 14:01

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.