最优化方法课件s

最优化方法

最优化篇

开篇有益

优化模型 实际问题中，人们经常遇到一类决策问题：在一系列客观或主观限制条件下，寻求使所关注的某个或多个指标达到最大（或最小）的决策。这种决策问题通常称为优化问题。解决这类问题的方法称为最优化方法，又称数学规划，它是运筹学里一个十分重要的分支。

最优化问题的数学模型的一般形式为：

opt z f x （1）

s.t. hi x 0,i 1, ,l gj x 0,j 1, ,m tk x 0,k 1, ,n x D Rs

（2）

opt（optimize）是最优化的意思，可以使求最小min（minimize）或求最大

max（maximize），s.t.（subject to）是“受约束于”。

模型包含三个要素：决策变量decision bariable，目标函数objective function，约束条件constraints。

（2）所确定的x的范围称为可行域feasible region，满足（2）的解x称为可行解feasible solution，同时满足（1）（2）的解x 称为最优解Optimal solution，整个可行域上的最优解称为全局最优解global optimal solution，可行域中某个领域上的最优解称为局部最优解local optimal solution。最优解所对应的目标函数值称为最优值optimum。

不同优化模型的求解方法以及求解难度有很大的不同，可按如下方法对模型进行分类：

（一）按有无约束条件（2）可分为：

1.无约束优化unconstrained optimization。 这类问题蕴含了重要的寻优计算方法。 2.约束优化constrained optimization。 大部分实际问题都是约束优化问题。 （二）按决策变量取值是否连续可分为：

1.数学规划mathematical programming或连续优化continuous optmization。 可继续划分为线性规划(LP)Linear programming和非线性规划(NLP) Nonlinear programming。在非线性规划中有一种规划叫做二次规划(QP)Quadratic programming，二次规划问题的目标为二次函数，约束为线性函数。

2.离散优化d-iscrete optimization或组合优化combinatorial optimization。 这类优化问题中包含一种常用的优化：整数规划(IP)Integer programming，整数规划中又包含很重要的一类规划：0-1（整数）规划Zero-one programming，这类规划问题的决策变量只取0或者1。

在求解组合优化问题中，出现了很多现代优化计算方法。

最优化方法

（三）按目标的多少可分为： 1.单目标规划。 2.多目标规划。

（四）按模型中参数和变量是否具有不确定性可分为： 1.确定性规划。 2.不确定性规划。

（五）按问题求解的特性可分为： 1.目标规划。 2.动态规划。 3.多层规划。 4.网络优化。 5.……等等。

求解软件

对优化问题的求解常用的是LINGO软件和MATLAB软件，本篇的程序编写基本都是用这两个软件完成的。

对于LINGO软件，线性优化求解程序通常使用单纯形法simplex method，单纯形法虽然在实际应用中是最好最有效的方法，但对某些问题具有指数阶的复杂性，为了能解大规模问题，也提供了内点算法interior point method备选（LINGO中一般称为障碍法，即barrier），非线性优化求解程序采用的是顺序线性规划法，也可用顺序二次规划法，广义既约梯度法，另外可以使用多初始点（LINGO中称multistart）找多个局部最优解增加找全局最优解的可能，还具有全局求解程序—分解原问题成一系列的凸规划。关于软件的使用方法可以参考ppt课件《LINGO软件武功秘籍》以及实验书籍《数学软件与数学实验》。

对于MATLAB软件，有MATLAB优化工具箱，线性规划大型问题使用内点算法（也是默认算法），单纯形法和积极集法根据实际情况来解中小型问题。对于非线性规划问题，基本函数用信赖域等方法的结合来求解不同规模的问题。

本篇导读

第一章 无约束优化

寻优经典计算算法,matlab实现 第二章 线性规划

完备的线性规划求解与应用 第三章 非线性规划

非线性模型的建立与求解 第四章 多目标规划

多目标决策的理论与方法 第五章 随机规划

随机规划的理论与方法 第六章 目标规划

目标规划的理论与方法 第七章 动态规划

动态规划的理论与方法

最优化方法

第八章 多层规划 ？？

第九章 网络优化

图论方法及其他网络方法 第十章 组合优化算法

禁忌搜索算法，模拟退火算法，遗传算法，蚁群优化算法，人工神经网络

最优化方法

第三章 非线性规划

理论印象

将非线性规划模型可以更具体的表示为如下形式：

minz f x

s.t. hi x 0,i 1, ,l

gj x 0,j 1, ,m x Rn

如果只有等约束hi，则可以用拉格朗日乘数法构造拉格朗日函数： ，然后求解非线性方程组 L x, f x ihi x （ i为参数）

i 1m

L

x 0 i

即可。

L 0 i

对上述模型，通过讨论x的可行方向与下降方向，可以得到如下的KKT条件（Karush-Kuhn-Tucker条件）（具体可微等条件略）：局部最优解x满足

ml

f x i hi x i gj x 0

， i, i 0。 i 1j 1

g x 0 jj

对等约束模型构造拉格朗日函数：

L x, , f x ihi x jgj x

i 1

j 1

ml

KKT条件中的公式刚好就是函数L对x的导数（梯度）等于0. , 通常称为拉格朗日乘子。

3.1 二次规划

理论印象

目标函数为二次函 …… 此处隐藏：8659字，全部文档内容请下载后查看。喜欢就下载吧 ……