Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
In short, the problem is actually: maximize a quadratic form (with positive coefficients) on the direct project of some unit spheres –  Guoxin Zhang Dec 11 '11 at 16:54
    
You haven't described any projection onto the nonnegative orthant- I assume that you're doing that. Although Q is nonnegative, it's conceivable that negative elements in d could cause the iteration to to move outside of the nonnegative orthant. If you used $y_{n+1}=2Qx_{n}+d$, then you'd have a projected gradient ascent algorithm for which there are plenty of convergence results. –  Brian Borchers Dec 11 '11 at 17:37
    
hi, thanks for the quick reply. It's should be $\frac{1}{2}x^TQx+d^Tx$ I've corrected it. d is also nonnegative, and I've mentioned that in the beginning. –  Guoxin Zhang Dec 11 '11 at 17:58
    
It seems not a standard gradient ascent algorithm. Can anyone give some hints? Thanks. –  Guoxin Zhang Dec 11 '11 at 18:33
    
In general, the way to prove such statement is with the Banach fixed point theorem. Have you tried it? –  Antoine Levitt Dec 11 '11 at 19:41

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.