🚀 go-pugleaf

In article <1992Nov6.170030.8063@qucis.queensu.ca> ismaeil@qucis.queensu.ca (Ossama Ismaeil) writes:
>
>   Now, the problem can be described as 
>
>                  T
>           Min   X  X  
>
>      S.T         T 
>                 X A X <= 0
>
>                 W X    = C   
>
>  where X is a vector , A is a square indefinite matrix, and W is a rectangular
>  matrix, and C is a constant vector.
>

(Assume that A is symmetric and W is of maximal rank.)

Write Y = W^T (W W^T)^{-1} C.  If Y^T A Y <= 0, then X = Y is the answer.

Otherwise, the answer will have X^T A X = 0.

Let Q be a rectangular matrix whose rows are are maximal set of orthonormal 
vectors orthogonal to the rows of W.  Then W X = C if and only if X is of the 
form Y + Q Z, where the vector Z is in 1-1 correspondence with X.

So we want to minimize X^T X - Y^T Y = Z^T Z given that 
    X^T A X = Z^T Q^T A Q Z + 2 Y^T A Q Z + Y^T A Y = 0.

Find the eigensystem of (Q^T A Q) and expand Z in terms of the eigenvectors.  
Then we can transform the problem into minimizing Sum_i (z_i^2) given that 
Sum_i (a_i z_i^2) + 2 Sum_i (b_i z_i) + c = 0.

The solution to this is z_i = lambda b_i / (1 - lambda a_i), where lambda is
one of the roots of a polynomial equation, got by substituting this z_i into
the given condition.  Hence Z, hence X.

David Handscomb
(dch@comlab.ox.ac.uk)