quapro

Scilab Function
Last update : 25/04/2007

quapro - linear quadratic programming solver

### Calling Sequence

  `[x,lagr,f]=quapro(Q,p,C,b [,x0])`
  `[x,lagr,f]=quapro(Q,p,C,b,ci,cs [,x0])`
  `[x,lagr,f]=quapro(Q,p,C,b,ci,cs,me [,x0])`
  `[x,lagr,f]=quapro(Q,p,C,b,ci,cs,me,x0 [,imp])`

### Parameters

- `Q` : real symmetric matrix (dimension `n x n` ).
- `p` : real (column) vector (dimension `n` )
- `C` : real matrix (dimension `(me + md) x n` ) (If no constraints are given, you can set `C = []` )
- `b` : RHS column vector (dimension `(me + md)` ) (If no constraints are given, you can set `b = []` )
- `ci` : column vector of lower-bounds (dimension `n` ). If there are no lower bound constraints, put `ci = []` . If some components of `x` are bounded from below, set the other (unconstrained) values of `ci` to a very large negative number (e.g. `ci(j) = -number_properties('huge')` .
- `cs` : column vector of upper-bounds. (Same remarks as above).
- `me` : number of equality constraints (i.e. `C(1:me,:)*x = b(1:me)` )
- `x0` : either an initial guess for `x` or one of the character strings `'v'` or `'g'` . If `x0='v'` the calculated initial feasible point is a vertex. If `x0='g'` the calculated initial feasible point is arbitrary.
- `imp` : verbose option (optional parameter) (Try `imp=7,8,...` ). warning the message are output in the window where scilab has been started.
- `x` : optimal solution found.
- `f` : optimal value of the cost function (i.e. `f=0.5*x'*Q*x+p'` ).
- `lagr` : vector of Lagrange multipliers. If lower and upper-bounds `ci,cs` are provided, `lagr` has `n + me + md` components and `lagr(1:n)` is the Lagrange vector associated with the bound constraints and `lagr (n+1 : n + me + md)` is the Lagrange vector associated with the linear constraints. (If an upper-bound (resp. lower-bound) constraint `i` is active `lagr(i)` is > 0 (resp. <0). If no bounds are provided, `lagr` has only `me + md` components.

### Description

Minimize `0.5*x'*Q*x + p'*x`

under the constraint

    C*x <= b

Minimize `0.5*x'*Q*x + p'*x`

under the constraints

    C*x <= b          ci <= x <= cs

Minimize `0.5*x'*Q*x + p'*x`

under the constraints

     C(j,:) x = b(j),  j=1,...,me
     C(j,:) x <= b(j), j=me+1,...,me+md
     ci <= x <= cs

If no initial point is given the program computes a feasible initial point which is a vertex of the region of feasible points if `x0='v'` .

If `x0='g'` , the program computes a feasible initial point which is not necessarily a vertex. This mode is advisable when the quadratic form is positive definite and there are few constraints in the problem or when there are large bounds on the variables that are just security bounds and very likely not active at the optimal solution.

Note that `Q` is not necessarily non-negative, i.e. `Q` may have negative eigenvalues.

### Examples

    //Find x in R^6 such that:
    //C1*x = b1 (3 equality constraints i.e me=3)
    C1= [1,-1,1,0,3,1;
        -1,0,-3,-4,5,6;
         2,5,3,0,1,0];
    b1=[1;2;3];
    //C2*x <= b2 (2 inequality constraints)
    C2=[0,1,0,1,2,-1;
        -1,0,2,1,1,0];
    b2=[-1;2.5];
    //with  x between ci and cs:
    ci=[-1000;-10000;0;-1000;-1000;-1000];cs=[10000;100;1.5;100;100;1000];
    //and minimize 0.5*x'*Q*x + p'*x with
    p=[1;2;3;4;5;6]; Q=eye(6,6);
    //No initial point is given;
    C=[C1;C2] ; //
    b=[b1;b2] ;  //
    me=3;
    [x,lagr,f]=quapro(Q,p,C,b,ci,cs,me)
    //Only linear constraints (1 to 4) are active (lagr(1:6)=0):
    [x,lagr,f]=quapro(Q,p,C,b,[],[],me)   //Same result as above

### See Also

`qld` , `linpro` , `optim` ,

### Authors

  Eduardo Casas Renteria, Universidad de Cantabria,
  Cecilia Pola Mendez , Universidad de Cantabria

### Bibliography

E. Casas and C. Pola, An algorithm for indefinite quadratic programming based on a partial Cholesky factorization, RAIRO-Recherche Opérationnelle/Operations Research, 27 (1993), 401-426.

### Used Function

in routines/optim directory (authors E.Casas, C. Pola Mendez):

anfm01.f anfm03.f anfm05.f anrs01.f auxo01.f dimp03.f dnrm0.f optr03.f pasr03.f zthz.f anfm02.f anfm04.f anfm06.f anrs02.f desr03.f dipvtf.f optr01.f opvf03.f plcbas.f

From BLAS library

daxpy.f dcopy.f ddot.f dnrm2.f dscal.f dswap.f idamax.f

in routines/calelm directory (authors INRIA):

add.f ddif.f dmmul.f

From LAPACK library : dlamch.f