ConvexOptimization

ConvexOptimization[f,cons,vars]

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

ConvexOptimization[,"prop"]

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

更多信息和选项

  • 凸优化是受凸约束条件限制的凸函数的全局非线性最优化. 对于凸问题,可以找到全局解.
  • 凸优化包括许多其他形式的优化,包括线性优化、线性分数优化、二次优化、二阶锥优化、半正定优化和锥优化等.
  • 如果 是凹函数,则 ConvexOptimization[-g,cons,vars] 将使 g 最大化.
  • 凸优化求的是可解下列问题的
  • 最小化
    受限于约束条件
    其中
  • 可将形为 的等式约束条件包括在 cons 中.
  • 混合整数凸优化求的是 ,以求解下列问题:
  • 最小化
    受限于约束条件
    其中
  • 当目标函数为实值时,ConvexOptimization 通过内部转换为实数变量 来求解 x in TemplateBox[{}, Complexes]^n,其中 .
  • 变量指定 vars 应该是一个列表,其中包含以下列形式之一给出变量的元素:
  • v名为 和推断尺寸的变量
    vReals实数标量变量
    vIntegers整数标量变量
    vComplexes复数标量变量
    v限制在几何区域 的向量变量
    vVectors[n,dom]属于 TemplateBox[{}, Complexes]^n 的向量变量
    vMatrices[{m,n},dom]属于 TemplateBox[{}, Complexes]^(m x n) 的矩阵变量
  • ConvexOptimization 自动进行必要的转换,以找到解决最小化问题的有效方法.
  • 所求解的原始最小化问题有一个相关的最大化问题,即拉格朗日对偶问题. 对偶最大值始终小于或等于原始最小值,因此它提供了一个下限. 对偶最大化程序提供有关原始问题的信息,包括最小值对约束变化的敏感性.
  • 可能的解的属性 "prop" 包括:
  • "PrimalMinimizer"最小化 的变量值列表
    "PrimalMinimizerRules"最小化 的变量值 vars={v1,}
    "PrimalMinimizerVector"最小化 的向量
    "PrimalMinimumValue"最小值
    "DualMaximizer"最大化对偶问题的向量
    "DualMaximumValue"对偶最大值
    "DualityGap"对偶最优值和原最优值之差
    "Slack"将不等式约束转换为等式的向量
    "ConstraintSensitivity"
    对约束摄动的敏感性
    {"prop1","prop2",} 解的多个属性
  • 可以给出以下选项:
  • MaxIterationsAutomatic使用的最大迭代次数
    Method Automatic使用方法
    PerformanceGoal $PerformanceGoal优化的目标
    Tolerance Automatic内部比较使用的公差
    WorkingPrecision MachinePrecision内部计算使用的精度
  • 选项 Methodmethod 可以用来指定要使用的方法. 可用的方法包括:
  • Automatic自动选择方法
    solver可能的情况下,对问题进行转换,用 solver 求解问题
    "SCS"SCS 劈分圆锥求解器
    "CSDP"CSDP 半定优化求解器
    "DSDP"DSDP 半定优化求解器
    "MOSEK"商用 MOSEK 凸优化求解器
    "Gurobi"商用 Gurobi 线性和二次优化求解器
    "Xpress"商用 Xpress 线性和二次优化求解器
  • Methodsolver 可以用来指定使用特定的求解器,以使所用的对偶公式对应于为 solver 所收录的公式. 可能的求解器有 LinearOptimizationLinearFractionalOptimizationQuadraticOptimizationSecondOrderConeOptimizationSemidefiniteOptimizationConicOptimizationGeometricOptimization.

范例

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

基本范例  (2)

最小化受线性约束条件限制的 TemplateBox[{{x, +, {2, y}}}, Abs]

最小化矩阵的范数,该矩阵的某些元素受约束条件的限制:

范围  (28)

基本用法  (12)

最小化 ,其中约束为

几个线性不等式约束可以使用 VectorGreaterEqual 表示:

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

使用标量不等式的等效形式:

使用向量变量

由于在 中可能的线程,不等式 可能与 不同:

要避免在 中的意外线程,使用 Inactive[Plus]

使用常数参数方程,以避免 中的意外线程:

VectorGreaterEqual 表示关于 "NonNegativeCone" 的圆锥不等式:

明确指定圆锥的尺寸,使用 {"NonNegativeCone",n}

求解:

最小化 ,其中约束为

使用带有 "NormCone" 的圆锥不等式,指定约束

求解:

在正半定矩阵约束 (x 1; 1 y)_(TemplateBox[{2}, SemidefiniteConeList])0 下最小化

求解:

使用向量变量 Indexed[x,i] 以指定单个分量:

使用 Vectors[n,Reals] 在向量变量可能不明确时指定其尺寸:

使用 NonNegativeReals () 指定非负约束:

使用向量不等式的等价形式

最大化矩形的面积,其周长最多为 1,高度最多为宽度的一半:

为正时,该问题可以通过 GeometricOptimization 方法求解:

使用方法 GeometricOptimization 隐式假定为正:

整数变量  (4)

使用 Integers 指定整数变量:

使用 Vectors[n,Integers] 指定向量变量的整数域约束:

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

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

复数变量  (8)

使用 Complexes 指定复变量:

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

. 将约束条件展开为实数分量可以得到:

对具有实值目标函数、复变量和复约束条件的问题进行求解:

求解具有实变量和实约束条件的相同问题:

使用含有埃尔米特矩阵 和实值变量的二次目标函数

使用含有埃尔米特矩阵 和复变量的目标函数 (1/2)Inactive[Dot][Conjugate[x],q,x]

使用含有埃尔米特矩阵 和实值变量的二次约束条件

使用含有埃尔米特矩阵 和复变量的约束条件 (1/2)Inactive[Dot][Conjugate[x],q,x]d

求具有最小2-范数(最大奇异值)的埃尔米特矩阵,使得矩阵 为半正定:

最大奇异值的最小值为:

使用具有埃尔米特或实对称矩阵的线性矩阵不等式约束 a_(0)+a_(1) x_(1)+a_(2) x_(2)>=_(TemplateBox[{2}, SemidefiniteConeList])0

线性矩阵不等式中的变量必须是实数才能使和保持为埃尔米特矩阵:

原模型属性  (1)

在三角形 和圆盘 的相交区域上最小化

得到作为向量的原始最小化程序:

得到最小值:

绘制解的图形:

对偶模型属性  (3)

最小化约束为

对偶问题是为了最大化约束为

由于强对偶性,原始最小值和对偶最大值重合:

这等同于对偶间隙为零. 一般地,在最优点

直接使用解的属性获取对偶最大值和对偶最大化程序:

"DualMaximizer" 可以通过下式获得:

对偶最大化程序矢量分区与对偶圆锥的数量和尺寸匹配:

要获取特定问题类型求解程序的对偶格式,需将其指定为方法选项:

选项  (13)

Method  (8)

"SCS" 是拆分圆锥求解器方法:

"CSDP" 是半定问题的内点法:

"DSDP" 是半定问题的替代内点法:

"IPOPT" 是非线性问题的内点法:

不同的方法具有不同的默认公差,这会影响准确性和精度:

计算精确和近似解:

"SCS" 的默认公差为

"CSDP""DSDP""IPOPT" 的默认公差为

当指定方法 "SCS" 时,将调用该方法并使用 SCS 库的默认公差 10-3

当使用默认选项时,该问题可通过公差为 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 设置会给出更精确的答案,但计算需要的时间可能更长:

较小的公差给出更精确的答案:

WorkingPrecision  (2)

默认工作精度为 MachinePrecision

如果可能,使用 WorkingPrecisionInfinity 将给出确切的解:

WorkingPrecision 而不是 MachinePrecision 将尝试使用具有扩展精度支持的方法:

使用 WorkingPrecisionAutomatic 将尝试使用输入问题的精度:

使用 24 位精度求解二次目标的问题:

当前没有使用精确算法求解二次目标问题的方法. 当不支持所要求的精度时,则计算使用机器数:

应用  (30)

基本模型变换  (11)

最大化约束为 . 通过对目标函数进行负转换来求解最大化问题:

对原始最小值求负以得到相应的最大值:

最小化约束为 . 由于约束 非凸,因此使用半定约束使凸性明确:

当且仅当矩阵的所有左上子矩阵的行列式均为非负值时,才是正半定矩阵:

求解:

最小化 ,约束为 ,假定当 时, 成立. 使用辅助变量 ,目标变为最小化 ,使得

检查 是否意味着

舒尔补条件是指,如果 ,当且仅当 时,分块矩阵 . 因此当且仅当 时, . 使用 Inactive[Plus] 构造约束以避免线程化:

在以 为中心的椭圆上最小化 TemplateBox[{x}, Norm]

上镜图(Epigraph)变换可用于构造具有线性目标以及附加变量和约束的问题:

这种形式的问题可以直接使用 ConicOptimization 求解:

通过最小化 来最小化 ,其中 是非递减函数. 对于这两个问题,原始最小化器 将保持不变. 考虑最小化 ,其约束为

的最小值可以通过将 应用于 的最小值来获得:

ConvexOptimization 将自动执行此转换:

,使得线性依赖于决策变量 的对称矩阵 的最大特征值最小. 由于 等价于 ,其中 的第 个特征值,该问题可以表述为线性矩阵不等式. 定义线性矩阵函数

实对称矩阵 可以用正交矩阵 对角线化使得 . 因此当且仅当 时, . 由于任何 ,认为 ,因此当且仅当 时,. 数值模拟表明这些公式是等效的:

得到的问题:

运行蒙特卡洛模拟以检查结果的合理性:

,使的对称于决策变量 的对称矩阵 的最小特征值最大. 定义线性矩阵函数

这个问题可以表述为线性矩阵不等式,因为 等价于 ,其中 的第 个特征值. 要最大化 ,需最小化

运行蒙特卡洛模拟以检查结果的合理性:

,使得线性依赖于决策变量 的对称矩阵 的最大和最小特征值之差最小. 定义线性矩阵函数

这个问题可以表述为线性矩阵不等式,由于 等价于 ,其中 的第 个特征值. 求解得到的问题:

在这种情况下,最小和最大特征值重合,差为0:

最小化线性依赖于决策变量 的对称矩阵 的最大特征值(按绝对值):

最大特征值满足 lambda I-A(x,y)>=_(TemplateBox[{2}, SemidefiniteConeList])0. 的最大(按绝对值)负特征值是 的最大特征值并满足 lambda I+A(x,y)>=_(TemplateBox[{2}, SemidefiniteConeList])0

,使得线性依赖于决策变量 的对称矩阵 的最大奇异值 最小化:

的最大奇异值 的最大特征值的平方根,并且根据前面的示例,它满足 ,或者等价于 (sigma I A(x,y); A(x,y)^T sigma I)_(TemplateBox[{5}, SemidefiniteConeList])0

绘制结果的图形:

对于包括椭圆体、二次锥和抛物面在内的二次集合 ,确定 是否成立,其中 是对称矩阵, 为向量, 为标量:

假定集合 是全维度的,S-procedure 表示,当且仅当存在某个非负数 使得 成立时, . 直观地看到存在一个非负数

考虑到可行性,将 0 用作目标函数. 由于 λ0,因此

几何问题  (8)

最小化面积为 4 的矩形的对角线长度,使得宽度加上高度的三倍小于 7:

求半径为 1 的两个圆盘之间的最小距离,圆盘的中心分别为 . 设 为圆盘 1 上的一个点. 设 为 圆盘 2 上的一个点. 目标是最小化 ,约束为

可视化两点的位置:

两点之间的距离是:

求表面积最大为 1 的椭圆体在体积最大时主轴 的半长:

表面积可以通过以下方式近似:

通过最小化其倒数使体积最大化:

结果是一个球. 如果对轴的长度附加约束条件将使结果发生改变:

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

最小化受约束条件 限制的半径

可视化最小包含球:

可通过 BoundingRegion 高效地找到最小包含球:

求凸多边形的解析中心. 解析中心是使约束的距离乘积最大化的点:

凸多边形的每个边可以表示为半平面 的交线. 提取线性不等式:

目标是最大化 . 对目标求 并取反,变换后的目标是

使用辅助变量 ,变换后的目标是 ,约束为

可视化中心的位置:

测试椭球是否是形式为 的另一个椭球的子集:

使用 S-procedure 可以证明,当且仅当 时,椭圆 2 是椭圆 1 的子集:

检查条件是否满足:

将椭圆体转换为显式形式,并确认椭圆 2 在椭圆 1 内:

移动椭圆 2,使其与椭圆 1 重合:

现在进行测试表明该问题是不可行的,这表明椭球 2 不是椭球 1 的子集:

求恰好可以放置到凸多边形中的、参数为 的、面积最大的椭圆:

凸多边形的每段可以表示为半平面 的交点. 提取线性不等式:

将参数化应用于半平面,可以得出 . 项 . 因此,约束条件为

最大化面积等价于最小化 ,这也等价于最小化

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

通过最小化体积,找到参数化为 {x:TemplateBox[{{{a, ., x}, +, b}}, Norm]<=1}、包括三维中的一组点的最小椭球体:

对于每个点 ,必须满足约束条件 TemplateBox[{{{a, ., {p, _, i}}, +, b,  }}, Norm]<=1, i=1,2,...,n

最小化体积等价于最小化 ,这也等价于最小化

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

也可以使用 BoundingRegion 得到包围椭圆体(体积不一定是最小的):

数据拟合问题  (4)

对于给定矩阵 a 和向量 b,最小化 ,约束条件为

将三次曲线拟合到离散数据,以使数据的第一个和最后一个点位于曲线上:

使用 DesignMatrix 构造矩阵:

定义约束,使第一个点和最后一个点必须位于曲线上:

通过最小化 求系数

将拟合度与数据进行比较:

通过最小化 来求对非线性离散数据的离群值较不敏感的拟合:

使用基础 拟合数据. 插值函数将是

求解:

可视化拟合:

将插值函数与参考函数进行比较:

对于复数 ,通过最小化 ||a.lambda-b||+sigma TemplateBox[{lambda, 1}, Norm2] 来求对复数数据的 正则化拟合:

对于基 ,使用 DesignMatrix 构建矩阵

求系数

为根据 的实部和虚部定义的拟合:

可视化 的实部的结果:

可视化 的虚部的结果:

平方和表示  (1)

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

目的是找到 使得 ,其中 是单项式的向量:

构造对称矩阵

的多项式系数,并确保它们相等:

的元素:

二次项 ,其中 是由 的 Cholesky 分解获得的下三角矩阵:

将平方和多项式与给定的多项式进行比较:

分类问题  (3)

找到将两组点 分开的直线

为了分开,集合 1 必须满足 ,集合 2 必须满足

目标是最小化 ,这给出了 之间厚度的两倍:

分隔线是:

求将两组三维点 分开的二次多项式:

使用 DesignMatrix 构造两个集合的二次多项式数据矩阵:

为了分开,集合 1 必须满足 ,集合 2 必须满足

通过最小化 来求分离多项式:

分离两组点的多项式为:

绘制将两个数据集分开的多项式:

将给定的点集 分成不同的组. 这通过最小化 以找到每个组的中心 得到,其中 是给定的本地内核, 是给定的惩罚参数:

内核 k-近邻()函数,使得 ,或者 . 对于此问题,选择 个最近邻:

目标 是:

求组的中心:

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

提取并绘制分组的点:

设施选址问题  (1)

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

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

为决策变量,如果客户 被基站 覆盖,则用 表示:

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

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

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

收集所有变量:

求基站的位置及其范围:

提取基站的位置和范围:

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

投资组合优化   (1)

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

回报为 ,其中 是由每只股票的预期回报值组成的向量:

风险由 给出; 为规避风险的参数,且

目标是最大化收益,同时在指定的风险规避参数的情况下最大程度地降低风险:

可用 模拟买卖股票对股票市场价格的影响,该模型通过上镜图变换用幂锥来模拟:

权重 必须大于 0,权重加上市场影响成本必须加起来为 1:

对于一系列风险规避参数计算收益和相应的风险:

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

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

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

图像处理  (1)

通过寻找在总变化范数下最接近的图像来恢复受损的图像:

通过随机删除 40% 的数据点来创建损坏的图像.

目标是最小化 sum_(i=1)^(n-1)sum_(j=1)^(m-1)sqrt(TemplateBox[{{TemplateBox[{u, {i, +, 1}, j}, IndexedDefault], -, TemplateBox[{u, i, j}, IndexedDefault]}}, Abs]^2+TemplateBox[{{TemplateBox[{u, i, {j, +, 1}}, IndexedDefault], -, TemplateBox[{u, i, j}, IndexedDefault]}}, Abs]^2),其中 是图像数据:

假设任何非零数据点 TemplateBox[{u, i, j}, IndexedDefault] 均未损坏. 对于这些位置,令 TemplateBox[{u, i, j}, IndexedDefault]=u_(i j)^(orig)

求解并显示还原的图像:

Wolfram Research (2020),ConvexOptimization,Wolfram 语言函数,https://reference.wolfram.com/language/ref/ConvexOptimization.html.

文本

Wolfram Research (2020),ConvexOptimization,Wolfram 语言函数,https://reference.wolfram.com/language/ref/ConvexOptimization.html.

CMS

Wolfram 语言. 2020. "ConvexOptimization." Wolfram 语言与系统参考资料中心. Wolfram Research. https://reference.wolfram.com/language/ref/ConvexOptimization.html.

APA

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

BibTeX

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

BibLaTeX

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