1. 研究目的与意义（文献综述）
非线性最优化是20世纪50年代发展起来的，它讨论非线性决策问题的最佳选择之特性，构造寻求最佳解的计算方法，研究这些计算方法的理论性质及实际计算表现。随着电子计算机的发展和应用，非线性最优化理论和方法有了很大发展。目前，它已成为运筹学的一个重要分支，并且在自然科学，工程技术，经济管理，系统工程，特别是“优化设计”等诸多领域得到广泛的应用，成为一门十分活跃的学科。非线性优化的传统方法几乎都是线搜索类型的方法，即每次迭代时产生一搜索方向，然后在搜索方向上进行精确的或不精确的一维搜索，以得到下一个迭代点。信赖域方法是一类很新的方法，它和线搜索法并列为目前求解非线性规划的2类主要的数值方法。信赖域方法思想新颖，算法可靠，具有很强的收敛性，它不仅能很快地解决良态问题，而且也能有效地求解病态的优化问题。因而对信赖域方法的研究是近20年来非线性规划领域的一个重要的研究方向，是当今寻求如何构造新的优化计算方法的主要途径。信赖域方法的研究起源于Powell1970年的工作，他提出了一个求解无约束优化问题的算法，该算法在每次迭代时强制性地要求新的迭代点与当前的迭代点之间的距离不超过某一控制量。引入控制步长是因为传统的线搜索方法常常由于步长过大而导致算法失败，特别是当问题是病态时尤为如此。控制步长实质上等价于在以当前迭代点为中心的一个邻域内对一个近似于原问题的简单模型求极值。这种技巧可理解为只在一个邻域内对近似模型信赖，所以此邻域被称为信赖域。利用这一技巧的方法也就被称为信赖域法。信赖域的大小通过迭代逐步调节。一般来说，如果在当前迭代模型较好地逼近原问题，则信赖域可扩大，否则信赖域应缩小。后来，人们发现信赖域方法的基本技巧在一定意义下等价于十分著名的求解非线性最小二乘问题的Levenberg-Marquadt方法。1975年，Powell给出了信赖域法的第一个收敛性结果，他在仅假定目标函数连续可微，且近似海色阵满足‖Bk‖≤c(1 ∑kk=1‖si‖)的条件下证明了无约束优化的信赖域法的超线性收敛性。Powell还在Bk是由PSB公式产生时，证明了信赖域法的超线性收敛性。1984年，Pow2ell又在‖Bk‖≤ck的假定下证明了收敛性，他只要求新点是一下降点，收敛是弱意义下的，即inf‖gk‖→0(k→ ∞)。在要求新点是一足够下降点和其他假定下，ShultzGA，ByrdRH和SchnabelRB于1985年证明了在强收敛意义下的全局收敛性。1982年，国际著名优化专家FletcherR提出了用信赖域法求解复合非光滑优化问题，他给出了一个模型算法，并在模型二次函数的海色矩阵一致有界的假定下证明了该算法的全局收敛性。关于非光滑优化的信赖域方法的收敛性研究，我国优化专家袁亚湘研究员得到了一系列在国际上多次被引用的结果，他在仅要求近似海色阵满足‖Bk‖≤ck的假定下证明了一大类非光滑优化的信赖域方法的全局收敛性。此外，他在1984年构造出一个极大极小问题，指出一类非光滑优化的信赖域方法无论Bk怎样选取也仅有线性收敛速度。为了克服这一类似于Marotos效应的现象，须对算法进行修正。其中方法之一是基于FletcherR提出的二阶校正步信赖域法。该方法基本上和它的模型信赖域算法一样，只是在一些迭代中需另外求解一个二阶校正子问题。关于有二阶校正步的信赖域方法的超线性收敛性的证明由袁亚湘于1985年给出，并且他还指出，如果Lagrange乘子的估计较好，则该方法还是二次收敛的。以上所述的关于无约束优化的信赖域方法的研究工作都是基石性的。有关这方面的其他研究工作都是它们的推广或更进一步的研究。这些研究工作可参阅文献。信赖域方法应用到约束优化的一个明显困难是线性化的约束在信赖域区域内可能无解。于是不可能像线搜索方法那样在线性化约束的可行域内找到新的迭代点。对于这一困难，目前有2种处理方法。第1种是将线性化约束条件的约束函数值项都乘上一个属于(0，1)区间上的参数，它实际上是将每一个线性化约束的可行域向当前迭代点平移。这种技巧在线搜索方法逐步二次规划(SQP)方法中早已用来处理线性化约束不相容的情况。第2种办法是将所有的线性化约束之误差的平方和当作一个约束，使得该平方和不超过某一容许量。约束优化的信赖域方法另一重要因素是价值函数(meritfunction)的选取。价值函数是用来判别一个试探点是否被接受，通常是某种形式的罚函数。在文献所述的方法中，价值函数是L1精确罚函数。利用L1精确罚函数的优点在于可容易地证明算法的全局收敛性。由于L1精确罚函数是非光滑的，Maratos效应可能发生，故不能保证算法超线性收敛性。为此，ByrdRH等人在1987年提出的算法中，当试探步不能接受时就计算一个二阶校正步，这样就能保证方法的超线性收敛性。另外，在1986年，袁亚湘和Powell合作，构造了利用FletcherR光滑罚函数作为价值函数的信赖域方法。这是第一个利用光滑价值函数的信赖域方法。利用光滑罚函数的优点是Maratos效应不可能出现，从而比较容易得到超线性收敛结果。美中不足的是，计算光滑函数的导数时需要目标函数和约束函数的二阶导数。为了克服这一困难，袁亚湘又提出了价值函数预估下降量的一种特别的近似计算公式，避免了计算任何二阶导数，而且还能保证算法的全局收敛性和局部超线性收敛性。有关约束优化的信赖域方法的其他研究工作可参阅文献。1991年，袁亚湘和NocedalJ合作，首创性地提出了用信赖域方法和传统的线搜索方法相结合来构造新的计算方法，并依此给出了一个利用信赖域以及回溯技巧的求解无约束优化的算法。这是综合了两大类方法之优点的一个大胆尝试。另外，他在1993年还提出了利用L∞精确罚函数处理约束优化的信赖域方法。在该方法中，袁亚湘给出了一个简单的很有技巧性的调节罚因子的公式，从而保证了算法的收敛性。同时，他还证明了在渐近情况下这个方法和SQR方法的等价性。正如文献中指出的，约束优化的信赖域方法的收敛性通常要求带有信赖域界的二次规划子问题具有全局最优解，而事实上我们所使用的方法通常至多仅能求出它的局部最优解。这样就可能使得通过迭代找到的新迭代点不能保证目标函数值充分下降，使得理论结果和实际计算不匹配。为克服这一困难，人们已尝试把传统的内点法与信赖域法结合起来求解约束优化问题，从而得到一种称之为信赖域内点法的方法。对于具有界约束的优化问题，已有较好的结果;对于带有线性等式或非负变量的约束问题，文献给出了一种信赖域内点法;而文献给出的信赖域内点法则处理带线性不等式约束优化问题。应当指出，上面提到的信赖域方法都有一个共同的特点，那就是为了保证算法的整体收敛性，都要求算法的每一步迭代全是“成功迭代”，即新的迭代点能保证目标函数值或价值函数值比当前的值要严格单调减少。然而，人们在实际计算中发现:对于某些问题，这样做并不能保证算法是有效的。例如，对著名的检验函数—Rosenbrock函数，若用通常的信赖域方法求解，则当迭代点接近最优点时，收敛速度变得非常慢，出现类似于Marotos效应的现象。1993年，我国数学工作者邓乃扬教授等人利用非单调性策略这一技巧首次提出了一类具有强收敛性的非单调信赖域算法。该算法的数值实验表明:非单调性策略对相当一部分实验函数可以明显加快算法在其最优点附近的收敛速度，得到精度更高的最优解。这一工作是开拓性的，有关非单调信赖域方法的其他研究成果都是它的推广或修正。但需要指出的是，目前对非单调信赖域方法的研究绝大多数仅限于光滑优化问题，这是一个值得研究的课题。除上述的信赖域方法外，数学工作者们还提出了另外几种方法，比如:曲线搜索信赖域方法，即它在信赖域范围内采用曲线路径搜索下一个迭代点而得到具有整体收敛性的算法;自适应信赖域方法，即每次迭代时都充分利用当前迭代点的信息自动产生一个恰当的信赖域半径，在此区域内，二次模型与目标函数尽可能一致，从而避免了盲目的搜索尝试，提高了计算效率。迄今为止，有关约束优化问题的信赖域方法几乎都是处理光滑的，而关于约束非光滑优化问题的信赖域方法几乎没有什么进展，只对某些特殊类型进行了研究。此外，将信赖域方法用于研究变分不等式和非线性方程组也得到一些研究成果，它们都是值得研究的课题。信赖域方法实现的关键是如何求得信赖域试探步。试探步一般是一子问题的解，所以如何求得试探步实质上归结为某一子问题的求解。在文献所述的方法中，每次迭代需要求解的子问题是在2个凸的二次约束下求一个二次函数的极小。袁亚湘研究员于1990年对该问题进行了深入研究，得到了求解信赖域子问题的开创性、基石性的结果，他给出了子问题求解的充分必要条件，证明了子问题的Lagrange函数的海色阵最多只有一个负特征值，还指出了子问题在只有一个约束时Lagrange函数的海色阵也可能有一个负特征值。1991年，他又给出了凸的子问题的一个对偶计算方法，这个算法具有超线性收敛性，但缺点是不适合于求解非凸问题。1992年，ZhangY提出求解凸子问题的另一个算法，该算法采用变量代换，将子问题转化为等价的单变量优化问题求解。需要指出的是，对于非凸子问题，目前还没有好的计算方法，是有待解决的重要问题。
2. 研究的基本内容与方案
最优化理论在工程,物理,经济管理等领域得到了广泛的应用,已成为一个非常活跃的研究课题和一门独立的学科。而针对优化问题，信赖域算法由于具有强收敛性和强适应性,因而受到非线性优化界的广泛重视。尤其是非单调的信赖域算法,与单调信赖域算法相比减少了计算子问题的次数,避免了Maratos效应,在实际应用具有重要的作用。
本论文着重研究非线性优化问题的非单调信赖域算法，提出一种新的信赖域算法,在适当的条件下,证明了算法的全局收敛性。采用Matlab进行数值，表明算法是可行、有效的。
3. 研究计划与安排
1-3周：查阅文献，完成开题报告
4-6周：总体设计，完成论文综述
7-10周：设计算法，功能模块设计
4. 参考文献（12篇以上）
[1]yaxiangyuan,recentadvancesintrustregionalgorithms[j],math.program.ser.b2015,151:249-281.
[2]yaxiangyuan,q.dong,x.liu,z.w.wen,aparallellinesearchsubspacecorrectionmethodforcompositeconvexoptimization[j],j.theoperationsresearchsocietyofchina,2015,3(2):163-187.
