QP

To adapt the model developed in Chapter 2 to the new way of looking at the problem, we need to make the following changes:

• New objective function: mean variance instead of total return.
• The risk-related constraint disappears.
• Addition of a new constraint: target yield.

The new objective function is the mean variance of the portfolio, namely:

where VAR_st is the variance/covariance matrix of all shares. This is a quadratic objective function (an objective function becomes quadratic either when a variable is squared, e.g., frac₁², or when two variables are multiplied together, e.g., frac₁ · frac₂).

The target yield constraint can be written as follows:

The limit on the North-American shares as well as the requirement to spend all the money, and the upper bounds on the fraction invested into every share are retained. We therefore obtain the following complete mathematical model formulation:

Implementation with BCL

The estimated returns and the variance/covariance matrix are given in the data file foliocppqp.dat:

! trs  haw  thr  tel  brw  hgw  car  bnk  sof  elc
0.1    0    0    0    0    0    0    0    0    0 ! treasury
  0   19   -2    4    1    1    1  0.5   10    5 ! hardware
  0   -2   28    1    2    1    1    0   -2   -1 ! theater
  0    4    1   22    0    1    2    0    3    4 ! telecom
  0    1    2    0    4 -1.5   -2   -1    1    1 ! brewery
  0    1    1    1 -1.5  3.5    2  0.5    1  1.5 ! highways
  0    1    1    2   -2    2    5  0.5    1  2.5 ! cars
  0  0.5    0    0   -1  0.5  0.5    1  0.5  0.5 ! bank
  0   10   -2    3    1    1    1  0.5   25    8 ! software
  0    5   -1    4    1  1.5  2.5  0.5    8   16 ! electronics

We may read this datafile with the function XPRBreadarrlinecb: all comments preceded by ! and also empty lines are skipped. We read an entire line at once indicating the format of an entry (`g') and the separator (any number of spaces or tabulations).

For the definition of the objective function we now use a quadratic expression (equally represented by the class XPRBexpr). Since we now wish to minimize the problem, we use the default optimization sense setting and optimization as a continuous problem is again started with the method lpOptimize (with empty string argument indicating the default algorithm).

#include <iostream>
#include "xprb_cpp.h"

using namespace std;
using namespace ::dashoptimization;

#define DATAFILE "foliocppqp.dat"

#define TARGET 9                     // Target yield
#define MAXNUM 4                     // Max. number of different assets

#define NSHARES 10                   // Number of shares
#define NNA 4                        // Number of North-American shares

double RET[] = {5,17,26,12,8,9,7,6,31,21};  // Estimated return in investment
int NA[] = {0,1,2,3};                // Shares issued in N.-America
double VAR[NSHARES][NSHARES];        // Variance/covariance matrix of
                                     // estimated returns

int main(int argc, char **argv)
{
 int s,t;
 XPRBprob p("FolioQP");              // Initialize a new problem in BCL
 XPRBexpr Na,Return,Cap,Num,Variance;
 XPRBvar frac[NSHARES];              // Fraction of capital used per share
 FILE *datafile;

// Read `VAR' data from file
 datafile=fopen(DATAFILE,"r");
 for(s=0;s<NSHARES;s++)
  XPRBreadarrlinecb(XPRB_FGETS, datafile, 200, "g ", VAR[s], NSHARES);
 fclose(datafile);

// Create the decision variables
 for(s=0;s<NSHARES;s++)
  frac[s] = p.newVar(XPRBnewname("frac(%d)",s+1), XPRB_PL, 0, 0.3);

// Objective: mean variance
 for(s=0;s<NSHARES;s++)
  for(t=0;t<NSHARES;t++) Variance += VAR[s][t]*frac[s]*frac[t];
 p.setObj(Variance);                 // Set the objective function

// Minimum amount of North-American values
 for(s=0;s<NNA;s++) Na += frac[NA[s]];
 p.newCtr(Na >= 0.5);

// Spend all the capital
 for(s=0;s<NSHARES;s++) Cap += frac[s];
 p.newCtr(Cap == 1);

// Target yield
 for(s=0;s<NSHARES;s++) Return += RET[s]*frac[s];
 p.newCtr(Return >= TARGET);

// Solve the problem
 p.lpOptimize("");

// Solution printing
 cout << "With a target of " << TARGET << " minimum variance is " <<
         p.getObjVal() << endl;
 for(s=0;s<NSHARES;s++)
  cout << s << ": " << frac[s].getSol()*100 << "%" << endl;

 return 0;
}

This program produces the following solution output with a dual-core processor (notice that the default algorithm for solving QP problems is Newton-Barrier, not the Simplex as in all previous examples):

Reading Problem FolioQP
Problem Statistics
           3 (      0 spare) rows
          10 (      0 spare) structural columns
          24 (      0 spare) non-zero elements
          76 quadratic elements
Global Statistics
           0 entities        0 sets        0 set members
Minimizing QP FolioQP
Original problem has:
         3 rows           10 cols           24 elements
        76 qobjelem
Presolved problem has:
         3 rows           10 cols           24 elements
        76 qobjelem
Barrier cache sizes : L1=32K L2=8192K
Using AVX support
Cores per CPU (CORESPERCPU): 8
Barrier starts, using up to 8 threads, 4 cores
Matrix ordering - Dense cols.:      9   NZ(L):        92   Flops:          584

  Its   P.inf      D.inf      U.inf      Primal obj.     Dual obj.      Compl.
   0  1.90e+001  1.85e+002  3.70e+000  8.7840000e+002 -1.1784000e+003  4.5e+003
   1  1.69e-001  1.58e+000  3.29e-002  7.1810240e+000 -2.7042733e+002  3.1e+002
   2  3.31e-003  1.48e-002  6.45e-004  5.1672666e+000 -1.2127681e+001  1.7e+001
   3  6.12e-007  2.66e-015  2.78e-017  1.5558934e+000 -4.8803143e+000  6.4e+000
   4  9.71e-017  1.39e-015  2.78e-017  7.2498306e-001  1.4062618e-001  5.8e-001
   5  3.64e-017  1.01e-015  5.55e-017  5.6634270e-001  5.2690100e-001  3.9e-002
   6  3.97e-017  7.15e-016  5.55e-017  5.5894833e-001  5.5591229e-001  3.0e-003
   7  1.22e-016  1.33e-015  5.55e-017  5.5760205e-001  5.5726378e-001  3.4e-004
   8  9.18e-017  1.68e-015  5.55e-017  5.5741308e-001  5.5738503e-001  2.8e-005
   9  2.36e-016  3.29e-016  5.55e-017  5.5739403e-001  5.5739328e-001  7.5e-007
Barrier method finished in 0 seconds
Uncrunching matrix
Optimal solution found
Barrier solved problem
  9 barrier iterations in 0s

Final objective                         : 5.573940299651456e-01
  Max primal violation      (abs / rel) : 7.347e-17 / 7.347e-17
  Max dual violation        (abs / rel) :       0.0 /       0.0
  Max complementarity viol. (abs / rel) : 6.075e-07 / 1.012e-07
All values within tolerances
With a target of 9 minimum variance is 0.557394
0: 30%
1: 7.15401%
2: 7.38237%
3: 5.46362%
4: 12.6561%
5: 5.91283%
6: 0.333491%
7: 29.9979%
8: 1.0997%
9: 6.97039e-06%