Documentation Center

  • Trial Software
  • Product Updates

qpdantz

Solve convex quadratic program using Dantzig-Wolfe's algorithm

    Note:   qpdantz will be removed in a future version. Use quadprog (requires Optimization Toolbox™) instead.

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

subject to Axb,xxmin

using Dantzig-Wolfe's active set method [2]. The Hessian matrix H should be positive definite. By default, xmin=1e-3. 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,[],[],-100,[],[],...
optimset('LargeScale','off','Algorithm','active-set'));
[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.

Was this topic helpful?