当前位置:文档之家› 1次最优化方法

1次最优化方法


n
s .t .
∑W
j =1
m i =1
ij
≤ c i , i = 1,2L , m
j = 1,2L , n
货栈的容量 市场的需要量
s ∑ W ij = q j ,
W ij ≥ 0, i = 1,2L , m; j = 1,2L n
1.2 最优化问题的分类与特征
连续与离散
• 某些或全部变量取整数值才有意义--整数规划 某些或全部变量取整数值才有意义--整数规划 取整数值才有意义-(上述运输问题中 上述运输问题中, (IP). (上述运输问题中,工厂生产拖拉机而非化 学产品). 学产品). • 分为整数线性规划和整数非线性规划;整数规划 分为整数线性规划和整数非线性规划; 整数线性规划和整数非线性规划 和混合整数规划;一般整数规划和0-1整数规划 和混合整数规划;一般整数规划和0 • 简单松弛策略. 忽略整数要求,当成实变量来求 简单松弛策略. 忽略整数要求, 解问题,然后将所有分量舍入到最近的整数---可 解问题,然后将所有分量舍入到最近的整数--可 给出问题的界.Lagrange松弛策略 松弛策略. 给出问题的界.Lagrange松弛策略. • 整数规划属NP难问题. 常用算法:分支定界法、 整数规划属NP难问题. 常用算法:分支定界法、 NP难问题 或其他启发式算法(求解一系列连续优化问题) 或其他启发式算法(求解一系列连续优化问题)
|| x ||∞ ≤|| x || 2 ≤ n || x ||∞ || x ||∞ ≤|| x || 2 ≤ n || x ||∞
p
3.诱导矩阵范数 3.诱导矩阵范数
|| A ||= max
x ≠0
|| Ax || , 其中 || ⋅ || 是某一向量范数。 是某一向量范数。 || x ||
矩阵范数性质(4) 矩阵范数性质
Cauchy序列: 设{ x ( k ) }是R n中的一个向量序列,如 果对 中的一个向量序列, 序列: 任意给定的 ε > 0, 总存在正整数 K ε , 使得当m , l > K ε 时,就 序列。 有 | x ( m ) − x ( l ) |< ε , 则{ x ( k ) }称为Cauchy序列。
优化问题的简单分类与求解难度
问题的求解难度依次增加! 问题的求解难度依次增加! 依次增加
1.3 优化算法和优化软件
◎ 优化算法
• 迭代法 • 从最优解的某个初始猜测出发,生成一个提高 从最优解的某个初始猜测出发 生成一个提高 某个初始猜测出发, 估计序列,直到达到一个解. 的估计序列,直到达到一个解. • 大部分利用目标函数和约束,可能还有这些函 大部分利用目标函数和约束 可能还有这些函 目标函数和约束, 数的一阶和二阶导数. 数的一阶和二阶导数. • 通常收敛到
先修课程:线性代数,高等数学, 先修课程:线性代数,高等数学,最好会某种高级语言
Chap 1 预备知识
一、最优化问题的一般形式: 最优化问题的一般形式:
min f ( x ) n
x∈ R
s.t. ci ( x ) = 0, i = 1,..., me ; ci ( x ) ≥ 0, i = me + 1,..., m .
*
x* ∈ D,使得 ∀x ∈ D, 均有 f ( x ) ≥ f ( x * ),
f ( x ) 在可行域上的全局极小点。 在可行域上的全局极小点 全局极小点。
则称 x 是
若存在x * ∈ D和x *的ε > 0的邻域 N ( x * , ε ) = { x | || x − x * ||< ε }, 使得对∀x ∈ D I N ( x * , ε )成立f ( x ) ≥ f ( x * ),
则称 x 是
*
f ( x ) 在可行域上的局部极小点。 在可行域上的局部极小点 局部极小点。
四、向量范数、矩阵范数 向量范数、 1、向量范数定义三条件: 向量范数定义三条件: 2、常见向量范数: 常见向量范数:
|| ⋅ ||∞ || ⋅ ||1 || ⋅ ||2 || ⋅ || p
范数的等价性: 范数的等价性:
(1) || Ax ||≤|| A || || x || ( 2) || λA ||=| λ | || A || ( 3) || A + B ||≤|| A || + || B || ( 4) || AD ||≤|| A || || D ||
常用的矩阵范数
|| A ||1 、 A || 2 和 || A ||∞ ||
优化问题的一般模型--数学规划问题 优化问题的一般模型--数学规划问题 --
优化建模(modeling):识别出给定 : 优化建模 问题的目标、变量和约束的过程。 问题的目标、变量和约束的过程。
• 建立恰当模型:第一步、最重要的一步(太 建立恰当模型:第一步、最重要的一步 太 简单-不能给实际问题提供有用的信息; 简单-不能给实际问题提供有用的信息; 太复杂-不易求解) 太复杂-不易求解 • 选择特定算法:很重要--决定求解速度及质 选择特定算法:很重要 决定求解速度及质 无通用优化算法 无通用优化算法, 求解特定类型优化 量(无通用优化算法,有求解特定类型优化 问题的算法) 问题的算法
4、向量序列的极限 极限、聚点、Cauchy序列 极限、聚点、Cauchy序列
极限: 极限: 设{ x
(k )
}是R 中一个向量序列, ∈ R , 如果对 中一个向量序列, x
n n
每个任给的 ε > 0存在正整数 K ε , 使得当 k > K ε 时就有 || x ( k ) − x ||< ε , 则称序列收敛到 x .
优化实例1 运输问题 优化实例1:运输问题(transportation problem) 背 数 景:化学制品公司考虑某种产品的产销问题. 化学制品公司考虑某种产品的产销问题. 据:

题:确定从每个工厂运送到每个销地的产品 数量,使其满足需求,同时极小化费用 数量,使其满足需求, 变 量: 的产品数量
定理: { x ( j ) } ⊂ R n 为Cauchy序列,则{ x ( j ) }的聚点为极限点。 序列, 的聚点为极限点。 设
随机与确定
有的问题进行优化建模时, 有的问题进行优化建模时,模型与一些不能提前确定 的参数有关(运输问题中, 的参数有关(运输问题中,零售市场的需求在实际中不能够 精确确定. 许多经济和金融规划模型也具有该特征, 精确确定. 许多经济和金融规划模型也具有该特征, 哪里 经常与未来的利息率和经济的未来趋向有关). 经常与未来的利息率和经济的未来趋向有关).
(无约束问题)驻点或者 无约束问题)驻点或者 约束问题)KKT点 极大点、极小点或鞍点). (约束问题)KKT点(极大点、极小点或鞍点). 如果问题是凸规划 则可确保算法收敛到全局极小点 凸规划, 收敛到全局极小点. 如果问题是凸规划,则可确保算法收敛到全局极小点
◎ 优化软件
• AMPL: A Modeling Language for Mathematical Programming • Lindo/Lingo软件 软件(\verb" " 软件 • Matlab优化工具箱 见姜启源等编的《数学实验》, 优化工具箱(见姜启源等编的 优化工具箱 见姜启源等编的《数学实验》 高教出版社) 高教出版社 • Cplex • 其它(Mathematica, Minos, Excel等的优化功能 其它 等的优化功能). 等的优化功能
决策变量,目标函数, 决策变量,目标函数, 约束函数(等式,不等式)、条件。 )、条件 约束函数(等式,不等式)、条件。
(p)
二、可行点与可行域 称满足约束条件的点为可行点 称满足约束条件的点为可行点 称可行点全体组成的集合为可行域 记为D 称可行点全体组成的集合为可行域, 记为 可行域 三、(严格)局部极小点与(严格)全局极小点 、(严格)局部极: 产量约束: 销量约束: 销量约束: 非负约束: 非负约束:
问题中目标和约束函数都是线性函数, 称此类型的问题为线性规划问题 线性规划问题. 问题中目标和约束函数都是线性函数, 称此类型的问题为线性规划问题. 目标 都是线性函数
优化实例2:选址问题 优化实例 :选址问题(facility location problem)
第 i 个货栈到第 ( x i , y i )( i = 1 , 2 L , m ). j 个市场的货物量为 W ij
( i = 1,2 L , m ; j = 1,2 L , n )
min ∑ ∑ W ij ( x i − a j ) 2 + ( y i − b j ) 2
i =1 j =1
n
m
最优化理论与算法
(54课时) 课时) 课时 ---绪论 绪论
李改弟 应用数理学院 ligd@
最优化研究什么? 最优化研究什么?
• 有选择的地方就有优化。 有选择的地方就有优化。 • 讨论在众多的方案中什么样的方案最优以 及怎样找出最优方案
城建规划:如何安排工厂、机关、学校、商店、医 城建规划:如何安排工厂、机关、学校、商店、 住户和其他单位的布局,方能方便群众, 院、住户和其他单位的布局,方能方便群众,利于城 市的房展
课程主题
介绍线性与非线性规划的-- 介绍线性与非线性规划的-- 基本理论、实用算法和部分应用 基本理论、 具体的主题包括: 具体的主题包括:
• 线性规划 基本性质、单纯形法、 基本性质、单纯形法、对偶理论 • 非线性规划 最优性条件、凸性、Lagrange对偶 最优性条件、凸性、Lagrange对偶 无约束优化的算法:线搜索法和信赖域法 无约束优化的算法:线搜索法和信赖域法 约束优化的算法:二次规划、 约束优化的算法:二次规划、罚函数法 • 动态规划 经营管理中多阶段决策过程的总体优化
1.1 数学描述与例子
相关主题