QuadraticOptimization

QuadraticOptimization[f,cons,vars]

求可最小化受线性约束条件 cons 限制的二次目标函数 f 的变量 vars 的值.

QuadraticOptimization[{q,c},{a,b}]

求可最小化受线性不等式约束条件 约束的二次目标函数 的向量 .

QuadraticOptimization[{q,c},{a,b},{aeq,beq}]

包括线性不等式约束条件 .

QuadraticOptimization[{q,c},…,{dom1,dom2,…}]

将 视为位于域 domi 中，其中 domi 为 Integers 或 Reals.

QuadraticOptimization[…,"prop"]

指定应返回解的属性 "prop".

更多信息和选项

  • 二次优化也称为二次规划 (QP)、混合整数二次规划 (MIQP) 或线性约束二次优化.
  • 二次优化通常用于诸如参数拟合、投资组合优化和几何距离之类的问题.
  • 二次优化是凸优化问题，可用实数、整数或复数变量高效地进行全局求解.
  • 二次优化求的是能解原始问题的 ： »
  • 最小化
    受限于约束条件
    其中
  • 空间 由对称半正定矩阵组成.
  • 混合整数二次优化求能解以下问题的 和 ：
  • 最小化
    受限于约束条件
    其中(q_(rr) q_(ri); TemplateBox[{{q, _, {(, {r, , i}, )}}}, Transpose] q_(ii)) in S_+^n,c_r in R^(n_r),c_i in R^(n_i),a_r in R^(mxn_r),a_i in R^(mxn_i),b in R^m,a_(eq_r) in R^(kxn_r),a_(eq_i) in R^(kxn_i)b_(eq) in R^k
  • 当目标函数取实数值时，QuadraticOptimization 在内部将 x in TemplateBox[{}, Complexes]^n 转换为实变量 （其中 ，）进行求解.
  • 变量指定 vars 应该是一个列表，其中的元素按以下形式给出变量：
  • v名称为 的变量，维度由推断而得
    v∈Reals实标量变量
    v∈Integers整数标量变量
    v∈Complexes复标量变量
    v∈ℛ限制在几何区域 内的向量变量
    v∈Vectors[n,dom]位于 或 的向量变量
    v∈Matrices[{m,n},dom]位于 或 的矩阵变量
  • 可用以下形式指定约束条件 cons：
  • LessEqual标量不等式
    GreaterEqual标量不等式
    VectorLessEqual向量不等式
    VectorGreaterEqual向量不等式
    Equal向量或标量等式
    Element凸域或区域元素
  • 对于 QuadraticOptimization[f,cons,vars]，可在约束条件中包括形式为 parval 的参数方程，以定义在 f 或 cons 中使用的参数，其中 par 不在 vars 中，val 是数值或数值数组.
  • 可用以下方式指定目标函数：
  • q
    {q,c}
    {{q_(f)},c}1/2(q_f.x).(q_f.x)+c.x=1/2(x.TemplateBox[{{q, _, f}}, Transpose]).(q_f.x)+c.x
    {{q_(f),c_(f)},c}1/2(c_f+q_f.x).(c_f+q_f.x)+c.x=1/2(x.TemplateBox[{{q, _, f}}, Transpose]+c_f).(q_f.x+c_f)+c.x
  • 在因式形式中， ，.
  • 原始最小化问题有相关的最大化问题，即拉格朗日对偶问题. 对偶最大值始终小于或等于原始最小值，因此它给出了下限. 对偶最大值点提供了有关原问题的信息，包括最小值对约束条件变化的敏感性.
  • 下面给出了目标函数为 的二次优化的拉格朗日对偶问题： »
  • 最大化
    受限于约束条件
    其中
  • 对于因式形式的二次目标函数 1/2(x.TemplateBox[{{q, _, f}}, Transpose]+c_f).(q_f.x+c_f)+c.x，对偶问题也可以表示为：
  • 最大化
    受限于约束条件
    其中
  • 因式形式的对偶向量 和非因式形式的对偶向量 之间的关系为 .
  • 对于二次优化，如果 为半正定矩阵，则强对偶性成立. 这意味着如果原始最小化问题的解存在，则对偶最大化问题的解也存在，并且对偶最大值等于原始最小值.
  • 可能的解的属性 "prop" 包括：
  • "PrimalMinimizer"一个最小化目标函数的变量值列表
    "PrimalMinimizerRules"最小化 的变量值 vars={v1,…}
    "PrimalMinimizerVector"最小化 的向量
    "PrimalMinimumValue"最小值
    "DualMaximizer"最大化
    • 的向量
    "DualMaximumValue"对偶最大值
    "DualityGap"对偶值和原始最优值之间的差（由于强对偶性，差应为 0）
    "Slack"
    		约束松弛向量
    "ConstraintSensitivity"
    		对约束条件扰动的敏感性
    "ObjectiveMatrix"二次目标矩阵
    "ObjectiveVector"线性目标向量
    "FactoredObjectiveMatrix"因式形式的目标函数内的矩阵
    "FactoredObjectiveVector"因式形式的目标函数内的向量
    "LinearInequalityConstraints"线性不等式约束矩阵和向量
    "LinearEqualityConstraints"线性等式约束矩阵和向量
    {"prop1","prop2",…} 解的几个属性
  • 对偶最大值点的分量 是 和 的函数，由 给出.
  • 可给出以下选项：
  • MaxIterationsAutomatic使用的最大迭代次数
    Method Automatic使用的方法
    PerformanceGoal $PerformanceGoal优化的目标
    Tolerance Automatic内部比较采用的容差
    WorkingPrecision MachinePrecision内部计算使用的精度
  • 选项 Method->method 可用来指定使用的方法. 可用的方法包括：
  • Automatic自动选择方法
    "COIN"COIN 二次规划求解器
    "SCS"SCS 劈分圆锥求解器
    "OSQP"OSQP 二次问题的算子分裂求解器
    "CSDP"CSDP 半正定优化求解器
    "DSDP"DSDP 半正定优化求解器
    "PolyhedralApproximation"用多面体近似目标上境图 (objective epigraph)
    "MOSEK"商用 MOSEK 凸优化求解器
    "Gurobi"商用 Gurobi 线性和二次优化求解器
    "Xpress"商用 Xpress 线性和二次优化求解器

范例

打开所有单元关闭所有单元

基本范例  (3)

最小化受约束条件 限制的 ：

最优点位于由约束条件定义的区域内 为最小值处：

最小化受等式约束条件 和不等式约束条件 限制的 ：

定义目标函数为 ，约束条件为 和 ：

用矩阵-向量输入求解：

最优点位于 的等值曲线与等式约束条件相切处：

最小化受约束条件 限制的 ：

使用等价的矩阵-向量表示：

范围  (26)

基本用法  (8)

最小化受约束条件 限制的 ：

用解的属性 "PrimalMinimumValue" 获取最小化值：

最小化受约束条件 限制的 ：

用解的属性获取最小化值和最小化向量：

最小化受约束条件 限制的 ：

定义目标函数为 ，约束条件为 ：

用矩阵-向量输入求解：

最小化受等式 和不等式 约束条件限制的 ：

定义目标函数为 ，约束条件为 和 ：

用矩阵-向量输入求解：

最小化受约束条件 限制的 ：

定义目标函数为 ，约束条件为 ：

用矩阵-向量输入求解：

最小化受约束条件 限制的 ：

用 VectorGreaterEqual (\[VectorGreaterEqual]) 和 VectorLessEqual (\[VectorLessEqual]) 指定约束条件 ：

最小化受约束条件 限制的 . 使用向量变量和常参数方程：

最小化受约束条件 限制的 . 用 NonNegativeReals 指定约束条件 ：

整数变量  (4)

用 Integers 指定整数域约束条件：

用 Vectors[n,Integers] 指定向量变量的整数域约束条件：

用 NonNegativeIntegers () 指定非负整数域约束条件：

用 NonPositiveIntegers () 指定非正整数域约束条件：

复变量  (3)

用 Complexes 指定复变量：

在含有实变量的目标函数 中使用 Hermitian 矩阵 ：

在含有复变量的目标函数 (1/2)Inactive[Dot][Conjugate[x],q,x] 中使用 Hermitian 矩阵 ：

原始模型属性  (4)

最小化受约束条件 限制的 ：

用 "PrimalMinimizer" 获取向量输出：

用 "PrimalMinimizerRules" 获取基于规则的结果：

用 "PrimalMinimumValue" 获取优化的最小值：

用符号输入获取原始最小值：

提取优化问题的矩阵-向量输入：

用矩阵-向量形式求解：

通过添加目标常量获取符号原始值：

求与最小化问题相关的不等式和等式的松弛向量：

获取最小值和约束矩阵：

不等式约束条件 的松弛向量为满足 的向量 ：

等式约束条件 的松弛向量为满足 的向量 ：

等式的松弛向量 通常为零向量：

对偶模型属性  (3)

最小化受约束条件 和 限制的 ：

对偶问题为最大化受约束条件 限制的 ：

由于强对偶性，原始最小值和对偶最大值相同：

所以对偶间隙为零. 一般情况下，在最优值点 ：

用从原始问题中提取的约束矩阵构建对偶问题：

提取目标和约束矩阵及向量：

对偶问题是最大化受约束条件 限制的 ：

用解的属性直接获取对偶最大值：

用解的属性直接获取对偶最大值点：

敏感性属性  (4)

用 "ConstraintSensitivity" 求由约束松弛造成的最优值的变化：

第一个向量是不等式敏感性，第二个是等式敏感性：

考虑新的约束条件 ，其中 为松弛向量：

下面给出了新的近似最优值：

与直接求解松弛问题相比较：

每种敏感性都与不等式或等式约束条件相关：

提取约束条件：

不等式约束条件及相关的敏感性：

等式约束条件及相关的敏感性：

约束松弛引起的最优值变化与灵敏度值成正比：

计算最小值和约束条件敏感性：

如果敏感性为零，放宽约束条件不会改变最优值：

负的敏感性将会使最优值减小：

正的敏感性将会使最优值增大：

"ConstraintSensitivity" 与问题的对偶最大值点相关：

不等式敏感性 满足 ，其中 为对偶不等式的最大值点：

等式敏感性 满足 ，其中 为对偶等式的最大值点：

选项  (12)

Method  (5)

方法 "COIN" 使用 COIN 库：

"CSDP" 和 "DSDP" 简化为半定优化：

"SCS" 简化为锥优化：

"PolyhedralApproximation" 用线性约束条件近似目标：

对于最小二乘型二次优化问题，"CSDP" 和 "DSDP" 比 "COIN" 或 "SCS" 慢：

用 "COIN" 方法求解最小二乘型问题：

用 "CSDP" 方法求解：

对于最小二乘类二次优化问题，"CSDP","DSDP" 和 "PolyhedralApproximation" 比 "COIN" 或or "SCS" 方法慢：

用 "COIN" 方法求解最小二乘问题：

用 "CSDP" 方法求解问题：

用 "PolyhedralApproximation" 方法求解问题：

对于具有多个最优解的问题，不同的方法可能会给出不同的结果：

最小化凹函数只能使用 Method"COIN"：

不能使用其他方法，因为它们需要对目标矩阵进行因式分解：

PerformanceGoal  (1)

使用 "Quality" 设置以更多的计算时间为代价获得更准确的结果：

用 "Speed" 可更快获得结果，但要以质量为代价：

Tolerance  (2)

Tolerance 的设置越小给出的结果越精确：

求使用不同的 Tolerance 设置时计算值和精确最小值之间的误差：

可视化最小值误差随容差的变化：

Tolerance 的设置越小给出的答案越精确，但通常情况下要花费更多的时间进行计算：

小的容差将花费更多时间进行计算：

更严格的容差给出更精确的答案：

WorkingPrecision  (4)

MachinePrecision 是 QuadraticOptimization 中 WorkingPrecision 选项的默认设置：

如果设置 WorkingPrecisionAutomatic，QuadraticOptimization 从输入推断要使用的精度：

QuadraticOptimization 可用任意精度的数字计算结果：

如果指定的精度小于输入参数的精度，则会发出一条消息：

如果无法算出高精度结果，发出一条消息，同时返回 MachinePrecision 的结果：

应用  (29)

基本模型转换  (7)

最大化受约束条件 限制的 . 对目标函数取负求解最大化问题：

对原始最小值取负获取相应的最大值：

通过将目标函数转换为 最小化 ：

展开 ，构建目标函数：

由于 QuadraticOptimization 最小化 ，矩阵乘以 2：

获得的原始函数的最小值为 ：

QuadraticOptimization 可直接进行此转换. 用 Inactive 构建目标函数以避免被运行：

最小化受约束条件 限制的 . 将目标函数转换为 ，对问题进行求解：

用转换 获取原始最小值：

最小化受约束条件 限制的 . 可将约束条件转换为 ：

最小化受约束条件 限制的 . 约束条件 可被解释为 . 根据每个约束条件对问题进行求解：

最优解为两个解中最小的那个：

最小化受约束条件 限制的 ，其中 是一个非递减函数，因而可代之以最小化 . 对于两个问题，原始最小值点 将保持不变. 考虑最小化受约束条件 限制的 ：

通过将函数 应用于原始最小值即可获得真正的最小值：

最小化 ，约束条件为 ：

由于 ，只有当原始最小值大于 0 时，所得解才是真正的解. 通过将函数 应用于原始最小值即可获得真正的最小值：

数据拟合问题  (7)

通过最小化 求离散数据的线性拟合：

用 DesignMatrix 构建因式形式的二次矩阵：

求曲线的系数：

将拟合结果与数据比较：

通过最小化 求离散数据的二次拟合：

用 DesignMatrix 构建因式形式的二次矩阵：

求二次曲线的系数：

将拟合结果与数据比较：

拟合二次曲线离散数据，使数据的第一个和最后一个点位于曲线上：

用 DesignMatrix 构建因式形式的二次矩阵：

两个等式约束条件为：

求曲线的系数：

将拟合结果与数据比较：

用基函数 求噪声数据的插值函数：

插值函数应为 ：

求插值函数的系数：

将拟合结果与数据比较：

最小化受约束条件 限制的 ：

与 不受条件约束的最小值比较：

基数约束最小二乘：最小化 ，使得 最多有 个非零元素：

令 为决策向量，如果 ，则 非零. 决策的约束条件为：

为了模拟约束条件 时 ，选择一个大的常数 ，使得 ：

求解基数约束最小二乘问题：

也可以用 Fit 通过 正则化更高效地完成子集选择. 首先，找到最多使用 个基函数的正则化参数的范围：

求 正则化拟合中的非零项：

求只含有这些基本项的拟合：

从候选函数集中找到最佳函数子集，以近似给定数据：

近似函数为 ：

在最后的近似中最多使用 5 个基函数：

与未选择的函数关联的系数必须为零：

求最佳函数子集：

将所得近似与给定数据相比较：

分类问题  (2)

求分隔两组 3D 点 和 的平面 ：

对于此分隔问题，第 1 组必须满足 ，第 2 组必须满足 . 通过最小化 找出超平面：

平面 和 之间的距离为 ：

分隔两组点的平面为：

绘制分隔两个数据集的平面：

求分隔两组 3D 点 和 的二次多项式：

用 DesignMatrix 构建两组点的二次多项式数据矩阵：

对于此分隔问题，第 1 组必须满足 ，第 2 组必须满足 . 通过最小化 找出分隔曲面：

分隔两组点的多项式为：

绘制分隔两个数据集的多项式：

几何问题  (3)

求距位于平面 和 上的点 最近的点 ：

求通过最小化 求距 最近的点. 构建目标函数时使用 Inactive Plus：

求两个凸多面体之间的距离：

用连接它们的线显示距离最近的点：

求包围给定区域的最小包含球的半径 和圆心 ：

原始最小化问题是最小化受 限制的 . 该问题的对偶问题是最大化受 限制的 ：

求解对偶最大化问题：

最小包含球的圆心为 ：

最小包含球的半径是最大值的 Sqrt：

可视化最小包含球：

使用 BoundingRegion 可有效地找到最小包含球：

投资问题  (3)

求要购买的四只股票的数量，以便获得至少 $1000 的股息并最小化风险. 与股票相关的预期收益值和协方差矩阵 为：

四只股票的单位价格为 $1. 每只股票最多可分配 $2500：

投资必须至少产生 $1000 的回报：

不能购买负的股票：

通过最小化 给出的风险，可以算出购买各个股票的总投资：

获取至少 $1000 回报的总投资为：

求要购买的有卖空期权的四只股票的数量，以便获得至少 $1000 的股息并最小化风险：

资金约束条件和投资回报约束条件为：

卖空期权允许卖出股票. 通过最小化目标函数 给出的风险，可以算出最佳买入/卖空股票的数量：

第二只股票可以卖空. 因卖空而获得至少 $1000 的总投资是：

如果不进行卖空，所需初始投资额将大幅增加：

求从 20 只候选股票中选取六只股票的最佳组合，最小化风险的同时最大化回报：

设在股票 上的投资占总投资的百分比为 . 收益由 给出，其中 是由每只股票的预期收益值组成的向量：

设 为决策变量，如果 ，则买入该股票. 要选择六只股票：

投资的百分比 必须大于 0 且总和为 1：

求最小化由 给出的风险、最大化收益的最佳股票组合：

最佳股票组合为：

投入各个股票的投资百分比为：

投资组合优化  (1)

求如何在六只股票之间分配资本，在最大程度地降低风险的同时最大化回报：

设在股票 上的投资占总投资的百分比为 . 回报为 ，其中 是由每只股票的预期回报值组成的向量：

风险由 给出， 为风险规避参数：

目标是最大化收益，同时最大程度地降低特定风险规避参数 的风险：

投资的百分比 必须大于 0 且总和为 1：

为一系列风险规避参数计算收益和相应的风险：

范围 内最佳的 给出在收益和风险之间折衷的上限：

计算指定数量的风险规避参数的投资百分比 ：

增大风险规避参数 会使购买的股票多样化以降低风险：

增大风险规避参数 会使投资预期回报值下降：

轨迹优化问题  (2)

最小化受约束条件 限制的 . 可使用梯形法则近似最小化函数积分. 离散化的目标函数为 ：

可用有限差分离散化约束条件 ：

可用 Indexed 函数表示约束条件 ：

可用有限差分离散化约束条件，只使用了第一行和最后一行：

解离散化的轨迹问题：

将离散化结果转换为 InterpolatingFunction：

将结果与解析解进行比较：

求两点之间的最短路径，同时避开障碍物. 指定障碍物：

提取形成凸障碍物的半空间：

指定路径的起始点：

可用 个点离散化路径. 令 表示位置向量：

目标是最小化 . 令 . 目标函数被转化为 ：

指定终点约束条件：

相邻两点之间的距离不应太大：

如果 中至少有一个元素小于零，则点 在障碍物之外. 为了强制实行该约束条件，令 为决策变量， 为 的第 个元素，使得 ，则 和 足够大，可满足 ：

求绕开障碍物的最短路径：

提取并展示路径：

为了避免与障碍物的边相交，可对区域进行放大并再次求解：

获取绕开障碍物的新约束条件：

求解新问题：

提取并展示新的路径：

最优控制问题  (2)

最小化受约束条件 和 限制的 ：

可使用梯形法对积分进行离散化：

. 目标函数为：

可用有限差分离散化 中的时间导数：

可用 Indexed 指定 end-condition 约束条件 ：

求解已被离散化的问题：

将离散化结果转换为 InterpolatingFunction：

绘制控制变量：

绘制状态变量：

最小化受约束条件 和 限制的 ，其中控制变量 ：

可使用梯形法对积分进行离散化：

. 目标函数为：

可用有限差分离散化 中的时间导数：

可用 Indexed 指定 end-condition 约束条件 ：

控制变量 的约束条件为：

求解已被离散化的问题：

将离散化结果转换为 InterpolatingFunction：

控制变量被限制在 和 5 之间：

绘制状态变量：

序列二次优化  (2)

最小化受非线性约束条件 限制的非线性函数 . 可将 近似为 ，将约束条件 近似为 来进行最小化. 由此我们得到一个可以进行迭代求解的二次最小化问题. 考虑 f=1-Exp((Sin(x)^2+Sin(y-1/2)^2)^2) 和 的情况：

最小化函数的梯度和海森矩阵是：

约束条件的梯度为：

子问题是通过最小化受约束条件 限制的 求得 ：

从初始猜测 开始迭代. 下一个迭代是 ，其中 是确保始终满足约束条件的步长：

可视化结果的收敛性. 用绿点表示最终结果：

最小化受约束条件 x+Sin(y)>=1,y<=2, x y=2 限制的 f(x,y)=sqrt(1+x^2+Cos(y/2)^2)：

最小化函数的梯度和海森矩阵是：

约束条件的梯度为：

子问题是最小化受约束条件 和 限制的 ：

从初始猜测 开始迭代：

可视化结果的收敛性. 用绿点表示最终结果：

属性和关系  (9)

QuadraticOptimization 给出目标函数的全局最小值：

可视化目标函数：

最小点可以位于可行区域的内部或边界：

Minimize 给出二次优化问题的全局精确结果：

NMinimize 可用全局方法获得近似结果：

FindMinimum 可用局部方法获得近似结果：

LinearOptimization 是 QuadraticOptimization 的特例：

在矩阵-向量形式中，二次项被设为 0：

SecondOrderConeOptimization 是 QuadraticOptimization 的推广：

使用辅助变量 ，并最小化受附加约束条件 限制的 ：

SemidefiniteOptimization 是 QuadraticOptimization 的推广：

使用辅助变量 ，并最小化受附加约束条件 限制的 ：

ConicOptimization 是 QuadraticOptimization 的推广：

使用辅助变量 ，并最小化受附加约束条件 限制的 ：

可能存在的问题  (6)

对于某些方法，可能无法满足用严格的不等式指定的约束条件：

原因是 QuadraticOptimization 求解的是 ：

空集或不可行问题的最小值被定义为 ：

最小值点为 Indeterminate：

无界集或无界问题的最小值是 ：

最小值点为 Indeterminate：

对于符号输入，某些解的属性不可用：

混合整数问题的对偶相关解属性可能不可用：

需使用向量不等式指定含有复数的约束条件：

只使用 GreaterEqual 是不可行的：

Wolfram Research (2019)，QuadraticOptimization，Wolfram 语言函数，https://reference.wolfram.com/language/ref/QuadraticOptimization.html （更新于 2020 年）.

文本

Wolfram Research (2019)，QuadraticOptimization，Wolfram 语言函数，https://reference.wolfram.com/language/ref/QuadraticOptimization.html （更新于 2020 年）.

CMS

Wolfram 语言. 2019. "QuadraticOptimization." Wolfram 语言与系统参考资料中心. Wolfram Research. 最新版本 2020. https://reference.wolfram.com/language/ref/QuadraticOptimization.html.

APA

Wolfram 语言. (2019). QuadraticOptimization. Wolfram 语言与系统参考资料中心. 追溯自 https://reference.wolfram.com/language/ref/QuadraticOptimization.html 年

BibTeX

@misc{reference.wolfram_2024_quadraticoptimization, author="Wolfram Research", title="{QuadraticOptimization}", year="2020", howpublished="\url{https://reference.wolfram.com/language/ref/QuadraticOptimization.html}", note=[Accessed: 22-November-2024 ]}

BibLaTeX

@online{reference.wolfram_2024_quadraticoptimization, organization={Wolfram Research}, title={QuadraticOptimization}, year={2020}, url={https://reference.wolfram.com/language/ref/QuadraticOptimization.html}, note=[Accessed: 22-November-2024 ]}