ConicOptimization

ConicOptimization[f,cons,vars]

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

ConicOptimization[…,"prop"]

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

更多信息和选项

  • 锥优化亦称为线性锥优化或线性锥规划.
  • 锥优化包括许多其他形式的优化，包括线性优化、线性分式优化、二次优化、二阶锥优化，半定优化和几何优化.
  • 锥优化是一个凸优化问题，可以使用实数、整数或复数变量全局有效地求解.
  • 锥优化求的是能解原问题的 ：
  • 最小化
    受限于约束条件
    其中
  • 集合 应是维度为 的真凸锥. 常见的 的锥规范和与 (VectorGreaterEqual[{x,0},κj]) 相对应的集合为：
  • {"NonNegativeCone", m}使得 成立的
    {"NormCone", m}使得 TemplateBox[{{{, {{x, _, 1}, ,, ..., ,, {x, _, {(, {m, -, 1}, )}}}, }}}, Norm]<=x_m 成立的
    {"SemidefiniteCone", m}对称正半定矩阵
    "ExponentialCone"使得 成立的
    "DualExponentialCone"使得 或 成立的
    {"PowerCone",α}使得 成立的
    {"DualPowerCone",α}使得 成立的
  • 当目标函数取实数值时，ConicOptimization 在内部将 x in TemplateBox[{}, Complexes]^n 转换为实变量 （其中 ，），对 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凸域或区域元素
  • 对于 ConicOptimization[f,cons,vars]，可在约束条件中包括形式为 parval 的参数方程，以定义在 f 或 cons 中使用的参数，其中 par 不在 vars 中，val 是数值或数值数组. »
  • 原始最小化问题有相关的最大化问题，即拉格朗日对偶问题. 对偶最大值始终小于或等于原始最小值，因此它给出了下限. 对偶最大值点提供了有关原问题的信息，包括最小值对约束条件变化的敏感性. »
  • 锥优化有对偶问题： »
  • 最大化
    受限于约束条件
    其中， 是 的对偶锥
  • 可能的解的属性 "prop" 包括： »
  • "PrimalMinimizer"一个最小化 的变量值列表
    "PrimalMinimizerRules"最小化 的变量值 vars={v1,…}
    "PrimalMinimizerVector"最小化 的向量
    "PrimalMinimumValue"最小值
    "DualMaximizer"最大化 的向量
    "DualMaximumValue"对偶最大值
    "DualityGap"对偶值和原始最优值之间的差
    "Slack"将不等式约束条件转换为等式约束条件的向量
    "ConstraintSensitivity"
    		对约束条件扰动的敏感性
    "ObjectiveVector"线性目标向量
    "ConicConstraints" 标准形式的锥约束条件列表
    "ConicConstraintConeSpecifications" 锥 的规范列表
    "ConicConstraintConeDimensions"{TemplateBox[{Dimensions, paclet:ref/Dimensions}, RefLink, BaseStyle -> {3ColumnTableMod}][kappa_1],...}锥约束条件中锥的维度列表
    "ConicConstraintAffineLists" 锥约束条件中仿射变换的矩阵、向量对列表
    {"prop1","prop2",…} 几个解的属性
  • 可给出以下选项：
  • MaxIterationsAutomatic使用的最大迭代次数
    Method Automatic使用的方法
    PerformanceGoal $PerformanceGoal优化的目标
    Tolerance Automatic内部比较采用的容差
  • 选项 Method->method 可用来指定使用的方法. 可用的方法包括：
  • Automatic自动选择方法
    "SCS"SCS 劈分圆锥求解器
    "CSDP"CSDP 半定优化求解器
    "DSDP"DSDP 半定优化求解器
    "MOSEK"商用 MOSEK 凸优化求解器
    "Gurobi"商用 Gurobi 线性和二次优化求解器
    "Xpress"商业 Xpress 线性和二次优化求解器
  • 计算受限于 MachinePrecision.

范例

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

基本范例  (3)

在二维 "NormCone" 上最小化 ：

最优值是 在由约束条件限定的区域内取最小值的点：

在三角形 和圆盘 的交叉区域内最小化 ：

可视化最小值点的位置：

最小化受约束条件 TemplateBox[{{{, {x, ,, y}, }}}, Norm]<=1,x in Z,y in R 限制的 ：

范围  (35)

基本用法  (11)

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

可用 VectorGreaterEqual:表示几个线性不等式约束条件：

用 v>= 或 \[VectorGreaterEqual] 输入向量不等式符号 ：

用标量不等式表示的等价形式：

使用向量变量 ：

因为 中的 threading，不等式 与 可能并不等价：

为了避免 中无意的 threading，可使用 Inactive[Plus]：

用恒定参数方程避免对 作用时出现不想要的组合：

VectorGreaterEqual 表示相对于的 "NonNegativeCone" 锥不等式：

为了明确指定锥的维度，请使用 {"NonNegativeCone",n}：

求解：

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

用含有 "NormCone" 的锥不等式指定约束条件 ：

求解：

最小化受正半定矩阵约束条件 (x 1; 1 y)_(TemplateBox[{2}, SemidefiniteConeList])0 限制的 :

求解：

用向量变量 和 Indexed[x,i] 指定单个分量：

用 Vectors[n] 在未明确给定时指定向量变量的维度：

用 NonNegativeReals () 指定非负约束条件：

用向量变量 给出等价形式：

整数变量  (4)

用 Integers 指定整数域约束：

用 Vectors[n,Integers] 在向量变量上指定整数域约束：

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

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

复变量  (5)

用 Complexes 指定复变量：

最小化含有复变量和复约束条件 的实目标函数 ：

令 ，将约束条件展开为实的分量，则有：

用复变量和复约束条件求解实目标函数：

用实变量和实约束条件求解同一问题：

将二次约束条件 与厄米特矩阵 和实变量一起使用：

在含有复变量的约束条件 中使用厄米特矩阵 ：

将线性矩阵不等式约束条件 a_(0)+a_(1) x_(1)+a_(2) x_(2)>=_(TemplateBox[{2}, SemidefiniteConeList])0 与厄米特矩阵或实对称矩阵一起使用：

线性矩阵不等式中的变量需为实数，才能使得和依然为厄米特矩阵：

原始模型属性  (4)

在三角形 和圆盘 的相交部分上最小化 ：

获取向量形式的原始最小值点：

获取最小值：

绘制解：

提取目标向量：

提取锥约束条件：

提取锥约束条件中的锥规范 ：

提取锥约束条件中的锥维度 ：

提取锥约束条件中的仿射变换列表 ：

不等式 在最小值点 处的松弛向量由 给出：

提取最小值点和锥约束条件中的仿射变换列表：

验证松弛向量满足 aj.x*+bj-sj=0 时 s={s0,…,sk}：

一些作者将标准形式的圆锥优化问题定义为在满足 和 情况下使 最小化. 要转换为标准格式，请为每个圆锥约束 ，添加一个变量 相应的线性相等约束 ：

提取目标向量，圆锥约束仿射列表和圆锥规格：

松弛约束 与 相同：

形成线性等式约束 ：

解决转换后的标准格式圆锥问题：

"Slack" 属性使您无需进行实际转换即可获取 的值：

对偶模型属性  (3)

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

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

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

这相当于对偶间隙为零. 一般情况下，在最优值点 ：

用从原始问题中提取的系数构建对偶问题：

提取目标向量和约束条件中的仿射变换列表：

获取 和 ：

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

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

可用下式获取 "DualMaximizer"：

对偶最大值点向量分割与对偶锥的个数和维度相匹配：

敏感性属性  (3)

求由约束条件扰动造成的最优值的变化：

计算 "ConstraintSensitivity"：

考虑新的约束条件 a.{x,y}+b+delta_(TemplateBox[{3}, NormConeList])0，其中 为扰动：

估计新的最优值为：

与直接求解扰动后的问题所得结果相比较：

最优值根据灵敏度元素的符号而变化：

在灵敏度为负的元素处，正的扰动将会使最优值减小：

在灵敏度为正的元素处，正的扰动将会使最优值增大：

也可以通过对偶最大值点的负值获取对约束条件的灵敏度：

支持的凸锥  (5)

"NonNegativeCone"  (1)

在正九角形上最小化 ：

在目标函数图上显示最小值点：

显示锥约束条件中使用的锥：

"NormCone"  (1)

在圆盘上最小化 ：

在目标函数图上显示最小值点：

显示锥约束条件中使用的锥：

"SemidefiniteCone"  (1)

最小化 使得 为半正定矩阵：

在目标函数图上显示最小值点：

显示锥约束条件中使用的锥：

"ExponentialCone"  (1)

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

在目标函数图上显示最小值点：

显示锥约束条件中使用的锥：

"PowerCone"  (1)

在范数为 4 的单位圆盘上最小化 ：

在目标函数图上显示最小值点：

显示锥约束条件中使用的锥：

选项  (11)

Method  (8)

"SCS" 使用 splitting conic solver 方法：

"CSDP" 是求解半定问题的内点法：

"DSDP" 是另一种求解半定问题的内点法：

"IPOPT" 是求解非线性问题的内点法：

不同的方法具有不同的默认容差，这会影响准确性和精度：

计算精确解和近似解：

"SCS" 的默认容差为 ：

"CSDP"、"DSDP" 和 "IPOPT" 的默认容差为 ：

如果指定了方法 "SCS"，将使用默认容差为 10-3 的 SCS 库：

使用容差为 10-6 的 "SCS" 方法求解下面的问题：

对于半定约束条件使用 "CSDP" 或 "DSDP" 方法：

用 "CSDP" 方法求解问题：

用 "DSDP" 方法求解问题：

在 "CSDP" 和 "DSDP" 方法不适用的情况下使用 "IPOPT" 方法获取准确的解：

"IPOPT" 给出的结果比 "SCS" 更准确，但是通常要慢一些：

与 "SCS" 方法所用时间相比较：

PerformanceGoal  (1)

PerformanceGoal 选项的默认值为 $PerformanceGoal：

用 PerformanceGoal"Quality" 获取更准确的结果：

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

比较用时：

"Speed" 设置给出的结果的准确性较低：

Tolerance  (2)

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

用 Minimize 计算精确最小值：

计算 Tolerance 设为不同值时最小值的误差：

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

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

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

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

应用  (29)

基本模型转换  (13)

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

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

在圆心位于 、半径为 的圆盘上最小化 . 将目标函数 转换为线性函数 ，额外限制条件为 ，等价于 ：

也可用 Norm 表示圆盘约束条件：

在正五边形上最小化 . 用 将目标函数转换为线性函数，额外限制条件为 ：

最小化 . 通过使用辅助变量 ，目标函数被转换为最小化受约束条件 限制的 ：

最小化受约束条件 限制的 . 通过使用两个辅助变量 ，将问题转换为最小化受约束条件 限制的：

最小化 . 通过使用辅助变量 ，将问题转换为最小化受约束条件 限制的 ：

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

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

在圆心位于 、半径为 的圆盘上最小化 . 通过使用辅助变量 ，目标函数被转换为最小化受额外约束条件 限制的 ：

当且仅当 {t,1,x+y}_(TemplateBox[{}, ExponentialConeString])0 时，约束条件 等价于指数锥约束条件 ：

在圆心位于 、半径为 的圆盘上最小化 TemplateBox[{{x, +, y}}, Abs]^(1.5). 通过使用辅助变量 ，将问题转换为最小化受约束条件 TemplateBox[{{x, +, , y}}, Abs]^(1.5)<=t 限制的 ：

约束条件 TemplateBox[{{x, +, , y}}, Abs]^(1.5)<=t 等价于 TemplateBox[{{x, +, y}}, Abs]<=t^((1/1.5))<==> TemplateBox[{{x, +, y}}, Abs]<=t^((1/1.5))1^((1-1/1.5)). 可用 "PowerCone" 通过 {t,1,x+y}_(TemplateBox[{{1, /, 1.5}}, PowerConeList])0 来表示：

求最小化 的 ：

通过使用辅助变量 ，将问题转换为最小化受约束条件 限制的 ：

可用 "PowerCone" 约束条件来表示. 因为当且仅当 sum_(i=1)^n(TemplateBox[{{{{a, _, i}, x}, -, {b, _, i}}}, Abs]^(1.5))/(t^(1.5-1))<=t 时 ||a.x-b||_(1.5)= (sum_(i=1)^nTemplateBox[{{{{a, _, i}, x}, -, {b, _, i}}}, Abs]^(1.5))^(1/1.5)<=t，用 限制 (TemplateBox[{{{{a, _, i}, x}, -, {b, _, i}}}, Abs]^(1.5))/(t^(1.5-1))，其中 给出 {s_i,t,a_ix-b_i}_(TemplateBox[{{1, /, 1.5}}, PowerConeList])0, i=1,...,n：

求最小化对称矩阵的最大特征值的 ，该特征值线性依赖于决策变量 ，. 可将该问题表述为线性矩阵不等式，因为 等价于 ，其中 是 的第 个特征值. 对于线性矩阵函数 ：

可用正交矩阵 将实对称矩阵 对角化，以使得 . 因而当且仅当 时 . 由于任一 ，取 ，，因而当且仅当 时 . 进行数值仿真以表明这些式子是等价的：

得到的问题：

运行蒙特卡罗仿真以检查结果的合理性：

最小化受约束条件 限制的 ，当 时假定 . 通过使用辅助变量 ，目标函数变为最小化 以使得 :

检查 是否意味着 ：

舒尔补条件表明如果 ，则当且仅当 时分块矩阵 . 因此当且仅当 时 . 用 Inactive Plus 来构建约束条件以避免 threading：

对于二次集合 ，其中包括椭球、二次锥体和抛物面，确定 是否成立， 其中 为对称矩阵， 为向量， 为标量：

假定集合 i 为全维 (full dimensional) 集合，S-procedure 表明当且仅当有一些非负数 存在使得 成立时 才成立. 图示有非负数 存在：

由于 λ≥0，因而有 ：

数据拟合问题  (5)

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

通过使用辅助变量 ，转换后的目标函数为最小化受约束条件 限制的 ：

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

用 DesignMatrix 构建矩阵：

定义约束条件，以便第一个和最后一个点必须位于曲线上：

通过最小化 求系数 . 通过使用辅助变量 ，转换后的目标函数为最小化受约束条件 限制的 ：

比较拟合曲线与数据：

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

以 为基础拟合数据. 插值函数为 ：

由于 ，因此使用辅助变量 . 问题被转换为最小化受约束条件 限制的 ：

可视化拟合曲线：

比较插值函数与参考函数：

用平方和多项式 表示给定多项式 ：

目标是求使得 成立的 ，其中 为单项式向量：

构建对称矩阵 ：

求 与 的多项式系数，并确保它们是相等的：

求 的元素：

二次项 ，其中 是对 进行 Cholesky 分解所得的下三角矩阵：

比较平方和多项式与给定多项式：

通过最小化 ||a.lambda-b||+sigma TemplateBox[{lambda, 1}, Norm2]（ 为复数）求复数数据的 正则化拟合：

用 DesignMatrix 构建矩阵 ，对于基 ：

求系数 ：

令 为被定义成是 的实部和虚部的函数的拟合：

可视化 的实部：

可视化 的虚部：

几何问题  (5)

求圆心位于 和 、半径为 1 的两个圆盘之间的最小距离. 令 为第一个圆盘上的点. 令 为第二个圆盘上的点. 目标是最小化 . 通过使用辅助变量 ，转换后的目标函数为最小化受约束条件 限制的 ：

图示两个点的位置：

辅助变量 给出了两个点之间的距离：

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

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

图示该包含球：

可用 BoundingRegion 高效求出最小包含球：

找到分隔两个非相交凸多边形的平面：

令 为 上的一个点. 令 为 上的一个点. 目标是最小化 . 通过使用辅助变量 ，转换后的目标函数为最小化受约束条件 限制的 ：

根据分隔超平面定理，与约束条件 相关的对偶问题将给出超平面的法线：

与 "NormCone" 相关的对偶为：

可用以下方式构建超平面：

可视化分隔两个多边形的平面：

求参数化为 的可被放进凸多边形的面积最大的椭圆：

凸多边形的每个线段可被表示为半平面 相交的地方. 提取线性不等式：

对半平面应用参数化给出 . 项 . 因此，约束条件为：

最小化面积等价于最小化 ，相当于最小化 ：

将参数化椭圆转换为显式形式 ：

求凸多边形的 analytic center. analytic center 是能最大化到限制边界的距离的乘积的点：

凸多边形的每个线段可被表示为半平面 相交的地方. 提取线性不等式：

目标是最大化 . 对目标函数取 并取负，转换后的目标函数为 ：

通过使用辅助变量 ，转换后的目标函数为最小化受约束条件 限制的 ：

可视化中心的位置：

分类问题  (3)

求分隔两组点 和 的直线 ：

对于此分隔问题，第 1 组点必须满足 ，第 2 组点必须满足 ：

目标是最小化 ，它给出的是 和 之间距离的两倍. 通过使用辅助变量 ，目标函数被转换为约束条件 ：

分隔线为：

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

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

对于此分隔问题，第 1 组必须满足 ，第 2 组必须满足 ：

通过最小化 找出分隔多项式. 通过使用辅助变量 ，转换后的目标函数为最小化受额外约束条件 限制的 ：

分隔两组点的多项式为：

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

将给定的点集 分成不同的组. 可通过最小化 找出每组的中心 来完成，其中 是给定的局部核， 是给定的惩罚参数：

核 为使得 ，否则 成立的 -近邻 () 函数. 对于此问题，选择 ：

通过使用辅助变量 ，目标函数被转换为最小化受约束条件 限制的 ：

求各组的中心：

每个数据点都有一个相应的中心. 属于同一组的数据将具有相同的中心值：

提取并绘制各组点：

最优控制问题  (1)

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

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

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

可用 Indexed 指定初始约束条件 ：

通过使用辅助变量 ，目标函数被转换为最小化受约束条件 限制的 ：

将离散化结果转换为 InterpolatingFunction：

绘制控制变量：

绘制状态变量. 状态变量尝试并跟踪函数 ：

设施选址问题  (1)

求服务位于 的客户所需的各种基站 的位置和范围 ：

每个基站消耗的功率与其范围成正比，由 给出. 目的是最大程度地降低功耗：

令 为决策变量，如果客户 被基站 覆盖，则用 表示：

每个基站必须位于能覆盖一些客户的位置：

每个基站可覆盖多个客户：

每个基站都有最小和最大覆盖范围：

收集所有变量：

给出基站的位置及覆盖范围：

提取基站的位置和范围：

可视化基站相对于客户所处地点的位置和范围：

投资组合优化  (1)

找到资本 的分布以投资六只股票，以在最大程度地降低风险的同时最大化回报：

收益由 给出，其中， 是每只股票的预期收益值的向量：

风险由 给出； 是风险规避参数，且 ：

目的是在使特定风险规避参数的风险最小化的同时，最大化回报率：

由股票买卖引起的对股票市场价格的影响可以通过 建模，该模型由幂锥建模，使用题词转换：

权重 必须都大于 0，并且权重加上市场影响成本必须相加为 1：

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

在 范围内的最优 给出了收益和风险之间权衡的上限：

计算指定数量的风险规避参数的权重：

通过考虑市场成本，可以获得低风险规避的分散投资组合，但是当风险规避较高时，由于购买分散程度较低的股票，市场影响成本占主导地位：

属性和关系  (8)

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

在可行区域上绘制目标函数和最小值：

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

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

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

SemidefiniteOptimization 是 ConicOptimization 的特例：

SecondOrderConeOptimization 是 ConicOptimization 的特例：

QuadraticOptimization 是 ConicOptimization 的特例：

通过使用辅助变量 ，最小化受额外约束条件 限制的 ：

LinearOptimization 是 ConicOptimization 的特例：

可能存在的问题  (6)

最优点的约束条件应满足容差：

通常可以用 Tolerance 选项控制对约束条件的违反：

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

最小值点为 Indeterminate:

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

最小值点为 Indeterminate：

缩放不当的问题会产生误差较大的结果：

正确的结果是：

在将 缩放 10-10 后，在数学上与以下问题等价：

、 的位于 5*10-10 ±10-6 上下的结果将符合容差 10-6，当去掉缩放后可产生的最大错误为：

你可以解决前面的缩放问题或尝试收紧默认容差：

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

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

即便理论上两边都是实数，只使用 Less 也是不可行的：

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

文本

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

CMS

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

APA

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

BibTeX

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

BibLaTeX

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