第一章 最优化问题与凸分析基础n在日常生活中，无论做什么事情，总是有 多种方案可供选择，并且可能出现多种不 同的结果。我们在做这些事情的时候，总 是自觉不自觉的选择一种最优方案，以期 达到最优结果。这种追求最优方案以达到 最优结果的学科就是最优化。寻求最优方 案的方法就是最优化方法。这种方法的理 论基础就是最优化理论，而凸分析又是最 优化理论的基础之一。1. 最优化问题n最优化问题：求一个一元函数或多元函数 的极值。在微积分中，我们曾经接触过一些比 较简单的极值问题。下面通过具体例子来 看看什么是最优化问题。1.1 最优化问题的例子例1 对边长为a的正方形铁板，在四个角处剪去相 等 的正方形以制成方形无盖水槽，问如何剪法使水 槽 的容积最大？ 解：设剪去的正方形边长为x，由题意易知，此问 题的数学模型为， 例2.（混合饲料配合）设每天需要混合饲料的批量为 100磅，这份饲料必须含：至少0.8%而不超过 1.2%的钙;至少22%的蛋白质;至多5%的粗纤维。 假定主要配料包括石灰石、谷物、大豆粉。这些配料 的主要营养成分如下表所示。试以最低成本确定满足 动物所需营养的最优混合饲料。配料每磅配料中的营养含量钙蛋白质纤维每磅成本（元 ）石灰石谷物大豆粉0.380 0.00 0.000.001 0.09 0.020.002 0.50 0.080.01640.04630.1250解:根据前面介绍的建模要素得出此问题的数学模型如下:设 是生产100磅混合饲料所须的石灰石、谷物 、大豆粉的量（磅）。1.2最优化问题的数学模型n一般形式n向量形式其中目标函数不等式约束等式约束称满足所有约束条件的向量 为可行解，或可行点，全体 可行点的集合称为可行集，记为 。若 是连续函数，则 是闭集。在可行集中找一点 ，使目标函数 在该点取最小值，即 满足： 的过程即为 最优化的求解过程。称为问题的最优点或最优解， 称为最优值。 定义1：整体（全局）最优解：若 ，对于一切 ， 恒有 则称 是最优化问题的整体最优解。定义2：局部最优解：若 ，存在某邻域 ，使得对于 一切 ，恒有 则称 是最优化问题 的局部最优解。其中严格最优解：当 ，有 则称 为问题的 严格最优解。f(X)f(X)局部最优解局部最优解整体最优解整体最优解1.3 最优化问题的分类n与时间的关系：静态问题，动态问题n是否有约束条件：有约束问题，无约束问题n函数类型：线性规划，非线性规划2、梯度与Hesse矩阵2.1 等高线二维问题的目标函数 表示三维空间中 的 曲面。在空间直角坐标系中，平面与曲面的交线 在 平面上的投影曲线为取不同的值得到不同的投影曲线。每一条投影曲 线 对应一个值，所以我们称此投影曲线为目标函数 的 等值线或等高线。当常数取不同的值当常数取不同的值 时，重复上面的讨论，时，重复上面的讨论， 在平面上得到一族曲线在平面上得到一族曲线 等高线等高线. .等高线的形状完全由等高线的形状完全由 曲面的形状所决定；反曲面的形状所决定；反 之，由等高线的形状也之，由等高线的形状也 可以推测出曲面的形状可以推测出曲面的形状 例例 在坐标平面在坐标平面 上画出目标函数上画出目标函数 的等高线的等高线解解: :因为当目标函数取常数时，曲线表示是以原点为因为当目标函数取常数时，曲线表示是以原点为 圆心，半径为的圆因此等高线是一族以原点为圆圆心，半径为的圆因此等高线是一族以原点为圆 心的同心圆（如图所示）心的同心圆（如图所示）2.2 梯度n梯度：多元函数 关于 的一阶导数2.3 Hesse矩阵nHesse 矩阵：多元函数 关于 的二阶偏导 数矩阵例：求目标函数 的梯度和Hesse矩阵。 解：因为 则又因为： 故Hesse阵为：下面几个公式是今后常用到的： （1） ，则 （2） ，则 (单位阵） （3） ，Q对称， 则（4）若 ，其中f： 则：3、 多元函数的Taylor展开多元函数Taylor展开式在最优化理论中十分重要。 许多方法及其收敛性的证明都是从它出发的。定理：设 具有二阶连续偏导数。则：其中 而01Taylor展开式还可写成如下形式：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为 mn矩阵，b为m维向量。 证明：任取 ，则所以，例：给定线性规划 ，其中 ， 若令 ，则 是凸集。定义：设 x(1) , x(2) , , x(m) Rn, j 0 j =1,那么称 j x(j) 为x(1), x(2), , x(m) 的凸组合。性质：l凸集的交集是凸集；（并集一般不是）l凸集的内点集是凸集；l凸集的闭包是凸集。4.2 凸函数定义: 设集合 S Rn 为凸集，函数 f :SR，若 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 上的凸 函 数 对任意 ，有定理：具有二阶连续偏导数的函数 f(x) 为非 空凸集 S 上的凸函数 是半正定矩 阵。 注： （1）当 是正定矩阵时，f(x) 是严格 凸函数； （2）当 是半正定矩阵时，- f(x) 是 凹函数例：判断下列函数的凹凸性。 （1） （2） 解：（1）为正定矩阵， 为严格凸 函数。 （2）因为 ，则易知所以 为凹函数。4.3 凸规划定义：对于规划若 与 都是凸函数，则称其为凸规划。例：线性规划 是凸规划。例：数学规划 易知， 与 都是凸函数，所以该规划是凸规划。对于一般的规划（P），其局部最优解不 一定是全局最优解，其可行集也未必是凸集。 但若（P）是凸规划，则有下面的结论。 定理：设规划（P）是凸规划，则 （1） （P）的可行集R为凸集； （2） （P）的最优解集合R*是凸集； （3） （P）的任何局部最优解都是全局最优 解。练习： 1、求 的梯度和Hesse 矩阵。 2、判断函数 的凹凸性。 3、判断下述非线性规划是否为凸规划？