第三章 无约束最优化方法

凸集 一个点集（或区域），如果连接其中任 意两点的线段都全部包含在该集合内， 就称该点集为凸集，否则为非凸集。
x1 x 2
7
第三章 无约束最优化方法
凸函数 函数f(x）为凸集定义域内的函数，若对任何的
0 1
及凸集域内的任意两点
x1 x 2
存在如下不等式：
f x1 1 x2 f x1 1 f ( x2 )
2 f x 2 x 1 2 f x * f x x1x2 2 f x x1xn 2 f x x2x1 2 f x
2 x2
2 f x*


2 f x x2xn
称 f x 是定义在凸集上的一个凸函数。
8
第三章 无约束最优化方法
9
第三章 无约束最优化方法
凸规划
对于约束优化问题
min f x
s.t.
g j x 0
j 1, 2,..., m
若 f x g j x 都为凸函数，则此问题为凸规划。
10
第三章 无约束最优化方法
当x1 x*时，则
f x1 f x2
25
3-2
一维搜索（0.618法）
从图中可看出，假定不知道极小点 x* 的位臵，任取 两点 x1 x2，如果 f x1 f x2 ，则 x*必在x1 , x2 之间； 若 f x1 f x2 ，则 x* x2 ；若 f x1 f x2 ，则 x* x1 。
梯度方向与等值面的关系
13
第三章 无约束最优化方法
方向导数 沿d方向的方向向 量
即
cos 1 cos 2 d ... cos n
T
T
f d
f x 0 d f x 0 cos f , d
x0
14
2 f x xn x1 2 f x xn x2 2 f x 2 xn
函数 f x 取得极小的充分条件是函数 f x 的Hessian矩阵 为正定方阵
16
第三章 无约束最优化方法
方阵
2 f x*
第三章 无约束最优化方法
方向导数的正负决定了函数的升降，而升降的快慢就由 f x 它的绝对值大小来决定。方向导数 0 又称为函数 f x d 在点x0 处沿 d方向的变化率。下降最快的方向称为最速 下降方向。 15
第三章 无约束最优化方法
Hessian矩阵（函数f x 的梯度f x 是它的一阶导数， Hessian矩阵是函数 f x 的二阶导数）
min
f x
x
假定 f x R1 ，且函数可微，则由极限的必备条件得 f x 0 一维搜索又称为直线搜索。
24
3-2
0.618法
一维搜索（0.618法）
0.618法适用于一般的单峰函数。所谓单峰函数，是指 这样的函数：在极小点 x*的左边，函数是严格减小的； 在 x* 的右边，函数是严格增加的。也就是说，若 x1 x2 是任意两点： f x1 f x2 当x2 x*时，则
一个对称矩阵 是不是正定的，可以用Sylvester定理来判定。 定理(Sylvester ) 一个 n×n阶对称矩阵Q 是正定矩阵 的充分必要条件是，矩阵Q 的各阶主子式都是正的。 11
第三章 无约束最优化方法
多元函数的梯度和性质 定义 以 f x 的n偏导数为分量的向量称为f x 在 x处 的梯度，记为
k
lim xk x
*
或等价地
k
lim xk -x* 0
* 那么就说该算法所产生的序列收敛于 x
18
第三章 无约束最优化方法
下降迭代法：在给定初始点后，如果每迭代一步都使目标 函数有所下降，即 f xk 1 f xk ，那么这种迭代法称为下 降法。 假定我们已经迭代到点 x k 处，那么下一步迭代将有以 下两种情况之一发生：
为正定的定义是：若对任何向量d (d!=0)，有
d T 2 f x* d 0
对称正定方阵 2 f x* 的检验方法是所有主子式均大于零。 二、迭代方法 求解 无约束最优化问题 T f x min x x1, x2 , , xn 的问题可以转变为求解n 元方程组
①、从 x k 出发沿任何方向移动，目标函数不再下降。x k 是局部极小点，迭代终止。
②、从 x k出发至少存在一个方向使目标函数有所下降。这 时，从中选定一个下降方向 pk ，再沿这个方向适当迈进 一步，即在直线
19
第三章 无约束最优化方法
x xk t pk
上适当选定一个新点 xk 1 xk tk pk
f x f x f x f x , , , x2 xn x1
T
梯度也可以称为函数 f x 关于向量 x的一阶导数。
12
第三章 无约束最优化方法
梯度的性质 ①、函数在某点的梯度若不为零，则必与过该点的等 值面‚垂直‛； ②、梯度方向是函数具有最大变化率的方向。 如图所示，证明上面性质①。为了证明性质②引入方 向导数的概念。
f x f x
*

所以函数f(x)在 x * 处取得局部极小值，称x *为
局部极小点。 而优化问题一般是要求目标函数在某一区域内 的全局极小点。 函数的局部极小点是不是一定是全局极小点呢？
5
第三章 无约束最优化方法
下凸的一元函数
可以证明凸规划问题的局部最小点就是其全局最小点。
6
第三章 无约束最优化方法
即
或
ax a x ax1 ' ab a1b1 ax1 1
' 1
' 1 2
2
（3-2.2） 30
3-2
一维搜索（0.618法）
28
3-2
一维搜索（0.618法）
设区间 a, b 的长为1，在与点 a 相距分别为 和 的点插 x1 和 x1 。为确定 和 ，我们提出一些条件：
应该怎样选取 xi 与 xi 呢？
a, b 中的位臵是对称的。这样一 第一，希望 xi 和 xi 两点在 来，无论删除哪一段，总是保留长为 的区间（板书所 示）。按这一条件有
正定矩阵 设 Q是n×n 阶对称矩阵。
若 x Rn 且 x 0 都有 x T Q x 0 ，则称矩阵Q 是正定的 若 x R
n n
T x 都有 Q x 0 ，则称矩阵Q 是半正定的
若 x R 且 x 0 都有 xT Q x 0 ，则称矩阵Q 是负定的 若 x Rn 都有 x T Q x 0 ，则称矩阵Q 是半负定的
21
第三章 无约束最优化方法
上述算法可用如Βιβλιοθήκη 框图表达开始选定x0 确定p使得
T f(x0) p 0
f(x0 tp) f(x0)
x x 0 tp
是
确定t使得
x满足终止准则 否
X,f(x)
22
x0 x
停
第三章 无约束最优化方法
三、无约束最优化方法的分类 可以处理复杂函数及没有数学表达式 直接法
j 1,2,
, m
, p
k m 1, m 2,
数学规划方法是在规定的约束条件下，用数学手段直 接求目标函数的极大、极小值。特殊情况：
2
第三章 无约束最优化方法
1、无约束最优化问题——不存在约束条件
2、线性规划——当目标函数、约束函数均是变量X的线 性函数时 3、非线性规划——当函数中至少有一个是非线性函数时
b ax1 x1
即
1
（3-2.1）
29
3-2
一维搜索（0.618法）
, b ，在保留下来的 第二，无论删除哪一段，例如删除 x1 ' a , x x x x1 区间里，再插入一个点 2 使得 2 ， x1 在 1 中 的位臵与 在 a, b中的位臵具有相同的比例。这就保证每次迭代 和 x1 都以同一 的比率缩短区间。按这一条件有
第三章 无约束最优化方法
同济大学土木工程学院建筑工程系 杨 彬 Course_yb@
1
第三章 无约束最优化方法
最优化的数学模型为 求 min
x x1, x2 , , xn
T
x Rn
f x
subject to (or s.t.) g j x 0
hk x 0
26
3-2
一维搜索（0.618法）
设给定一个较小的步长δ，从α=0开始，先计算φ(0)，然 后计算在 (1.618)0 的函数值φ(δ)；如果φ(δ)<φ(0)， 则讲步长δ增大1.618倍，得到一个新点 1.618 2.618 , 计算φ(2.618δ)；如果φ(2.618δ)仍小于φ(δ)，再继续增加 步长为原步长的1.618倍，如下图所示，从而得到一系列 j 点的αj的值为 '
3
第三章 无约束最优化方法
3-1 无约束最优化方法概述
无约束最优化问题是数学规划的基础。 无约束最优化问题的定义：求函数 f x 的极小（或极 n n维欧氏空间）。 大）值， x R（ 求函数 极小值。
4
第三章 无约束最优化方法
一、最优性条件 根据函数极值条件确定了极小点
x*
则函数f(x)在 x * 附近的一切x均满足不等式
j (1.618)
i 0
(3.2- 1)
27
3-2