Solve convex quadratic program using Dantzig-Wolfe's algorithm
Note: qpdantz will be removed in a future version. Use quadprog (requires Optimization Toolbox™) instead.
[xopt,lambda,how]=qpdantz(H,f,A,b,xmin) solves the convex quadratic program
subject to Ax ≤ b,x ≥ xmin
using Dantzig-Wolfe's active set method . 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 ).
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));