Example 9.10 Quadratic Programming

The quadratic program

can be solved by solving an equivalent linear complementarity problem when is positive semidefinite. The approach is outlined in the discussion of the LCP subroutine in Chapter 23.

The following routine solves the quadratic problem.

      /*              Routine to solve quadratic programs            */
      /* names: the names of the decision variables                  */
      /* c:  vector of linear coefficients of the objective function */
      /* H:  matrix of quadratic terms in the objective function     */
      /* G:  matrix of constraint coefficients                       */
      /* rel: character array of values: '<=' or '>=' or '='         */
      /* b:   right-hand side of constraints                         */
      /* activity: returns the optimal value of decision variables   */

   start qp( names, c, H, G, rel, b, activity);
      if min(eigval(h))<0 then
      do;
         print
               'ERROR: The minimum eigenvalue of the H matrix is negative. ';
         print '       Thus it is not positive semidefinite.               ';
         print '       QP is terminating with this error.                  ';
         stop;
      end;
      nr=nrow(G);
      nc=ncol(G);

         /* Put in canonical form */
      rev=(rel='<=');
      adj=(-1 * rev) + ^rev;
      g=adj# G; b = adj # b;
      eq=( rel = '='  );
      if max(eq)=1 then
      do;
         g=g // -(diag(eq)*G)[loc(eq),];
         b=b // -(diag(eq)*b)[loc(eq)];
      end;
      m=(h || -g`) //(g || j(nrow(g),nrow(g),0));
      q=c // -b;

         /* Solve the problem */
      call lcp(rc,w,z,M,q);

         /* Report the solution */
      reset noname;
      print ( { '*************Solution is optimal***************',
                '*********No solution possible******************',
                ' ',
                ' ',
                ' ',
                '**********Solution is numerically unstable*****',
                '***********Not enough memory*******************',
                '**********Number of iterations exceeded********'}[rc+1]);
      reset name;
      activity=z[1:nc];
      objval=c`*activity + activity`*H*activity/2;
      print ,'Objective Value ' objval,
             'Decision Variables ' activity[r=names],
             '***********************************************';

      finish qp;

As an example, consider the following problem in portfolio selection. Models used in selecting investment portfolios include assessment of the proposed portfolio’s expected gain and its associated risk. One such model seeks to minimize the variance of the portfolio subject to a minimum expected gain. This can be modeled as a quadratic program in which the decision variables are the proportions to invest in each of the possible securities. The quadratic component of the objective function is the covariance of gain between the securities; the first constraint is a proportionality constraint; and the second constraint gives the minimum acceptable expected gain.

The following data are used to illustrate the model and its solution:

   c = { 0, 0, 0, 0 };
   h = { 1003.1 4.3 6.3 5.9 ,
            4.3 2.2 2.1 3.9 ,
            6.3 2.1 3.5 4.8 ,
            5.9 3.9 4.8 10 };
   g = {  1   1   1   1  ,
         .17 .11 .10 .18 };
   b = { 1 , .10 };
   rel = { '=', '>='};
   names = {'ibm', 'dec', 'dg', 'prime' };
   run qp(names,c,h,g,rel,b,activity);

The results in Output 9.10.1 show that the minimum variance portfolio achieving the 0.10 expected gain is composed of DEC and DG stock in proportions of 0.933 and 0.067.