GeometricOptimization

GeometricOptimization[f,cons,vars]

求可最小化受正多项式约束条件 cons 限制的正多项式目标函数的变量 vars 的正值.

GeometricOptimization[{a0,b0},{{a1,b1},},{aeq,beq}]

求可最小化受不等式约束条件 和线性等式约束条件 限制的 的正向量 x=y.

GeometricOptimization[,"prop"]

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

更多信息和选项

  • 几何优化亦称为几何规划 (GP) 或混合整数几何规划 (MIGP).
  • 几何优化经常被用于最小化面积、体积或功率等量.
  • 几何优化求的是能解原问题的
  • 最小化
    受限于约束条件
    其中
  • 单项式是幂的积 ,其中 . 正多项式是单项式 的正和,其中 .
  • 广义正多项式 是一个正多项式或广义多项式的组合:
  • 正多项式
    广义正多项式的和
    广义正多项式的积
    广义正多项式的最大值
    广义正多项式的正实数次幂
  • 通过变换 ,正多项式 对应于一个 的矩阵 (其中 )和 -向量 (其中 ),如下所示:
  • 问题的等效表达形式是求 ,其中 为问题的解:
  • 最小化
    受限于约束条件
    其中
  • GeometricOptimization[{a0,b0},{{a1,b1},},{aeq,beq}] 中,ai 应为 的矩阵,bi 应为 向量,aeq 应为一个 的矩阵,b_(eq) 应为一个 向量. 如果没有等式约束条件,可用 {} 给定{aeq,beq} 或省略.
  • 原始最小化问题有相关的最大化问题,即拉格朗日对偶问题. 对偶最大值始终小于或等于原始最小值,因此它给出了下限. 对偶最大值点提供了有关原问题的信息,包括最小值对约束条件变化的敏感性.
  • 几何优化有以下对偶问题:
  • 最大化
    受限于约束条件
    其中
  • 对于锥优化,强对偶性始终成立,这意味着如果原始最小化问题的解存在,那么对偶最大化问题的解也存在,并且对偶最大值等于原始最小值.
  • 可能的解的属性 "prop" 包括:
  • "PrimalMinimizer"最小化 f 的变量值列表 vars={v1,}
    "PrimalMinimizerRules"最小化 vars={v1,} 的值的规则
    "PrimalMinimizerVector"最小化 的向量
    "PrimalMinimumValue"最小值
    "DualMaximizer"最大化 的向量 的列表
    "DualMaximumValue"对偶最大值
    "DualityGap"对偶值和原始最优值之间的差
    "Slack"给出正多项式的每个单项式的值的向量
    "ConstraintSensitivity"
    对约束条件扰动的敏感性
    "ConstraintMatrices" 的矩阵
    "ObjectiveFunction"目标函数
    "GeometricConstraints" 几何约束条件列表
    {"prop1","prop2",} 几个解的属性
  • 可给出以下选项:
  • MaxIterationsAutomatic使用的最大迭代次数
    MethodAutomatic使用的方法
    PerformanceGoal$PerformanceGoal优化的目标
    ToleranceAutomatic内部比较采用的容差
  • 计算受限于 MachinePrecision.

范例

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

基本范例  (1)

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

范围  (12)

基本用法  (4)

用矩阵指定几何问题:

给出问题的等效目标函数和几何约束条件:

求解几何问题,以标准形式给出等式约束条件:

求解以广义正多项式给出的几何问题:

该算法会自动添加额外的变量,以得到中间的正多项式形式:

求解以向量变量形式给出的几何问题:

原始模型属性  (3)

求解以标准正多项式形式给出的几何问题:

获取最小值和最小化向量:

显示问题的矩阵表示形式:

求解以广义正多项式形式给出的几何问题:

获取被转换过的约束条件,包括引入的中间变量:

以下是相应的矩阵表示:

求解以矩阵形式给出的几何问题:

获取用形式变量表示的符号形式的几何问题:

对偶模型属性  (2)

,其中 最小化受 限制的

对偶问题是最大化受 限制的

ConicOptimization 形成的式子用中间变量 替换了凸项 ,添加了约束条件 ,等价于先前使用的对偶指数锥约束条件;{-TemplateBox[{{(, {lambda, _, 1}, )}, j}, IndexedDefault],TemplateBox[{{(, {t, _, 1}, )}, j}, IndexedDefault]-TemplateBox[{{(, {lambda, _, 1}, )}, j}, IndexedDefault],1^.lambda_1}_(TemplateBox[{}, DualExponentialConeString])0 要求 xTemplateBox[{{(, {lambda, _, 1}, )}, j}, IndexedDefault] ⅇ^((TemplateBox[{{TemplateBox[{{(, {t, _, 1}, )}, j}, IndexedDefault], -, {(, {lambda, _, 1}, )}}, j}, IndexedDefault])/(-TemplateBox[{{(, {lambda, _, 1}, )}, j}, IndexedDefault])-1)<=1^.lambda_1 ∧-TemplateBox[{{(, {lambda, _, 1}, )}, j}, IndexedDefault]<=0.

可以通过 "DualMaximizer" 属性更容易地获得

由于强对偶性,原始最小值和对偶最大值相同:

最小化受约束条件 限制的

获取对偶问题的解:

原始最小值和对偶最大值相同,因为 GeometricOptimization 具有强对偶性. 它们的差被称为对偶间隙:

对偶问题是用问题的矩阵表示来定义的:

因为所有项都是单项式,所以所有矩阵 只有一个行,对偶向量 只有一个元素,所以 . 最大化 相当于最小化 ,由于指数是单调递增函数,因此相当于最小化 ,所以可用以下方式求解对偶问题:

注意,原问题也可以通过利用指数的单调性的线性优化来求解:

敏感性属性  (3)

最大化一个开口盒子的体积,盒子的高度 、宽度 和深度 的约束条件为要使得盒子的成本小于 $100. 底部的成本为每单位面积 $10,侧面的成本为每单位面积 $1:

如果底部的成本降低了 10%,请估算盒子体积的相对变化:

底部的成本是第二个元素的第一部分(第一个元素对应于目标). 敏感性为负的,因为

一个盒子,高度为 ,宽度为 ,深度为 ,如果顶部和底部的面积和侧面的面积受约束条件而发生变化,求盒子的最大体积的相对变化. 最大化体积等同于最小化体积的倒数:

将侧面的总面积限制为小于或等于 ,并将顶部和底部的面积限制为小于或等于

此外,限制高宽比:

定义一个函数,给定 ,计算体积:

时的最大体积:

时目标函数对约束条件的相对灵敏度:

与面积约束条件相关的是第二个和第三个(第一个与目标相关)元素:

体积关于 的相对变化为

这意味着 的微小变化不会改变 {α,β}={38,47} 时的体积:

足够小时,它会影响体积:

灵敏度是对数-对数图上曲线的斜率:

的两个元素来自两组相对的边,所以体积的相对变化为:

增大 .5,预测的变化为:

实际的变化为:

可以用有限差分验证灵敏度:

求受约束条件 限制的 的最小值关于 的相对变化:

用有限差分来验证

用类似方法来验证

有限差分估计值在优化的容差范围内:

应用  (16)

基本模型转换  (1)

确定使问题可行的约束条件的限制:

问题可行:

下面的问题则不可行:

几何问题  (4)

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

为体积为 的球形冰淇淋设计一个锥形杯. 假定冰淇淋的半径和锥形杯的半径相同. 最小化锥形杯的表面积,使得冰淇淋融化时锥形杯能盛下整个冰淇淋:

求能最大化椭圆体(最大表面积为 1)的体积的

相差不大时,,表面积可以近似为:

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

不出所料,是一个球. 对轴的长度进行限制,情况发生变化:

最大化高度为 、宽度为 、深度为 的盒子的体积,使得任意两个尺寸的差别不超过 2 倍,并且限制侧面、顶部和底部的总表面积:

定义一个函数,给定总侧面积 及顶部和底部面积的和 ,返回体积:

计算体积表:

用对数图显示作为侧面面积及顶部和底部面积的函数的体积:

针对侧面面积的不同值,显示体积与允许的顶部/底部面积的权衡曲线:

矩阵问题  (2)

给定具有非负实数项的 的矩阵 ,求可最小化相似矩阵 的平方和(Frobenius 范数的平方)的具有正数项的对角矩阵

d={d1,,dn} 的对角线项. 因为 di 是正的, 的项为 {1/d1,,1/dn},所以积的项为

比较原始矩阵和缩放过的矩阵的范数:

矩阵相似,因此特征值相等:

为一个 TemplateBox[{}, Reals]^(n x n) 矩阵,由用 x in TemplateBox[{}, Reals]^k 变量表示的正多项式元素组成. 求可最小化 的光谱半径的 . 光谱半径等于 的特征值的绝对值的最大值,max(TemplateBox[{lambda}, Abs], A.v=lambda:

光谱半径也等于 PerronFrobenius 特征值 ,可用 来计算:

以下是具有最小光谱半径的矩阵:

验证算出的 为光谱半径:

随机选择 ,比较相应的光谱半径:

设计储存罐  (1)

在半径 ,高度 和长宽比 受到限制的情况下,最小化圆柱形储存罐的建造和运营成本:

建造成本是底部的成本加上侧壁的成本:

装填成本与货物的体积 和储存罐的体积 之比成正比:

最小化总成本:

平面规划  (1)

规划具有最小总面积的矩形平面,该矩形平面将 个指定面积的矩形围在一起,限制这些矩形的长宽比、矩形之间的距离和相对位置.

Rectangle[{0,0},{H,W}] 描述大矩形,用 ri=Rectangle[{xi,yi},{xi+wi,yi+hi}], i=1,,n 描述被围的小矩形.

对于 ,将每个小矩形的长宽比 限制在 之间,.

可以用两个有向图来描述相对位置,用 描述水平方向上的放置,用 描述垂直方向上的放置. 如果存在边 ij,则 ri 应在 rj 的左侧(或下方):

为矩形之间的最小间距. 当 有边 ij 时,矩形 被限制为位于矩形 的左侧,因而 . 当 有边 ij 时,矩形 被限制为位于矩形 的下边,因而 . 可用以下函数对图进行遍历并考虑可能位于平面边缘的矩形:

给定布局图、面积 ,可通过使用 GeometricOptimization 的函数将规则合并起来:

以下是描述 3 个矩形的相对位置的图,第一个位于其他两个矩形的左侧,第二个位于第三个矩形的下方:

下面是显示布局的函数:

下面是随机指定面积的 10 个矩形的布局:

结构型优化问题  (3)

设计能承受垂直载荷 或水平载荷 的重量最小的桁架. 桁架的杆是空心管,内径为 ,外径为 ,密度为

用桁架的高度 和宽度 定义杆的长度. 截面积为 . 目标是最小化重量:

当施加垂直载荷 时,每个杆的受力为:

当施加水平载荷 时,每个杆的受力为:

杆上承受的总力不得超过允许的最大受力 ,其中 为允许的最大应力:

桁架高度 和桁架宽度 被限制为:

要求空心管的壁厚最小. 可要求 () 来实现. 杆的面积与半径之间的关系为 ,不是单项函数. 通过使用 和约束条件 ,所得约束条件为单项式:

指定桁架的参数:

,求得最佳桁架:

通过 得出杆的外半径

设计能承受垂直载荷 的重量最小的桁架. 已知桁架的高度 和宽度 . 节点 的垂直位置未知:

分别为杆 的截面积, 为杆的密度. 桁架的重量由下式给出:

承受的是张力. 令 为材料的拉伸应力. 杆 上承受的力不得超过允许的最大受力:

承受的是压力. 令 为材料的抗压应力. 杆 上承受的力不得超过允许的最大受力:

指定参数:

给定 的值,可求解几何优化问题的的特定实例. 假设节点 的垂直位置必须在一定范围内,在该范围内求解:

绘制最小重量:

求给出最小重量的 的特定值:

求最佳截面积和桁架的重量:

设计一个自由端能承受垂直载荷 的重量最小的悬臂. 悬臂由 个单位长度的节段组成. 每个节段的宽度为 ,高度为

载荷使梁偏斜,在梁的每个节段上产生应力 . 应力必须小于允许的最大应力

为节段 右端的挠度. 可递归式求出自由端的挠度 ,其中 是杨氏模量,斜率 . 由于第 个节段是固定的,所以

梁的自由端的挠度必须小于允许的最大挠度

宽度、高度和长宽比被限制在一定范围内:

指定参数:

通过最小化重量求每个节段的尺寸:

可视化悬臂梁:

电路问题  (3)

设计数字电路门的大小:求给定电路中受功率和面积限制的门的最佳尺寸,以最小化电路中的延迟. 考虑由七个门组成的电路:

为每个门必须增大的比例因子:

假定每个门占用的面积与比例因子成正比,因此电路的总面积为:

转换时损失的能量与比例因子 成正比,门转换时的转换频率 和能量损失 为:

的输入电容 ,门 6 和 7 除外,它们的输入电容为 10:

的驱动电阻为

的电容是与其输出相连的门的输入电容之和,输出门 6 和 7 除外,它们的电容与其输入电容相同:

的延迟是其驱动电阻和门电容的乘积:

目标是使电路中可遍历的所有路径组合的最坏情况下的延迟最小化:

电路的面积必须小于规定的最大面积:

消耗的功率必须小于指定的最大功率:

求对允许的最大面积和功率进行组合得出的最小面积:

绘制最佳折衷曲线:

在已知电容的电路中,求 段电线的宽度. 下面的网络中有五段电线:

每段电线的电阻为 ,电容为 ,其中 为正常数,具体取决于电线的特性, 是电线的长度,宽度为 :

使用 模型,用一个电阻和电容来模拟电线. 所得网络为电阻器-电容器网络:

通过将各个网络电容与电线的电容 相加,可以得到模型的新电容:

Elmore 延迟测量的是电压变化并收敛到新值所造成的延迟. 每个电容 的 Elmore 延迟为 ,其中 是电容 之间的一组电阻:

目标是最小化最大的 Elmore 延迟:

电线的宽度被限制在以下范围内:

总面积不能超过允许的最大面积:

指定参数:

求电线的宽度:

求晶体管的最佳掺杂分布,以最小化基区渡越时间. 令 为掺杂分布,其中 为基区宽度. 令 为基区渡越时间. 给出了作为 的函数的简化模型,其中 是一个常数. 令 ;可用 个等距点将积分离散化:

掺杂梯度约束条件 可被近似为:

掺杂分布具有上限和下限以及指定的初始和最终状态:

指定参数:

求解由此产生的几何优化问题,获得最佳掺杂分布:

绘制所得分布:

功率控制  (1)

最小化 个发射机发射到 个接收机的总功率

接收机 接收的来自发射机 的功率为 ,其中 表示从发射机 到接收机 的路径增益:

接收机 处的信号功率为

接收机 处的干扰功率是接收的来自除 之外的所有发射机的总功率

个接收机/发射机对的信号与干扰加噪声比 (SINR) 为 ,其中 是接收机 处的噪声功率:

任意接收机/发射机对的 SINR 有一个最小阈值a. 为了使它成为一个正多项式约束条件,取 SINR 约束条件的倒数

功率有上限和下限:

指定参数:

求功率:

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

文本

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

CMS

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

APA

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

BibTeX

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

BibLaTeX

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