文档介绍：南京航空航天大学
硕士学位论文
非负最小二乘问题的算法研究
姓名:江潇
申请学位级别:硕士
专业:运学与控制论
指导教师:殷洪友
20090301
南京航空航天大学硕士学位论文
摘要
随着无约束最小二乘问题在物理、统计、控制论和经济等领域中的广泛应用,其算法的研
究越来越受到重视,近年来涌现出许多新方法。然而在许多实际问题中,目标函数中的变量的
各个分量之间可能不完全独立,它们的数值常要受到某些物理或者数学条件的约束。例如,在
曲线拟合时,为使拟合函数或它的导函数在某些点上有指定的数值,或者为保证分段拟合曲线
在连接点处连续与光滑,就出现等式约束条件;不等式约束产生于要求拟合曲线具有单调性与
凸性等情况。同样,在物理、统计、数学规划、控制论与经济等领域中,经常会遇到约束条件
的最小二乘问题。因此,研究这类问题的计算方法是非常有意义的。
本文主要研究非负最小二乘问题的理论和算法,文中先后研究了非负线性最小二乘问题和
非负非线性最小二乘问题。利用 Kuhn-Tucker 条件将其转化成线性互补问题或非线性互补问题。
在处理满秩情形的非负线性最小二乘问题时,本文设计了两类不动点算法,并证明了算法的收
敛性以及原问题解的唯一性。当处理亏秩情形非负线性最小二乘问题时,作者利用辅助技术设
计了新的辅助算法,并证明了算法的收敛性。在第三章针对一类特殊的非负线性最小二乘问题
给出了罚函数法,证明了当罚参数趋于无穷时,罚方程的解收敛到原问题的解。第四章设计了
两种内点算法对非负线性最小二乘问题进行求解。本文分满秩和亏秩两种情形分析研究了小残
量的非负非线性最小二乘问题。最后对非负线性最小二乘问题进行了数值实验,结果表明第二
章所提算法的可行性。

关键词:非负最小二乘问题,互补问题,Kuhn-Tucker 条件,不动点算法,辅助方法,罚函数
法,内点算法
i
非负最小二乘问题的算法研究
Abstract
With the broad application in physics, statistics, ics and economics of unconstrained
least squares problem, more attentions are paid to study of the algorithm and many new methods are
advanced in recent years. But in many practical problems, ponent of the variable which in
the objective functions is probably not absolute independence. The value of them is often subject to
some physical or mathematical conditions. For instance, in curve fitting, in order to make the fitting
functions or the derived functions satisfy specific value, or for the purpose of guarantee sub fitting
functions continue and smooth at the joint point, equality constraints appear. In order to make the
fitting functions satisfy monotony and convexity, inequality constraints appear. In physics, statistics,
mathematic programming, ics and economics, we often met constrained least squares
problem. As a result, it’s very significant to study the algorithm of this kind of problem.
In this thesis, we investigate the theory and algorithm of the nonnegative least squares problem.
We focus on the nonnegative linear least squares problems