最优化理论与算法VIP免费

1 / 30 最优化理论与算法（数学专业研究生）第一章引论§1.1 引言一、历史与现状最优化理论最早可追溯到古老的极值问题，但成为一门独立的学科则是在20 世纪四十年代末至五十年代初。其奠基性工作包括FritzJohn 最优性条件（ 1948），Kuhn-Tucker 最优性条件（ 1951），和 Karush 最优性条件 (1939) 。近几十年来最优化理论与算法发展十分迅速，应用也越来越广泛。现在已形成一个相当庞大的研究领域。关于最优化理论与方法，狭义的主要指非线性规划的相关内容，而广义的则涵盖：线性规划、非线性规划、动态规划、整数规划、几何规划、多目标规划、随机规划甚至还包括变分、最优控制等动态优化内容。本课程所涉及的内容属于前者。二、最优化问题的一般形式1、无约束最优化问题min( )nx Rf x（1.1 ）2、约束最优化问题min( )( )0,..( )0,iif xc xiEstc xiI（1.2 ）这里 E 和 I 均为指标集。§1.2 数学基础一、范数1. 向量范数maxixx （ l范数）（1.3 ）11niixx （1l 范数）（1.4 ）12221()niixx（2l 范数）（1.5 ）2 / 30 11()nppipixx（pl 范数）（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；②对于任意 kR ，都有 kAkA ；③ ABAB ；④ ABA B ；若还进一步满足：⑤ppAxAx则称之为与向量范数p 相协调（相容）的方阵范数。若令0maxxAxAx（这里x 是某一向量范数）（1.8 ）可证这样定义的范数是与向量范数相协调的，通常称之为由向量范数诱导的方阵范数。 特别地，对方阵()ijn nAa，有：11maxnijjiAa（列和的最大者）（ 1.9 ）1maxnijijAa（行和的最大者）（1.10 ）122()TA AA（TA A 表示TA A 的特征值的最大者） (1.11) 称为 谱范数 （注：方阵A 的特征值的模的最大者称为A 的谱半径，记为()A ）。对于由向量诱导的方阵范数，总有：3 / 30 101minxAAxx，1I（ I 为单位阵）对于方阵范数，除了上述由向量范数诱导的范数之外，还有常用的Frobenius 范数，简称F- 范数 ：1122211()[tr()]nnTijFijAaA A (1.12) 及加权 Frobenius 范数和加权2l 范数 : ,M FFAMAM(1.13) ,22MAMAM(1.14) 其中 M 为对称正定矩阵。3. 范数的等价性定义 1.2 设与...