Optimization Toolbox

Quadratic Minimization with Bound Constraints

To minimize a large-scale quadratic with upper and lower bounds, you can use the quadprog function.

The problem stored in the MAT-file qpbox1.mat is a positive definite quadratic, and the Hessian matrix H is tridiagonal, subject to upper (ub) and lower (lb) bounds.

Step 1: Load the Hessian and define f, lb, ub.

• load qpbox1   % Get H
  lb = zeros(400,1); lb(400) = -inf;
  ub = 0.9*ones(400,1); ub(400) = inf;
  f = zeros(400,1); f([1 400]) = -2;
  

Step 2: Call a quadratic minimization routine with a starting point xstart.

• xstart = 0.5*ones(400,1);
  [x,fval,exitflag,output] = ... 
          quadprog(H,f,[],[],[],[],lb,ub,xstart);
  

Looking at the resulting values of exitflag and output,

• exitflag =
       1
  output = 
      firstorderopt: 7.8435e-006
         iterations: 20
       cgiterations: 1809
          algorithm: 'large-scale: reflective trust-region'
  

you can see that while convergence occurred in 20 iterations, the high number of CG iterations indicates that the cost of the linear system solve is high. In light of this cost, one strategy would be to limit the number of CG iterations per optimization iteration. The default number is the dimension of the problem divided by two, 200 for this problem. Suppose you limit it to 50 using the MaxPCGIter flag in options:

• options = optimset('MaxPCGIter',50);
  [x,fval,exitflag,output] = ... 
          quadprog(H,f,[],[],[],[],lb,ub,xstart,options);
  

This time convergence still occurs and the total number of CG iterations (1547) has dropped:

• exitflag =
       1
  output = 
      firstorderopt: 2.3821e-005
         iterations: 36
       cgiterations: 1547
          algorithm: 'large-scale: reflective trust-region'
  

A second strategy would be to use a direct solver at each iteration by setting the PrecondBandWidth parameter to inf:

• options = optimset('PrecondBandWidth',inf);
  [x,fval,exitflag,output] = ... 
          quadprog(H,f,[],[],[],[],lb,ub,xstart,options);
  

Now the number of iterations has dropped to 10:

• exitflag =
       1
  output = 
      firstorderopt: 4.8955e-007
         iterations: 10
       cgiterations: 9
          algorithm: 'large-scale: reflective trust-region'
  

Using a direct solve at each iteration usually causes the number of iterations to decrease, but often takes more time per iteration. For this problem, the tradeoff is beneficial, as the time for quadprog to solve the problem decreases by a factor of 10.

Nonlinear Minimization with a Dense but Structured Hessian and Equality Constraints

Quadratic Minimization with a Dense but Structured Hessian