Abstract:
In industrial applications, the invention relates to various algorithms for determining optimal resources or assets allocations under various equality and inequality constraints. In particular, constrained quadratic or conic optimization problems of unique importance for portfolio asset allocation are seamlessly solved in analytic and efficient ways. In addition, by providing exact or analytic optimum expressions, robustness can be readily ascertained.

Description:
BACKGROUND OF THE INVENTION 
     In industrial applications, a substantial number of problems of efficient allocations of resources can be translated into the mathematical resolution of one or more constrained optimization problems, that is problems in which one seeks to minimize or maximize a real function by systematically choosing the values of real or integer variables from within a constrained allowed set. 
     As a subset of optimization problems, quadratic or conic optimization problems comprise one of the most important areas of nonlinear programming. They are currently solved in practical applications preferentially using variations of so-called “interior point methods” i  that are generally relevant for convex optimization problems. Numerous practical problems, including problems in financial portfolio optimization, portfolio hedging, planning and scheduling, economies of scale, and engineering design, and control are naturally expressed as quadratic optimization problems. 
     We describe a new and more effective method for solving optimization problems in general by actually explicitly solving the apparently intractable Karush-Kuhn Tucker (KKT) equations and inequalities associated with the mathematical formulation of the problems. The general method outlined in our drawings and below is illustrated in detail through the resolution of classical quadratic and conic optimization problems. 
    
    
     
       BRIEF DESCRIPTION OF THE SEVERAL VIEWS OF THE DRAWINGS 
         FIG. 1  illustrates the components and structure of the algorithm implementing our method. 
         FIG. 2  describes the procedure for obtaining candidate local extrema from KKT equations. 
         FIG. 3  outlines the conditions under which a local extremum may be admissible via the verification of first and second order inequality constraints. 
         FIG. 4  outline the disposition of potential candidate local extrema. 
         FIG. 5  describes various strategies that may be used to effect computational gains. 
         FIG. 6  summarizes obvious benefits of the method. 
         FIG. 7  expands on the scope of applications. 
     
    
    
     DETAILED DESCRIPTION 
       FIGS. 1 to 7  present the method in general. Our detailed description provides added clarity through the detailed study of two specific cases. These illustrations are made even more practical in the Mathematica computer implementation of Appendix 2. 
     Case 1: A Generic Quadratically Constrained Minimization Problem 
     This problem can be generally stated analytically as: 
     Find the solution to the constrained quadratic optimization problem 
               Min   ⁢     1   2     ⁢     W   t     ⁢   Σ   ⁢           ⁢   W     +       C   t     ⁢   W   ⁢           ⁢   subject   ⁢           ⁢   to   ⁢           ⁢   constraints                 {                     AW   t     -   B     =   0     ;                      W   -         M   _     +     M   _       2            ≤         M   _     -     M   _       2             ⁢     
     ⁢   with   ⁢           ⁢     M   _       ,   W   ,   C   ,       M   _     ⁢     ∈   m       ,       M   _     ≤   W   ≤     M   _       ,       A   ⁢     ∈   s     ⁢     ×   m       ;     
     ⁢       Rank   ⁡     (   A   )       =     s   ≤   m         ,     B   ⁢     ∈   s               
Solution:
 
     We proceed as outlined in  FIG. 2 . The KKT Equations are: 
               K   =           1   2     ⁢     W   t     ⁢   Σ   ⁢           ⁢   W     +       C   t     ⁢   W     +       λ     ′   t       ⁡     (     AW   -   B     )       -       γ   -     ⁡     (     W   -     M   _       )       +         γ   +     ⁡     (     W   -     M   _       )       ⁢     λ   ′         ⁢     ∈   s         ,     
     ⁢           ⁢       M   _     ≤   W   ≤     M   _       ,       A   ⁢     ∈   s     ⁢     ×   m       ;           
the so-called
 
slacking parameters γ + ,γ −  must verify γ + ,γ − ε +   m ,
 
We note γ γ + −γ − ; We have:
 
                   {             ∇     K   t       =         Σ   ⁢           ⁢   W     +   C   +       A   t     ⁢     λ   ′       +   γ     =   0             (   1   )                 AW   -   B     =   0           (   2   )                     γ   +     ⁡     (     W   -     M   _       )       =   0     ,         γ   -     ⁡     (     W   -     M   _       )       =   0             (   3   )                   ∇ K   t   =ΣW+C+A   t λ′+γ=0  (1)
 
     We suppose there are p active constraints and q=m−p non-active ones. We perform a block decomposition along active and non active constraints. We introduce the operator LinSol defined in Appendix 1. 
     The non-active constraints lead to γ q =0. Hence, 
     
       
         
           
             
               
                 ( 
                 1 
                 ) 
               
               ⇔ 
               
                 
                   - 
                   
                     ( 
                     
                       
                         
                           
                             s 
                             pp 
                           
                         
                         
                           
                             s 
                             pq 
                           
                         
                       
                       
                         
                           
                             s 
                             pq 
                             t 
                           
                         
                         
                           
                             s 
                             qq 
                           
                         
                       
                     
                     ) 
                   
                 
                 ⁢ 
                 
                   ( 
                   
                     
                       
                         
                           M 
                           p 
                         
                       
                     
                     
                       
                         
                           W 
                           q 
                         
                       
                     
                   
                   ) 
                 
               
             
             = 
             
               
                 ( 
                 
                   
                     
                       
                         
                           A 
                           p 
                           t 
                         
                         ⁢ 
                         
                           λ 
                           ′ 
                         
                       
                     
                   
                   
                     
                       
                         
                           A 
                           q 
                           t 
                         
                         ⁢ 
                         
                           λ 
                           ′ 
                         
                       
                     
                   
                 
                 ) 
               
               + 
               
                 ( 
                 
                   
                     
                       
                         C 
                         p 
                       
                     
                   
                   
                     
                       
                         C 
                         q 
                       
                     
                   
                 
                 ) 
               
               + 
               
                 ( 
                 
                   
                     
                       
                         γ 
                         p 
                       
                     
                   
                   
                     
                       0 
                     
                   
                 
                 ) 
               
             
           
         
       
       
         
           
             
               
                 ( 
                 1 
                 ) 
               
               ⇔ 
               
                 
                   - 
                   
                     ( 
                     
                       
                         
                           
                             s 
                             pp 
                           
                         
                         
                           
                             s 
                             pq 
                           
                         
                       
                       
                         
                           
                             s 
                             pq 
                             t 
                           
                         
                         
                           
                             s 
                             qq 
                           
                         
                       
                     
                     ) 
                   
                 
                 ⁢ 
                 
                   ( 
                   
                     
                       
                         
                           M 
                           p 
                         
                       
                     
                     
                       
                         
                           W 
                           q 
                         
                       
                     
                   
                   ) 
                 
               
             
             = 
             
               
                 ( 
                 
                   
                     
                       
                         
                           A 
                           p 
                           t 
                         
                         ⁢ 
                         
                           λ 
                           ′ 
                         
                       
                     
                   
                   
                     
                       
                         
                           A 
                           q 
                           t 
                         
                         ⁢ 
                         
                           λ 
                           ′ 
                         
                       
                     
                   
                 
                 ) 
               
               + 
               
                 ( 
                 
                   
                     
                       
                         C 
                         p 
                       
                     
                   
                   
                     
                       
                         C 
                         q 
                       
                     
                   
                 
                 ) 
               
               + 
               
                 ( 
                 
                   
                     
                       
                         γ 
                         p 
                       
                     
                   
                   
                     
                       0 
                     
                   
                 
                 ) 
               
             
           
         
       
       
         
           
             
               
                 W 
                 q 
               
               = 
               
                 - 
                 
                   LinSol 
                   ⁡ 
                   
                     ( 
                     
                       
                         s 
                         qq 
                       
                       , 
                       
                         
                           
                             s 
                             pq 
                             t 
                           
                           ⁢ 
                           
                             M 
                             p 
                           
                         
                         + 
                         
                           
                             A 
                             q 
                             t 
                           
                           ⁢ 
                           
                             λ 
                             ′ 
                           
                         
                         + 
                         
                           C 
                           q 
                         
                       
                     
                     ) 
                   
                 
               
             
             ; 
           
         
       
       
         
           
             
               
                 γ 
                 p 
               
               = 
               
                 
                   
                     - 
                     
                       s 
                       pp 
                     
                   
                   ⁢ 
                   
                     M 
                     p 
                   
                 
                 - 
                 
                   
                     A 
                     p 
                     t 
                   
                   ⁢ 
                   
                     λ 
                     ′ 
                   
                 
                 - 
                 
                   C 
                   p 
                 
                 + 
                 
                   
                     s 
                     pq 
                   
                   ⁢ 
                   
                     LinSol 
                     ⁡ 
                     
                       ( 
                       
                         
                           
                             
                               
                                 s 
                                 qq 
                               
                               , 
                               
                                 
                                   
                                     s 
                                     pq 
                                     t 
                                   
                                   ⁢ 
                                   
                                     M 
                                     p 
                                   
                                 
                                 + 
                               
                             
                           
                         
                         
                           
                             
                               
                                 
                                   A 
                                   q 
                                   t 
                                 
                                 ⁢ 
                                 
                                   λ 
                                   ′ 
                                 
                               
                               + 
                               
                                 C 
                                 q 
                               
                             
                           
                         
                       
                       ) 
                     
                   
                 
               
             
             ; 
           
         
       
       
         
           
             
               
                 ( 
                 2 
                 ) 
               
               ⇔ 
               
                 
                   
                     ( 
                     
                       
                         A 
                         p 
                       
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       
                         A 
                         q 
                       
                     
                     ) 
                   
                   ⁢ 
                   
                     ( 
                     
                       
                         
                           
                             M 
                             p 
                           
                         
                       
                       
                         
                           
                             W 
                             q 
                           
                         
                       
                     
                     ) 
                   
                 
                 - 
                 B 
               
             
             = 
             0 
           
         
       
     
     Note that A p  is an s×p matrix and A q  is an s×q matrix. 
     
       
         
           
             
               
                 
                   
                     ( 
                     2 
                     ) 
                   
                   ⇔ 
                   
                     
                       A 
                       q 
                     
                     ⁢ 
                     
                       W 
                       q 
                     
                   
                 
                 = 
                 
                   B 
                   - 
                   
                     
                       A 
                       p 
                     
                     ⁢ 
                     
                       M 
                       p 
                     
                   
                 
               
               ; 
             
             ⁢ 
             
                 
             
           
         
       
       
         
           
             
               
                 
                   ( 
                   1 
                   ) 
                 
                 + 
                 
                   ( 
                   2 
                   ) 
                 
               
               ⇒ 
               
                 
                   - 
                   
                     A 
                     q 
                   
                 
                 ⁢ 
                 
                   LinSol 
                   ⁡ 
                   
                     ( 
                     
                       
                         s 
                         qq 
                       
                       , 
                       
                         
                           
                             s 
                             pq 
                             t 
                           
                           ⁢ 
                           
                             M 
                             p 
                           
                         
                         + 
                         
                           
                             A 
                             q 
                             t 
                           
                           ⁢ 
                           
                             λ 
                             ′ 
                           
                         
                         + 
                         
                           C 
                           q 
                         
                       
                     
                     ) 
                   
                 
               
             
             = 
             
               B 
               - 
               
                 
                   A 
                   p 
                 
                 ⁢ 
                 
                   M 
                   p 
                 
               
             
           
         
       
       
         
           
             
               
                 A 
                 q 
               
               ⁢ 
               
                 LinSol 
                 ⁡ 
                 
                   ( 
                   
                     
                       s 
                       qq 
                     
                     , 
                     
                       A 
                       q 
                       t 
                     
                   
                   ) 
                 
               
               ⁢ 
               
                 λ 
                 ′ 
               
             
             = 
             
               
                 
                   A 
                   p 
                 
                 ⁢ 
                 
                   M 
                   p 
                 
               
               - 
               B 
               - 
               
                 
                   A 
                   q 
                 
                 ⁢ 
                 
                   LinSol 
                   ⁡ 
                   
                     ( 
                     
                       
                         s 
                         qq 
                       
                       , 
                       
                         
                           
                             s 
                             pq 
                             t 
                           
                           ⁢ 
                           
                             M 
                             p 
                           
                         
                         + 
                         
                           C 
                           q 
                         
                       
                     
                     ) 
                   
                 
               
             
           
         
       
       
         
           
             
               λ 
               ′ 
             
             = 
             
               LinSol 
               ⁡ 
               
                 ( 
                 
                   
                     
                       A 
                       q 
                     
                     ⁢ 
                     
                       LinSol 
                       ⁡ 
                       
                         ( 
                         
                           
                             s 
                             qq 
                           
                           , 
                           
                             A 
                             q 
                             t 
                           
                         
                         ) 
                       
                     
                   
                   , 
                   
                     
                       
                         A 
                         p 
                       
                       ⁢ 
                       
                         M 
                         p 
                       
                     
                     - 
                     B 
                     - 
                     
                       
                         A 
                         q 
                       
                       ⁢ 
                       
                         LinSol 
                         ⁡ 
                         
                           ( 
                           
                             
                               s 
                               qq 
                             
                             , 
                             
                               
                                 
                                   s 
                                   pq 
                                   t 
                                 
                                 ⁢ 
                                 
                                   M 
                                   p 
                                 
                               
                               + 
                               
                                 C 
                                 q 
                               
                             
                           
                           ) 
                         
                       
                     
                   
                 
                 ) 
               
             
           
         
       
     
     We recall 
     
       
         
           
             
               
                 
                   
                     
                       W 
                       q 
                     
                     = 
                       
                     ⁢ 
                     
                       - 
                       
                         LinSol 
                         ⁡ 
                         
                           ( 
                           
                             
                               s 
                               qq 
                             
                             , 
                             
                               
                                 
                                   s 
                                   pq 
                                   t 
                                 
                                 ⁢ 
                                 
                                   M 
                                   p 
                                 
                               
                               + 
                               
                                 
                                   A 
                                   q 
                                   t 
                                 
                                 ⁢ 
                                 
                                   λ 
                                   ′ 
                                 
                               
                               + 
                               
                                 C 
                                 q 
                               
                             
                           
                           ) 
                         
                       
                     
                   
                   ; 
                 
               
             
             
               
                 
                   
                     
                       γ 
                       p 
                     
                     = 
                       
                     ⁢ 
                     
                       
                         
                           - 
                           
                             s 
                             pp 
                           
                         
                         ⁢ 
                         
                           M 
                           p 
                         
                       
                       - 
                       
                         
                           A 
                           p 
                           t 
                         
                         ⁢ 
                         
                           λ 
                           ′ 
                         
                       
                       - 
                       
                         C 
                         p 
                       
                       + 
                       
                         
                           s 
                           pq 
                         
                         ⁢ 
                         
                           LinSol 
                           ⁡ 
                           
                             ( 
                             
                               
                                 s 
                                 qq 
                               
                               , 
                               
                                 
                                   
                                     s 
                                     pq 
                                     t 
                                   
                                   ⁢ 
                                   
                                     M 
                                     p 
                                   
                                 
                                 + 
                                 
                                   
                                     A 
                                     q 
                                     t 
                                   
                                   ⁢ 
                                   
                                     λ 
                                     ′ 
                                   
                                 
                                 + 
                                 
                                   C 
                                   q 
                                 
                               
                             
                             ) 
                           
                         
                       
                     
                   
                   ; 
                 
               
             
           
         
       
     
     This provides the general expression of the KKT local minima. In order for them to be admissible, they have to verify the admissibility conditions outlined in  FIG. 3 . 
     Appendix 2 shows how the algorithm implementing the structure outlined in  FIG. 1  disposes of the local extrema as shown in  FIG. 4 . and implements the applicable strategies to effect computational gains as described in  FIG. 5 . The computer code in Appendix 2 is written in Mathematica, owned and copyrighted by Wolfram research. For clarity purposes, the matrix Σ is assumed to be symmetric positive definite. This algorithm also counts the number of cases of local extrema actually computed to measure the effectiveness of the computational strategies used. It empirically appears that the number of local extrema actually computed, which a priory grows exponentially with m, becomes here reduce to polynomial of order approximating 3, supporting our claims of computational gains outline in  FIG. 6 . 
     Case 2: A Maximization Problem with Quadratically Constrained Equations and Inequalities 
     This case illustrate that the constraints may be linear or quadratic. It is typically classified as a conic optimization problem. It may be used to solve a broad number of assets allocations problems in finance. 
     Problem 
     This problem can be generally stated analytically as finding the solution to the constrained quadratic optimization problem: 
     MaxW t  R subject to constraint s 
             {                   AW   -   B     =   0     ;           W   t     ⁢   Σ   ⁢           ⁢   W     -     σ   2       =   0                        W   -         M   _     +     M   _       2            ≤         M   _     -     M   _       2             ⁢     
     ⁢   with   ⁢           ⁢     M   _       ,   W   ,     M   _     ,     R   ⁢     ∈   m       ,       M   _     ≤   W   ≤     M   _       ,     σ   ⁢     ∈   +       ,       A   ⁢     ∈   s     ⁢     ×         m         ;     
     ⁢       Rank   ⁡     (   A   )       =     s   ≤   m         ,     B   ⁢     ∈   s               
Solution:
 
     The KKT Equations are: 
     
       
         
           
             
               K 
               = 
               
                 
                   
                     
                       W 
                       t 
                     
                     ⁢ 
                     R 
                   
                   + 
                   
                     
                       λ 
                       
                         ′ 
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         t 
                       
                     
                     ⁡ 
                     
                       ( 
                       
                         AW 
                         - 
                         B 
                       
                       ) 
                     
                   
                   + 
                   
                     
                       λ 
                       2 
                     
                     ⁢ 
                     
                       ( 
                       
                         
                           
                             W 
                             t 
                           
                           ⁢ 
                           Σ 
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           W 
                         
                         - 
                         
                           σ 
                           2 
                         
                       
                       ) 
                     
                   
                   - 
                   
                     
                       γ 
                       - 
                     
                     ⁡ 
                     
                       ( 
                       
                         W 
                         - 
                         
                           M 
                           _ 
                         
                       
                       ) 
                     
                   
                   + 
                   
                     
                       
                         γ 
                         + 
                       
                       ⁡ 
                       
                         ( 
                         
                           W 
                           - 
                           
                             M 
                             _ 
                           
                         
                         ) 
                       
                     
                     ⁢ 
                     
                       λ 
                       ′ 
                     
                   
                 
                 ⁢ 
                 
                   ∈ 
                   s 
                 
               
             
             , 
             
               
 
             
             ⁢ 
             
                 
             
             ⁢ 
             
               λ 
               ∈ 
             
             , 
             
               
                 
                   M 
                   _ 
                 
                 ≤ 
                 W 
                 ≤ 
                 
                   M 
                   _ 
                 
               
               ⁢ 
               
                 ∈ 
                 m 
               
             
             , 
             
               
                 A 
                 ⁢ 
                 
                   ∈ 
                   s 
                 
                 ⁢ 
                 
                   × 
                   m 
                 
               
               ; 
             
           
         
       
       
         
           
             
                 
             
             ⁢ 
             
               
                 
                   Rank 
                   ⁡ 
                   
                     ( 
                     A 
                     ) 
                   
                 
                 = 
                 
                   s 
                   ≤ 
                   m 
                 
               
               , 
               
                 B 
                 ⁢ 
                 
                   ∈ 
                   s 
                 
               
             
           
         
       
     
     The so-called slacking parameters γ + ,γ −  must verify γ + ,γ − ε +   m , 
     We note γ + −γ − ; We have: 
               (   I   )     ⁢     {             ∇   K     =         R   t     +       λ     ′   ⁢           ⁢   t       ⁢   A     +     λ   ⁢           ⁢     W   t     ⁢   Σ     +     γ   t       =   0                     ⁢     (   1   )                   AW   -   B     =   0                   ⁢     (   2   )                       W   t     ⁢   Σ   ⁢           ⁢   W     -     σ   2       =   0                   ⁢     (   3   )                       γ   +     ⁡     (     W   -     M   _       )       =   0     ,         γ   -     ⁡     (     W   -     M   _       )       =   0                     ⁢     (   4   )                     
(i) Let&#39;s first deal with constraints (I)
 
     We suppose there are p active constraints, 0≦p≦m, q=m−p. 
     We note according to a block matrix decomposition 
               Σ   =     (           s   pp           s   pq               s   pq   t           s   qq           )       ;                 ɛ   =       (           ɛ   1                     0                       ⋱                       0                     ɛ     m   t             )     =     (           ɛ   pp           0   pq               0   qp           0   qq           )         ;                   ɛ   i     ∈     {       -   1     ,   0   ,   1     }       ,         
where s pp , s pq , s qq , ε pp  are block matrices with the indices indicating the number of rows and columns respectively.
 
     We also note 
               γ   =     (           γ   p             0         )       ;     R   =     (           R   p               R   q           )       ;                 W   =     (               1   2     ⁢     (         M   _     p     +       M   _     p       )       +         ɛ   pp     2     ⁢     (         M   _     p     +       M   _     p       )               M   p               W   q                       )       ;         
Expression of W q , γ p 
 
                         (     ∇     K   t       )     t     =       R   +       A   t     ⁢     λ   ′       +     λ   ⁢           ⁢   Σ   ⁢           ⁢   W     +   γ     =       0   ⁢     
     -     λ   ⁢           ⁢   Σ   ⁢           ⁢   W       =       R   +       A   t     ⁢     λ   ′       +   γ   ⁢     
     -       λ   ⁡     (           s   pp           s   pq               s   pq   t           s   qq           )       ⁢     (           M   p               W   q           )         =       (           R   p               R   q           )     +     (             A   p   t     ⁢     λ   ′                   A   q   t     ⁢     λ   ′             )     +     (           γ   p             0         )               ⁢     
     ⁢     {             γ   p     =         λ   ⁡     (         s   pq     ⁢     s   qq     -   1       ⁢     s   pq   t       -     s   pp       )       ⁢     M   p       +     (         s   pq     ⁢       s   qq     -   1       ⁡     (       R   q     +       A   q   t     ⁢     λ   ′         )         -     (       R   p     +       A   p   t     ⁢     λ   ′         )       )                     W   q     =     -       s   qq     -   1       ⁡     (         s   pq   t     ⁢     M   p       +       1   λ     ⁢     (       R   q     +       A   q   t     ⁢     λ   ′         )         )                           (   1   )               
Elimination of λ′
 
(2)             A   q   W   q   =B−A   p   M   p  

     Note that A p  is an s×p matrix and A q  is an s×q matrix. 
                     ⁢           (   1   )     +     (   2   )       ⇒       -     A   q       ⁢       s   qq     -   1       ⁡     (         s   pq   t     ⁢     M   p       +       1   λ     ⁢     (       R   q     +       A   q   t     ⁢     λ   ′         )         )           =     B   -       A   p     ⁢     M   p                               ⁢             (       A   p     -       A   q     ⁢     s   qq     -   1       ⁢     s   pq   t         )     ⁢     M   p       -   B     =         1   λ     ⁢     A   q     ⁢     s   qq     -   1       ⁢     R   q       +       1   λ     ⁢     A   q     ⁢     s   qq     -   1       ⁢     A   q   t     ⁢     λ   ′           ;       χ   s     ⁢     A   q     ⁢     s   qq     -   1       ⁢     A   q   t       ;                         ⁢         λ   ′     =       χ   s     -   1       ⁡     (       λ   ⁡     (         (       A   p     -       A   q     ⁢     s   qq     -   1       ⁢     s   pq   t         )     ⁢     M   p       -   B     )       -       A   q     ⁢     s   qq     -   1       ⁢     R   q         )         ;                       1   λ     ⁢     (       R   q     +       A   q   t     ⁢     λ   ′         )       =       1   λ     ⁢     (       R   q     +       A   q   t     ⁢       χ   s     -   1       ⁡     (       λ   ⁡     (         (       A   p     -       A   q     ⁢     s   qq     -   1       ⁢     s   pq   t         )     ⁢     M   p       -   B     )       -       A   q     ⁢     s   qq     -   1       ⁢     R   q         )           )         ;                   1   λ     ⁢     (       R   q     +       A   q   t     ⁢     λ   ′         )       =           ⁢         A   q   t     ⁢           ⁢       χ   s     -   1       (         (       A   p     -       A   q     ⁢     s   qq     -   1       ⁢     s   pq   t         )     ⁢     M   p       -   B     ⁢           )       +                 ⁢         1   λ     ⁢           ⁢     (       I   q     -           ⁢       A   q   t     ⁢     χ   s     -   1       ⁢     A   q     ⁢     s   qq     -   1           )     ⁢           ⁢     R   q       ;     
     ⁢       W   q     =         -       s   qq     -   1       ⁡     (         s   pq   t     ⁢     M   p       +       A   q   t     ⁢       χ   s     -   1       ⁡     (         (       A   p     -       A   q     ⁢     s   qq     -   1       ⁢     s   pq   t         )     ⁢     M   p       -   B     )         +       1   λ     ⁢     (       I   q     -       A   q   t     ⁢     χ   s     -   1       ⁢     A   q     ⁢     s   qq     -   1           )     ⁢     R   q         )         ⁢     
     ⁢           ⁢     γ   p       =           λ   ⁡     (         s   pq     ⁢     s   qq     -   1       ⁢     s   pq   t       -     s   pp       )       ⁢     M   p       +       (         s   pq     ⁢       s   qq     -   1       ⁡     (       R   q     +       A   q   t     ⁢     λ   ′         )         -     (       R   p     +       A   p   t     ⁢     λ   ′         )       )     ⁢     
     ⁢     γ   p         =       λ   ⁡     (         (         s   pq     ⁢     s   qq     -   1       ⁢     s   pq   t       -     s   pp     +       (         s   pq     ⁢     s   qq     -   1       ⁢     A   q   t       -     A   p   t       )     ⁢       χ   s     -   1       ⁡     (       A   p     -       A   q     ⁢     s   qq     -   1       ⁢     s   pq   t         )           )     ⁢     M   p       -       (         s   pq     ⁢     s   qq     -   1       ⁢     A   q   t       -     A   p   t       )     ⁢     χ   s     -   1       ⁢   B       )       +     (         s   pq     ⁢     s   qq     -   1       ⁢     R   q       -     R   p       )     -       (         s   pq     ⁢     s   qq     -   1       ⁢     A   q   t       -     A   p   t       )     ⁢     χ   s     -   1       ⁢     A   q     ⁢     s   qq     -   1       ⁢     R   q                           
Elimination of λ
 
     
       
         
           
             
               
                 
                   
                       
                   
                   ⁢ 
                   
                     
                       
                         
                           W 
                           q 
                         
                         = 
                         
                           
                             
                               1 
                               λ 
                             
                             ⁢ 
                             
                               a 
                               q 
                             
                           
                           - 
                           
                             b 
                             q 
                           
                         
                       
                       ; 
                       
                         W 
                         = 
                         
                           
                             ( 
                             
                               
                                 
                                   
                                     M 
                                     p 
                                   
                                 
                               
                               
                                 
                                   
                                     W 
                                     q 
                                   
                                 
                               
                             
                             ) 
                           
                           = 
                           
                             
                               
                                 1 
                                 λ 
                               
                               ⁢ 
                               
                                 ( 
                                 
                                   
                                     
                                       0 
                                     
                                   
                                   
                                     
                                       
                                         a 
                                         q 
                                       
                                     
                                   
                                 
                                 ) 
                               
                             
                             + 
                             
                               ( 
                               
                                 
                                   
                                     
                                       M 
                                       p 
                                     
                                   
                                 
                                 
                                   
                                     
                                       - 
                                       
                                         b 
                                         q 
                                       
                                     
                                   
                                 
                               
                               ) 
                             
                           
                         
                       
                       ; 
                     
                     ⁢ 
                     
                       
 
                     
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     
                       
                         a 
                         ⁡ 
                         
                           ( 
                           
                             
                               
                                 0 
                               
                             
                             
                               
                                 
                                   a 
                                   q 
                                 
                               
                             
                           
                           ) 
                         
                       
                       ; 
                       
                         b 
                         ⁡ 
                         
                           ( 
                           
                             
                               
                                 
                                   M 
                                   p 
                                 
                               
                             
                             
                               
                                 
                                   - 
                                   
                                     b 
                                     q 
                                   
                                 
                               
                             
                           
                           ) 
                         
                       
                       ; 
                       
                         W 
                         = 
                         
                           
                             
                               1 
                               λ 
                             
                             ⁢ 
                             a 
                           
                           - 
                           b 
                         
                       
                       ; 
                     
                     ⁢ 
                     
                       
 
                     
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     
                       
                         a 
                         = 
                         
                           ( 
                           
                             
                               
                                 0 
                               
                             
                             
                               
                                 
                                   
                                     - 
                                     
                                       
                                         s 
                                         qq 
                                         
                                           - 
                                           1 
                                         
                                       
                                       ⁡ 
                                       
                                         ( 
                                         
                                           
                                             I 
                                             q 
                                           
                                           - 
                                           
                                             
                                               A 
                                               q 
                                               t 
                                             
                                             ⁢ 
                                             
                                               χ 
                                               s 
                                               
                                                 - 
                                                 1 
                                               
                                             
                                             ⁢ 
                                             
                                               A 
                                               q 
                                             
                                             ⁢ 
                                             
                                               s 
                                               qq 
                                               
                                                 - 
                                                 1 
                                               
                                             
                                           
                                         
                                         ) 
                                       
                                     
                                   
                                   ⁢ 
                                   
                                     R 
                                     q 
                                   
                                 
                               
                             
                           
                           ) 
                         
                       
                       ; 
                     
                     ⁢ 
                     
                       
 
                     
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     
                       
                         b 
                         = 
                         
                           
                             
                               ( 
                               
                                 
                                   
                                     
                                       - 
                                       
                                         I 
                                         p 
                                       
                                     
                                   
                                 
                                 
                                   
                                     
                                       
                                         s 
                                         qq 
                                         
                                           - 
                                           1 
                                         
                                       
                                       ⁡ 
                                       
                                         ( 
                                         
                                           
                                             s 
                                             pq 
                                             t 
                                           
                                           + 
                                           
                                             
                                               A 
                                               q 
                                               t 
                                             
                                             ⁢ 
                                             
                                               
                                                 χ 
                                                 s 
                                                 
                                                   - 
                                                   1 
                                                 
                                               
                                               ⁡ 
                                               
                                                 ( 
                                                 
                                                   
                                                     A 
                                                     p 
                                                   
                                                   - 
                                                   
                                                     
                                                       A 
                                                       q 
                                                     
                                                     ⁢ 
                                                     
                                                       s 
                                                       qq 
                                                       
                                                         - 
                                                         1 
                                                       
                                                     
                                                     ⁢ 
                                                     
                                                       s 
                                                       pq 
                                                       t 
                                                     
                                                   
                                                 
                                                 ) 
                                               
                                             
                                           
                                         
                                         ) 
                                       
                                     
                                   
                                 
                               
                               ) 
                             
                             ⁢ 
                             
                               M 
                               p 
                             
                           
                           - 
                           
                             ( 
                             
                               
                                 
                                   
                                     0 
                                     p 
                                   
                                 
                               
                               
                                 
                                   
                                     
                                       s 
                                       qq 
                                       
                                         - 
                                         1 
                                       
                                     
                                     ⁢ 
                                     
                                       A 
                                       q 
                                       t 
                                     
                                     ⁢ 
                                     
                                       χ 
                                       s 
                                       
                                         - 
                                         1 
                                       
                                     
                                     ⁢ 
                                     B 
                                   
                                 
                               
                             
                             ) 
                           
                         
                       
                       ; 
                     
                     ⁢ 
                     
                       
 
                     
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     
                       
                         
                           W 
                           t 
                         
                         ⁢ 
                         Σ 
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         W 
                       
                       = 
                       
                         
                           
                             
                               ( 
                               
                                 
                                   
                                     1 
                                     λ 
                                   
                                   ⁢ 
                                   a 
                                 
                                 - 
                                 b 
                               
                               ) 
                             
                             t 
                           
                           ⁢ 
                           
                             Σ 
                             ⁡ 
                             
                               ( 
                               
                                 
                                   
                                     1 
                                     λ 
                                   
                                   ⁢ 
                                   a 
                                 
                                 - 
                                 b 
                               
                               ) 
                             
                           
                         
                         = 
                         
                           
                             
                               1 
                               
                                 λ 
                                 2 
                               
                             
                             ⁢ 
                             
                               a 
                               t 
                             
                             ⁢ 
                             Σ 
                             ⁢ 
                             
                                 
                             
                             ⁢ 
                             a 
                           
                           - 
                           
                             2 
                             ⁢ 
                             
                                 
                             
                             ⁢ 
                             
                               a 
                               t 
                             
                             ⁢ 
                             Σ 
                             ⁢ 
                             
                                 
                             
                             ⁢ 
                             b 
                             ⁢ 
                             
                               1 
                               λ 
                             
                           
                           + 
                           
                             
                               b 
                               t 
                             
                             ⁢ 
                             Σ 
                             ⁢ 
                             
                                 
                             
                             ⁢ 
                             b 
                           
                         
                       
                     
                     ⁢ 
                     
                       
 
                     
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     
                       
                         
                           
                             W 
                             t 
                           
                           ⁢ 
                           Σ 
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           W 
                         
                         - 
                         
                           σ 
                           2 
                         
                       
                       = 
                       0 
                     
                     ⁢ 
                     
                       
 
                     
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     
                       
                         
                           
                             
                               1 
                               
                                 λ 
                                 2 
                               
                             
                             ⁢ 
                             
                               a 
                               t 
                             
                             ⁢ 
                             Σ 
                             ⁢ 
                             
                                 
                             
                             ⁢ 
                             a 
                           
                           - 
                           
                             2 
                             ⁢ 
                             
                               a 
                               t 
                             
                             ⁢ 
                             Σ 
                             ⁢ 
                             
                                 
                             
                             ⁢ 
                             b 
                             ⁢ 
                             
                               1 
                               λ 
                             
                           
                           + 
                           
                             
                               b 
                               t 
                             
                             ⁢ 
                             Σ 
                             ⁢ 
                             
                                 
                             
                             ⁢ 
                             b 
                           
                           - 
                           
                             σ 
                             2 
                           
                         
                         = 
                         0 
                       
                       ; 
                     
                     ⁢ 
                     
                       
 
                     
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     
                       
                         
                           If 
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           
                             σ 
                             2 
                           
                         
                         ≥ 
                         
                           
                             
                               
                                 ( 
                                 
                                   
                                     a 
                                     t 
                                   
                                   ⁢ 
                                   Σ 
                                   ⁢ 
                                   
                                       
                                   
                                   ⁢ 
                                   a 
                                 
                                 ) 
                               
                               ⁢ 
                               
                                 ( 
                                 
                                   
                                     b 
                                     t 
                                   
                                   ⁢ 
                                   Σ 
                                   ⁢ 
                                   
                                       
                                   
                                   ⁢ 
                                   b 
                                 
                                 ) 
                               
                             
                             - 
                             
                               
                                 ( 
                                 
                                   
                                     a 
                                     t 
                                   
                                   ⁢ 
                                   Σ 
                                   ⁢ 
                                   
                                       
                                   
                                   ⁢ 
                                   b 
                                 
                                 ) 
                               
                               2 
                             
                           
                           
                             
                               a 
                               t 
                             
                             ⁢ 
                             Σ 
                             ⁢ 
                             
                                 
                             
                             ⁢ 
                             a 
                           
                         
                       
                       , 
                       
                         
 
                       
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       
                         
                           1 
                           
                             λ 
                             ± 
                           
                         
                         = 
                         
                           
                             
                               
                                 a 
                                 t 
                               
                               ⁢ 
                               Σ 
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               b 
                             
                             
                               
                                 a 
                                 t 
                               
                               ⁢ 
                               Σ 
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               a 
                             
                           
                           ± 
                           
                             
                               
                                 1 
                                 
                                   
                                     a 
                                     t 
                                   
                                   ⁢ 
                                   Σ 
                                   ⁢ 
                                   
                                       
                                   
                                   ⁢ 
                                   a 
                                 
                               
                               ⁢ 
                               
                                 ( 
                                 
                                   
                                     σ 
                                     2 
                                   
                                   - 
                                   
                                     
                                       
                                         
                                           ( 
                                           
                                             
                                               a 
                                               t 
                                             
                                             ⁢ 
                                             Σ 
                                             ⁢ 
                                             
                                                 
                                             
                                             ⁢ 
                                             a 
                                           
                                           ) 
                                         
                                         ⁢ 
                                         
                                           ( 
                                           
                                             
                                               b 
                                               t 
                                             
                                             ⁢ 
                                             Σ 
                                             ⁢ 
                                             
                                                 
                                             
                                             ⁢ 
                                             b 
                                           
                                           ) 
                                         
                                       
                                       - 
                                       
                                         
                                           ( 
                                           
                                             
                                               a 
                                               t 
                                             
                                             ⁢ 
                                             Σ 
                                             ⁢ 
                                             
                                                 
                                             
                                             ⁢ 
                                             b 
                                           
                                           ) 
                                         
                                         2 
                                       
                                     
                                     
                                       
                                         a 
                                         t 
                                       
                                       ⁢ 
                                       Σ 
                                       ⁢ 
                                       
                                           
                                       
                                       ⁢ 
                                       a 
                                     
                                   
                                 
                                 ) 
                               
                             
                           
                         
                       
                     
                     ⁢ 
                     
                       
 
                     
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     
                       
                         W 
                         ± 
                       
                       = 
                       
                         
                           
                             
                               1 
                               
                                 λ 
                                 ± 
                               
                             
                             ⁢ 
                             a 
                           
                           - 
                           b 
                         
                         = 
                         
                             
                           
                             
                               ( 
                               
                                 
                                   
                                     
                                       
                                         a 
                                         t 
                                       
                                       ⁢ 
                                       Σ 
                                       ⁢ 
                                       
                                           
                                       
                                       ⁢ 
                                       b 
                                     
                                     
                                       
                                         a 
                                         t 
                                       
                                       ⁢ 
                                       Σ 
                                       ⁢ 
                                       
                                           
                                       
                                       ⁢ 
                                       a 
                                     
                                   
                                   ⁢ 
                                   a 
                                 
                                 - 
                                 b 
                               
                               ) 
                             
                             ⁢ 
                             
                                 
                               
                                 ± 
                                 
                                     
                                   
                                     
                                       
                                         
                                           
                                             1 
                                             
                                               
                                                 a 
                                                 t 
                                               
                                               ⁢ 
                                               Σ 
                                               ⁢ 
                                               
                                                   
                                               
                                               ⁢ 
                                               a 
                                             
                                           
                                           ⁢ 
                                           
                                             ( 
                                             
                                               
                                                 σ 
                                                 2 
                                               
                                               - 
                                               
                                                 
                                                   
                                                     
                                                       ( 
                                                       
                                                         
                                                           a 
                                                           t 
                                                         
                                                         ⁢ 
                                                         Σ 
                                                         ⁢ 
                                                         
                                                             
                                                         
                                                         ⁢ 
                                                         a 
                                                       
                                                       ) 
                                                     
                                                     ⁢ 
                                                     
                                                       ( 
                                                       
                                                         
                                                           b 
                                                           t 
                                                         
                                                         ⁢ 
                                                         Σ 
                                                         ⁢ 
                                                         
                                                             
                                                         
                                                         ⁢ 
                                                         b 
                                                       
                                                       ) 
                                                     
                                                   
                                                   - 
                                                   
                                                     
                                                       ( 
                                                       
                                                         
                                                           a 
                                                           t 
                                                         
                                                         ⁢ 
                                                         Σ 
                                                         ⁢ 
                                                         
                                                             
                                                         
                                                         ⁢ 
                                                         b 
                                                       
                                                       ) 
                                                     
                                                     2 
                                                   
                                                 
                                                 
                                                   
                                                     a 
                                                     t 
                                                   
                                                   ⁢ 
                                                   Σ 
                                                   ⁢ 
                                                   
                                                       
                                                   
                                                   ⁢ 
                                                   a 
                                                 
                                               
                                             
                                             ) 
                                           
                                         
                                       
                                       ⁢ 
                                       a 
                                       ⁢ 
                                       
                                         
 
                                       
                                       ⁢ 
                                       
                                           
                                       
                                       ⁢ 
                                       
                                         
                                           R 
                                           t 
                                         
                                         ⁡ 
                                         
                                           ( 
                                           
                                             
                                               W 
                                               - 
                                             
                                             - 
                                             
                                               W 
                                               + 
                                             
                                           
                                           ) 
                                         
                                       
                                     
                                     = 
                                     
                                       
                                         - 
                                         2 
                                       
                                       ⁢ 
                                       
                                         
                                           
                                             1 
                                             
                                               
                                                 a 
                                                 t 
                                               
                                               ⁢ 
                                               Σ 
                                               ⁢ 
                                               
                                                   
                                               
                                               ⁢ 
                                               a 
                                             
                                           
                                           ⁢ 
                                           
                                             ( 
                                             
                                               
                                                 σ 
                                                 2 
                                               
                                               - 
                                               
                                                 
                                                   
                                                     
                                                       ( 
                                                       
                                                         
                                                           a 
                                                           t 
                                                         
                                                         ⁢ 
                                                         Σ 
                                                         ⁢ 
                                                         
                                                             
                                                         
                                                         ⁢ 
                                                         a 
                                                       
                                                       ) 
                                                     
                                                     ⁢ 
                                                     
                                                       ( 
                                                       
                                                         
                                                           b 
                                                           t 
                                                         
                                                         ⁢ 
                                                         Σ 
                                                         ⁢ 
                                                         
                                                             
                                                         
                                                         ⁢ 
                                                         b 
                                                       
                                                       ) 
                                                     
                                                   
                                                   - 
                                                   
                                                     
                                                       ( 
                                                       
                                                         
                                                           a 
                                                           t 
                                                         
                                                         ⁢ 
                                                         Σ 
                                                         ⁢ 
                                                         
                                                             
                                                         
                                                         ⁢ 
                                                         b 
                                                       
                                                       ) 
                                                     
                                                     2 
                                                   
                                                 
                                                 
                                                   
                                                     a 
                                                     t 
                                                   
                                                   ⁢ 
                                                   Σ 
                                                   ⁢ 
                                                   
                                                       
                                                   
                                                   ⁢ 
                                                   a 
                                                 
                                               
                                             
                                             ) 
                                           
                                         
                                       
                                       ⁢ 
                                       
                                         R 
                                         t 
                                       
                                       ⁢ 
                                       a 
                                     
                                   
                                 
                               
                             
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   3 
                   ) 
                 
               
             
           
         
       
     
     Note that s qq   −1 (I q −A q   t χ s   −1 A q s qq   −1 ) is a symmetric positive semi-definite matrix. 
     
       
         
           
             
                 
             
             ⁢ 
             
               
                 
                   R 
                   t 
                 
                 ⁡ 
                 
                   ( 
                   
                     
                       W 
                       - 
                     
                     - 
                     
                       W 
                       + 
                     
                   
                   ) 
                 
               
               = 
               
                 
                   - 
                   2 
                 
                 ⁢ 
                 
                   
                     
                       1 
                       
                         
                           a 
                           t 
                         
                         ⁢ 
                         Σ 
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         a 
                       
                     
                     ⁢ 
                     
                       ( 
                       
                         
                           σ 
                           2 
                         
                         - 
                         
                           
                             
                               
                                 ( 
                                 
                                   
                                     a 
                                     t 
                                   
                                   ⁢ 
                                   Σ 
                                   ⁢ 
                                   
                                       
                                   
                                   ⁢ 
                                   a 
                                 
                                 ) 
                               
                               ⁢ 
                               
                                 ( 
                                 
                                   
                                     b 
                                     t 
                                   
                                   ⁢ 
                                   Σ 
                                   ⁢ 
                                   
                                       
                                   
                                   ⁢ 
                                   b 
                                 
                                 ) 
                               
                             
                             - 
                             
                               
                                 ( 
                                 
                                   
                                     a 
                                     t 
                                   
                                   ⁢ 
                                   Σ 
                                   ⁢ 
                                   
                                       
                                   
                                   ⁢ 
                                   b 
                                 
                                 ) 
                               
                               2 
                             
                           
                           
                             
                               a 
                               t 
                             
                             ⁢ 
                             Σ 
                             ⁢ 
                             
                                 
                             
                             ⁢ 
                             a 
                           
                         
                       
                       ) 
                     
                   
                 
                 ⁢ 
                 
                   R 
                   t 
                 
                 ⁢ 
                 a 
               
             
           
         
       
       
         
           
             
                 
             
             ⁢ 
             
               Hence 
               ⁢ 
               
                 
 
               
               = 
               
                 
                   2 
                   ⁢ 
                   
                     
                       
                         1 
                         
                           
                             a 
                             t 
                           
                           ⁢ 
                           Σ 
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           a 
                         
                       
                       ⁢ 
                       
                         ( 
                         
                           
                             σ 
                             2 
                           
                           - 
                           
                             
                               
                                 
                                   
                                     
                                       
                                         ( 
                                         
                                           
                                             a 
                                             t 
                                           
                                           ⁢ 
                                           Σ 
                                           ⁢ 
                                           
                                               
                                           
                                           ⁢ 
                                           a 
                                         
                                         ) 
                                       
                                       ⁢ 
                                       
                                         ( 
                                         
                                           
                                             b 
                                             t 
                                           
                                           ⁢ 
                                           Σ 
                                           ⁢ 
                                           
                                               
                                           
                                           ⁢ 
                                           b 
                                         
                                         ) 
                                       
                                     
                                     - 
                                   
                                 
                               
                               
                                 
                                   
                                     
                                       ( 
                                       
                                         
                                           a 
                                           t 
                                         
                                         ⁢ 
                                         Σ 
                                         ⁢ 
                                         
                                             
                                         
                                         ⁢ 
                                         b 
                                       
                                       ) 
                                     
                                     2 
                                   
                                 
                               
                             
                             
                               
                                 a 
                                 t 
                               
                               ⁢ 
                               Σ 
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               a 
                             
                           
                         
                         ) 
                       
                     
                   
                   ⁢ 
                   
                     
                       ( 
                       
                         R 
                         q 
                       
                       ) 
                     
                     t 
                   
                   ⁢ 
                   
                     ( 
                     
                       
                         s 
                         qq 
                         
                           - 
                           1 
                         
                       
                       ⁡ 
                       
                         ( 
                         
                           
                             I 
                             q 
                           
                           - 
                           
                             
                               A 
                               q 
                               t 
                             
                             ⁢ 
                             
                               χ 
                               s 
                               
                                 - 
                                 1 
                               
                             
                             ⁢ 
                             
                               A 
                               q 
                             
                             ⁢ 
                             
                               s 
                               qq 
                               
                                 - 
                                 1 
                               
                             
                           
                         
                         ) 
                       
                     
                     ) 
                   
                   ⁢ 
                   
                     R 
                     q 
                   
                 
                 ≥ 
                 0 
               
             
           
         
       
     
     Therefore, 
     
       
         
           
             W 
             = 
             
               
                 W 
                 - 
               
               = 
               
                 
                   
                     ( 
                     
                       
                         
                           
                             a 
                             i 
                           
                           ⁢ 
                           Σ 
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           b 
                         
                         
                           
                             a 
                             i 
                           
                           ⁢ 
                           Σ 
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           a 
                         
                       
                       - 
                       
                         
                           
                             1 
                             
                               
                                 a 
                                 t 
                               
                               ⁢ 
                               Σ 
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               a 
                             
                           
                           ⁢ 
                           
                             ( 
                             
                               
                                 σ 
                                 2 
                               
                               - 
                               
                                 
                                   
                                     
                                       ( 
                                       
                                         
                                           a 
                                           t 
                                         
                                         ⁢ 
                                         Σ 
                                         ⁢ 
                                         
                                             
                                         
                                         ⁢ 
                                         a 
                                       
                                       ) 
                                     
                                     ⁢ 
                                     
                                       ( 
                                       
                                         
                                           b 
                                           t 
                                         
                                         ⁢ 
                                         Σ 
                                         ⁢ 
                                         
                                             
                                         
                                         ⁢ 
                                         b 
                                       
                                       ) 
                                     
                                   
                                   - 
                                   
                                     
                                       ( 
                                       
                                         
                                           a 
                                           t 
                                         
                                         ⁢ 
                                         Σ 
                                         ⁢ 
                                         
                                             
                                         
                                         ⁢ 
                                         b 
                                       
                                       ) 
                                     
                                     2 
                                   
                                 
                                 
                                   
                                     a 
                                     t 
                                   
                                   ⁢ 
                                   Σ 
                                   ⁢ 
                                   
                                       
                                   
                                   ⁢ 
                                   a 
                                 
                               
                             
                             ) 
                           
                         
                       
                     
                     ) 
                   
                   ⁢ 
                   a 
                 
                 - 
                 b 
               
             
           
         
       
     
     The sufficient second order condition for a maximum translates as 
                 1   λ     ≤   0     ,         
i.e.:
 
( b   t   Σb−σ   2 ) or  a   t   Σb≦ 0
 
     Once we have the general formula for candidate local optimum here, the treatment to obtain the global maximum mirrors Case 1. This case can be extended in a variety of ways in financial applications. 
     Immediate Extensions 
     a) Maximizing Functions of Expectations and Variance 
     The local maxima in the derivation of Case II are all of the form W(ε)=U(ε)√{square root over (σ 2 −c(ε))}+V(ε). This observation may facilitate the computation of global optima on a wider scope, for instance optimizing targets that are both functions of expected returns and variance; the target may thus be reduced to a simple function of a variance number over the range of values of ε. More formally this observation can be formulated as: 
     Let&#39;s consider a function f defined on x +  so that: 
     
         
         
           
             for any given xε, f(x,y) is a decreasing function of y 
             for any given yε + , f(x,y) is an increasing function of x 
           
         
       
    
     There exists U,Vε m cε + , such that Maximizing f( t W t R t ,  t W t Σ t W t ) 
     subject to 
                   {           AW   =   B                 M   _     ≤   W   ≤     M   _                     
is simplified by taking W(ε)=U(ε)√{square root over (σ(ε) 2 −c(ε))}{square root over (σ(ε) 2 −c(ε))}+V(ε) and σ(ε) 2  a solution to the single variable optimization problem: Maximize f(R t U(ε)√{square root over (σ(ε) 2 −c)}+R t V(ε),σ(ε) 2 ), for σ(ε) 2 ≧c(ε).
 
     Examples of such functions f in finance include Sharpe Ratio functions or Kelly criterion functions. Notice that any choice σ(ε) must be such that W(ε)(σ(ε)) maximize the target over all the other W(ε′)(σ(ε)) ε′ in E. Here the order relationship described in  FIG. 1  that helps eliminate potential local extrema for speed gains is no longer applicable. One may rather seek to analytically study relationships between the W(ε)(σ(ε)) or σ(ε) to make deductions yielding computational gains. 
     Note that a similar treatment can also be made using the expression of local minima in case 1. 
     b) Optimization of Returns within VAR (Value at Risk) Boundaries or Tail Conditional VAR Constraints for Elliptic Distributions 
     
         
         
           
             The result of Case II can also be straightforwardly used to maximize portfolio returns within VAR boundaries via the Chebyschev lemma correspondence between a portfolio VAR and its variance. 
             Recently, there has been growing interest among insurance and investment experts to focus on the use of a tail conditional expectation because it shares properties that are considered desirable and applicable in a variety of situations. In particular, it satisfies requirements of a “coherent” risk measure in the spirit developed by Artzner, et al ii . The existence of explicit formulas for computing tail conditional expectations for elliptical distributions iii —a family of symmetric distributions which includes the more familiar normal and student-t distributions—as functions of expectations and variance means Case II can be used to maximize returns on targets that put boundaries on Tail-Conditional VAR.
 
c) Optimization on Returns Targets with Transaction Costs
 
           
         
       
    
     One can also in Case II include transaction costs by giving differentiated value of expected returns for positive (long) and negative (short) asset allocations. In this case, through the introduction of unit step functions, results marginally change, analytical derivations simply result in one having to associate differentiated returns to the local optima vector W, with positive values coordinates being multiplied by the long expected return and negative value coordinates being multiplied by the short expected return. 
     In financial applications, the method of Case II and its extensions, by their exact derivations can be more reliably used to establish Optimal VAR funds, Optimal Sharpe ratio funds, Optimal Kelly criterion funds and the like. Tail conditional VAR funds may also be used as well as obviously similar strategies. 
     Local Extrema Reduction Computation Methods 
     An easy to overlook yet simple computational reduction method is exploiting invariance by group transformations, for example Group of permutations of indices. This idea can be made more explicit with the following result: 
     If a subset I s  of the set of indices I m ={1, . . . , m} is such that the problem statement is invariant by operations of the group of permutations of S s  of I s , then the dimension of the problem may be reduced by making the variables indexed in I s  identical. 
     Example: Find satisfying x 1 , . . . , x m  satisfying 
             Max   ⁢       ∑   1   m     ⁢     x   i   2             
with |x i |≦1
 
     Here it is easy to see that I s =I m ={1, . . . , m}. The problem reduces to Find x satisfying Max m x 2  with |x|≦1 whose solution is obviously x=±1 leading us back to the solution of to the problem as x 1 , . . . , x m  is in {±1} m  and the maximum value reached is m. 
     While the present invention has been described in connection with preferred embodiments, it is not intended to limit the scope of the invention to the particular form set forth, but, on the contrary, it is intended to cover such alternatives, modifications, equivalents as may be included within the spirit and scope of the invention defined in the appended claims. 
     Appendix 1: The Operator LinSol 
     This operator is used in the resolution of the linear equation when Σ may not be an invertible matrix. Hence if ΣX=B; X=LinSol(Σ, B)+Ker(Σ); The function LinearSolve in Mathematica 6.0 returns a solution of ΣX=B even when Ker(Σ)={0} so that LinSol may simply take that solution and add Ker(Σ) to it. 
     Properties of LinSol 
     
       
         
           
             
               
                 - 
                 
                   LinSol 
                   ⁡ 
                   
                     ( 
                     
                       Σ 
                       , 
                       
                         
                           α 
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           B 
                         
                         + 
                         
                           β 
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           
                             B 
                             ′ 
                           
                         
                       
                     
                     ) 
                   
                 
               
               = 
               
                 
                   α 
                   ⁢ 
                   
                       
                   
                   ⁢ 
                   
                     LinSol 
                     ⁡ 
                     
                       ( 
                       
                         Σ 
                         , 
                         B 
                       
                       ) 
                     
                   
                 
                 + 
                 
                   β 
                   ⁢ 
                   
                       
                   
                   ⁢ 
                   
                     LinSol 
                     ⁡ 
                     
                       ( 
                       
                         Σ 
                         , 
                         
                           B 
                           ′ 
                         
                       
                       ) 
                     
                   
                 
               
             
             ; 
           
         
       
       
         
           
             
               
                 If 
                 ⁢ 
                 
                     
                 
                 ⁢ 
                 Σ 
                 ⁢ 
                 
                     
                 
                 ⁢ 
                 
                   X 
                   0 
                 
               
               = 
               
                 
                   α 
                   ⁢ 
                   
                       
                   
                   ⁢ 
                   B 
                 
                 + 
                 
                   β 
                   ⁢ 
                   
                       
                   
                   ⁢ 
                   
                     B 
                     ′ 
                   
                 
               
             
             , 
             
               
                 X 
                 0 
               
               = 
               
                 LinSol 
                 ⁡ 
                 
                   ( 
                   
                     Σ 
                     , 
                     
                       
                         α 
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         B 
                       
                       + 
                       
                         β 
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         
                           B 
                           ′ 
                         
                       
                     
                   
                   ) 
                 
               
             
           
         
       
       
         
           
             
               
                 If 
                 ⁢ 
                 
                     
                 
                 ⁢ 
                 Σ 
                 ⁢ 
                 
                     
                 
                 ⁢ 
                 
                   X 
                   
                     0 
                     , 
                     1 
                   
                 
               
               = 
               B 
             
             ; 
             
               
                 X 
                 
                   0 
                   , 
                   1 
                 
               
               = 
               
                 LinSol 
                 ⁡ 
                 
                   ( 
                   
                     Σ 
                     , 
                     B 
                   
                   ) 
                 
               
             
             ; 
           
         
       
       
         
           
             
               
                 If 
                 ⁢ 
                 
                     
                 
                 ⁢ 
                 Σ 
                 ⁢ 
                 
                     
                 
                 ⁢ 
                 
                   X 
                   
                     0 
                     , 
                     2 
                   
                 
               
               = 
               
                 B 
                 ′ 
               
             
             ; 
             
               
                 X 
                 
                   0 
                   , 
                   2 
                 
               
               = 
               
                 LinSol 
                 ⁡ 
                 
                   ( 
                   
                     Σ 
                     , 
                     
                       B 
                       ′ 
                     
                   
                   ) 
                 
               
             
             ; 
           
         
       
       
         
           
             
               Σ 
               ⁡ 
               
                 ( 
                 
                   
                     α 
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     
                       X 
                       
                         0 
                         , 
                         1 
                       
                     
                   
                   + 
                   
                     β 
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     
                       X 
                       
                         0 
                         , 
                         2 
                       
                     
                   
                 
                 ) 
               
             
             = 
             
               
                 
                   α 
                   ⁢ 
                   
                       
                   
                   ⁢ 
                   B 
                 
                 + 
                 
                   β 
                   ⁢ 
                   
                       
                   
                   ⁢ 
                   
                     B 
                     ′ 
                   
                   ⁢ 
                   
                       
                   
                   ⁢ 
                   means 
                   ⁢ 
                   
                       
                   
                   ⁢ 
                   
                     X 
                     0 
                   
                 
               
               = 
               
                 
                   
                     α 
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     
                       X 
                       
                         0 
                         , 
                         1 
                       
                     
                   
                   + 
                   
                     β 
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     
                       X 
                       
                         0 
                         , 
                         2 
                       
                     
                   
                   ⁢ 
                   
                     
 
                   
                   - 
                   
                     LinSol 
                     ⁡ 
                     
                       ( 
                       
                         
                           α 
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           Σ 
                         
                         , 
                         B 
                       
                       ) 
                     
                   
                 
                 = 
                 
                   
                     1 
                     α 
                   
                   ⁢ 
                   
                     LinSol 
                     ⁡ 
                     
                       ( 
                       
                         Σ 
                         , 
                         B 
                       
                       ) 
                     
                   
                 
               
             
           
         
       
       
         
           
             
               
                 If 
                 ⁢ 
                 
                     
                 
                 ⁢ 
                 α 
                 ⁢ 
                 
                     
                 
                 ⁢ 
                 Σ 
                 ⁢ 
                 
                     
                 
                 ⁢ 
                 
                   X 
                   0 
                 
               
               = 
               B 
             
             , 
             
               
                 
                   X 
                   0 
                 
                 = 
                 
                   LinSol 
                   ⁡ 
                   
                     ( 
                     
                       
                         α 
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         Σ 
                       
                       , 
                       B 
                     
                     ) 
                   
                 
               
               ; 
             
           
         
       
       
         
           
             
               
                 Σ 
                 ⁢ 
                 
                     
                 
                 ⁢ 
                 
                   ( 
                   
                     α 
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     
                       X 
                       0 
                     
                   
                   ) 
                 
               
               = 
               B 
             
             , 
             
               
                 
                   i 
                   . 
                   e 
                   . 
                   
                     : 
                   
                 
                 ⁢ 
                 
                     
                 
                 ⁢ 
                 α 
                 ⁢ 
                 
                     
                 
                 ⁢ 
                 
                   X 
                   0 
                 
               
               = 
               
                 LinSol 
                 ⁡ 
                 
                   ( 
                   
                     Σ 
                     , 
                     B 
                   
                   ) 
                 
               
             
           
         
       
         
           i “Numerical Optimization Second Edition” Nocedal &amp; Wright Springer Series in Operations Research, 2006 
           ii “Coherent Measures of Risk,” Mathematical Finance, 9: 203-228 Artzner, P., Delbaen, F., Eber, J. M., and Heath, D. 
           iii “Tail Conditional Expectations for Elliptical Distributions”, Landsman, Z., Valdez, A. E., University of Haifa Technical Report N 02-04, 2002. 
       
    
     
       
         
               
             
               
             
           
               
                 APPENDIX 2 
               
               
                   
               
               
                 (*Portfolio Risk Minimization with constraints on the 
               
               
                 variance and on both sides of proportions*) 
               
               
                   
               
             
             
               
                   
               
             
          
           
               
                   (*copyright 2008 Phil Kongtcheu,All rights reserved;*) 
               
               
                   Clear[Sig, Sig, R, σ, Onem, Wc, Wc0]; 
               
               
                   Sig = {{0.00022433435108527324, 0.00014394886649762045, 
               
               
                      0.0002251458847394454, 0.00010021000625408, 0.00014097563165037515}, 
               
               
                     {0.00014394886649762045, 0.0001540053903706062, 0.00014265099501746512, 
               
               
                      0.00006621477020039582, 0.00010796790816927302}, 
               
               
                     {0.0002251458847394454, 0.00014265099501746512, 0.0003638252251988667, 
               
               
                      0.00009860266849531493, 0.0001390927967353812}, 
               
               
                     {0.00010021000625408, 0.00006621477020039582, 0.00009860266849531493, 
               
               
                      0.00016282098507368263, 0.00008430875019934272}, 
               
               
                     {0.00014097563165037515, 0.00010796790816927302, 0.0001390927967353812, 
               
               
                      0.00008430875019934272, 0.0002544098977099555}}; 
               
               
                   R = {{0.001707819241706326}, {0.00014524409298784336}, {−0.0008888039976398021}, 
               
               
                     {0.001571110192807092}, {0.002792841482083083}}; 
               
               
                   σ = Sqrt[0.0002]; m = Length[R]; Onem = Table[{1}, {m}]; 
               
               
                   Clear[C0]; C0 = Table[{0.00}, {i, m}]; 
               
               
                   (*Solving the Optimization Problem using Mathematica&#39;s built- 
               
               
                    in Algorithm- to be used as a benchmark against the proposed novel method*) 
               
               
                   Wc = ToExpression[Table[{“w”&lt;&gt;ToString[i]}, {i, m}]]; 
               
               
                   Wc0 = ToExpression[Table[“w”&lt;&gt;ToString[i], {i, m}]]; 
               
               
                   Clear[InSig0]; InSig0 = Inverse[Sig]; 
               
               
                   Timing[NMinimize[{(Transpose[Wc].Sig.Wc) [[1]][[1]], (Transpose[Onem].Wc) [[1]][[1]] == 1, 
               
               
                       Norm[Wc, Infinity] ≦ 1, Table[If[i == 1, 1, R[[j]][[1]]], {i, 2}, {j, m}].Wc == 
               
               
                        {{1}, {0.006739289957201789′}}}, Wc0]] 
               
               
                   NMinimize::incst : NMinimize was unable to generate any initial points satisfying the inequality constraints 
               
               
                       {−1 + Max[Abs[w1], Abs[w2], Abs[&lt;&lt;1&gt;&gt;], Abs[−1.07193−0.294711w1−0.719134w2−0.331844w4], Abs[w4]] ≦ 
               
               
                         0}. The initial region specified may not contain any feasible points. Changing 
               
               
                       the initial region or specifying explicit initial points may provide a better solution. &gt;&gt; 
               
               
                 Out[82]= {5.047, {0.000517121, {w1 → 1., w2 → −0.947372, w3 → −0.999591, w4 → 0.946955, w5 → 1.}}} 
               
               
                 In[89]= (*Symmetric Positive definite Matrix inversion algorithms*) 
               
               
                   (*Inverse through Cholesky *) 
               
               
                   Clear[InvCh] 
               
               
                   InvCh[S_] := Module[{Ui}, Ui = Inverse[CholeskyDecomposition[S]]; Ui.Transpose[Ui]]; 
               
               
                   (*Algorithm for inverting SDP matrices*) 
               
               
                   Clear[InvS]; 
               
               
                   InvS[S_] := Module[{ns, u, InS, Si, Sis, Sit, Xc, B, Bp, Bi, k, i}, 
               
               
                    ns = Length[S]; InS = Table[0, {i, ns}, {j, ns}]; Sis = S; Sit = Transpose[Sis]; 
               
               
                    (*Initiating Case*) 
               
               
                    Si = S; B = Table[If[k = 1, 1, 0], {k, ns}]; 
               
               
                    If[! (Sit == Si), Si = 0.5 (Sis + Sit)]; 
               
               
                    If[Quiet[Check[Xc = LinearSolve[Si, B], { }]] = { }, InS = { }; Goto[End1]]; 
               
               
                    (*Filling InS*) 
               
               
                    For[k = 1, k ≦ ns, k++, u = InS[[k]]; u[[1]] = Xc[[k]]; InS[[k]] = u; 
               
               
                      u = InS[[1]]; u[[k]] = Xc[[k]]; InS[[1]] = u] 
               
               
                     (*Loop*) 
               
               
                     For[i = 2, i ≦ ns, i++, Bp = Table[If[k = i, 1, 0], {k, ns}]; 
               
               
                      B = Bp − Sum[InS[[j]][[i]]*Table[Sis[[k]][[j]], {k, ns}], {j, i − 1}]; 
               
               
                      Bi = Table[B[[k]], {k, i, ns}]; 
               
               
                      Si = Table[Sis[[k]][[l]], {k, i, ns}, {l, i, ns}]; 
               
               
                      If[Quiet[Check[Xc = LinearSolve[Si, Bi], { }]] == { }, InS = { }; Goto[End2]]; 
               
               
                      (*Filling InS*) 
               
               
                      For[k = i, k ≦ ns, k++, u = InS[[k]]; u[[i]] = Xc[[k − i + 1]]; 
               
               
                       InS[[k]] = u; u = InS[[i]]; u[[k]] = Xc[[k − i + 1]]; InS[[i]] = u] 
               
               
                     ]; Label[End1]; Label[End2]; InS] 
               
               
                   Clear[InvSp]; 
               
               
                   InvSp[InSigp_, eqc_, er_Integer, q_Integer] := Module[{Ss, Ss0, d, Sb, sp, x, t}, 
               
               
                     (*Begin computing the inverse matrix of Sigp from the inverse of the parent matrix*) 
               
               
                     (*!!! This Algorithm is computationally very 
               
               
                        important. It helps transform the matrix inversion process into an O 
               
               
                        (q{circumflex over ( )}2) instead of an O(q{circumflex over ( )}3) as provided by existing algorithms!!!*) 
               
               
                     Ss = InSigp; x = Union[eqc, {er}]; t = 1; While[x[[t]] ≠ er, t++]; 
               
               
                     Ss0 = Table[Ss[[If[i &lt; t, i, i + 1]]][[If[j &lt; t, j, j + 1]]], {i, q}, {j, q}]; 
               
               
                     d = Ss[[t]][[t]]; 
               
               
                     Sb = Table[{Ss[[If[i &lt; t, i, i + 1]]][[t]]}, {i, q}]; 
               
               
                     sp = Ss0 − Sb.Transpose[Sb] /d; (*Sb.Transpose[Sb]/d can 
               
               
                      also be given directly as a Table, so choose whichever is faster*) 
               
               
                     (*End computing the inverse matrix of Sigp from the inverse of the parent matrix*) 
               
               
                     sp] 
               
               
                 In[64]= (*This case is abit more general as it includes the general quadratic minimization problem 
               
               
                    with an added linear term C t W to address various special cases, i.e. Min ½W t ΣW+C t W*) 
               
               
                   (*Here we implement the first Candidate extrema which gives the 
               
               
                    Global Minimum solution when there are no constraints activated *) 
               
               
                   Clear[W0sg]; 
               
               
                   W0sg[m_Integer, Sig_, InSig_, A_, B_, C_, Mi_, Ms_] := 
               
               
                    Module[{W, Wc, Wc0, Wx0, w0, w1, sp, σm, λp, Xmd, Udpm, Xdpm, k, s0, End1, End2, End3}, 
               
               
                     If[Quiet[Check[LinearSolve[A, B], { }]] == { }, w0 = −1; w1 = 1; Goto[End1], 
               
               
                      sp = InSig; Udpm = A.sp; Xdpm = Udpm.Transpose[A]; 
               
               
                      Xmd = InvS[Xdpm]; If[Xmd == { }, w0 = −1; w1 = 1; Goto[End1]]; 
               
               
                      (*This is to correct rounding errors that may preclude the symetry of Xmd*); 
               
               
                      λp = −Xmd. (B + Udpm.C); W = −sp. (Transpose[A].λp + C); 
               
               
                      s0 = 0; k = 1; 
               
               
                      While[And[s0 == 0, k ≦ m], If[Abs[W[[k]][[1]] − (Ms[[k]][[1]] + Mi[[k]][[1]]) /2] &gt; 
               
               
                        (Ms[[k]][[1]] − Mi[[k]][[1]]) /2, s0++]; k++]; 
               
               
                      If[s0 == 0, w0 = 1; σm = (0.5*Transpose[W].Sig.W + Transpose[C].W)[[1]][[1]]; 
               
               
                       w1 = {W, σm); Goto[End1], w0 = 0; w1 = sp; Goto[End1]] 
               
               
                     ]; Label[End1]; {w0, w1}]; 
               
               
                 In{66}= (*Computing the Constrained Vectors Case:r p  condition not verified leads to w0[[1]]=0*) 
               
               
                   Clear[Wpsg]; Wpsg[m_Integer, p_Integer, e_, Sig_, InSigp_, A_, B_, C_, Mi_, Ms_] := 
               
               
                    Module[{End1, Wx, Wc, Wx0, ep, epc, eqc, n, q, e0, n0, n1, w0, t, sp, λp, 
               
               
                      Udpm, Xdpm, σm, Ag, Ap, Cq, Cp, fdp, tfdp, Vdpm, s0, sigbq, sigmpq, pos, Mp, 
               
               
                      spq, spqt, db, Wc0, i, j, k, Sigq, Sigp, Xmd, r, x, er, ep1, Sol), q = m − p; 
               
               
                     ep = e[[1]]; ep1 = e[[1]]; er = e[[2]]; n = Length[ep] ; db = Length[B]; (*e[[3]]= 
               
               
                      Length[ep; Correct the structure of the set E and its operations to reflect this]*); 
               
               
                     (*Checking first the trivial case where all constraints are active, p=m; q=0*) 
               
               
                     If[q == 0, For[j = 1, j &lt;= n, Mp = Table[If[ep[[j]][[k]] &lt; 0, Mi[[k]], Ms[[k]]], {k, m}]; 
               
               
                       If[A.Mp == B, w0[ep[[j]]] = {1, {Mp, 0.5*Transpose[Mp].Sig.Mp+Transpose[C].Mp}}, 
               
               
                        w0[ep[[j]]] = {−1, 1}] ; j++], 
               
               
                      (* If not all constraints are active, this follows... *) 
               
               
                      e0 = ep; n0 = n; epc = Sort[Abs[ep[[1]]]]; eqc = Complement[Table[k, {k, m}], epc]; 
               
               
                      Ap = Table[A[[i]][[epc[[j]]]], {i, db}, {j, p}]; 
               
               
                      Aq = Table[A[[i]][[eqc[[j]]]], {i, db}, {j, q}]; 
               
               
                      Cq = Table[C[[eqc[[j]]]], {j, q}]; Cp = Table[C[[epc[[i]]]], {i, p}]; 
               
               
                      (*Begin first loop*) 
               
               
                      (*This step may be eliminated when the existence of W verifiant the linear equality 
               
               
                       constraint is trivial, but this is generally not visibly the case, unless d=1*) 
               
               
                      For[j = 1, j ≦ n, (*Defining Mp*) 
               
               
                       Mp = Table[If[ep[[j]][[l]] &lt; 0, Mi[[epc[[l]]]], Ms[[epc[[l]]]]], {l, p}]; 
               
               
                        (*Begin checking that the linear equality constraint ApMp+AqWq=B is verified*) 
               
               
                       If[Quiet[Check[LinearSolve[Aq, B − Ap.Mp], { }]] == { }, w0[ep[[j]]] = {−1, 1}; 
               
               
                        e0 = Complement[e0, {ep[[j]]}]; n0−−;]; j++]; 
               
               
                      (*End checking that the linear equality constraint ApMp+AqWq=B is verified*) 
               
               
                      (*End first loop*) 
               
               
                     ep = e0; n1 = n0; If[n1 ≧ 1, 
               
               
                      sp = InvSp[InSigp, eqc, er, q]; 
               
               
                       (*Begin computing intermediary parameters to compute the candidate optimum*) 
               
               
                      spq = Table[Sig[[epc[[i]]]][[eqc[[j]]]], {i, p}, {j, q}]; spqt = Transpose[spq]; 
               
               
                      Sigq = Table[Sig[[eqc[[i]]]][[eqc[[j]]]], {i, q}, {j, q}]; 
               
               
                      Sigp = Table[Sig[[epc[[i]]]][[epc[[j]]]], {i, p}, {j, p}]; 
               
               
                      Udpm = Aq.sp; Xdpm = Udpm.Transpose[Aq]; Xmd = InvS[Xdpm]; 
               
               
                      If[Xmd == { }, w0[ep[[j]]] = {−1, 1}; Goto[End1]]; 
               
               
                      fdp = Ap − Udpm.spqt; tfdp = Transpose[fdp]; 
               
               
                      Mp = Table[{0}, {i, p}]; For[j = 1, j ≦ n1, (*Defining Mp*) 
               
               
                       Mp = Table[If[ep[[j]][[k]] &lt; 0, Mi[[epc[[k]]]], Ms[[epc[[k]]]]], {k, p}]; 
               
               
                       λp = Xmd.(fdp.Mp − (B + Udpm.Cq)); 
               
               
                       Wx0 = −sp.(spqt.Mp + Transpose[Aq].λp + Cq); 
               
               
                       For[i = 1, i ≦ q, pos[eqc[[i]]] = i; i++]; For[i = 1, i ≦ p, pos[epc[[i]]] = i; i++]; 
               
               
                       Wx = Table[If[MemberQ[eqc, k], Wx0[[pos[k]]], Mp[[pos[k]]] ], {k, m}]; 
               
               
                       r = (spq.sp.spqt − Sigp).Mp + (spq.sp.Cq − Cp) − tfdp.λp; 
               
               
                       (*Begin Algorithm for checking r p *) 
               
               
                       s0 = 0; k = 1; 
               
               
                       While[And[k ≦ p, s0 == 0], If[! Or[ And[Mp[[k]] == Mi[[epc[[k]]]], r[[k]][[1]] ≧ 0], 
               
               
                           And[Mp[[k]] == Ms[[epc[[k]]]], r[[k]][[1]] &lt;= 0]], s0++] ; k++]; 
               
               
                       (*End Algorithm for checking r p *) 
               
               
                       (*Begin Algorithm for checking that Abs[Wx−(Ms+Mi)/2]≦(Ms−Mi)/2&lt;→s0=0*) 
               
               
                       k =1; While[And[k ≦ q, s0 == 0], 
               
               
                        If[ Abs[Wx0[[k]][[1]] − (Ms[[eqc[[k]]]][[1]] + Mi[[eqc[[k]]]][[1]]) / 2] &gt; 
               
               
                           (Ms[[eqc[[k]]]][[1]] − Mi[[eqc[[k]]]][[1]]) / 2, s0++] ; k++]; 
               
               
                       (*End Algorithm for checking that Abs[W−(Ms+Mi)/2]≦(Ms−Mi)/2 &amp; r p &lt;→s0=0*) 
               
               
                       If[s0 == 0, w0[ep[[j]]] = {1, {Wx, 0.5 * Transpose[Wx].Sig.Wx + Transpose[C].Wx}}, 
               
               
                        w0[ep[[j]]] = {0, sp}]; Label[End1]; 
               
               
                      j++]; 
               
               
                     ];]; 
               
               
                     Sol = Table[w0[ep1[[j]]], {j, n}]; Sol]; 
               
               
                 In[67]= (*Intermediate functions to facilitate the 
               
               
                    handling of alternative cases in the global algorithm*) 
               
               
                   (*The inclusion function checks if e1 is included in e0*) 
               
               
                   (*This function also assumes e0 and e1 are represented as e0,e1={i 1   s ,...,i p   s };*) 
               
               
                   Clear[Inc]; Inc[e0_, e1_] := If[e0∩e1 == e0, 1, 0]; 
               
               
                   (*This function is used to add elements to Eps when Abs[w0]=1*) 
               
               
                   Clear[Addp]; Addp[e_, Ep_] := Union[{e}, Ep]; 
               
               
                   (*This function checks if ep is a descendent of an element in Esp*) 
               
               
                   (*This function assumes ep represented as ep= 
               
               
                    {i 1   s ,...,i k ,...,i p   s }is and Esp is represented as Esp= 
               
               
                     {{{i 1   1 },...,{i n01   n01 }},..,{{i 1   1 ,...,i m   1 },...,{i 1   1 ,...,i m   n0m }}}*) 
               
               
                   Clear[DesI]; DesI[ep_, Esp_] := Module[{d, i, j, p, n0}, d = 0; i = 1; 
               
               
                     p = Length[ep]; While[And[d == 0, i &lt; p], n0 = Length[Esp[[i]]]; j = 1; 
               
               
                      If[n0 &gt; 0, While[And[d == 0, j ≦ n0], d = Inc[Esp[[i]][[j]], ep]; j++]]; i++]; d]; 
               
               
                   (*Subs is used to remove from a list of equivalent elements of Es, 
               
               
                   those that descend from elements in Eps *) 
               
               
                   (*This function assumes e is represented as e= 
               
               
                    {{{i 1   1 ,...,i k ,...,i p   1 },...,{i 1   n0 ,...,i k ,...,i p   n0 }},i k }; 
               
               
                   Indeed the n0 elements of e[[1]] are equivalent; 
               
               
                   Ep is represented as Ep={{{i 1   1 },...,{i n01   n01 }},...,{{i 1   1 ,...,i m   1 },...,{i 1   1 ,...,i m   n0m }}}*) 
               
               
                   Clear[Subs]; Subs[e_, Ep_] := 
               
               
                    Module[{p, n0, e0}, p = Length[e[[1]][[1]]]; If[p ≦ 1, e, e0 = e; n0 = Length[e[[1]]] ; 
               
               
                     If[n0 &gt; 0, For[i = 1, i ≦ n0, If[DesI[e[[1]][[i]], Ep] == 1, 
               
               
                        e0[[1]] = Complement[e0[[1]], {e[[1]][[i]]}] ] ; i++]]; e0] ]; 
               
               
                   (*Check the issue of “Return” within “Module”, especially for the computation of Wp*) 
               
               
                   (*Make sure the structure of e, e&#39;,E,Ep, is harmonized throughout and 
               
               
                    how p may be a parameter that does not have to be computed each time*) 
               
               
                   (*Sorts is meant to prevent that rearranged indices get duplicated in e[[1]] 
               
               
                    simply because their listing order is different.To see its importance, 
               
               
                   remove the Sorts funtion in the Add funtion below, i.e. es=Sorts[e]; 
               
               
                   becomes es=e and try this example for both 
               
               
                     cases:AddD[{1,2},{{{{1,2,3},{1,2,−3}},3},{{{−1,2,4},{−1,2,−4}},4}},4,2] *) 
               
               
                   Clear[Sorts]; Sorts[e_] := Module[{es, es1, est, p}, es = e; es1 = es[[1]]; 
               
               
                     p = Length[es1]; est = { }; For[i = 1, i ≦ p, es1[[i]] = Sort[es1[[i]]]; 
               
               
                      est = Union[est, {es1[[i]]}]; i++]; es[[1]] = est; es]; 
               
               
                   (*Add is used to add elements to Es when Abs[w0]=0*) 
               
               
                   (*This function assumes e is represented as e= 
               
               
                    {{{i 1   1 ,...,i k ,...,i p   1 },...,{i 1   n0 ,...,i k ,...,i p   n0 }},i k }; 
               
               
                   Indeed the n0 elements of e[[1]] are equivalent; Ep is represented as Ep= 
               
               
                    {e0,...,en0} where e is the representative form of the elements ek of Ep*) 
               
               
                   Clear[Add]; Add[e_, Ep_] := 
               
               
                    Module[{n0, j, ej, Eps, es}, es = Sorts[e]; Eps = Ep; n0 = Length[Eps] ; 
               
               
                     If[n0 &gt; 0, 
               
               
                      j = 1; ej = Eps[[1]]; While[And[j ≦ n0, Sort[Abs[es[[1]][[1]]]] ≠ Sort[Abs[ej[[1]][[1]]]]], 
               
               
                       If[j + 1 ≦ n0, ej = Eps[[j + 1]]]; j++]; If[j ≦ n0, ej[[1]] = Union[ej[[1]], es[[1]]]; 
               
               
                       ej[[2]] = es[[2]]; Eps[[j]] = ej; Eps, Union[{es}, Ep] ] , 
               
               
                      {e} ] 
               
               
                    ]; 
               
               
                   (* This function assumes e is represented as e={i 1   s ,...,i p   s }; 
               
               
                   Ep is represented as Ep={e0,...,en0} where e is the representative form of the elements ek= 
               
               
                     {{{i 1   1 ,...,i k ,...,i p   1 },...,{i 1   n0 ,...,i k ,...,i p   n0 }},i k } of Ep *) 
               
               
                   Clear[AddD]; AddD[e_, Ep_, dim_, p_] := Module[{de, q, Ad, desck}, 
               
               
                     de = Complement[Table[i, {i, dim}], Abs[e]]; q = dim − p; Ad = Ep; 
               
               
                     If[q ≧ 1, For[k = 1, k ≦ q, desck = {{Union[e, {de[[k]]}], Union[e, {−de[[k]]}]}, de[[k]]}; 
               
               
                       Ad = Add[desck, Ad]; k++] ]; Ad ]; 
               
               
                 In[74]= (*MAIN ALGORITHM*) 
               
               
                   Clear[QuadOptEg] 
               
               
                   QuadOptEg[m_Integer, Sig_, InSig_, A_, B_, C_, Mi_, Ms_] := 
               
               
                     Module[ {Wm, sp, Wo, e, e10, n0, n, Em, Ep, i, j, p, 
               
               
                       σm, σ0, InSigp, Inve, A0, B0, Mi0, Ms0, End1, End2, x0, y0, z0, dn}, 
               
               
                      Wm = { }; σm = +∞; σ0 = +∞; 
               
               
                      sp = InSig; x0 = { }; Inve[x0] = sp; (*Inve is an internally defined function 
               
               
                       that stores inverse matrices of submatrices of Sig previously computed*) 
               
               
                      dn = 1; Wo = W0sg[m, Sig, sp, A, B, C, Mi, Ms]; 
               
               
                      If[Abs[Wo[[1]]] == 1, 
               
               
                         If[Wo[[1]] == 1, 
               
               
                           Wm = {Wo[[2]][[1]]}; σm = Wo[[2]][[2]]; Goto[End1], 
               
               
                            Wm = { }; σm = Null; Goto[End2]] , 
               
               
                       Em = Table[{ }, {i, m}]; Ep = Table[{ }, {i, m}]; 
               
               
                       For[k = 1, k ≦ m, Em[[1]] = Em[[1]]∪{{{{−k}, {k}} , k}}; k++]; 
               
               
                       p = 1; While[ p ≦ m, n0 = Length[Em[[p]]]; 
               
               
                        i = 1; While[ i ≦ n0, e = Subs[Em[[p]][[i]], Ep]; n = Length[e[[1]]]; 
               
               
                         If[n &gt; 0, dn++; 
               
               
                          x0 = Complement[Abs[e[[1]][[1]]], {e[[2]]}]; 
               
               
                          InSigp = Inve[x0]; Wo = Wpsg[m, p, e, Sig, InSigp, A, B, C, Mi, Ms]; 
               
               
                          For[j = 1, j ≦ n, 
               
               
                           If[Abs[Wo[[j]][[1]]] == 1, y0 = Addp[e[[1]][[j]], Ep[[p]]]; Ep[[p]] = y0; 
               
               
                            If[Wo[[j]][[1]] == 1, σ0 = Wo[[j]][[2]][[2]][[1]][[1]]; 
               
               
                             If[σm &gt; σ0, σm = σ0; Wm = {Wo[[j]][[2]][[1]]}, 
               
               
                              If[σm == σ0, Wm = Union[Wm, {Wo[[j]][[2]][[1]]}]] ] 
               
               
                            ], e10 = e[[1]][[j]]; Inve[Sort[Abs[e10]]] = Wo[[j]][[2]]; 
               
               
                            If[p + 1 ≦ m, z0 = AddD[e10, Em[[p + 1]], m, p]; Em[[p + 1]] = z0]; 
               
               
                           ]; j++]]; 
               
               
                         i++]; 
               
               
                        p++] 
               
               
                      ]; 
               
               
                      Label[End1]; Label[End2]; {dn, Wm, σm}]; 
               
               
                   (* END MAIN ALGORITHM *) 
               
               
                   In[76]= Timing[QuadOptEg[m, Sig, InSig0, Table[If[i == 1, 1, R[[j]][[1]]], {i, 2}, {j, m}], 
               
               
                      {{1}, {0.006739289957201789`}}, C0, −Onem, Onem]] 
               
               
                 Out[76]= {0.64, {31, {{{0.951336}, {−0.951336}, {−1}, {1}, {1}}}, 0.00026333}}