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

1.1 最优化问题的例子例1 对边长为a的正方形铁板，在四个角处剪去相等的正方形以制成方形无盖水槽，问如何剪法使水槽的容积最大？2max(2)axx例例2.（混合饲料配合）设每天需要混合饲料的批量（混合饲料配合）设每天需要混合饲料的批量为为100磅，这份饲料必须含：至少磅，这份饲料必须含：至少0.8%而不超过而不超过1.2%的钙的钙;至少至少22%的蛋白质的蛋白质;至多至多5%的粗纤维。的粗纤维。假定主要配料包括石灰石、谷物、大豆粉。这些配假定主要配料包括石灰石、谷物、大豆粉。这些配料的主要营养成分如下表所示。试以最低成本确定料的主要营养成分如下表所示。试以最低成本确定满足动物所需营养的最优混合饲料。满足动物所需营养的最优混合饲料。配料每磅配料中的营养含量钙蛋白质纤维每磅成本（元）石灰石谷物大豆粉0.380 0.00 0.000.001 0.09 0.020.002 0.50 0.08 0.0164 0.0463 0.1250解解:根据前面介绍的建模要素得出此问题的数学模型如下根据前面介绍的建模要素得出此问题的数学模型如下:设设 是生产是生产100磅混合饲料所须的石灰石、谷物、磅混合饲料所须的石灰石、谷物、大豆粉的量（磅）。大豆粉的量（磅）。321xxx00010005.008.002.010022.050.009.0100008.0002.0001.0380.0100012.0002.0001.0380.0100.1250.00463.00164.0min3213232321321321321xxxxxxxxxxxxxxxxt sxxxZ121212min()()012.()012()ninjnf x xxg x xxils th x xxjm m n，11()()()()()()TTlmG Xg Xg XH Xh XhX，min()()0.()0fG Xs tH X，X12(,)nXx xx min.00jifxs tgxhx 目标函数目标函数不等式约束不等式约束等式约束等式约束 称满足所有约束条件的向量称满足所有约束条件的向量 为为可行解，或可行点可行解，或可行点，全体，全体可行点的集合称为可行点的集合称为可行集，记为可行集，记为 。x|0,1,2,0,1,2,ijnDx hximgxjp xR 若若 是连续函数，则是连续函数，则 是闭集。是闭集。(),()ijhxgxDD 在可行集中找一点在可行集中找一点 ，使目标函数，使目标函数 在该点取最小值，即在该点取最小值，即满足：满足：的过程即为的过程即为最优化的求解过程。最优化的求解过程。称为问题的称为问题的最优点或最优点或最优解最优解，称为称为最优值最优值。*x fx *min.0.0jifxfxs tgxhx*x *fx定义定义1：整体（全局）最优解：整体（全局）最优解：若若 ，对于一切，对于一切 ，恒有恒有 则称则称 是最优化问题的整体最优解。是最优化问题的整体最优解。定义定义2：局部最优解：局部最优解：若若 ，存在某邻域，存在某邻域 ，使得对于，使得对于一切一切 ，恒有，恒有 则称则称 是最优化问题是最优化问题的局部最优解。其中的局部最优解。其中 严格最优解：严格最优解：当当 ，有，有 则称则称 为问题的为问题的严格最优解。严格最优解。*xD xD *fxfx*x*xD*()Nx*()xNxD *fxfx*x*()|,0Nxxxx *xx *fxfx*x1,2()tf x x 12(,)tf x xtC 12xx，221212()f x xxx，n梯度：多元函数梯度：多元函数 关于关于 的的一阶导数一阶导数12()(,)Tnffff xxxx()f xxnHesse 矩阵：多元函数矩阵：多元函数 关于关于 的二阶偏导的二阶偏导数矩阵数矩阵 22222111222221 222222212f Xf Xf Xxxxxnxf Xf Xf Xf Xf Xx xxxnxf Xf Xf Xx xx xnnxn ()f xx例：求目标函数的梯度和Hesse矩阵。解：因为 则 又因为：故Hesse阵为：2221231 22 33()223f xxxxxxx xx 2202220222Xf2,2,20,2,2232322222312212212xfxxfxfxxfxxfxf TxxxxxxxXf233122122,3222,22 23322xxxXf 21122xxxXf 32223122xxxxXf下面几个公式是今后常用到的：（1），则 （2），则 (单位阵）（3），Q对称，则（4）若 ，其中f：则：TfXb X nnXfbXf0.212TfXX X IXfXXf2.12TfXX QX .,2QXfQXXf 0tfXtp.1RRn.:11RR ,0,20.TTtfXtpptpfXtp p 多元函数Taylor展开式在最优化理论中十分重要。许多方法及其收敛性的证明都是从它出发的。定理：设定理：设 具有二阶连续偏导数。则：具有二阶连续偏导数。则：其中 而01 Taylor展开式还可写成如下形式：展开式还可写成如下形式：1:nfRR 212TTf Xpf Xf Xppf X p.XXp 22102TTf Xpf Xf Xppf X pp凸集凸集非凸集非凸集非凸集非凸集12,XXS12,AXb AXb1212(1)(1)(1)AXXAXAXbbb|SX AXb12(1)XXSmin .0TC XstAXbX,nmm nnCR bRARXR*|,0RX AXb X*RX严格凸函数严格凸函数凸函数凸函数严格凹函数严格凹函数 12121212()mmmmfxxxf xf xf x 12,xxS 1121(2)()()()Tf xf xf xxx2()f x2()f x2()f x221122()32210f xxxxx2212()f xxx 1212()()62,41,f xf xxxxx222222121221()()()()6,4,0,f xf xf xf xxxx xx x260()04f x()f x2212()f xxx220()02f x()f xmin ()().()0,1,2,if XPstg Xim()f X()ig Xmin .0TC XstAXbX2212121212min 22.1 0,0 xxx xstxxxx221212()22f Xxxx x12()1g Xxx2221231 3()3234f xxxxxx2211 22()23f xxxxx222123221213123min ()2.4 510 ,0f xxxxstxxxxx x x