最优化理论与算法(第一章)

1 最优化理论与算法（数学专业研究生） 第一章 引论 §1.1 引言 一、历史与现状 最优化理论最早可追溯到古老的极值问题，但成为一门独立的学科则是在 20 世纪四十年代末至五十年代初。其奠基性工作包括 Fritz John 最优性条件（1948），Kuhn-Tucker 最优性条件（1951），和 Karush 最优性条件(1939)。近几十年来最优化理论与算法发展十分迅速，应用也越来越广泛。现在已形成一个相当庞大的研究领域。关于最优化理论与方法，狭义的主要指非线性规划的相关内容，而广义的则涵盖：线性规划、非线性规划、动态规划、整数规划、几何规划、多目标规划、随机规划甚至还包括变分、最优控制等动态优化内容。本课程所涉及的内容属于前者。 二、最优化问题的一般形式 1、无约束最优化问题 min( )nxRf x （1.1） 2、约束最优化问题 min( )( )0, . .( )0, iif xc xiEs tc xiI （1.2） 这里 E 和 I 均为指标集。 §1.2 数学基础 一、 范数 1. 向量范数 maxixx  （l 范数） （1.3） 11niixx  （1l 范数） （1.4） 12221()niixx  （2l 范数） （1.5） 2 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，都有kAk A； ③ ABAB； ④ ABA B； 若还进一步满足： ⑤ ppAxA x 则称之为与向量范数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 101minxAAxx ，1I  （I 为单位阵） 对于方阵范数，除了上述由向量范数诱导的范数之外，还有常用的Frobenius 范...