# Documentation

### This is machine translation

Translated by
Mouseover text to see original. Click the button below to return to the English verison of the 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.