毕业论文课题相关文献综述

毕业设计开题报告文献综述

题目：一般约束优化算法的测试和应用

一、 前言

约束优化方法是寻求具有约束条件的线性或非线性规划问题解的数值算法。1951年，H.W.库恩和A.W.塔克尔发表论非线性规划一文后，随着计算技术的迅速发展，线性约束的非线性规划出现了不少行之有效的算法。在非线性约束规划的研究上，近十几年来有相当的进展。

本课题主要研究一般约束优化算法的非线性规划问题。非线性规划是具有非线性约束条件或目标函数的数学规划，是运筹学的一个重要分支。非线性规划是20世纪50年代才开始形成的一门新兴学科。1951年H.W.库恩和A.W.塔克发表的关于最优性条件（后来称为库恩－塔克条件）的论文是非线性规划正式诞生的一个重要标志。在50年代还得出了可分离规划和二次规划的n种解法，它们大都是以G.B.丹齐克提出的解线性规划的单纯形法为基础的。50年代末到60年代末出现了许多解非线性规划问题的有效算法，70年代又得到进一步的发展。非线性规划在工程、管理、经济、科研、军事等方面都有广泛的应用，为最优设计提供了有力的工具。20世纪80年代以来，随着计算机技术的快速发展，非线性规划方法取得了长足进步，在信赖域法、稀疏拟牛顿法、并行计算、内点法和有限存储法等领域取得了丰硕的成果。

二、主题

非线性规划问题是利用非线性规划研究一个n元实函数的极值问题，且目标函数和约束条件至少有一个是未知量的非线性函数。其数学表达如下 （最大化目标函数可以简单转化为最小化目标函数）： \min_{x \in X}f(x) 受限于 g(x) \le 0 h(x) = 0\, 其中 f: R^n \to R X \subseteq R^n. 定义域X中满足约束条件的点称为问题的可行解。全体可行解所成的集合称为问题的可行集。对于一个可行解x*，如果存在x*的一个邻域，使目标函数在x*处的值优于 （指不大于或不小于）该邻域中任何其他可行解处的函数值，则称x*为问题的局部最优解（简称局部解）。如果目标函数在x*处的值优于一切可行解处的目标函数值，则称x*为问题的整体最优解（简称整体解）。许多应用问题都可以归结为该类问题，现已有一些相对成熟算法求解该类问题。本课题采用如下几种算法进行测试和应用。

凸优化和单调变分不等式的收缩算法何炳生

a 单调变分不等式的求解方法变分不等式法: 求u*∈Ω,( u-u*)^TF(u*)≧0,任意u∈Ω。应用科学中, 特别是统计与机器学习中的许多问题都可以归结为形如min{f(x)|Ax = b,x∈X}或者min{f1(x) f2(y)|Ax By = b,x∈X,y∈Y}的凸优化问题，然后用单调变分不等式的收缩算法来实现。

b 基于投影梯度的收缩算法：变分不等式u*∈Ω,( u-u*)^Tg(u*)≧0,任意u∈Ω，其中g(x) 是某个凸函数f(x) 的梯度，f(x) 是无法提供的, 只是对给定的x, 可以观测到g(x), 求解时只有g(x) 的信息可以使用. 采用迭代公式x^{k 1} = P_Ω[x^k β_kg(x_k)]，要求x^k, 步长β_k和新的迭代点x^{k 1}满足(x^k- x^{k 1})^T (g(x^k)-g(x^{k 1}))≦(v/β_k)|| x^k- x^{k 1}||²,v∈(0,1)。这样产生的序列{x^k}隐含了(那个我们并不知道的) f(x) 满足下降性质f（x^{k 1}) ≦f（x^k)-（（1-v）/β_k）|| x^k- x^{k 1}||²。