20190602——最优化理论基础
所谓最优化方法,就是求一个多元函数在某个给定集合上的极值。
min f(x)
s.t. x属于K
K是某个给定的集合(称为可行集或者是可行域)f(x)是定义在集合K上的实值函数,此外,在模型中,x通常称为决策变量,s.t. 是subject to 的缩写
人们按照可行集的性质对最优化问题,进行一个大致的分类
线性规划和非线性规划 可行集是有限维空间的一个子集
组合优化或网络规划 可行集中的元素是有限的
动态规划 可行集是一个依赖时间的决策序列
最优控制 可行集是无穷维空间的中的一个连续子集
精确线搜索分为两类,一类是使用导数的搜索法,如牛顿法、插值法及抛物线法;另一类是不用导数的搜索,如0.618法,分数法及成功-失败方法
黄金分割法
黄金分割法也称为0.618法,其基本思想是通过试探点函数值的比较,使得包含极小点的搜索区间不断缩小,该方法仅需要计算函数值,适用范围广,使用方便,
φ(s) = f(xk + sdk),
此函数是搜索区间[a0,b0]上的单峰函数,在第i次迭代之后,区间为[ai,bi],取两个试探点pi,qi属于[ai,bi] 且pi<qi 那么计算这个函数的pi和qi的值,