最优化方法 第一章 最优化问题与凸分析基础

第一章最优化问题与凸分析基础在日常生活中，无论做什么事情，总是有多种方案可供选择，并且可能出现多种不同的结果。我们在做这些事情的时候，总是自觉不自觉的选择一种最优方案，以期达到最优结果。这种追求最优方案以达到最优结果的学科就是最优化。寻求最优方案的方法就是最优化方法。这种方法的理论基础就是最优化理论，而凸分析又是最优化理论的基础之一。1.最优化问题最优化问题：求一个一元函数或多元函数的极值。在微积分中，我们曾经接触过一些比较简单的极值问题。下面通过具体例子来看看什么是最优化问题。1.1最优化问题的例子例1对边长为a的正方形铁板，在四个角处剪去相等的正方形以制成方形无盖水槽，问如何剪法使水槽的容积最大？解：设剪去的正方形边长为x，由题意易知，此问题的数学模型为，2max(2)axx例2.（混合饲料配合）设每天需要混合饲料的批量为100磅，这份饲料必须含：至少0.8%而不超过1.2%的钙;至少22%的蛋白质;至多5%的粗纤维。假定主要配料包括石灰石、谷物、大豆粉。这些配料的主要营养成分如下表所示。试以最低成本确定满足动物所需营养的最优混合饲料。配料每磅配料中的营养含量钙蛋白质纤维每磅成本（元）石灰石谷物大豆粉0.3800.000.000.0010.090.020.0020.500.080.01640.04630.1250解:根据前面介绍的建模要素得出此问题的数学模型如下:设是生产100磅混合饲料所须的石灰石、谷物、大豆粉的量（磅）。321xxx00010005.008.002.010022.050.009.0100008.0002.0001.0380.0100012.0002.0001.0380.0100..1250.00463.00164.0min3213232321321321321xxxxxxxxxxxxxxxxtsxxxZ1.2最优化问题的数学模型一般形式向量形式其中121212min()()012..()012()ninjnfxxxgxxxilsthxxxjmmn，，，，，，，，，，，，，，，，，，，．11()[()()]()[()()]TTlmGXgXgXHXhXhX，，，，，min()()0..()0fGXstHX，，，X12(,,)nXxxxmin..00jifxstgxhx目标函数不等式约束等式约束称满足所有约束条件的向量为可行解，或可行点，全体可行点的集合称为可行集，记为。x{|0,1,2,,0,1,2,,}ijnDxhximgxjpxR若是连续函数，则是闭集。(),()ijhxgxDD在可行集中找一点，使目标函数在该点取最小值，即满足：的过程即为最优化的求解过程。称为问题的最优点或最优解，称为最优值。*xfx**min...0.0jifxfxstgxhx*x*fx定义1：整体（全局）最优解：若，对于一切，恒有则称是最优化问题的整体最优解。定义2：局部最优解：若，存在某邻域，使得对于一切，恒有则称是最优化问题的局部最优解。其中严格最优解：当，有则称为问题的严格最优解。*xDxD*fxfx*x*xD*()Nx*()xNxD*fxfx*x**(){|,0}Nxxxx*xx*fxfx*xf(X)局部最优解整体最优解1.3最优化问题的分类与时间的关系：静态问题，动态问题是否有约束条件：有约束问题，无约束问题函数类型：线性规划，非线性规划2、梯度与Hesse矩阵2.1等高线二维问题的目标函数表示三维空间中的曲面。在空间直角坐标系中，平面与曲面的交线在平面上的投影曲线为取不同的值得到不同的投影曲线。每一条投影曲线对应一个值，所以我们称此投影曲线为目标函数的等值线或等高线。1,2()tfxx12(,)tfxxtC当常数取不同的值时，重复上面的讨论，在平面上得到一族曲线——等高线.等高线的形状完全由曲面的形状所决定；反之，由等高线的形状也可以推测出曲面的形状．例在坐标平面上画出目标函数的等高线．解:因为当目标函数取常数时，曲线表示是以原点为圆心，半径为的圆．因此等高线是一族以原点为圆心的同心圆（如图所示）12xx，221212()fxxxx，2.2梯度梯度：多元函数关于的一阶导数12()(,,)Tnffffxxxx()fxx2.3Hesse矩阵Hesse矩阵：多元函数关于的二阶偏导数矩阵22222111222221222222212fXfXfXxxxxnxfXfXfXfXfXxxxxnxfXfXfXxxxxnnxn()fxx例：求目标函数的梯度和Hesse矩阵。解：因为则又因为：故Hesse阵为：22212312233()223fxxxxxxxxx2202220222Xf2,2,20,2,2232322222312212212xfxxfxfxxfxxfxfTxxxxxxxXf233122122,3222,2223322xxxXf21122xxxXf32223122xxxxXf下面几个公式是今后常用到的：（1），则（2），则(单位阵）（3），Q对称，则（4）若，其中f：则：TfXbXnnXfbXf0.212TfXXXIXfXXf2.12TfXXQX.,2QXfQXXf0tfXtp.1RRn.:11RR,0,,20.TTtfXtpptpfXtpp3、多元函数的Taylor展开多元函数Taylor展开式在最优化理论中十分重要。许多方法及其收敛性的证明都是从它出发的。定理：设具有二阶连续偏导数。则：其中而0＜θ＜1Taylor展开式还可写成如下形式：1:nfRR212TTfXpfXfXppfXp.XXp22102TTfXpfXfXppfXpp4、凸集、凸函数和凸规划4.1凸集定义：设集合SRn，若x(1),x(2)S,[0,1]，必有x(1)＋(1-)x(2)S，则称S为凸集。规定：单点集{x}为凸集，空集为凸集。注:x(1)＋(1-)x(2)=x(2)＋(x(1)-x(2))是连接x(1)与x(2)的线段。凸集非凸集非凸集例:证明集合是凸集。其中，A为mn矩阵，b为m维向量。证明：任取，则所以，12,XXS12,AXbAXb1212[(1)](1)(1)AXXAXAXbbb{|}SXAXb12(1)XXS例：给定线性规划，其中，若令，则是凸集。min..0TCXstAXbX,,,nmmnnCRbRARXR*{|,0}RXAXbX*R定义：设x(1),x(2),…,x(m)Rn,j≥0j=1,那么称jx(j)为x(1),x(2),…,x(m)的凸组合。性质：1)凸集的交集是凸集；（并集一般不是）2)凸集的内点集是凸集；3)凸集的闭包是凸集。X4.2凸函数定义:设集合SRn为凸集，函数f:SR，若x(1),x(2)S,(0,1)，均有f(x(1)＋(1-)x(2))≤f(x(1))+(1-)f(x(2))，则称f(x)为凸集S上的凸函数。若进一步有上面不等式以严格不等式成立，则称f(x)为凸集S上的严格凸函数。当-f(x)为凸函数（严格凸函数）时，则称f(x)为凹函数（严格凹函数）。严格凸函数凸函数严格凹函数定理：f(x)为凸集S上的凸函数S上任意有限点的凸组合的函数值不大于各点函数值的凸组合。定理：可微函数f(x)为非空凸集S上的凸函数对任意，有12121212()mmmmfxxxfxfxfx12,xxS1121(2)()()()Tfxfxfxxx定理：具有二阶连续偏导数的函数f(x)为非空凸集S上的凸函数是半正定矩阵。注：（1）当是正定矩阵时，f(x)是严格凸函数；（2）当是半正定矩阵时，-f(x)是凹函数2()fx2()fx2()fx例：判断下列函数的凹凸性。（1）（2）解：（1）为正定矩阵，为严格凸函数。（2）因为，则易知所以为凹函数。221122()32210fxxxxx2212()fxxx1212()()62,41,fxfxxxxx222222121221()()()()6,4,0,fxfxfxfxxxxxxx260()04fx()fx2212()fxxx220()02fx()fx4.3凸规划定义：对于规划若与都是凸函数，则称其为凸规划。例：线性规划是凸规划。min()()..()0,1,2,ifXPstgXim()fX()igXmin..0TCXstAXbX例：数学规划易知，与都是凸函数，所以该规划是凸规划。2212121212min22..10,0xxxxstxxxx221212()22fXxxxx12()1gXxx对于一般的规划（P），其局部最优解不一定是全局最优解，其可行集也未必是凸集。但若（P）是凸规划，则有下面的结论。定理：设规划（P）是凸规划，则（1）（P）的可行集R为凸集；（2）（P）的最优解集合R*是凸集；（3）（P）的任何局部最优解都是全局最优解。练习：1、求的梯度和Hesse矩阵。2、判断函数的凹凸性。3、判断下述非线性规划是否为凸规划？22212313()3234fxxxxxx221122()23fxxxxx222123221213123min()2..4510,,0fxxxxstxxxxxxx