Model Predictive Control Toolbox™

Solve convex quadratic program using Dantzig-Wolfe's algorithm

Syntax

• [xopt,lambda,how]=qpdantz(H,f,A,b,xmin)
  [xopt,lambda,how]=qpdantz(H,f,A,b,xmin,maxiter)
  

Description

[xopt,lambda,how]=qpdantz(H,f,A,b,xmin) solves the convex quadratic program

using Dantzig-Wolfe's active set method [1]. The Hessian matrix H should be positive definite. By default, xmin=1e-5. Vector xopt is the optimizer. Vector lambda contains the optimal dual variables (Lagrange multipliers).

The exit flag how is either 'feasible', 'infeasible' or 'unreliable'. The latter occurs when the solver terminates because the maximum number maxiter of allowed iterations was exceeded.

The solver is implemented in qpsolver.mex. Dantzig-Wolfe's algorithm uses the direction of the largest gradient, and the optimum is usually found after about n+q iterations, where n=dim(x) is the number of optimization variables, and q=dim(b) is the number of constraints. More than 3(n+q) iterations are rarely required (see Chapter 7.3 of [2]).

Examples

Solve a random QP problem using quadprog from the Optimization Toolbox™ software and qpdantz.

• n=50;     % Number of vars
  
  H=rand(n,n);H=H'*H;H=(H+H')/2;
  f=rand(n,1);
  A=[eye(n);-eye(n)];
  b=[rand(n,1);rand(n,1)];
  
  x1=quadprog(H,f,A,b);
  [x2,how]=qpdantz(H,f,A,b,-100*ones(n,1));
  

References

[1]  Fletcher, R. Practical Methods of Optimization, John Wiley & Sons, Chichester, UK, 1987.

[2]  Dantzig, G.B. Linear Programming and Extensions, Princeton University Press, Princeton, 1963.

Provide feedback about this page

plot

set

© 1984-2008- The MathWorks, Inc.    -   Site Help   -   Patents   -   Trademarks   -   Privacy Policy   -   Preventing Piracy   -   RSS