非线性规划.ppt

非线性规划,基础知识 直线搜索问题 无约束问题 不等式约束问题 等式和不等式约束问题 拉格朗日对偶问题,主要内容,基础知识,非线性规划的一般形式,其中,定义可行集,上述一般形式可简写成,全局最优解 ：,的 邻域：,局部最优解 ：,，且存在 满足,如果在上面的定义中用 替换 ， 则称 为严格局部最优解和严格全局最优解,局部最优解,全局最优解,邻域,标量函数求偏导数（梯度）,向量函数求偏导数,海赛（Hesse）矩阵,对向量函数的点积求偏导数,对常数矩阵和向量函数的乘积求偏导数,对二次函数求偏导数（ ）,一元函数在原点的二阶泰勒（Taylor）展开,其中,多元函数在给定点沿给定方向的二阶泰勒展开,其中,无约束优化问题最优性条件,1） 是局部最优解的必要条件：,理由：,不是局部最优解,2） 是严格局部最优解的充分条件：,理由：,（凸集上的）凸函数和凹函数,设 是定义在集合 上的函数，如果 是凸集，并且对 中任意两点 以及闭区间 中任意一点 都满足,则称 是（凸集 上的）凸函数，如果 是（凸集 上的）凸函数，则称 是（凸集 上的）凹函数，此时在上面的条件下应满足,一元凸（凹）函数的图象,凸函数,凹函数,一元可导凸（凹）函数的充要条件,凸函数,凸函数,凹函数,多元可导凸（凹）函数的一阶充要条件,必要性：,利用二阶泰勒展开可得,记,令 充分小，由凸（凹）性可得上面的不等式,充分性：,用 和 分别乘以上两式再相加，再利用,可得,记 ，则 ，利用给定条件,可得,凸（凹）函数的二阶充分条件,记,因为,若 是开集，前面的充分条件也是必要条件,若存在 和 使得 ， 必存在充分小的 满足,取 满足 ，利用,记 ，由以上条件可得,和前面证明的凸（凹）函数的充要条件矛盾,凸性对优化问题的基本作用,如果 是凸集， 是其上的连续凸函数，称,解，那么它也是该问题的全局最优解,是凸规划问题,如果 是凸规划问题的任意一个局部最优,证明：如果存在 满足,接近 ，说明 不是局部最优解，矛盾,又因为,因为对充分小的 ， 能够充分,可行下降方向,对于优化问题 ，给定可行解 以,称为可行下降方向,称 是 处的可行方向，如果存在 满足,及向量 ，如果存在 满足,称 是 处的下降方向，既可行又下降的方向,的等值线,可行（不下降）方向,可行下降方向,（不可行）下降方向,可行下降迭代算法,确定可行下降方向,确定初始可行解,确定 处的可行下降方向,直线搜索确定 满足 以及,在 处沿 进行一维,搜索确定,如此继续,