QPS_MIPS Quadratic Program Solver based on MIPS.
[X, F, EXITFLAG, OUTPUT, LAMBDA] = ...
QPS_MIPS(H, C, A, L, U, XMIN, XMAX, X0, OPT)
Uses the MATLAB Interior Point Solver (MIPS) to solve the following
QP (quadratic programming) problem:
min 1/2 X'*H*X + C'*X
X
subject to
L <= A*X <= U (linear constraints)
XMIN <= X <= XMAX (variable bounds)
Inputs (all optional except H, C, A and L):
H : matrix (possibly sparse) of quadratic cost coefficients
C : vector of linear cost coefficients
A, L, U : define the optional linear constraints. Default
values for the elements of L and U are -Inf and Inf,
respectively.
XMIN, XMAX : optional lower and upper bounds on the
X variables, defaults are -Inf and Inf, respectively.
X0 : optional starting value of optimization vector X
OPT : optional options structure with the following fields,
all of which are also optional (default values shown in
parentheses)
verbose (0) - controls level of progress output displayed
0 = no progress output
1 = some progress output
2 = verbose progress output
feastol (1e-6) - termination tolerance for feasibility
condition
gradtol (1e-6) - termination tolerance for gradient
condition
comptol (1e-6) - termination tolerance for complementarity
condition
costtol (1e-6) - termination tolerance for cost condition
max_it (150) - maximum number of iterations
step_control (0) - set to 1 to enable step-size control
max_red (20) - maximum number of step-size reductions if
step-control is on
cost_mult (1) - cost multiplier used to scale the objective
function for improved conditioning.
PROBLEM : The inputs can alternatively be supplied in a single
PROBLEM struct with fields corresponding to the input arguments
described above: H, c, A, l, u, xmin, xmax, x0, opt
Outputs:
X : solution vector
F : final objective function value
EXITFLAG : exit flag
1 = first order optimality conditions satisfied
0 = maximum number of iterations reached
-1 = numerically failed
OUTPUT : output struct with the following fields:
iterations - number of iterations performed
hist - struct array with trajectories of the following:
feascond, gradcond, compcond, costcond, gamma,
stepsize, obj, alphap, alphad
message - exit message
LAMBDA : struct containing the Langrange and Kuhn-Tucker
multipliers on the constraints, with fields:
mu_l - lower (left-hand) limit on linear constraints
mu_u - upper (right-hand) limit on linear constraints
lower - lower bound on optimization variables
upper - upper bound on optimization variables
Note the calling syntax is almost identical to that of QUADPROG
from MathWorks' Optimization Toolbox. The main difference is that
the linear constraints are specified with A, L, U instead of
A, B, Aeq, Beq.
Calling syntax options:
[x, f, exitflag, output, lambda] = ...
qps_mips(H, c, A, l, u, xmin, xmax, x0, opt)
x = qps_mips(H, c, A, l, u)
x = qps_mips(H, c, A, l, u, xmin, xmax)
x = qps_mips(H, c, A, l, u, xmin, xmax, x0)
x = qps_mips(H, c, A, l, u, xmin, xmax, x0, opt)
x = qps_mips(problem), where problem is a struct with fields:
H, c, A, l, u, xmin, xmax, x0, opt
all fields except 'c', 'A' and 'l' or 'u' are optional
x = qps_mips(...)
[x, f] = qps_mips(...)
[x, f, exitflag] = qps_mips(...)
[x, f, exitflag, output] = qps_mips(...)
[x, f, exitflag, output, lambda] = qps_mips(...)
Example: (problem from from http://www.jmu.edu/docs/sasdoc/sashtml/iml/chap8/sect12.htm)
H = [ 1003.1 4.3 6.3 5.9;
4.3 2.2 2.1 3.9;
6.3 2.1 3.5 4.8;
5.9 3.9 4.8 10 ];
c = zeros(4,1);
A = [ 1 1 1 1;
0.17 0.11 0.10 0.18 ];
l = [1; 0.10];
u = [1; Inf];
xmin = zeros(4,1);
x0 = [1; 0; 0; 1];
opt = struct('verbose', 2);
[x, f, s, out, lam] = qps_mips(H, c, A, l, u, xmin, [], x0, opt);
See also MIPS.0001 function [x, f, eflag, output, lambda] = qps_mips(H, c, A, l, u, xmin, xmax, x0, opt) 0002 %QPS_MIPS Quadratic Program Solver based on MIPS. 0003 % [X, F, EXITFLAG, OUTPUT, LAMBDA] = ... 0004 % QPS_MIPS(H, C, A, L, U, XMIN, XMAX, X0, OPT) 0005 % Uses the MATLAB Interior Point Solver (MIPS) to solve the following 0006 % QP (quadratic programming) problem: 0007 % 0008 % min 1/2 X'*H*X + C'*X 0009 % X 0010 % 0011 % subject to 0012 % 0013 % L <= A*X <= U (linear constraints) 0014 % XMIN <= X <= XMAX (variable bounds) 0015 % 0016 % Inputs (all optional except H, C, A and L): 0017 % H : matrix (possibly sparse) of quadratic cost coefficients 0018 % C : vector of linear cost coefficients 0019 % A, L, U : define the optional linear constraints. Default 0020 % values for the elements of L and U are -Inf and Inf, 0021 % respectively. 0022 % XMIN, XMAX : optional lower and upper bounds on the 0023 % X variables, defaults are -Inf and Inf, respectively. 0024 % X0 : optional starting value of optimization vector X 0025 % OPT : optional options structure with the following fields, 0026 % all of which are also optional (default values shown in 0027 % parentheses) 0028 % verbose (0) - controls level of progress output displayed 0029 % 0 = no progress output 0030 % 1 = some progress output 0031 % 2 = verbose progress output 0032 % feastol (1e-6) - termination tolerance for feasibility 0033 % condition 0034 % gradtol (1e-6) - termination tolerance for gradient 0035 % condition 0036 % comptol (1e-6) - termination tolerance for complementarity 0037 % condition 0038 % costtol (1e-6) - termination tolerance for cost condition 0039 % max_it (150) - maximum number of iterations 0040 % step_control (0) - set to 1 to enable step-size control 0041 % max_red (20) - maximum number of step-size reductions if 0042 % step-control is on 0043 % cost_mult (1) - cost multiplier used to scale the objective 0044 % function for improved conditioning. 0045 % PROBLEM : The inputs can alternatively be supplied in a single 0046 % PROBLEM struct with fields corresponding to the input arguments 0047 % described above: H, c, A, l, u, xmin, xmax, x0, opt 0048 % 0049 % Outputs: 0050 % X : solution vector 0051 % F : final objective function value 0052 % EXITFLAG : exit flag 0053 % 1 = first order optimality conditions satisfied 0054 % 0 = maximum number of iterations reached 0055 % -1 = numerically failed 0056 % OUTPUT : output struct with the following fields: 0057 % iterations - number of iterations performed 0058 % hist - struct array with trajectories of the following: 0059 % feascond, gradcond, compcond, costcond, gamma, 0060 % stepsize, obj, alphap, alphad 0061 % message - exit message 0062 % LAMBDA : struct containing the Langrange and Kuhn-Tucker 0063 % multipliers on the constraints, with fields: 0064 % mu_l - lower (left-hand) limit on linear constraints 0065 % mu_u - upper (right-hand) limit on linear constraints 0066 % lower - lower bound on optimization variables 0067 % upper - upper bound on optimization variables 0068 % 0069 % Note the calling syntax is almost identical to that of QUADPROG 0070 % from MathWorks' Optimization Toolbox. The main difference is that 0071 % the linear constraints are specified with A, L, U instead of 0072 % A, B, Aeq, Beq. 0073 % 0074 % Calling syntax options: 0075 % [x, f, exitflag, output, lambda] = ... 0076 % qps_mips(H, c, A, l, u, xmin, xmax, x0, opt) 0077 % 0078 % x = qps_mips(H, c, A, l, u) 0079 % x = qps_mips(H, c, A, l, u, xmin, xmax) 0080 % x = qps_mips(H, c, A, l, u, xmin, xmax, x0) 0081 % x = qps_mips(H, c, A, l, u, xmin, xmax, x0, opt) 0082 % x = qps_mips(problem), where problem is a struct with fields: 0083 % H, c, A, l, u, xmin, xmax, x0, opt 0084 % all fields except 'c', 'A' and 'l' or 'u' are optional 0085 % x = qps_mips(...) 0086 % [x, f] = qps_mips(...) 0087 % [x, f, exitflag] = qps_mips(...) 0088 % [x, f, exitflag, output] = qps_mips(...) 0089 % [x, f, exitflag, output, lambda] = qps_mips(...) 0090 % 0091 % Example: (problem from from http://www.jmu.edu/docs/sasdoc/sashtml/iml/chap8/sect12.htm) 0092 % H = [ 1003.1 4.3 6.3 5.9; 0093 % 4.3 2.2 2.1 3.9; 0094 % 6.3 2.1 3.5 4.8; 0095 % 5.9 3.9 4.8 10 ]; 0096 % c = zeros(4,1); 0097 % A = [ 1 1 1 1; 0098 % 0.17 0.11 0.10 0.18 ]; 0099 % l = [1; 0.10]; 0100 % u = [1; Inf]; 0101 % xmin = zeros(4,1); 0102 % x0 = [1; 0; 0; 1]; 0103 % opt = struct('verbose', 2); 0104 % [x, f, s, out, lam] = qps_mips(H, c, A, l, u, xmin, [], x0, opt); 0105 % 0106 % See also MIPS. 0107 0108 % MIPS 0109 % $Id: qps_mips.m,v 1.10 2010/12/15 18:40:42 cvs Exp $ 0110 % by Ray Zimmerman, PSERC Cornell 0111 % Copyright (c) 2010 by Power System Engineering Research Center (PSERC) 0112 % 0113 % This file is part of MIPS. 0114 % See http://www.pserc.cornell.edu/matpower/ for more info. 0115 % 0116 % MIPS is free software: you can redistribute it and/or modify 0117 % it under the terms of the GNU General Public License as published 0118 % by the Free Software Foundation, either version 3 of the License, 0119 % or (at your option) any later version. 0120 % 0121 % MIPS is distributed in the hope that it will be useful, 0122 % but WITHOUT ANY WARRANTY; without even the implied warranty of 0123 % MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 0124 % GNU General Public License for more details. 0125 % 0126 % You should have received a copy of the GNU General Public License 0127 % along with MIPS. If not, see <http://www.gnu.org/licenses/>. 0128 % 0129 % Additional permission under GNU GPL version 3 section 7 0130 % 0131 % If you modify MIPS, or any covered work, to interface with 0132 % other modules (such as MATLAB code and MEX-files) available in a 0133 % MATLAB(R) or comparable environment containing parts covered 0134 % under other licensing terms, the licensors of MIPS grant 0135 % you additional permission to convey the resulting work. 0136 0137 %%----- input argument handling ----- 0138 %% gather inputs 0139 if nargin == 1 && isstruct(H) %% problem struct 0140 p = H; 0141 else %% individual args 0142 p = struct('H', H, 'c', c, 'A', A, 'l', l, 'u', u); 0143 if nargin > 5 0144 p.xmin = xmin; 0145 if nargin > 6 0146 p.xmax = xmax; 0147 if nargin > 7 0148 p.x0 = x0; 0149 if nargin > 8 0150 p.opt = opt; 0151 end 0152 end 0153 end 0154 end 0155 end 0156 0157 %% define nx, set default values for H and c 0158 if ~isfield(p, 'H') || isempty(p.H) || ~any(any(p.H)) 0159 if (~isfield(p, 'A') || isempty(p.A)) && ... 0160 (~isfield(p, 'xmin') || isempty(p.xmin)) && ... 0161 (~isfield(p, 'xmax') || isempty(p.xmax)) 0162 error('qps_mips: LP problem must include constraints or variable bounds'); 0163 else 0164 if isfield(p, 'A') && ~isempty(p.A) 0165 nx = size(p.A, 2); 0166 elseif isfield(p, 'xmin') && ~isempty(p.xmin) 0167 nx = length(p.xmin); 0168 else % if isfield(p, 'xmax') && ~isempty(p.xmax) 0169 nx = length(p.xmax); 0170 end 0171 end 0172 p.H = sparse(nx, nx); 0173 else 0174 nx = size(p.H, 1); 0175 end 0176 if ~isfield(p, 'c') || isempty(p.c) 0177 p.c = zeros(nx, 1); 0178 end 0179 if ~isfield(p, 'x0') || isempty(p.x0) 0180 p.x0 = zeros(nx, 1); 0181 end 0182 0183 %%----- run optimization ----- 0184 p.f_fcn = @(x)qp_f(x, p.H, p.c); 0185 [x, f, eflag, output, lambda] = mips(p); 0186 0187 %%----- objective function ----- 0188 function [f, df, d2f] = qp_f(x, H, c) 0189 f = 0.5 * x' * H * x + c' * x; 0190 if nargout > 1 0191 df = H * x + c; 0192 if nargout > 2 0193 d2f = H; 0194 end 0195 end