25.2 二次规划 ¶

Octave 还可以求解二次规划问题，即

min 0.5 x'*H*x + x'*q

满足约束条件

     A*x = b
     lb <= x <= ub
     A_lb <= A_in*x <= A_ub

[x, obj, info, lambda] = qp (x0, H) ¶

[x, obj, info, lambda] = qp (x0, H, q) ¶

[x, obj, info, lambda] = qp (x0, H, q, A, b) ¶

[x, obj, info, lambda] = qp (x0, H, q, A, b, lb, ub) ¶

[x, obj, info, lambda] = qp (x0, H, q, A, b, lb, ub, A_lb, A_in, A_ub) ¶

[x, obj, info, lambda] = qp (…, options) ¶

求解一个二次规划（QP）问题。

求解如下定义的二次规划问题：

min 0.5 x'*H*x + x'*q
 x

满足约束条件

A*x = b
lb <= x <= ub
A_lb <= A_in*x <= A_ub

使用零空间活动集方法（null-space active-set method）求解。

任何不存在的约束（A、b、lb、ub、A_in、A_lb、A_ub）可以设置为空矩阵（[]）。约束条件 A 和 A_in 是矩阵，每行代表一个单独的约束。其他边界是标量或向量，具体取决于约束的数量。如果初始猜测点是可行的，算法会更快速。

options 是一个结构体，用于指定控制算法的附加参数。目前，qp 识别以下选项："MaxIter"、"TolX"、"AllowSemidefinite"。

"MaxIter" 设置在优化停止前算法的最大迭代次数。默认值为 200。该值必须为正整数。

"TolX" 指定未知变量 x 的终止容差。默认值为 sqrt (eps)，约等于 1e-8。

"AllowSemidefinite" 是一个布尔标志：true 允许半正定问题（Hessian 矩阵有一个或多个特征值为零）；false 要求正定性（所有特征值为正）。默认值为 false。

返回时，x 是最小值点的位置，fval 包含在 x 处的目标函数值。

info

包含算法运行时信息的结构体。定义以下字段：

solveiter

找到解所需的迭代次数。

info

表示求解状态的整数。

0

问题是可行且凸的。找到全局解。

1

问题不是凸的。找到局部解。

2

问题不是凸的且无界。

3

达到最大迭代次数。

6

问题不可行。

另请参阅：sqp。

x = pqpnonneg (c, d) ¶

x = pqpnonneg (c, d, x0) ¶

x = pqpnonneg (c, d, x0, options) ¶

[x, minval] = pqpnonneg (…) ¶

[x, minval, exitflag] = pqpnonneg (…) ¶

[x, minval, exitflag, output] = pqpnonneg (…) ¶

[x, minval, exitflag, output, lambda] = pqpnonneg (…) ¶

最小化 (1/2 * x' * c * x + d' * x) ，满足 x >= 0 约束条件。

c 和 d 必须是实数矩阵，且 c 必须是对称正定矩阵。

x0 是解 x 的可选初始猜测值。

options 是一个选项结构体，用于改变算法的行为（参见 optimset）。pqpnonneg 识别一个选项："MaxIter"。

输出：

x

解矩阵

minval

达到的最小模型值，1/2*xmin'*c*xmin + d'*xmin

exitflag

收敛指示符。0 表示超过迭代次数，因此未达到收敛；>0 表示算法已收敛（该算法稳定，在足够多的迭代次数下会收敛）。

output

包含两个字段的结构体：

• "algorithm"：使用的算法（"nnls"）
• "iterations"：执行的迭代次数。

lambda

拉格朗日乘子。如果这些值非零，则对应的 x 值应为零，表示解被压在一个坐标平面上。该值的大小表示如果在该方向上放宽 x >= 0 约束，残差将改善多少。

另请参阅：lsqnonneg，qp，optimset。