文档介绍：膅最优化理论与算法(数学专业研究生)蒂莁第一章引论蚇§、历史与现状节最优化理论最早可追溯到古老的极值问题,但成为一门独立的学科则是在20世纪四十年代末至五十年代初。其奠基性工作包括FritzJohn最优性条件(1948),Kuhn-Tucker最优性条件(1951),和Karush最优性条件(1939)。近几十年来最优化理论与算法发展十分迅速,应用也越来越广泛。现在已形成一个相当庞大的研究领域。关于最优化理论与方法,狭义的主要指非线性规划的相关内容,而广义的则涵盖:线性规划、非线性规划、动态规划、整数规划、几何规划、多目标规划、随机规划甚至还包括变分、最优控制等动态优化内容。本课程所涉及的内容属于前者。聿二、最优化问题的一般形式聿1、无约束最优化问题羄()羃2、约束最优化问题膀()***这里和均为指标集。蚇螃§、(范数)()蒃(范数)()聿(范数)()蚈(范数)()薆(正定)(椭球范数)()膄事实上1-范数、2-范数与范数分别是-范数当=1、2和时情形。,它具有下列性质:羅①对于都有,而时;羄②对于任意,都有;膁③;腿④;莅若还进一步满足:蚅⑤罿则称之为与向量范数相协调(相容)的方阵范数。若令芇(这里是某一向量范数)()螄可证这样定义的范数是与向量范数相协调的,通常称之为由向量范数诱导的方阵范数。特别地,对方阵,有:膁(列和的最大者)()羀(行和的最大者)()莆(表示的特征值的最大者)()芃称为谱范数(注:方阵的特征值的模的最大者称为的谱半径,记为)。羁对于由向量诱导的方阵范数,总有:肂,(为单位阵)螈对于方阵范数,除了上述由向量范数诱导的范数之外,还有常用的Frobenius范数,简称F-范数:()羇及加权Frobenius范数和加权范数:蚂()衿()袆其中为对称正定矩阵。,若存在,使得羀,()艿则称范数与是等价的。螅容易证明:膂()羂()莇()芅()袃()蝿其中是的最大特征值,而是的最小特征值。由此可见,中的常用向量范数均等价,事实上还可证明:中所有向量范数均等价。。蚄①Cauchy-Schwarz不等式蚃(当且仅当和线性相关时,等式成立)()袀②设是正定矩阵,则袈(当且仅当与线性相关时,等式成立)()肄由是一种内积,以及一般内积的Cauchy-Schwarz不等式即得。莄③设是正定矩阵,则袂(仅当与线性相关时,等式成立)()羆()螇其中的不等号由②可得。膄④Young不等式:假定与都是大于1的实数,且满足,则,有虿,()荿当且仅当时,等式成立。其证明由算术-几何不等式直接给出,事实上膆(算术-几何不等式)袄⑤Hölder不等式螁()蒇其中与都是大于1的实数,且满足,其证明利用Young不等式可得。蚆⑥Minkowski不等式莁,()()螂后面将利用凸函数理论予以证明。衿肅二、-(Von-Neumann引理)设,是单位阵,是满足的相容矩阵范数。如果,则非奇异,且羈,蒄若非奇异,,则非奇异,且袁,.蚁证明:因为,故定义了一个Cauchy序列,因而收敛。由肆袄可得薂故有螂进一步有。葿再令,莃知莂由上面结论可得,葿薇所以有肇进一步有。肃注:这个定理表明,若充分接近一个可逆矩阵,则也可逆,且逆矩阵可由的逆矩阵来表示。薁上述定理还可以写成下面形式:,,可逆,。若,且,则可逆,且蒆。螃证明:只需注意到,再由上述Von-Neumann引理即得。,若满足:袅()薃则称是的广义逆。其中是的共轭转置。蒀广义逆的求法膆①设,秩,若直交分解为,其中,分别为酉矩阵,,,其中是非奇异的上三角矩阵。则的广义逆为:芅其中()芄②若的奇异值分解为,其中,均为酉矩阵,,而是的非零奇异值,则的广义逆为:蒁,其中()蒈③若的最大秩分解为,则的广义逆为:螄.()肄芈三、,,则称膃()(),则Rayleigh商具有下列性质:罿1)齐次性:()袇2)极性: