最优化理论与方法-第一章

最优化方法-习题解答张彦斌计算机学院2014年10月20日Contents1第一章最优化理论基础-P13习题1(1)、2(3)(4)、3、412第二章线搜索算法-P27习题2、4、643第三章最速下降法和牛顿法P41习题1，2，374第四章共轭梯度法P51习题1，3，6(1)105第五章拟牛顿法P73-2126第六章信赖域方法P86-8147第七章非线性最小二乘问题P98-1，2，6188第八章最优性条件P112-1，2,5,6239第九章罚函数法P132，1-(1)、2-(1)、3-(3),62610第十一章二次规划习题11P178-1（1），5291第一章最优化理论基础-P13习题1(1)、2(3)(4)、3、4 1.验证下列各集合是凸集:(1)S={(x1,x2)|2x1+x2≥1,x1−2x2≥1};需要验证：根据凸集的定义，对任意的x(x1,x2),y(y1,y2)∈S及任意的实数λ∈[0,1],都有λx+(1−λ)y∈S.即,(λx1+(1−λ)y1,λx2+(1−λ)y2)∈S证：由x(x1,x2),y(y1,y2)∈S得到，{2x1+x2≥1,x1−2x2≥12y1+y2≥1,y1−2y2≥1(1)1把(1)中的两个式子对应的左右两部分分别乘以λ和1−λ,然后再相加，即得λ(2x1+x2)+(1−λ)(2y1+y2)≥1,λ(x1−2x2)+(1−λ)(y1−2y2)≥1(2)合并同类项，2(λx1+(1−λ)y1)+(λx2+(1−λ)y2)≥1,(λx1+(1−λ)y1)−2(λx2+(1−λ)y2)≥1(3)证毕.2.判断下列函数为凸（凹）函数或严格凸（凹）函数：(3)f(x)=x21−2x1x2+x22+2x1+3x2首先二阶导数连续可微，根据定理1.5，f在凸集上是（I）凸函数的充分必要条件是∇2f(x)对一切x为半正定；（II）严格凸函数的充分条件是∇2f(x)对一切x为正定。

最优化理论与算法（数学专业研究生）第一章 引论§1.1 引言一、历史与现状最优化理论最早可追溯到古老的极值问题，但成为一门独立的学科则是在20世纪四十年代末至五十年代初。

其奠基性工作包括Fritz John 最优性条件（1948），Kuhn-Tucker 最优性条件（1951），和Karush 最优性条件(1939)。

近几十年来最优化理论与算法发展十分迅速，应用也越来越广泛。

现在已形成一个相当庞大的研究领域。

关于最优化理论与方法，狭义的主要指非线性规划的相关内容，而广义的则涵盖：线性规划、非线性规划、动态规划、整数规划、几何规划、多目标规划、随机规划甚至还包括变分、最优控制等动态优化内容。

本课程所涉及的内容属于前者。

二、最优化问题的一般形式 1、无约束最优化问题min ()nx Rf x ∈ （1.1） 2、约束最优化问题min ()()0, ..()0, i i f x c x i E s t c x i I=∈⎧⎨≥∈⎩ （1.2）这里E 和I 均为指标集。

§1.2数学基础一、 范数 1. 向量范数max i x x ∞= （l ∞范数） （1.3）11ni i x x ==∑ （1l 范数） （1.4）12221()ni i x x ==∑ （2l 范数） （1.5）11()np pi pi xx ==∑ （p l 范数） （1.6）12()TAxx Ax = （A 正定） （椭球范数） （1.7）事实上1－范数、2－范数与∞-范数分别是 p －范数当 p ＝1、2和p →∞时情形。

2．矩阵范数定义1.1 方阵A 的范数是指与A 相关联并记做A 的一个非负数，它具有下列性质： ① 对于0A ≠都有0A >，而0A =时0A =； ② 对于任意k R ∈，都有kA k A =； ③ A B A B +≤+； ④ AB A B ≤； 若还进一步满足： ⑤ pp AxA x ≤则称之为与向量范数p相协调（相容）的方阵范数。

最优化基础理论与⽅法⽬录1．最优化的概念与分类 (2)2. 最优化问题的求解⽅法 (3)2.1线性规划求解 (3)2.1.1线性规划模型 (3)2.1.2线性规划求解⽅法 (3)2.1.3 线性规划算法未来研究⽅向 (3)2.2⾮线性规划求解 (4)2.2.1⼀维搜索 (4)2.2.2⽆约束法 (4)2.2.3约束法 (4)2.2.4凸规划 (5)2.2.5⼆次规划 (5)2.2.6⾮线性规划算法未来研究⽅向 (5)2.3组合规划求解⽅法 (5)2.3.1 整数规划 (5)2.3.2 ⽹络流规划 (7)2.4多⽬标规划求解⽅法 (7)2.4.1 基于⼀个单⽬标问题的⽅法 (7)2.4.2 基于多个单⽬标问题的⽅法 (8)2.4.3多⽬标规划未来的研究⽅向 (8)2.5动态规划算法 (8)2.5.1 逆推解法 (8)2.5.2 顺推解法 (9)2.5.3 动态规划算法的优点及研究⽅向 (9)2.6 全局优化算法 (9)2.6.1 外逼近与割平⾯算法 (9)2.6.2 凹性割⽅法 (9)2.6.3 分⽀定界法 (9)2.6.4 全局优化的研究⽅向 (9)2.7随机规划 (9)2.7.1 期望值算法 (10)2.7.2 机会约束算法 (10)2.7.3 相关机会规划算法 (10)2.7.4 智能优化 (10)2.8 最优化软件介绍 (11)3 最优化算法在电⼒系统中的应⽤及发展趋势 (12)3.1 电⼒系统的安全经济调度问题 (12)3.1.1电⼒系统的安全经济调度问题的介绍 (12)3.1.2电⼒系统的安全经济调度问题优化算法的发展趋势 (12)2. 最优化问题的求解⽅法最优化⽅法是近⼏⼗年形成的，它主要运⽤数学⽅法研究各种优化问题的优化途径及⽅案，为决策者提供科学决策的依据。

最优化⽅法的主要研究对象是各种有组织系统的管理问题及其⽣产经营活动。

最优化⽅法的⽬的在于针对所研究的系统，求得⼀个合理运⽤⼈⼒、物⼒和财⼒的最佳⽅案，发挥和提⾼系统的效能及效益，最终达到系统的最优⽬标。

第1讲最优化理论与方法概述
优化理论与方法是科学技术、工程技术及社会经济领域最基本的理论与方法之一，它包括有效管理信息、数据资源、计算资源、计算方法及其运用于完成一定任务的整个过程。

优化理论与方法的基本特征是求解问题的最优解，即能够以最少的代价实现最大的效果。

因此，这门学科也有时被称为优化算法、优化方法、最优化理论与方法等。

优化理论与方法一般涉及到分析、求解、估算、定制和能力提升等基本活动。

它主要是通过分析、提取、重新组合有效信息，以最少的费用实现最大效益，系统地实现数据决策的动态过程，最终达到给定目标的一种科学过程。

优化理论与方法的应用范围十分广泛，既可以应用到工业管理、经济管理等领域，也可以应用到物理、化学、生物和生态学中，甚至可以用于地理系统分析和空间规划等方面。

在求解优化问题时，可以采取数学优化方法，也可以采用模拟优化方法，或利用一组算法和经验性算法等复杂技术来实现多目标的最优化。

常见的优化方法包括数学规划、非线性规划、半定规划、综合规划、多目标优化法、博弈论、动态规划、多变量优化及经验性算法等，这些方法可以根据具体问题，选择最合适的解决办法。

牛顿法牛顿法作为求解非线性方程的一种经典的迭代方法，它的收敛速度快，有内在函数可以直接使用。

结合着matlab 可以对其进行应用，求解方程。

牛顿迭代法（Newton ’s method ）又称为牛顿-拉夫逊方法（Newton-Raphson method ）,它是牛顿在17世纪提出的一种在实数域和复数域上近似求解方程的方法,其基本思想是利用目标函数的二次Taylor 展开，并将其极小化。

牛顿法使用函数()f x 的泰勒级数的前面几项来寻找方程()0f x =的根。

牛顿法是求方程根的重要方法之一，其最大优点是在方程()0f x =的单根附近具有平方收敛，而且该法还可以用来求方程的重根、复根，此时非线性收敛，但是可通过一些方法变成线性收敛。

牛顿法的几何解释：方程()0f x =的根*x 可解释为曲线()y f x =与x 轴的焦点的横坐标。

如下图：设k x 是根*x 的某个近似值，过曲线()y f x =上横坐标为k x 的点k P 引切线，并将该切线与x 轴的交点 的横坐标1k x +作为*x 的新的近似值。

鉴于这种几何背景，牛顿法亦称为切线法。

2 牛顿迭代公式：（1）最速下降法：以负梯度方向作为极小化算法的下降方向，也称为梯度法。

设函数()f x 在k x 附近连续可微，且()0k k g f x =∇≠。

由泰勒展开式： ()()()()()T k k k k fx f x x x f x x x ο=+-∇+- （*）可知，若记为k k x x d α-=，则满足0Tk k d g <的方向k d 是下降方向。

当α取定后，Tk k d g 的值越小，即T kk d g -的值越大，函数下降的越快。

由Cauchy-Schwartz 不等式： T k k kk d g d g ≤，故当且仅当k k d g =-时，Tk k d g 最小，从而称k g -是最速下降方向。

最速下降法的迭代格式为： 1k k k k x x g α+=-。