The problem is actually a quadratically constrained quadratic program. And the formulation is: $max: \frac{1}{2}x^TQx + d^Tx$
$s.t. x\in R^{n,+} ,\sum_{i\in I_p}x_i^2=1, p=1..k$
where $d\in R^{n,+}$, Q is an $n\times n$ irreducible symmetric non-negative matrix, $I_1..I_k$ is a partition of $1..n$.
An iteration similar to the power iteration is given by:
$y_{n+1}=Qx_n+d$
$x_{n+1,i}=\frac{y_{n+1,i}}{\sqrt{\sum_{j\in I_{pi}}y_j^2}}$
where $x_{n+1,i}$ is just the $i$th component of vector $x_{n+1}$
in the second formula, $I_{pi}$ is the set which $i$ belongs to. In short, the second step is just 'projection to the constraint'.
To begin the iteration, we start from any positive vector.
The problem is whether $x_n$ always converges? In practice, it seems always this case.
Using the result from the paper 'Optimization of positive generalized polynomials under Lp constraints' (Theorem 5), we have that there is a unique maximum value, which is also the unique fixed point $x^*$ of such an iteration.
However, I still do not know whether the iteration generally convergences to $x^*$.
The paper 'Efficient MAP Approximation for Dense Energy Functions' uses the result but does not give any proof.
This problem is of great importance in the optimization for the MAP labeling problem. Does anyone know how to prove it?
Thanks very much.
