一种求解大规模优化问题的三目标筛选内点算法.doc

大规模非线性优化问题的一种三目标过滤内点算法摘要：本文以Fletcher和Leyffer提出的基本过滤方法为基础，根据内点法的特点提出了一种三目标线性搜索过滤内点算法。新算法根据内点算法的KKT条件，将可行性，稳定性，以及辅助性作为搜索步长的目标，以等式约束违反量，障碍目标函数和辅助条件作为过滤器选项，计算搜索步长。该方法相对于基本过滤方法，可以获得更大的搜索步长，从而达到快速收敛的目的，并且能够获得更好的收敛性。数值测试的结果证明了提出方法的鲁棒性和有效性。1 引言基本过滤方法是求解大规模非线性优化问题中迭代步长的一种方法。它首先是由Fletcher和Leyffer1提出的，这种方法通过构造过滤器来选择试探迭代，而且能够加强算法从任意点开始的全局收敛性。在过滤方法中，非支配的概念（来自于多目标优化）被引入进来，并且通过它进行判断是否接受试探点，从而使得过滤方法取代了价值函数方法。自从过滤方法在1997年提出后，它已经被应用到SLP算法 2 和SQP算法34。内点算法作为一种有效的求解大规模不等式约束问题的算法，并且是SQP方法的有效替代方法，成为优化问题的一个研究热点。它相对于SQP方法最大的区别在于其将不等式约束通过障碍函数的方法合并到目标函数中，从而避免了积极约束的选取。由于特殊的不等式处理方式，内点算法的KKT条件相对于SQP算法的KKT条件增加了辅助性条件。由于内点算法的有效性和快速性，因此过滤方法也被引入到了内点算法中。Benson, Shanno和Vanderbei 5 提出了障碍过滤方法和Markov过滤方法，并将其应用到了内点算法中，同时指出了过滤方法在内点算法中相对于价值函数方法的有效性。Ulbrich 6 将过滤方法应用到信赖域原-对偶内点算法，并结合内点算法的特点按照扰动最优性条件来选取步长。但是该方法为了适应基本滤波算法的两目标构架，将扰动最优性条件中的辅助性条件并入到约束违反项之中进行计算，因此在一定程度上影响了算法的性能。Wachter 和Biegler 7 提出了线性搜索过滤方法构架，并将其应用到了SQP算法和内点算法，但是他们提出的过滤方法是一种通用方法，并未结合内点算法的特点。综上所述，由于大多数过滤内点算法仅考虑了可行性和稳定性57，忽略了辅助性对算法性能的影响，所以本文提出了一种三目标过滤方法。该方法充分考虑内点算法的特点，从内点算法的KKT条件出发，分别以可行性，稳定性和辅助性为作为选择步长的目标，以障碍目标函数，等式约束违反，辅助条件违反为过滤项，从而达到快速收敛的目的。除此以外，Maratos效应是约束优化中在转换为无约束优化时出现的超线性收敛步长不可接受现象，因此我们应当在保证收敛的前提下尽可能地接受步长为1的步长因子8。三目标过滤方法相对于基本过滤方法，对于步长的接受条件更弱，因而更有利于避免Maratos效应，从而达到快速收敛的目的。2 原-对偶内点算法本文研究的问题可以描述为(1a) subject to (1b)(1c)其中和是在开集上的二次连续可导的函数。引入障碍项后：,(2a),(2b)其中是正数（障碍参数）。原-对偶内点法是基于将牛顿法应用于扰动一阶最优性条件（KKT条件）的方法，因此原问题的KKT条件可以写为 （可行性）(3)（稳定性）(4) (辅助性)(5)，(6)其中，是拉格朗日乘子，和分别是的梯度和的雅克比矩阵，是以为对角量的对角阵。我们将KKT方程的(5)项进行扰动，可以得到(7)其中。在算法过程中，我们取，其中是中心参数，并且(8)根据KKT条件，在我们的过滤算法中，很自然的我们可以定义可行性，稳定性和辅助性的对应项。因此我们定义可行性量度(9)稳定性量度(10)辅助性量度(11)分别作为过滤器的各项。对于KKT条件（7），通过牛顿法我们可以得到满足条件的点。相对应的牛顿系统可以写为：(12)当通过(12)求得搜索方向时，为了获得下一个迭代点：(13)步长必须确定。三目标过滤方法正是求取迭代步长的方法，这种方法将在下一节陈述。3. 三目标过滤方法3.1 基本过滤方法对于非线性数学规划问题（1），问题的解可以看作是由两个相互竞争的目标组成的：最小化可行性度量和最小化目标函数。因此，问题（1）可以转化为两目标优化问题。通过罚函数的方法来组合两个目标是常用的方法，而 Fletcher和Leyffer 1提出了基本过滤方法从而将约束违反和目标函数的下降同时考虑，并定义了一个过滤器来处理这两个目标，并取得了很好的效果。过滤器在迭代过程中起到收集以前迭代信息的作用，同时作为选择新迭代点的标准。在基本过滤方法中，一个过滤器是由点对组成，它与点对应相关，并要求在过滤器中任何项不被其他点支配。其中支配的概念是基本过滤方法的核心，起到选择存储信息和选择新点的标准的作用：如果一个点加入到过滤器中，则所有的被点支配的项将被移除；一个迭代点可以接受，则必须不能被过滤器中任何点支配。3.2 三目标过滤方法三目标过滤方法的本质是以内点算法的KKT条件为基础，将KKT条件转化为步长搜索的评判标准。该方法将障碍问题转化为一个三目标优化问题，而不是像基本过滤方法的两目标优化问题。可行性，稳定性，辅助性构成了三目标过滤方法的目标。但是简单的将KKT条件中的公式直接作为过滤项是不合适的，我们必须进行必要的转换。对于稳定性量度（10），它是障碍目标函数梯度的范数，以它作为标准可以起到快速收敛的作用，但同时对于非凸问题，这种方法将影响解的全局最优性，因为梯度的范数为零点并不一定是全局最小点，如图1，2所示图1. 非凸问题的目标函数值图2. 非凸问题的目标函数梯度函数，它的梯度为，它存在两个拐点，因此在拐点处，障碍目标函数的梯度为零，如果采用则其他点无法接受，使得算法存在缺陷。因此我们用障碍目标函数来代替障碍目标函数梯度，从而防止产生局部极小的问题。因此，三目标过滤方法的各目标的度量标准重新定义为：可行性量度(14)稳定性量度(15)辅助性量度。(16)由于以上三目标过滤方法与基本过滤方法存在着很大的不同，因此以下将定义该方法的基本概念：定义一：（支配）点，或者与该点对应的集合支配于点，或者点对应的集合，即, 和 或者等价于以下不满足于不等式：。定义二：（过滤器）过滤器是一个由集合有限集合，其中有限集合内没有集合支配其他集合。定义三：如果一个点要加入到过滤器，则我们需要进行以下操作：(17)当然，以上简单的概念并使得三目标过滤方法具有充分的有效性，其他方法必须也要考虑在内，它们将在下一节介绍。4 实际算法4.1 充分减小在非线性规划中，对于大多数线性搜索的优化算法采用价值函数作为评判标准，并且通过Armijo条件来保证解的充分减小。最近，Watcher 和 Biegler将基本过滤方法引入到了线性搜索方法中，并提出了f类型转换条件。采用这种转换条件的目的是防止在过滤方法中仅一个评判标准下降而导致收敛到一个可行但不是最优的解。在他们的方法的启发下，本文提出了三目标转换条件。在这种方法中，对于当前试探步长，有以下几个转换条件：三目标下降条件： ， ，和(18)其中,和，为常数，(19)是障碍目标函数关于方向的线性模型。如果条件(18)满足，方向是障碍目标函数的下降方向。这样对于试探步长，我们采用下面的Armijo条件。(20)其中是常数。通过这个下降标准以及三目标转换条件，我们首先选择一个能够使得三个目标都下降的试探步长。当条件(18)不满足的时候，我们采用传统的Armijo条件，即(21)(22)或者。(23)4.2 算法步骤下面我们将介绍求解障碍问题（2）的三目标线性搜索内点算法的整个步骤。给定起点 其中 ；给定障碍参数初始值 ；给定常数 ； ； ; ; ; ; ; .1. 初始化迭代次数 and , 且。通过(11)计算得。 2. 判断原问题的收敛性。 3. 判断障碍问题的收敛性。4. 通过(6) (8)计算搜索方向。5. 回退线性搜索5.1初始化线性搜索步长。设置和 。5.2计算新的迭代点。设置 。5.3判断对于过滤器是否可以接受。如果 对于过滤器是可接受的，则跳转到6，否则跳转到5.4。5.4 选择新的迭代步长。设置 和 。如果试探步长太小，即，则跳转到可行修复阶段9。否则，返回5.2。6. 接受试探步长。设置，和更新 估计乘子 和 。7. 扩大过滤器。添加点到过滤器，并去除过滤器内被点支配的点。8. 循环迭代。增加迭代次数 并且返回2。9. 可行修复。根据（17）扩大过滤器，以减小可行性度量为目标计算新的迭代点0，并将新的迭代点加入到过滤器。然后转到一般性迭代步骤8。5. 数值测试：算法比较为了证明算法的有效性，本节我们将测试本文提出算法的实际性能。数值测试的计算环境如下：操作系统为Redhat 9.0，CPU为PIV 2.8G，内存为512m。为了进行数值比较，我们采用约束和非约束（CUTEr）测试集合9，其中初始点采用CUTEr的原始问题的初始设定值。我们采用Dolan-More提出的性能标准作为测试标准10，它的具体测试标准如下所述。给定包含测试问题的测试集合，和不同的执行算法选项，这种性能标准对每个问题和每个选项获得的性能指标值（例如迭代次数和CPU时间）进行描绘，从而对不同算法的进行比较。不同问题和选项的性能比定义为：(24)如果对于问题，选项无法求解，我们定义。然后，我们定义测试问题的性能比率：（25）它代表测试问题中选项是求解问题的最好选项，并且选项的性能比小于性能因子的问题所占比例。算法的性能是通过绘制选项的关于的函数来进行比较的。在我们的数值测试中，我们选择了四种过滤方法，并在内点算法构架内进行了比较，这四种过滤方法分别如下：l Triple-Objective Filterl IPOPTl FL Filterl Ulbrich Filter其中Triple-objective Filter是本文提出的三目标过滤方法；IPOPT是由Wachter 和Biegler7提出的通用过滤方法（采用IPOPT默认设置进行比较）；FL Filter是由Fletcher和Leyffer提出的基本过滤方法1；Ulbrich filter是由Ulbrich6在内点法上提出的过滤方法（本文仅采用这种方法的过滤方法进行比较，未单独采用这种方法的步长搜索方法）。所有这些算法的代码都在IPOPT的代码基础上进行实现的，仅采用了不同的过滤方法，并且所有方法使用同样的停止准则，以及停止误差。我们测试了CUTEr测试集合中的规模小于1000的 571个测试问题。在成功率方面，三目标过滤方法成功求解所有问题中的522个，IPOPT和FL Filter方法成功求解了所有问题中的510个，Ulbrich Filter成功求解了400个。图3，图4，和图5是上述测试标准在三种不同测试项下的结果。在数值测试中，我们仅包含了所有方法都不可以求解或者都得到相同解的问题。对于图5关于不同方法运行时间的比较，我们仅考虑了162个问题，因为不被考虑的问题的运行时间小于0.05 CPU秒。对于不被考虑的问题，系统的微小不同可能影响比较的结果。因此我们将运行时间小于0.05 CPU秒的问题排除在比较之外。在迭代次数和函数估计次数方面，Triple-objective Filter表现出了优异的性能。在运行时间方面，Triple-objective Filter略优于IPOPT方法，因为在过滤方法计算过程中，虽然在迭代次数方面Triple-objective Filter优于IPOPT方法，但在计算过滤时，Triple-objective Filter方法需要比IPOPT方法多计算一项辅助性条件，因此在迭代次数差距不大的情况下，计算时间会略多于IPOPT方法。采用三目标过滤方法可以使得算法得到更长的搜索步长。如果采用基本过滤方法，步长可能会变短，因为它可能仅减小辅助性条件而不减小稳定性条件和可行性条件。图3显示了三目标过滤方法在迭代次数上优于其他三种基本过滤方法，这表明我们在选取试探步长时，采用更大的步长将会更快的达到问题收敛。三目标过滤方法不仅有利于算法的步长搜索，而且在改进算法步长的同时，由于它比其他方法更多的考虑了内点算法的特点，并增加了辅助性标准，因此它在全局收敛性方面也优于基本过滤方法。在所有测试问题中，三目标过滤方法相对于其他方法成功求解了更多的问题，这表明了该方法有利于算法的收敛性。图3 过滤方法对于迭代次数评判标准的比较图4 过滤方法对于函数估计次数评判标准的比较图5 过滤方法对于运行时间评判标准的比较6结论本文提出了一种三目标过滤方法，并将它应用到了内点算法的迭代步长选择中。该方法是在基本过滤方法的基础上，根据内点算法的特点，将约束优化问题看作三目标优化问题进行处理。该方法的本质是内点算法的KKT条件，并且从KKT条件出发，将可行性，稳定性和辅助性作为选择步长的目标。由于该方法相对于基本过滤方法在步长选择上更放松，因此可以得到更长的步长，并且由于其根据内点算法的特点，该方法在得到更长的步长的同时，也能够更快的收敛，获得更好的收敛性。数值测试的结果表明，三目标过滤方法优于基本过滤方法，特别对于大规模问题，这种方法更具有可比性。参考文献：1 Fletcher, R. J. and S. J. Leyffer (2002). Nonlinear programming without a penalty function. Mathematical Programming 91(2): 239-269.2 Chin, C. M. M. and R. M. Fletcher (2003). On the global convergence of an SLP-filter algorithm that takes EQP steps. Mathematical Programming 96(1): 161-177.3 Ulbrich, S. A Globally Convergent Primal-Dual Interior-Point Filter Method for Nonconvex Nonlinear Programming Michael Ulbrich.4 Benson, H. Y. V., R. J. V. Vanderbei, et al. (2002). Interior-Point Methods for Nonconvex Nonlinear Programming: Filter Methods and Merit Functions. Computational Optimization and Applications 23(2): 257-272.5Wachter, A. G. and L. T. G. Biegler (2006). On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming. Mathematical Programming 106(1): 25-57.6Byrd, R. H., M. E. Hribar, et al. (1999). An interior point algorithm for