最优化方法

第1章凸集和凸函数 　　本章首先简要介绍*优化方法这门学科，然后着重介绍凸集和凸函数这两个基本概念及其相关的性质.凸集和凸函数在*优化方法中广泛出现在线性规划、无约束优化以及约束优化等问题的描述和求解方法中. 　　1.1*优化问题和方法 　　*优化方法学科研究优化问题的求解方法.现实生活中，优化问题多种多样，*优化方法主要研究那些可以用数学模型刻画的优化问题.这些问题从总体上可分为组合优化问题和连续优化问题两类，它们是按照数学模型中所使用的变量的不同类型来划分的. 　　在历史上，优化技术出现得很早.17世纪时，在微积分技术的发展过程中，牛顿就研究过极值问题.后来又出现了处理带约束的目标函数极值问题的拉格朗日(Joseph-Louis Lagrange，法国，1736-1813)乘数法 1847年，柯西(Augustin-LouisCauchy，法国，1789-1857)研究了函数值沿什么方向下降*快的问题，提出了*速下降法.1939年，康托罗维奇(Kantorovich，苏联，1912-1986)提出了下料问题和运输问题的求解方法.直至20世纪30年代，*优化这个古老的课题尚未形成独立的学科. 　　20世纪40年代以来，由于工业生产和科学研究的迅猛发展，特别是计算机的日益广泛应用，*优化理论和算法迅速发展起来，成为运筹学的主体内容.运筹学(*优化方法)中的组合优化部分和计算机科学中的算法设计与分析部分是部分重合的，由于组合优化技术更强调了数学方法的运用，因此组合优化可以看作是传统的算法设计与分析的延伸.运筹学中的连续优化部分是在数学分析中的求导数和求极值的基础上发展起来的.现在，机器学习中损失函数的求解正好是连续优化问题.因此，运筹学的连续优化部分也构成了应用计算机科学解决实际问题的基础. 　　*优化方法的组合优化技术主要包括整数线性规划、动态规划以及面向问题的各种启发式方法等.*优化方法中的连续优化技术可分为线性规划和非线性规划，也可分为无约束优化和约束优化，这是分别按照不同的划分标准划分的.值得指出的是，线性规划技术，按照变量的类型划分属于连续优化，但线性规划技术也可以用于求解组合优化问题.例如在近似算法中，线性规划是获得广泛成功的一种算法设计方法.使用线性规划技术设计组合优化问题的近似算法时，人们首先用线性规划描述组合优化问题的松弛，然后求解线性规划得到*优解，再通过舍入等方法将线性规划*优解转化为组合优化问题的可行解. 　　下面我们看几个典型的优化问题. 　　例1.1.1利润*大化问题.某工厂用种原料生产种产品.第种原料的数量为每单位的第种产品需要第种原料的数量为，可获利润为.问如何安排生产，才能使总利润*大？ 　　例1.1.1中的利润*大化问题是经济领域中经常遇到的一个非常基本的问题.这个问题可以用线性规划或整数线性规划进行描述和求解. 　　在这里，我们定义为第种产品的产量.则所有种产品的总利润就是.问题的目标是*大化这个总利润.当然，利润不可能无限大，因为安排生产受限于原材料的供给.当第种产品的产量为时，生产这种产品对原料的需求为，显然应有，因为第种原料总共有那么多.另外，每种产品的产量也不能为负数.综合起来，我们就得到 　　(1.1.1) 　　这就是例1.1.1的数学模型，这是一个线性规划，因为在这个规划中目标函数和约束条件都只包含变量的一次项，没有变量的二次项以及更高次项，更没有变量的幂以外的其他函数. 　　值得指出的是，线性规划(1.1.1)适用于描述那些产品“无限可分”的利润*大化问题，如产品为面粉、食用油等.换言之，产品数量取值为实数应该是有意义的. 　　如果在利润*大化问题中，产品数量仅能取值为整数，例如产品为家具、门窗等，则我们需要使用整数线性规划为利润*大化问题建模，如线性规划(1.1.2)所示. 　　(1.1.2) 　　1.1*优化问題和方法 　定义1.1.2设施选址问题(FacilityLocation Problem) 　　实例：有个设施和个客户，设施和客户之间，以及设施之间、客户之间都有距离，这些距离满足三角不等式.打开第个设施有一个费用方.每个客户都需要连接到一个打开的设施上. 　　目标：打开若干设施，满足客户的连通需求，使得设施的打开费用和客户的连接费用之和*小. 　　设施选址问题是组合优化领域中一个著名的*小优化问题.它描述了这样一种场景：比如有一个工厂，它有分布在多处地点的零售点.现在这个工厂要建立若干仓库，以满足向零售点配送货物的需要.建设仓库就有一个建设费用，仓库建好之后，零售点就会选择距离*近的仓库供货.如何在若干的候选位置建设仓库，以满足零售点的供货需求，就表达为设施选址问题.在这里，仓库的候选位置就是设施位置，零售点就是客户.设施的打开费用就是建设仓库的费用，客户的连接费用就是所有零售点到其*近的仓库的距离之和. 　　在定义1.1.2中，一个问题是按照实例和目标两部分叙述的.这是在计算机科学中对问题描述的一种常见的形式.定义1.1.2中的“实例”也可以叫做“输入”，“目标”也可以叫做“输出当问题是判定问题时(即，回答“是”和“否”的问题)，“目标”也可以写作“询问. 　　关于设施选址问题，“从m个设施中选择若干设施打开”和“从m个设施位置中选择若干位置建立设施”这两种说法是等价的. 　　在这里，我们继续用线性规划对设施选址问题进行建模，以领略线性规划强大的表达能力. 　　定义变量表示是否打开设施，若，表示不打开设施，若，则表示打开设施定义变量表示客户是否连接到设施上，它的值也是或者.这样，问题的总费用就可以表达为里表示顶点和之间的距离.客户要连接到设施上，必须设施打开的条件下才行，这可以用来表达.另外，每个客户一定要连接到某个设施上，这可表达为.因此，设施选址问题的线性规划模型为. 　　这个线性规划是一个整数线性规划，因为它的每个变量只能取整数值. 　　设施选择问题是一个基本的NP困难问题.设施选址问题还有很多的变形.对于设施选址问题及其变形，学者们设计了很多的近似算法，其中有若干算法是非常有名的.感兴趣的读者可进一步参考等著作及其引用的论文. 　　例1.1.3机器学习中的函数优化问题.神经网络是机器学习中的一种模型，它和优化问题密切相关.多层感知机(Multi-Layer Perceptron，MLP)是一种由若干模拟的神经元排列成矩阵结构的前馈神经网络，它所完成的基本任务是进行分类.可以使用一个函数来表达多层感知机所完成的任务.这里，向量是输入数据，向量:是多层感知机使用的参数，是多层感知机的输出，其含义是把输入数据在参数*的控制下分类成所表达的那种类型.例如，在实际应用中，可将图像数据输入给神经网络，让它将图像分成若干种类型. 　　为了使神经网络能够以尽量高的准确率完成分类，需要设定参数*的合适的值，这是在训练数据的帮助下完成的，即人们通常说的“训练一个神经网络训练集可表达为，即，已经知道数据，的类型为，也称为数据的标签.训练一个神经网络，就是调整参数，使得某种损失函数的值尽量地小.若选择平方误差为损失函数，则多层感知机的优化模型为. 　　其中，表示范数，其定义为按照*优化方法的观点，这是一个无约束优化问题.在这里，为了简单说明问题，我们将优化模型简化了.实际使用的优化模型还要加上一个正则项来进行修正.这些细节就略去了. 　　在足够强大的训练集的支持下将一个神经网络训练好(即，选择好了参数a:的值)，就可以在应用中使用这个神经网络完成数据分类任务了. 　　1.2凸集及相关性质 　　定义1.2.1 　　两个点，的凸组合还是中的一个点.它们的所有凸组合构成以这两个点为端点的一条线段. 　　定义I.2.2 　　定义1.2.3 　　例如，欧氏空间中三角形区域、矩形区域、圆形区域都是凸集.在几何直观上，凸集就是边界“向外鼓”的集合. 　　例1.2.4 　　例1.2.5 　　定义1.2.6 　　在几何直观上，三角形区域的顶点、矩形区域的顶点都是符合定义1.2.6的顶点.读者可领略定义1.2.6的精妙.注意，圆形区域是凸集，它有无数个顶点. 　　凸集具有良好的性质，人们对凸集有比较深入的把握.当一个数学规划的可行解的集合是一个凸集时，意味着这个数学规划可能会比较容易求解.例如，线性规划的可行域是凸集，当一个线性规划有解时，它的*优解可在顶点上取得.这些知识将在第2章中详细介绍. 　　1.3凸集的分离 　　凸集是点的集合，不在一个凸集中的点，在直观上，位于这个凸集的“外面我们如何使用数学的语言来精确描述这种直观？进而，两个凸集若不相交，它们是“分离”开的，这样的直观用数学语言如何表达？令人惊奇的是，这种看上去非常基本的直观概念，却蕴含着深刻的道理.例如，由点和凸集的分离定理1.3.3，可以推导出著名的Farkas引理(引理1.3.4)(G.Farkas，匈牙利，1847-1930)，而Farkas引理可推导出线性规划的强对偶定理(定理4.2.5).再如，由凸集和凸集的分离定理1.3.9可推导出戈丹引理(引理1.3.10)(P.A.Gordan，德国，1837—1912)，而戈丹引理又可推导出关于约束优化的著名的K-T定理(定理10.3.7). 　　1.3.1点和凸集的分离 　　在介绍定理1.3.2之前，先来回顾一下下确界符号inf. 　　定义1.3.1令SgR是一个集合，若3m，使得Vze民都有;则称m是S的一个下界.记L是S的所有下界所组成的集合.则L中的*大元素a称为S的下确界，记为 　　定理1.3.2 　　证明 　　则f(x)是连续函数. 　　若S是有界集，则是非空、有界且闭的，所以函数在上可以达到*小值，即，使得 　　即， 　　现在假设不是有界集.在中任取一点以为球心，为半径做一个球，如图1.3.1所示. ……