基于凝聚函数的互补问题的自调节内点算法

An Aggregate-Function-Based Self-adjusting Interior Point Algorithm for Solving Linear Complementarity Problems

对于不可微的"极大值"形式的函数,可以利用凝聚函数对其进行光滑逼近.借助这个技术,给出了求解线性互补问题的一个具有自调节功能的内点算法.基于邻近度量和线性互补问题的标准中心化方程的关系,定义了一个新的邻近度量函数,并以极小化这个函数的最优性条件代替了该中心化方程.以此在摄动方程本身建立一种自调节的机制,从而使牛顿方向能够根据上次迭代点的信息做出自适应的调整.基于改造后的摄动方程组,建立了一个具有自调节功能的内点算法.通过一些考题对这个算法进行了数值试验,结果显示了算法的有效性和稳定性.

The undifferentiable ＂max＂ function can be approximated by a differentiable aggregate function. Based on this technique, a self-adjusting interior algorithm for solving linear complementarity problems is presented in this paper. Based on the rain-max principle, the standard centering equation in the interior point method is replaced by the optimality condition of a new proximity measure function. Thus a self-adjusting mechanism is constructed in the new perturbed system. The Newton direction can be adjusted self-adaptively according to the information of last iterates. A self-adjusting interior point method is given based on the new perturbed system. The reliability and efficiency of the algorithm is demonstrated by numerical experiments.