几何规划算法.ppt

文档介绍：1
4. 几何规划算法
几何规划是一类特殊的非线性规划问题, 是最优化理论和方法研究的一个重要分支。最初是由Zener(1961)从实际工程设计问题中提出并命名的, Duffin, Peterson和Zener针对几何规划问题做了进一步的基础性研究工作。在其最初发展中, 算术几何平均不等式起了非常关键的作用, 对其研究具有广泛的应用价值, 几乎涉及自然科学和社会科学的各个领域, 如工程设计、经济学与统计学、生产管理及化学平衡等。由于实际问题中抽象出来的许多优化模型都是几何规划形式, 因此几何规划已成为研究与解决自然科学和社会科学中, 许多优化模型的一个强有力工具。
2
几何规划作为一类特殊的非线性规划, 包含线性规划、二次规划、多项式规划和分式规划等。许多数学规划研究者曾预料: 在一定条件下, 可以用一串几何规划去逼近任意非线性规划, 假若该设想能实现, 必将开辟非线性规划求解方法的新纪元!!!
目前, 针对几何规划(特别是广义几何规划)的求解方法还不够完善, 许多方法都存在数值困难, 特别是对于实际问题中抽象出来的非线性程度较高、规模较大的广义几何规划问题, 而对于广义几何规划全局优化算法的设计难度更大, 因此对广义几何规划局部优化和全局优化算法的研究, 既具有重要的理论意义和应用价值, 又是一个极具挑战性的研究课题。
3
(1) 正项式几何规划
正项式几何规划的一般形式为:
其中常系数ckj>0(k=0,1,2,···,m), 显然, 目标函数和约束条件函数都是正项式函数。
正项式函数不一定是凸函数, 如f(x)=x1/2是正项式函数, 但在x>0的区域内不是凸的。
4
对正项式几何规划, 其相应的求解算法有:
当极小化一个非凸函数时, 很难找到其全局极小点, 仅能求得其局部极小点。但对于正项式几何规划, 其局部极小点也是其全局极小点, 因为每个正项式几何规划问题都等价于一个凸规划, 也就是等价于在凸区域上极小化一个凸函数, 这是正项式几何规划的一个重要特征。
ⅰ) 对偶方法
ⅱ) 基于原规划的压缩法
ⅲ) 正项式几何规划的等价形式—半无限线性规划
5
求解正项式几何规划的新进展
ⅰ) Kortanek针对正项式几何规划问题提出一种不可行内点算法,