7 A Quadratic Convex Program (examp-qp)

Run LPL Code  ,  PDF Document

Problem

The general quadratic programming model – called QP – consists of m linear constraints, n variables and a quadratic convex objective function f(x). It can be compactly formulated as follows:

            ∑                ∑
min               xjQj,kxk +      cjxj
           j∑∈J,k∈J             j∈J
subjectto       a  x ≥  b                          forall i ∈ I
                 i,j j    i
           j∈J
           xj ≥ 0                                  forall j ∈ J
           J =  {1...m }, I = {1 ...n}, m, n ≥ 0

An more compact formulation using matrix notation for the model is as follows:

min        xQx ′ + c ⋅ x
subjectto  A ⋅ x ≥ b

           x ≥ 0

The objective function f the constraints gi, and X (in the general format) are as follows:

f (x1,...,xn) =   x1Q1,1x1 + x1Q1,2x2 + ...+ xnQn,n -1xn-1 + xnQn,nxn
gi(x1,...,xn ) =  bi - (ai,1x1 + ...+ ai,nxn) ≤ 0  forall i = 1,...,m
                  x ∈ Rn

Note that the matrix Q must be semi-definite positive (SDP), (that is: there exist a vector x such that xQx0). In many applications the matrix Q is also symmetric (Q = QT).

If the matrix Q is not semi-definite positive then it cannot be solved as a convex problem and it must be considered as an non-linear problem.

In the following, a concrete problem with random data for the two matrices A, Q and the two vectors b and c is specified (with n = 15 and m = 15):

    (                                                          )
c =  16  73  39  81  68  60  90  11  33  89  71  12  24  23  47

    (                                                           )         (    )
    | 87  34  0   0   43  0   52  85  36  0   0   0   0   0   0 |         |  0 |
    | 0   0   39  0   84  0   0   88  0   0   0   0   0   0   22|         |  0 |
    || 55  63  79  0   0   0   0   71  0   0   0   0   70  0   79||         ||  0 ||
    || 0   0   0   0   0   0   0   73  0   0   0   22  0   0   0 ||         ||  0 ||
    || 0   0   0   66  0   0   34  0   0   24  0   61  0   0   64||         ||  0 ||
    || 0   0   16  19  0   0   0   0   0   0   0   0   0   0   18||         ||  0 ||
    || 15  70  61  0   0   0   0   0   0   0   0   0   0   0   0 ||         ||  0 ||
    |                                                           |         |    |
A = || 0   0   0   0   0   0   0   0   52  0   14  0   0   92  0 ||     b = || 58 ||
    || 0   0   0   0   0   0   0   30  0   0   98  0   19  0   0 ||         || 44 ||
    || 0   70  37  0   0   0   0   0   0   0   0   86  0   93  0 ||         ||  0 ||
    || 90  0   82  0   66  0   0   0   0   26  0   0   0   0   0 ||         ||  0 ||
    | 77  30  0   0   0   0   13  10  0   0   0   50  0   0   0 |         |  0 |
    || 0   0   0   0   0   0   0   0   0   0   0   0   0   0   0 ||         ||  0 ||
    |( 0   72  0   0   0   79  0   0   0   0   0   11  90  0   0 |)         |(  0 |)
      0   0   0   0   0   32  55  0   23  0   0   0   0   0   36            119

          (                                                     )
diag(Q) =  7  5  5  6   17  19  6  8  16  19  12  5  13  17   18

Note that this matrix Q consisting of positive diagonal entries and zero otherwise is semidefinite positive.

The data given above specify the following explicit linear program:

min        7x21 + 5x22 + 5x23 + 6x24 + 17x25 + 19x26 + 6x27 + 8x28
              +16x2 +  19x2 +  12x2 +  5x2 + 13x2  + 17x2  + 18x2
              +16x 9+  73x10+  39x 11+ 81x 12+ 68x  1+360x  +1490x  + 1511x
                   1      2      3      4       5      6      7      8
              +33x9 +  89x10 + 71x11 + 12x12 + 24x13 + 23x14 + 47x15
subjectto  87x1 +  34x2 + 43x5 + 52x7 + 85x8 + 36x9 ≥  0
           39x3 +  84x5 + 88x8 + 22x15 ≥ 0
           55x1 +  63x2 + 79x3 + 71x8 + 70x13 + 79x15 ≥ 0

           73x8 +  22x12 ≥ 0
           66x4 +  34x7 + 24x10 + 61x12 + 64x15 ≥ 0
           16x3 +  19x4 + 18x15 ≥ 0
           15x1 +  70x2 + 61x3 ≥ 0
           52x  +  14x  +  92x  ≥  58
               9      11      14
           30x8 +  98x11 + 19x13 ≥ 44
           70x2 +  37x3 + 86x12 + 93x14 ≥ 0
           90x1 +  82x3 + 66x5 + 26x10 ≥ 0
           77x1 +  30x2 + 13x7 + 10x8 + 50x12 ≥ 0
           72x  +  79x +  11x  +  90x   ≥ 0
               2      6      12      13
           32x6 +  55x7 + 23x9 + 36x15 ≥ 119
           xj ≥  0   forall j ∈ {1 ...15}

Modeling Steps

The formulation of the model in LPL modeling language is straightforward and the notation is close to the mathematical notation using indices: First, the two sets i and j are defined. Then the data are declare and assigned as parameters A, c, b, and a semidefinite positive matrix Q. The variable vector x is declared, and finally the constraints R and the minimizing objective function obj are written.

Note that the data matrices A, b, c, and Q are generated using LPL’s own random generator. (To generate each time the same data, the code can also use the function SetRandomSeed(a) where a is an integer.)


Listing 5: The Complete Model implemented in LPL [10]
model Qp15 "A Quadratic Convex Program"; 
  set i := [1..15];  j,k := [1..15]; 
  parameter A{i,j}:= Trunc(if(Rnd(0,1)<.25,Rnd(10,100))); 
            c{j}  := Trunc(Rnd(10,100)); 
            b{i}  := Trunc(if(Rnd(0,1)<.15, Rnd(0,120))); 
            Q{j,k}:= Trunc(if(j=k, Rnd(5,20))); //SDP 
  variable  x{j}; 
  constraint R{i} : sum{j} A*x >= b; 
  minimize obj    : sum{j} c*x + sum{j,k} x[j]*Q*x[k]; 
  Writep(obj,x); 
end

Solution

The small model defined above has the following optimal solution:

    (                                                               )
x =  0  0  0 0  0  0.051  1.37  0.7  0.839  0  0.23  0  0  0.121  0.63

The optimal value of the objective function is:

obj = 245.4168

Further Comments

There are interesting applications in Portfolio Theory for the quadratic convex problems. Especially, the Markowitz approach in portfolio models can be formulated as a QP model. For several implemented models see Casebook I. Other applications are robust optimization and chance constraint optimization, and much more.

Note that the constraints can also be quadratic, we then have a QPC model where the Q matrix must be semi-definite positive:

           ∑
min             cjxj
           j∈J
            ∑                ∑
subjectto         xjQj,kxk +      ai,jxj ≥ bi       forall i ∈ I
           j∈J,k∈J             j∈J
           xj ≥ 0                                  forall j ∈ J
           J =  {1...m }, I = {1 ...n}, m, n ≥ 0