【数值分析中约束优化的教学探讨】 数值分析第五版答案pdf
摘要：最优化在数值分析课程教学中日趋重要，但目前教学中大多侧重于无约束优化，而弱化或忽略了约束优化的内容。本文探讨约束优化的内容设置及教学安排，具体给出三个教学模块：约束优化基础知识、罚函数法、可行方向法。
关键词：数值分析；约束优化；教学探讨
中图分类号：G642.4 文献标识码：A 文章编号：1674-9324（2012）07-0139-02
数值分析是一门介绍科学计算的基础理论和数值方法的课程，目前已成为数学类专业以及大多数工科类专业的一门必修课程。该课程针对大量的数学问题，如求解方程组、微分方程、最优化等，给出了相应的数值算法，并分析其理论性质，理论性、实践性和应用性均较强。由于最优化问题广泛应用于经济管理、工程设计、交通运输等重要领域，最优化在数值分析课程教学中日益受到重视，国内外不少教材已将最优化作为一章专门介绍。遗憾的是，目前关于最优化的教学大多仅侧重于无约束优化，而弱化或忽略了约束优化的内容，通常仅介绍最简单的线性规划。笔者认为，这是不够完善的。因为在实际问题当中，约束优化更常见、更具代表性。因此，将约束优化纳入数值分析的教学中是十分必要的。然而，约束优化内容极其丰富，方法繁多，因此，如何选择适当的内容进行教学，既难易适中、适合课堂教学和学时要求，又能让学生领会约束优化的本质，是一个值得深入探讨的问题。基于以上考虑，本文探讨约束优化在数值分析课程教学中的内容设置及教学安排，并结合笔者的科学研究和教学实践，具体给出三个教学模块：约束优化基础知识、罚函数法、可行方向法。
一、约束优化基础知识
此模块主要介绍约束优化问题的描述、解的概念、最优性条件等基础知识，为后续介绍具体方法奠定基础。基于教学方便考虑，可先讨论如下非线性不等式约束优化问题，推广到带等式约束的问题，可作为补充知识简要介绍或作为拓展知识自学。
Minimize f（x）
subject to Ci（x）≤0，i∈I={1，L，m}?摇?摇?摇?摇
其中x∈Rn为决策变量，f：Rn→R为需要极小化的目标函数，Ci：Rn→R（i∈I）为约束函数（或称为限制条件），且设f，Ci（i∈I）均为一阶连续可微函数。记问题（1）的可行集为
X={x∈Rn：Ci（x）≤0，i∈I}.
定义1 设f（x）：Rn→R，若偏导数■，i=1，L，n，都存在，则称f（x）在x处一阶可导，并称向量?荦f（x）=（■，L，■）T为f（x）在x处的一阶导数或梯度。
定义2 设x*∈X，若f（x*）≤f（x），?坌x∈X成立，则称x*是问题（1）的全局最优解；若对某一常数?着＞0，存在邻域N（x*，?着），使得f（x*）≤f（x），?坌x∈XIN（x*，?着）成立，则称x*是问题（1）的局部最优解。
定理1 （FJ条件） 设x*是（1）的局部最优解，则存在常数u0*，及向量u=（ui*，i∈I）使得
u0*?荦f（x*）+■ui*?荦ci（x*）=0，（u0*，u*）≠0 （2）
ci（x*）≤0，ui*ci（x*）=0，u0*≥0，ui*≥0，i∈I （3）
成立。称满足条件（2）和（3）的点x*为问题（1）的一个Fritz John （FJ）点。
定义3 （KKT条件）设x*∈X，若存在向量u*=（ui*，i∈I），使得
?荦f（x*）+■ui*?荦ci（x*）=0，ci（x*）≤0，ui*ci（x*）=0，u0*≥0，ui*≥0，i∈I
成立，则称x*是问题（1）的一个Kuhn-Tucker-Karush（KKT）点，并称u*为相应的KKT乘子。
对于一般的约束优化问题，优化算法通常不能直接找到问题（1）的全局或局部最优解，而是得到FJ点或KKT点。当然，在适当假设条件下，FJ点或KKT点即为问题（1）的最优解。
二、罚函数法
约束优化方法繁多，但最经典、最常用的当属罚函数方法。罚函数法通过引入一个罚参数将约束违背惩罚到目标函数，从而将约束优化问题转化为一个或一系列无约束优化问题，进而用无约束优化方法求解。我们希望无约束优化问题的最优解亦为问题（1）的最优解，或至少逼近问题（1）的最优解。因此，要求在无约束问题的最优解处约束条件满足，或违背量逼近于0。 通常可简单考虑如下l1罚函数P（x，r）=f（x）+r■max{0，ci（x）}，其中r＞0为一个较大的数（称为罚参数）。对应的无约束优化问题为：■（x，r）。
一般罚参数r的选取不能一步到位，而是需要在算法迭代中不断增加，下面给出罚函数法的迭代框架。
算法1 初始步：取终止参数?着＞0，初始点x1，初始罚参数r1＞0，常数β＞1。令k=1，转主步。
主步：1.由xk开始，求解如下无约束优化问题 ■（x，rk）。（4）
设xk+1为最优解，转步骤2。
2.若rk■max{0，ci（xk+1）}，算法终止；否则令rk+1=βrk， k=k+1，转步骤1。
定理2 设问题（1）的全局最优解存在，rk→+∞，且对每个k，问题（4）的全局最优解xk+1存在，则由算法1产生的序列{xk}的任何聚点x*均为问题（1）的全局最优解。
在算法描述之后，可以举一个简单实例如下，展示算法的迭代过程。
例1 考虑问题Minimize x12+x22 subject to 1-x1≤0显然，该问题的精确最优解为x*=（1，0）T，f（x*）=1。取?着=10-6，x1=（0.5，0.5）T，r1=0.1，β=10。利用Matlab编程，详细迭代过程见表1。
三、可行方向法
前述的罚函数法的特点是算法结构简单，初始点及迭代点均在可行域外。由此可见罚函数法满足不了一些实际问题，如工程设计、实时控制等，对可行性的严格要求。以下介绍的可行方向法能产生可行的迭代点和最优解，能满足可行性的要求。由于可行方向法种类较多，还有各种改进和变异形式，考虑到算法理论的完善性和教学特点，可以选取经典的Topkis-Veinott可行方向法[3]作为教学内容。