书-最优化问题

《书-最优化问题》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第一章绪论1.1最优化问题所谓最优化问题，就是在满足一定的约束条件下，寻找一组参数值，以使某些最优性度量得到满足，即使系统的某些性能指标达到最大或最小。最优化问题的应用可以说遍布工业、社会、经济、管理等各个领域，其重要性是不言而喻的。最优化问题根据其目标函数、约束函数的性质以及优化变量的取值等可以分成许多类型，每一种类型的最优化问题根据其性质的不同都有其特定的求解方法。不失一般性，设所考虑的最优化问题为：minσ=f(X)(1.1)s.t.X∈S={X

2、g(X)≤0j=1,…,m}i其中，σ=f(X)为目标函数，g(X)为约束函数，S为约束域，X为n维优化变量。通

3、常最大i化问题很容易转换为最小化问题(σ=−f(X))，对于g(X)≥0的约束和等式约束也可转换为i−g(X)≤0的约束，所以(1.1)式所描述的最优化问题不失一般性。i当f(X)、g(X)为线性函数，且X≥0时，上述最优化问题即为线性规划问题，其求解方i法有成熟的单纯形法和Karmarc方法。当f(X)、g(X)中至少有一个函数为非线性函数时，上述问题即为非线性规划问题。非线i性规划问题相当复杂，其求解方法多种多样，但到目前仍然没有一种有效的适应所有问题的方法。当优化变量X仅取整数值时，上述问题即为整数规划问题，特别是当X仅能取0或1时，上述问题即为0－1整数规

4、划问题。由于整数规划问题属于组合优化范畴，其计算量随变量维数的增长而指数增长，所以存在着“维数灾难”问题。n当g(X)≤0(j=1,…,m)所限制的约束空间为整个n维欧氏空间，即R时，上述最优化问i题为无约束优化问题，即minσ=f(X)(1.2)ns.t.X∈S⊂R非线性规划问题（包括无约束优化问题和约束优化问题），由于函数的非线性，使得问题的求解变得十分困难，特别是当目标函数在约束域内存在多峰值时。常见的求解非线性问题的优化方法，其求解结果与初值的选择关系很大，也就是说，一般的约束或无约束非线性优化方法均是求目标函数在约束域内的近似极值点，而非真正的最小点。1

5、.1.1局部优化算法*定义1.1如果存在X∈B，使得对∀X∈B有B1*f(X)≤f(X),X∈B(1.3)Bn*成立，其中B⊂S⊆R，S为由约束函数限定的搜索空间，则称X为f(X)在B内的局部极小B*点，f(X)为局部极小值。B常见的优化方法大多为局部优化方法，都是从一个给定的初始点X∈S开始，依据一定的0方法寻找下一个使得目标函数得到改善的更好解，直至满足某种停止准则。成熟的局部优化方法很多，如Newton-Raphson法、共轭梯度法、Fletcher-Reeves法、Polar-Ribiere法、Davidon-Fletcher-Power(DFP)法、Br

6、oyden-Fletcher-Goldfarb-Shann(BFGS)方法等等，还有专门为求解最小二乘问题而发展的Levenberg-Marquardt(LM)算法。所有这些局部优化算法都是针对无约束优化问题而提出的，而且对目标函数均有一定的解析性质要求，如Newton-Raphson法要求目标函数连续可微，同时要求其一阶导数连续。对于约束非线性优化问题，除了根据一阶最优化必要条件直接将最优化问题转换为非线性代数方程组，然后采用非线性代数方程组的数值解法进行求解外，还有序列线性规划法、可行方向法、拉格朗日乘子法等等。最常用的方法是将约束问题通过罚函数法转换为无约束

7、优化问题，然后再采用无约束优化方法进行求解。这些具体方法请读者参阅有关最优化理论与方法方面的文献。1.1.2全局优化算法*定义1.2如果存在X∈S，使得对∀X∈S，有：*f(X)≤f(X),X∈S(1.4)n**成立，其中S⊆R为由约束条件限定的搜索空间，则称X为f(X)在S内的全局极小点，f(X)为其全局极小值。前面指出，已发展成熟的最优化方法大多为局部优化方法，其求解结果与初始值相关。对于目标函数为凸函数、约束域为凸域的所谓凸规划问题，局部最优与全局最优等效。而对于非凸问题，由于在约束域内目标函数存在多峰值，因而其全局最优与局部最优相差甚远。目前为止，全局优化

8、问题也已存在了许多算法，如填充函数法等，但比起局部优化问题的众多成熟方法，其间还有很大差距。另外，解析性优化方法对目标函数及约束域均有较强的解析性要求，对于诸如目标函数不连续、约束域不连通、目标函数难以用解析函数表达或者难以精确估计(如仿真优化问题)等问题时，解析确定性优化方法就难以适应。为了可靠解决全局优化问题，人们试图离开解析确定型的优化算法研究，转而探讨对函数解析性质要求较低甚至不作要求的随机型优化方法。最早的随机型优化方法是基于Monte-Carlo方法的思想，针对具体问题性质的特点，构造以概率1收敛于全局最小点的随机搜索算法。真正有效且具有普遍适应性的随

9、机全局优化