第三章 无约束最优化方法

第三章 无约束最优化方法同济大学土木工程学院建筑工程系 杨 彬 Course_yb@http://doc.guandang.net1

第三章 无约束最优化方法最优化的数学模型为 求 minx x1, x2 , , xn T

x Rn

f x

subject to (or s.t.) g j x 0hk x 0

j 1,2,

, m , p

k m 1, m 2,

数学规划方法是在规定的约束条件下，用数学手段直 接求目标函数的极大、极小值。特殊情况：2

第三章 无约束最优化方法1、无约束最优化问题——不存在约束条件2、线性规划——当目标函数、约束函数均是变量X的线 性函数时 3、非线性规划——当函数中至少有一个是非线性函数时

第三章 无约束最优化方法3-1 无约束最优化方法概述

无约束最优化问题是数学规划的基础。 无约束最优化问题的定义：求函数 f x 的极小(或极 n n维欧氏空间)。 大)值， x R( 求函数 极小值。

第三章 无约束最优化方法一、最优性条件 根据函数极值条件确定了极小点

x*

则函数f(x)在 x * 附近的一切x均满足不等式

f x f x

*

所以函数f(x)在 x * 处取得局部极小值，称x *为局部极小点。 而优化问题一般是要求目标函数在某一区域内 的全局极小点。 函数的局部极小点是不是一定是全局极小点呢？

第三章 无约束最优化方法

下凸的一元函数

可以证明凸规划问题的局部最小点就是其全局最小点。6

第三章 无约束最优化方法凸集 一个点集(或区域),如果连接其中任 意两点的线段都全部包含在该集合内， 就称该点集为凸集，否则为非凸集。

x1 x 2

第三章 无约束最优化方法凸函数 函数f(x)为凸集定义域内的函数，若对任何的

0 1

及凸集域内的任意两点

x1 x 2

存在如下不等式：

f x1 1 x2 f x1 1 f ( x2 )称 f x 是定义在凸集上的一个凸函数。

第三章 无约束最优化方法

第三章 无约束最优化方法凸规划对于约束优化问题

min f x

s.t.

g j x 0

j 1, 2,..., m

若 f x g j x 都为凸函数，则此问题为凸规划。

第三章 无约束最优化方法正定矩阵 设 Q是n×n 阶对称矩阵。

若 x Rn 且 x 0 都有 x T Q x 0 ,则称矩阵Q 是正定的 若 x Rn nT x 都有 Q x 0 ,则称矩阵Q 是半正定的

若 x R 且 x 0 都有 xT Q x 0 ,则称矩阵Q 是负定的 若 x Rn 都有 x T Q x 0 ,则称矩阵Q 是半负定的

一个对称矩阵 是不是正定的，可以用Sylvester定理来判定。 定理(Sylvester ) 一个 n×n阶对称矩阵Q 是正定矩阵 的充分必要条件是，矩阵Q 的各阶主子式都是正的。 11

第三章

无约束最优化方法多元函数的梯度和性质 定义 以 f x 的n偏导数为分量的向量称为f x 在 x处 的梯度，记为

f x f x f x f x , , , x2 xn x1

T

梯度也可以称为函数 f x 关于向量 x的一阶导数。

第三章 无约束最优化方法梯度的性质 ①、函数在某点的梯度若不为零，则必与过该点的等 值面 垂直 ; ②、梯度方向是函数具有最大变化率的方向。 如图所示，证明上面性质①。为了证明性质②引入方 向导数的概念。

梯度方向与等值面的关系13

第三章 无约束最优化方法方向导数 沿d方向的方向向 量即 cos 1 cos 2 d ... cos n TT

f d

f x 0 d f x 0 cos f , d x0

第三章 无约束最优化方法

方向导数的正负决定了函数的升降，而升降的快慢就由 f x 它的绝对值大小来决定。方向导数 0 又称为函数 f x d 在点x0 处沿 d方向的变化率。下降最快的方向称为最速 下降方向。 15

第三章 无约束最优化方法Hessian矩阵(函数f x 的梯度 f x 是它的一阶导数， Hessian矩阵是函数 f x 的二阶导数) 2 f x 2 x 1 2 f x * f x x1 x2 2 f x x1 xn 2 f x x2 x1 2 f x 2 x2

2 f x*

2 f x x2 xn

2 f x xn x1 2 f x xn x2 2 f x 2 xn

函数 f x 取得极小的充分条件是函数 f x 的Hessian矩阵 为正定方阵16