Main Content

本页翻译不是最新的。点击此处可查看最新英文版本。

quadprog

二次规划

说明

具有线性约束的二次目标函数的求解器。

quadprog 求由下式指定的问题的最小值

minx12xTHx+fTx such that {Axb,Aeqx=beq,lbxub.

H、A 和 Aeq 是矩阵,f、b、beq、lb、ub 和 x 是向量。

您可以将 f、lb 和 ub 作为向量或矩阵进行传递;请参阅矩阵参量

注意

quadprog 仅适用于基于求解器的方法。有关这两种优化方法的讨论,请参阅首先选择基于问题或基于求解器的方法

x = quadprog(H,f) 返回使 1/2*x'*H*x + f'*x 最小的向量 x。要使问题具有有限最小值,输入 H 必须为正定矩阵。如果 H 是正定矩阵,则解 x = H\(-f)

示例

x = quadprog(H,f,A,b)A*x b 的条件下求 1/2*x'*H*x + f'*x 的最小值。输入 A 是由双精度值组成的矩阵,b 是由双精度值组成的向量。

示例

x = quadprog(H,f,A,b,Aeq,beq) 在满足 Aeq*x = beq 的限制条件下求解上述问题。Aeq 是由双精度值组成的矩阵,beq 是由双精度值组成的向量。如果不存在不等式,则设置 A = []b = []

示例

x = quadprog(H,f,A,b,Aeq,beq,lb,ub) 在满足 lb x ub 的限制条件下求解上述问题。输入 lbub 是由双精度值组成的向量,这些限制适用于每个 x 分量。如果不存在等式,请设置 Aeq = []beq = []

注意

如果为问题指定的输入边界不一致,则输出 xx0,输出 fval[]

quadprogx0 中违反边界 lb x ub 的分量重置为在这些边界定义的框内。quadprog 不会更改遵守边界的分量。

x = quadprog(H,f,A,b,Aeq,beq,lb,ub,x0) 从向量 x0 开始求解上述问题。如果不存在边界,请设置 lb = []ub = []。一些 quadprog 算法会忽略 x0;请参阅 x0

注意

x0'active-set' 算法的必需参数。

示例

x = quadprog(H,f,A,b,Aeq,beq,lb,ub,x0,options) 使用 options 中指定的优化选项求解上述问题。使用 optimoptions 创建 options。如果您不提供初始点,请设置 x0 = []

示例

x = quadprog(problem) 返回 problem 的最小值,它是 problem 中所述的一个结构体。使用圆点表示法或 struct 函数创建 problem 结构体。或者,使用 prob2structOptimizationProblem 对象创建 problem 结构体。

示例

对于任何输入变量,[x,fval] = quadprog(___) 还会返回 fval,即在 x 处的目标函数值:

fval = 0.5*x'*H*x + f'*x

示例

[x,fval,exitflag,output] = quadprog(___) 还返回 exitflag(描述 quadprog 退出条件的整数)以及 output(包含有关优化信息的结构体)。

示例

[x,fval,exitflag,output,lambda] = quadprog(___) 还返回 lambda 结构体,其字段包含在解 x 处的拉格朗日乘数。

示例

[wsout,fval,exitflag,output,lambda] = quadprog(H,f,A,b,Aeq,beq,lb,ub,ws) 使用 ws 中的选项,从热启动对象 ws 中的数据启动 quadprog。返回的参数 wsout 包含 wsout.X 中的解点。通过在后续求解器调用中使用 wsout 作为初始热启动对象,quadprog 可以提高运行速度。

示例

全部折叠

找到下式的最小值

f(x)=12x12+x22-x1x2-2x1-6x2

需满足以下约束

x1+x22-x1+2x222x1+x23.

quadprog 语法中,此问题可表示为最小化下式

f(x)=12xTHx+fTx,

其中

H=[1-1-12]f=[-2-6],

问题具有线性约束。

要求解此问题,首先输入系数矩阵。

H = [1 -1; -1 2]; 
f = [-2; -6];
A = [1 1; -1 2; 2 1];
b = [2; 2; 3];

调用 quadprog

[x,fval,exitflag,output,lambda] = ...
   quadprog(H,f,A,b);
Minimum found that satisfies the constraints.

Optimization completed because the objective function is non-decreasing in 
feasible directions, to within the value of the optimality tolerance,
and constraints are satisfied to within the value of the constraint tolerance.

检查终点、函数值和退出标志。

x,fval,exitflag
x = 2×1

    0.6667
    1.3333

fval = -8.2222
exitflag = 1

退出标志为 1 表示结果是局部最小值。由于 H 是正定矩阵,此问题为凸型,因此最小值是全局最小值。

通过检查特征值,确认 H 是正定矩阵。

eig(H)
ans = 2×1

    0.3820
    2.6180

找到下式的最小值

f(x)=12x12+x22-x1x2-2x1-6x2

需满足以下约束

x1+x2=0.

quadprog 语法中,此问题可表示为最小化下式

f(x)=12xTHx+fTx,

其中

H=[1-1-12]f=[-2-6],

问题具有线性约束。

要求解此问题,首先输入系数矩阵。

H = [1 -1; -1 2]; 
f = [-2; -6];
Aeq = [1 1];
beq = 0;

调用 quadprog,为输入项 Ab 输入 []

[x,fval,exitflag,output,lambda] = ...
   quadprog(H,f,[],[],Aeq,beq);
Minimum found that satisfies the constraints.

Optimization completed because the objective function is non-decreasing in 
feasible directions, to within the value of the optimality tolerance,
and constraints are satisfied to within the value of the constraint tolerance.

检查终点、函数值和退出标志。

x,fval,exitflag
x = 2×1

   -0.8000
    0.8000

fval = -1.6000
exitflag = 1

退出标志为 1 表示结果是局部最小值。由于 H 是正定矩阵,此问题为凸型,因此最小值是全局最小值。

通过检查特征值,确认 H 是正定矩阵。

eig(H)
ans = 2×1

    0.3820
    2.6180

求使二次表达式最小的 x

12xTHx+fTx

其中

H=[1-11-12-21-24], f=[2-31],

需满足以下约束

0x1, x=1/2.

要求解此问题,首先输入系数。

H = [1,-1,1
    -1,2,-2
    1,-2,4];
f = [2;-3;1];
lb = zeros(3,1);
ub = ones(size(lb));
Aeq = ones(1,3);
beq = 1/2;

调用 quadprog,为输入项 Ab 输入 []

x = quadprog(H,f,[],[],Aeq,beq,lb,ub)
Minimum found that satisfies the constraints.

Optimization completed because the objective function is non-decreasing in 
feasible directions, to within the value of the optimality tolerance,
and constraints are satisfied to within the value of the constraint tolerance.
x = 3×1

    0.0000
    0.5000
    0.0000

设置选项以监控 quadprog 的进度。

options = optimoptions('quadprog','Display','iter');

定义具有二次目标和线性不等式约束的问题。

H = [1 -1; -1 2]; 
f = [-2; -6];
A = [1 1; -1 2; 2 1];
b = [2; 2; 3];

为了帮助编写 quadprog 函数调用,请将不必要的输入设置为 []

Aeq = [];
beq = [];
lb = [];
ub = [];
x0 = [];

调用 quadprog 以求解问题。

x = quadprog(H,f,A,b,Aeq,beq,lb,ub,x0,options)
 Iter            Fval  Primal Infeas    Dual Infeas  Complementarity  
    0   -8.884885e+00   3.214286e+00   1.071429e-01     1.000000e+00  
    1   -8.331868e+00   1.321041e-01   4.403472e-03     1.910489e-01  
    2   -8.212804e+00   1.676295e-03   5.587652e-05     1.009601e-02  
    3   -8.222204e+00   8.381476e-07   2.793826e-08     1.809485e-05  
    4   -8.222222e+00   3.064216e-14   1.352696e-12     7.525735e-13  

Minimum found that satisfies the constraints.

Optimization completed because the objective function is non-decreasing in 
feasible directions, to within the value of the optimality tolerance,
and constraints are satisfied to within the value of the constraint tolerance.
x = 2×1

    0.6667
    1.3333

使用基于问题的优化工作流创建一个 problem 结构体。创建一个等效于具有线性约束的二次规划的优化问题。

x = optimvar('x',2);
objec = x(1)^2/2 + x(2)^2 - x(1)*x(2) - 2*x(1) - 6*x(2);
prob = optimproblem('Objective',objec);
prob.Constraints.cons1 = sum(x) <= 2;
prob.Constraints.cons2 = -x(1) + 2*x(2) <= 2;
prob.Constraints.cons3 = 2*x(1) + x(2) <= 3;

prob 转换为 problem 结构体。

problem = prob2struct(prob);

使用 quadprog 求解问题。

[x,fval] = quadprog(problem)
Warning: Your Hessian is not symmetric. Resetting H=(H+H')/2.
Minimum found that satisfies the constraints.

Optimization completed because the objective function is non-decreasing in 
feasible directions, to within the value of the optimality tolerance,
and constraints are satisfied to within the value of the constraint tolerance.
x = 2×1

    0.6667
    1.3333

fval = -8.2222

求解二次规划,并返回解和目标函数值。

H = [1,-1,1
    -1,2,-2
    1,-2,4];
f = [-7;-12;-15];
A = [1,1,1];
b = 3;
[x,fval] = quadprog(H,f,A,b)
Minimum found that satisfies the constraints.

Optimization completed because the objective function is non-decreasing in 
feasible directions, to within the value of the optimality tolerance,
and constraints are satisfied to within the value of the constraint tolerance.
x = 3×1

   -3.5714
    2.9286
    3.6429

fval = -47.1786

检查返回的目标函数值是否与根据 quadprog 目标函数定义计算的值相匹配。

fval2 = 1/2*x'*H*x + f'*x
fval2 = -47.1786

要查看 quadprog 的优化过程,请设置选项以显示迭代输出并返回四个输出。问题可以表示为最小化下式

12xTHx+fTx

约束条件为

0x1,

其中

H=[21-11312-1125], f=[4-712].

输入问题系数。

H = [2 1 -1
    1 3 1/2
    -1 1/2 5];
f = [4;-7;12];
lb = zeros(3,1);
ub = ones(3,1);

设置选项以显示求解器的迭代进度。

options = optimoptions('quadprog','Display','iter');

调用带有四个输出的 quadprog

[x fval,exitflag,output] = quadprog(H,f,[],[],[],[],lb,ub,[],options)
 Iter            Fval  Primal Infeas    Dual Infeas  Complementarity  
    0    2.691769e+01   1.582123e+00   1.712849e+01     1.680447e+00  
    1   -3.889430e+00   0.000000e+00   8.564246e-03     9.971731e-01  
    2   -5.451769e+00   0.000000e+00   4.282123e-06     2.710131e-02  
    3   -5.499997e+00   0.000000e+00   1.221903e-10     6.939689e-07  
    4   -5.500000e+00   0.000000e+00   5.842173e-14     3.469847e-10  

Minimum found that satisfies the constraints.

Optimization completed because the objective function is non-decreasing in 
feasible directions, to within the value of the optimality tolerance,
and constraints are satisfied to within the value of the constraint tolerance.
x = 3×1

    0.0000
    1.0000
    0.0000

fval = -5.5000
exitflag = 1
output = struct with fields:
            message: 'Minimum found that satisfies the constraints....'
          algorithm: 'interior-point-convex'
      firstorderopt: 1.5921e-09
    constrviolation: 0
         iterations: 4
       linearsolver: 'dense'
       cgiterations: []

求解二次规划问题并返回拉格朗日乘数。

H = [1,-1,1
    -1,2,-2
    1,-2,4];
f = [-7;-12;-15];
A = [1,1,1];
b = 3;
lb = zeros(3,1);
[x,fval,exitflag,output,lambda] = quadprog(H,f,A,b,[],[],lb);
Minimum found that satisfies the constraints.

Optimization completed because the objective function is non-decreasing in 
feasible directions, to within the value of the optimality tolerance,
and constraints are satisfied to within the value of the constraint tolerance.

检查拉格朗日乘数结构体 lambda

disp(lambda)
    ineqlin: 12.0000
      eqlin: [0x1 double]
      lower: [3x1 double]
      upper: [3x1 double]

线性不等式约束有一个相关联的拉格朗日乘数 12

显示与下界相关联的乘数。

disp(lambda.lower)
    5.0000
    0.0000
    0.0000

只有 lambda.lower 的第一个分量具有非零乘数。这通常意味着只有 x 的第一个分量位于下界(即零)上。这可通过显示 x 的分量进行确认。

disp(x)
    0.0000
    1.5000
    1.5000

要加速后续的 quadprog 调用,请创建一个热启动对象。

options = optimoptions('quadprog','Algorithm','active-set');
x0 = [1 2 3];
ws = optimwarmstart(x0,options);

使用 ws 求解二次规划。

H = [1,-1,1
    -1,2,-2
    1,-2,4];
f = [-7;-12;-15];
A = [1,1,1];
b = 3;
lb = zeros(3,1);
tic
[ws,fval,exitflag,output,lambda] = quadprog(H,f,A,b,[],[],lb,[],ws);
toc
Minimum found that satisfies the constraints.

Optimization completed because the objective function is non-decreasing in 
feasible directions, to within the value of the optimality tolerance,
and constraints are satisfied to within the value of the constraint tolerance.
Elapsed time is 0.021717 seconds.

更改目标函数,重新求解问题。

f = [-10;-15;-20];

tic
[ws,fval,exitflag,output,lambda] = quadprog(H,f,A,b,[],[],lb,[],ws);
toc
Minimum found that satisfies the constraints.

Optimization completed because the objective function is non-decreasing in 
feasible directions, to within the value of the optimality tolerance,
and constraints are satisfied to within the value of the constraint tolerance.
Elapsed time is 0.018485 seconds.

输入参数

全部折叠

二次目标项,指定为对称实矩阵。H1/2*x'*H*x + f'*x 表达式形式表示二次矩阵。如果 H 不对称,quadprog 会发出警告,并改用对称版本 (H + H')/2

如果二次矩阵 H 为稀疏矩阵,则默认情况下,'interior-point-convex' 算法使用的算法与 H 为稠密矩阵时略有不同。通常,对于大型稀疏问题,稀疏算法更快,对于稠密或小型问题,稠密算法更快。有关详细信息,请参阅 LinearSolver 选项说明和interior-point-convex quadprog 算法

示例: [2,1;1,3]

数据类型: double

线性目标项,指定为实数向量。f 表示 1/2*x'*H*x + f'*x 表达式中的线性项。

示例: [1;3;2]

数据类型: double

线性不等式约束,指定为实矩阵。AM×N 矩阵,其中 M 是不等式的数目,而 N 是变量的数目(x0 中的元素数)。对于大型问题,将 A 作为稀疏矩阵传递。

A 以如下形式编写 M 个线性不等式

A*x <= b,

其中,x 是由 N 个变量组成的列向量 x(:)b 是具有 M 个元素的列向量。

例如,假设有以下不等式:

x1 +2x2 ≤10
3x1 +4x2 ≤20
5x1 +6x2 ≤30,

通过输入以下约束来指定不等式。

A = [1,2;3,4;5,6];
b = [10;20;30];

示例: 要指定 x 分量总和等于或小于 1,请使用 A = ones(1,N)b = 1

数据类型: double

线性不等式约束,指定为实数向量。b 是与 A 矩阵相关的包含 M 个元素的向量。如果将 b 作为行向量传递,求解器会在内部将 b 转换为列向量 b(:)。对于大型问题,将 b 作为稀疏向量传递。

b 以如下形式编写 M 个线性不等式

A*x <= b,

其中,x 是由 N 个变量组成的列向量 x(:)A 是大小为 M×N 的矩阵。

例如,假设有以下不等式:

x1 + 2x2 ≤ 10
3x1 + 4x2 ≤ 20
5x1 + 6x2 ≤ 30。

通过输入以下约束来指定不等式。

A = [1,2;3,4;5,6];
b = [10;20;30];

示例: 要指定 x 分量总和等于或小于 1,请使用 A = ones(1,N)b = 1

数据类型: double

线性等式约束,指定为实矩阵。AeqMe×N 矩阵,其中 Me 是等式的数目,而 N 是变量的数目(x0 中的元素数)。对于大型问题,将 Aeq 作为稀疏矩阵传递。

Aeq 以如下形式编写 Me 个线性等式

Aeq*x = beq,

其中,x 是由 N 个变量组成的列向量 x(:)beq 是具有 Me 个元素的列向量。

例如,假设有以下不等式:

x1 +2x2 +3x3 =10
2x1 +4x2 + x3 =20,

通过输入以下约束来指定不等式。

Aeq = [1,2,3;2,4,1];
beq = [10;20];

示例: 要指定 x 分量总和为 1,请使用 Aeq = ones(1,N)beq = 1

数据类型: double

线性等式约束,指定为实数向量。beq 是与 Aeq 矩阵相关的包含 Me 个元素的向量。如果将 beq 作为行向量传递,求解器会在内部将 beq 转换为列向量 beq(:)。对于大型问题,将 beq 作为稀疏向量传递。

beq 以如下形式编写 Me 个线性等式

Aeq*x = beq,

其中,x 是由 N 个变量组成的列向量 x(:)Aeq 是大小为 Me×N 的矩阵。

例如,请参考以下等式:

x1 + 2x2 + 3x3 = 10
2x1 + 4x2 + x3 = 20。

通过输入以下约束来指定等式。

Aeq = [1,2,3;2,4,1];
beq = [10;20];

示例: 要指定 x 分量总和为 1,请使用 Aeq = ones(1,N)beq = 1

数据类型: double

下界,指定为实数向量或实数数组。如果 x0 中的元素数等于 lb 中的元素数,则 lb 指定

x(i) >= lb(i)(对于全部 i)。

如果 numel(lb) < numel(x0),则 lb 指定

x(i) >= lb(i) (1 <= i <= numel(lb))。

如果 lb 的元素数少于 x0,求解器将发出警告。

示例: 要指定所有 x 分量为正,请使用 lb = zeros(size(x0))

数据类型: double

上界,指定为实数向量或实数数组。如果 x0 中的元素数等于 ub 中的元素数,则 ub 指定

x(i) <= ub(i)(对于全部 i)。

如果 numel(ub) < numel(x0),则 ub 指定

x(i) <= ub(i) (1 <= i <= numel(ub))。

如果 ub 的元素数少于 x0,求解器将发出警告。

示例: 要指定 x 的所有分量小于 1,请使用 ub = ones(size(x0))

数据类型: double

初始点,指定为实数向量。x0 的长度是 H 的行数或列数。

当问题只有边界约束时,x0 适用于 'trust-region-reflective' 算法。x0 也适用于 'active-set' 算法。

注意

x0'active-set' 算法的必需参数。

如果您未指定 x0quadprog 会将 x0 的所有分量设置为由边界定义的框内部的一个点。对于 'interior-point-convex' 算法和具有等式约束的 'trust-region-reflective' 算法,quadprog 将忽略 x0

示例: [1;2;1]

数据类型: double

优化选项,指定为 optimoptions 的输出或 optimset 等返回的结构体。

optimoptions 显示中缺少某些选项。这些选项在下表中以斜体显示。有关详细信息,请参阅查看优化选项

所有算法

Algorithm

选择算法:

  • 'interior-point-convex'(默认值)

  • 'trust-region-reflective'

  • 'active-set'

'interior-point-convex' 算法只处理凸问题。'trust-region-reflective' 算法处理只有边界或只有线性等式约束的问题,但不处理同时具有两者的问题。'active-set' 算法处理不定问题,前提是 HAeq 的零空间上的投影是半正定的。有关详细信息,请参阅选择算法

Diagnostics

显示关于要最小化或求解的函数的诊断信息。选项是 'on''off'(默认值)。

Display

显示级别(请参阅迭代输出):

  • 'off''none' 不显示输出。

  • 'final' 仅显示最终输出(默认值)。

'interior-point-convex''active-set' 算法允许附加值:

  • 'iter' 指定迭代输出。

  • 'iter-detailed' 指定迭代输出以及详细的退出消息。

  • 'final-detailed' 仅显示最终输出以及详细的退出消息。

MaxIterations

允许的迭代最大次数,为正整数。

  • 对于 'trust-region-reflective' 等式约束问题,默认值为 2*(numberOfVariables – numberOfEqualities)

  • 'active-set' 的默认值为 10*(numberOfVariables + numberOfConstraints)

  • 对于所有其他算法和问题,默认值为 200

对于 optimset,选项名称为 MaxIter。请参阅当前选项名称和旧选项名称

OptimalityTolerance

一阶最优性的终止容差:正标量。

  • 对于 'trust-region-reflective' 等式约束问题,默认值为 1e-6

  • 对于 'trust-region-reflective' 边界约束问题,默认值为 100*eps,大约为 2.2204e-14

  • 对于 'interior-point-convex''active-set' 算法,默认值为 1e-8

请参阅容差和停止条件

对于 optimset,选项名称为 TolFun。请参阅当前选项名称和旧选项名称

StepTolerance

关于正标量 x 的终止容差。

  • 对于 'trust-region-reflective',默认值为 100*eps,大约为 2.2204e-14

  • 对于 'interior-point-convex',默认值为 1e-12

  • 对于 'active-set',默认值为 1e-8

对于 optimset,选项名称为 TolX。请参阅当前选项名称和旧选项名称

'trust-region-reflective' 算法

FunctionTolerance

函数值的终止容差(正标量)。默认值取决于问题类型:边界约束问题使用 100*eps,线性等式约束问题使用 1e-6。请参阅容差和停止条件

对于 optimset,选项名称为 TolFun。请参阅当前选项名称和旧选项名称

HessianMultiplyFcn

黑塞矩阵乘法函数,指定为函数句柄。对于大规模结构问题,此函数计算黑塞矩阵乘积 H*Y,而并不实际构造 H。函数具有以下形式

W = hmfun(Hinfo,Y)

其中 Hinfo(可能还有一些附加参数)包含用于计算 H*Y 的矩阵。

有关使用此选项的示例,请参阅Quadratic Minimization with Dense, Structured Hessian

对于 optimset,选项名称为 HessMult。请参阅当前选项名称和旧选项名称

MaxPCGIter

PCG(预条件共轭梯度)迭代的最大次数;正标量。对于边界约束问题,默认值为 max(1,floor(numberOfVariables/2))。对于等式约束问题,quadprog 将忽略 MaxPCGIter 并使用 MaxIterations 来限制 PCG 迭代的次数。有关详细信息,请参阅预条件共轭梯度法

PrecondBandWidth

PCG 的预条件子的上带宽;非负整数。默认情况下,quadprog 使用对角预条件(上带宽 0)。对于某些问题,增加带宽会减少 PCG 迭代次数。将 PrecondBandWidth 设置为 Inf 会使用直接分解(乔列斯基分解),而不是共轭梯度 (CG)。直接分解的计算成本较 CG 高,但所得的求解步质量更好。

SubproblemAlgorithm

确定迭代步的计算方式。与 'factorization' 相比,默认值 'cg' 采用的步执行速度更快,但不够准确。请参阅trust-region-reflective quadprog 算法

TolPCG

PCG 迭代的终止容差:正标量。默认值为 0.1

TypicalX

典型的 x 值。TypicalX 中的元素数等于起点 x0 中的元素数。默认值为 ones(numberOfVariables,1)quadprog 在内部使用 TypicalX 进行缩放。仅当 x 具有无界分量且一个无界分量的 TypicalX 值超过 1 时,TypicalX 才会起作用。

'interior-point-convex' 算法

ConstraintTolerance

约束违反值容差;正标量。默认值为 1e-8

对于 optimset,选项名称为 TolCon。请参阅当前选项名称和旧选项名称

LinearSolver

算法内部线性求解器的类型:

  • 'auto'(默认值)- 如果 H 矩阵为稀疏矩阵,则使用 'sparse',否则使用 'dense'

  • 'sparse' - 使用稀疏线性代数。请参阅稀疏矩阵

  • 'dense' - 使用稠密线性代数。

'active-set' 算法

ConstraintTolerance

约束违反值容差;正标量。默认值为 1e-8

对于 optimset,选项名称为 TolCon。请参阅当前选项名称和旧选项名称

ObjectiveLimit

容差(停止条件),标量。如果目标函数值低于 ObjectiveLimit 并且当前点可行,则迭代停止,因为问题很可能是无界的。默认值为 -1e20

问题结构体,指定为具有以下字段的结构体:

H

1/2*x'*H*x 中的对称矩阵

f

线性项 f'*x 中的向量

Aineq

线性不等式约束 Aineq*x bineq 中的矩阵

bineq

线性不等式约束 Aineq*x bineq 中的向量

Aeq

线性等式约束 Aeq*x = beq 中的矩阵

beq

线性等式约束 Aeq*x = beq 中的向量
lb由下界组成的向量
ub由上界组成的向量

x0

x 的初始点

solver

'quadprog'

options

使用 optimoptionsoptimset 创建的选项

必需字段有 Hfsolveroptions。在求解时,quadprog 忽略 problem 中上面列出的字段以外的任何字段。

注意

您不能将热启动与 problem 参数结合使用。

数据类型: struct

热启动对象,指定为使用 optimwarmstart 创建的对象。热启动对象包含起点和选项,以及代码生成中的内存大小数据(可选)。请参阅Warm Start Best Practices

示例: ws = optimwarmstart(x0,options)

输出参数

全部折叠

解,以实数向量形式返回。x 是在满足所有边界和线性约束的条件下对 1/2*x'*H*x + f'*x 进行最小化的向量。x 可以是非凸问题的局部最小值。对于凸问题,x 是全局最小值。有关详细信息,请参阅局部最优与全局最优

热启动对象求解,以 QuadprogWarmStart 对象形式返回。解点是 wsout.X

您可以在后续的 quadprog 调用中使用 wsout 作为输入热启动对象。

在解处的目标函数值,以实数标量形式返回。fval1/2*x'*H*x + f'*x 在解 x 处的值。

quadprog 停止的原因,以下表中所述的整数形式返回。

所有算法

1

函数收敛于解 x

0

迭代次数超出 options.MaxIterations

-2

问题不可行。或者,对于 'interior-point-convex',步长小于 options.StepTolerance,但不满足约束。

-3

问题无界。

'interior-point-convex' 算法

2

步长小于 options.StepTolerance,也满足约束。

-6

检测到非凸问题。

-8

无法计算步的方向。

'trust-region-reflective' 算法

4

找到局部最小值;最小值不唯一。

3

目标函数值的变化小于 options.FunctionTolerance

-4

当前搜索方向不是下降方向。无法取得进一步进展。

'active-set' 算法

-6

检测到非凸问题;HAeq 的零空间上的投影不是半正定的。

注意

有时,在问题实际无界时,'active-set' 算法会停止并返回退出标志 0。设置更高的迭代限制也会返回退出标志 0

有关优化过程的信息,以包含下列字段的结构体形式返回:

iterations

执行的迭代次数

algorithm

使用的优化算法

cgiterations

PCG 迭代总数(仅适用于 'trust-region-reflective' 算法)

constrviolation

约束函数的最大值

firstorderopt

一阶最优性的测度

linearsolver

内部线性求解器的类型,'dense''sparse'(仅适用于 'interior-point-convex' 算法)

message

退出消息

在解处的拉格朗日乘数,以包含下列字段的结构体形式返回:

lower

下界 lb

upper

上界 ub

ineqlin

线性不等式

eqlin

线性等式

有关详细信息,请参阅拉格朗日乘数结构体

算法

全部折叠

'interior-point-convex'

'interior-point-convex' 算法尝试遵循严格在约束范围内的路径。它使用预求解模块来消除冗余,并通过求解简单的分量来简化问题。

该算法针对稀疏黑塞矩阵 H 和稠密矩阵有不同的实现。通常,对于大型稀疏问题,稀疏实现更快,对于稠密或小型问题,稠密实现更快。有关详细信息,请参阅interior-point-convex quadprog 算法

'trust-region-reflective'

'trust-region-reflective' 算法基于 [1] 中所述的内部反射牛顿法的子空间信赖域方法。每次迭代都涉及使用预条件共轭梯度法 (PCG) 来近似求解大型线性方程组。有关详细信息,请参阅trust-region-reflective quadprog 算法

'active-set'

'active-set' 算法是一种投影方法,类似于 [2] 中所述的方法。算法不是大型算法;请参阅大规模算法与中等规模算法。有关详细信息,请参阅active-set quadprog 算法

热启动

热启动对象维护先前已求解问题的活动约束列表。求解器将尽可能多地携带活动约束信息来求解当前问题。如果前一个问题与当前问题差异太大,则不会重用任何活动约束集信息。在这种情况下,求解器实际上执行冷启动,以重新构建活动约束列表。

替代功能

App

优化实时编辑器任务为 quadprog 提供可视化界面。

参考

[1] Coleman, T. F., and Y. Li. “A Reflective Newton Method for Minimizing a Quadratic Function Subject to Bounds on Some of the Variables.” SIAM Journal on Optimization. Vol. 6, Number 4, 1996, pp. 1040–1058.

[2] Gill, P. E., W. Murray, and M. H. Wright. Practical Optimization. London: Academic Press, 1981.

[3] Gould, N., and P. L. Toint. “Preprocessing for quadratic programming.” Mathematical Programming. Series B, Vol. 100, 2004, pp. 95–132.

扩展功能

版本历史记录

在 R2006a 之前推出