最优化理论与方法概述

第一章最优化问题与凸分析基础在日常生活中，无论做什么事情，总是有多种方案可供选择，并且可能出现多种不同的结果。我们在做这些事情的时候，总是自觉不自觉的选择一种最优方案，以期达到最优结果。这种追求最优方案以达到最优结果的学科就是最优化。寻求最优方案的方法就是最优化方法。这种方法的理论基础就是最优化理论，而凸分析又是最优化理论的基础之一。1.最优化问题最优化问题：求一个一元函数或多元函数的极值。在微积分中，我们曾经接触过一些比较简单的极值问题。下面通过具体例子来看看什么是最优化问题。1.1最优化问题的例子例1对边长为a的正方形铁板，在四个角处剪去相等的正方形以制成方形无盖水槽，问如何剪法使水槽的容积最大？解：设剪去的正方形边长为x，由题意易知，此问题的数学模型为， 配料每磅配料中的营养含量钙蛋白质纤维每磅成本（元）石灰石谷物大豆粉0.3800.000.000.0010.090.020.0020.500.08

0.01640.04630.1250例2.（混合饲料配合）设每天需要混合饲料的批量为100磅，这份饲料必须含：至少0.8%而不超过1.2%的钙;至少22%的蛋白质;至多5%的粗纤维。假定主要配料包括石灰石、谷物、大豆粉。这些配料的主要营养成分如下表所示。试以最低成本确定满足动物所需营养的最优混合饲料。解:根据前面介绍的建模要素得出此问题的数学模型如下:设是生产100磅混合饲料所须的石灰石、谷物、大豆粉的量（磅）。1.2最优化问题的数学模型一般形式向量形式其中

目标函数不等式约束等式约束

称满足所有约束条件的向量为可行解，或可行点，全体可行点的集合称为可行集，记为。

若是连续函数，则是闭集。

在可行集中找一点，使目标函数在该点取最小值，即满足：的过程即为最优化的求解过程。称为问题的最优点或最优解，称为最优值。

定义1：整体（全局）最优解：若，对于一切，恒有则称是最优化问题的整体最优解。定义2：局部最优解：若，存在某邻域，使得对于一切，恒有则称是最优化问题的局部最优解。其中严格最优解：当，有则称为问题的严格最优解。f(X)局部最优解整体最优解1.3最优化问题的分类与时间的关系：静态问题，动态问题是否有约束条件：有约束问题，无约束问题函数类型：线性规划，非线性规划2、梯度与Hesse矩阵2.1等值线二维问题的目标函数表示三维空间中的曲面。在空间直角坐标系中，平面与曲面的交线在平面上的投影曲线为取不同的值得到不同的投影曲线。每一条投影曲线对应一个值，所以我们称此投影曲线为目标函数的等值线或等高线。当常数取不同的值时，重复上面的讨论，在平面上得到一族曲线——等值线.等值线的形状完全由曲面的形状所决定；反之，由等高线的形状也可以推测出曲面的形状．例

在坐标平面上画出目标函数的等值线．

解:因为当目标函数取常数时，曲线表示是以原点为圆心，半径为的圆．因此等值线是一族以原点为圆心的同心圆（如图所示）

2.2n元函数的可微性与梯度梯度：多元函数关于的一阶导数Hesse矩阵：多元函数关于的二阶偏导数矩阵例：求目标函数的梯度和Hesse矩阵。解：因为

则又因为：

故Hesse阵为：

下面几个公式是今后常用到的：（1），则（2），则(单位阵）（3），Q对称，则（4）若，其中f：则：

3、多元函数的Taylor展开

多元函数Taylor展开式在最优化理论中十分重要。许多方法及其收敛性的证明都是从它出发的。

定理：设具有二阶连续偏导数。则：

其中而0＜θ＜1多元函数Taylor展开其他形式：

凸集和凸函数在非线性规划的理论中具有重要作用，下面给出凸集和凸函数的一些基本知识。定义1

设，若对D中任意两点与，连接与的线段仍属于D；换言之，对，∈D，∈[0,1]恒有

+(1-)∈D则称D为凸集。+(1-)称为和的凸组合。nRDÍ)1(x)2(x)1(x)2(x")1(x)2(xa")1(xa)2(xa)1(xaa)2(x)1(x)2(x5、凸集、凸函数和凸规划例规定：欧式空间是凸集，空集是凸集，单点集{x}为凸集例:证明集合是凸集。其中，A为mn矩阵，b为m维向量。证明：任取，则所以，例：给定线性规划，其中，若令，则是凸集。凸集的性质有限个凸集的交集仍然是凸集。设是凸集，则是凸集。设是凸集，则是凸集。凸集的和集仍然是凸集。设是凸集，则是凸集。推论：设是凸集，，则也是凸集，其中。定义3极点（顶点）：设D是凸集,若D中的点x不能成为D中任何线段上的内点，则称x为凸集D的极点。设D为凸集，X∈D,若X不能用X(1)∈D,X(2)∈D两点的一个凸组合表示为X=αX(1)+(1-α)X(2),其中0<α<1，则称X为D的一个极点。定义2.凸组合：设X(1)，X(2)，…，X(k)是n维欧式空间中的k个点，若存在μ1,μ2,…,μk满足0≤μi≤1,(i=1,2,…,k),

使X=μ1X(1)+μ2X(2)+…μkX(k)，则称X为X(1)，X(2)，…，X(k)的凸组合。

多边形的顶点是凸集的极点（顶点）。圆周上的点都是凸集的极点（顶点）。定义4

设D为R中非空凸集，若对，∈D，∈(0,1)恒有n")1(x)2(xa"f[+(1-)]≤+(1-)f(*))1(xa)2(xa)()1(xfaa)()2(x则称为D上的凸函数；进一步，若≠时，(*)式仅〝<〞成立,则称为D上严格凸函数。)(xf)1(x)2(x)(xf对凸的一元函数的几何意义为：在曲线上任取两点P1(x1,),P2(x2,)弦位于弧之上（见图）。)(xf)(1xf(x2)f21PP21PPx1x2x(x,y)p1p2)(xf性质1：

f(x)是凸集D上的凹函数的充要条件是-f(x)是D上的凸函数。+(1-)-a)(1xfa)(2xf])1([21xxfaa-+=2221)1(xxaa-+221])1([xxaa-+-=2221)1(xxaa-+-])1(2)1([21222212xxxxaaaa-+-+=212221)1(2)1()1(xxxxaaaaaa---+-=(1-)aa)2(212221xxxx-+=(1-)aa(x1-x2)≥02∴+(1-)≥a)(1xfa)(2xf])1([21xxfaa-+所以，=

x是R上凸函数。)(xf2例如，对=x，因x1,x2∈R，∈(0,1))(xf"a"2例：证明线性函数是上的凸函数。

同理可证线性函数

也是上的凹函数。

定理2(一阶条件）：

设D是R中非空开凸集,是定义在D上的可微函数,则是凸函数的充要条件为x,y∈D,有n)(xf)(xf")(yf≥+(

y-x) )(xfT)(xfÑ而是D上严格凸函数为x,y∈D,x≠y,上式仅〝>〞成立。)(xf"xf(x)证明：必要性即由Taylor公式令得设则充分性令即所以同理定理3（二阶条件）：

设D是R中非空开凸集,是定义在D上的二次可微函数,则是凸函数的充要条件为对x∈D,≥0,即Hesse矩阵半正定。n)(xf)(xf")(2xfÑ)(2xfÑ若x∈D,>0，即Hesse矩阵正定，则为严格凸函数。")(2xfÑ)(xf证明：必要性所以由Taylor公式令得因为为开集。由一阶条件所以由p的任意性，半正定。充分性其中因为半正定故为凸函数。所以严格凸函数？充分性其中因为正定，故为严格凸函数。所以例：判断下列函数的凹凸性。（1）（2）解：

若规划ïîïíì===³ljhmigtsfji,,2,1,0)(,,2,1,0)(..)(minxxx……中,和-