Documentation

This is machine translation

Translated by Microsoft
Mouseover text to see original. Click the button below to return to the English verison of the page.

Note: This page has been translated by MathWorks. Please click here
To view all translated materals including this page, select Japan from the country navigator on the bottom of this page.

Large Sparse Quadratic Program with Interior Point Algorithm

This example shows the value of using sparse arithmetic when you have a sparse problem. The matrix has n rows, where you choose n to be a large value. A full matrix of size n-by-n can use up all available memory, but a sparse matrix presents no problem.

The problem is to minimize x'*H*x/2 + f'*x subject to

x(1) + x(2) + ... + x(n) = 0,

where f = [-1;-2;-3;...;-n].

  1. Create the parameter n and the utility matrix T. The matrix T is a sparse circulant matrix that is simply a helper for creating the sparse positive-definite quadratic matrix H.

    n = 30000; % Adjust n to a large value
    T = spalloc(n,n,n); % make a sparse circulant matrix
    r = 1:n-1;
    for m = r
        T(m,m+1)=1;
    end
    T(n,1) = 1;
  2. Create a sparse vector v. Then create the matrix H by shifted versions of v*v'. The matrix T creates shifts of v.

    v(n) = 0; v(1) = 1; v(2) = 2; v(4) = 3;
    v = (sparse(v))';
    % Make a banded type of matrix
    H = spalloc(n,n,7*n);
    r = 1:n;
    for m = r
        H = H + v*v';
        v = T*v;
    end
  3. Take a look at the structure of H:

    spy(H)

  4. Create the problem vector f and linear constraint.

    f = -r; % linear term
    A = ones(1,n); b = 0;
  5. Solve the quadratic programming problem with the interior-point-convex algorithm. Set the StepTolerance option to a very low value so that the algorithm does not stop too early.

    options = optimoptions(@quadprog,'Algorithm','interior-point-convex','StepTolerance',1e-15);
    [x,fval,exitflag,output,lambda] = ...
        quadprog(H,f,A,b,[],[],[],[],[],options);
  6. View the solution value, number of iterations, and Lagrange multiplier associated with linear inequalities:

    fval,output.iterations,lambda.ineqlin
    
    fval =
    
      -3.1331e+10
    
    
    ans =
    
         6
    
    
    ans =
    
       1.5000e+04

    Since there are no lower bounds or upper bounds, all the values in lambda.lower and lambda.upper are 0. The inequality constraint is active, since lambda.ineqlin is nonzero.

  7. On many computers you cannot create a full n-by-n matrix when n = 30000. So you can run this problem only using sparse matrices.

Was this topic helpful?