期刊文献+

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

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.
出处 《数学的实践与认识》 CSCD 北大核心 2009年第8期160-166,共7页 Mathematics in Practice and Theory
基金 国家自然科学基金资助项目(10590354) 国家自然科学基金资助项目(10572031)
关键词 凝聚函数 线性互补问题 邻近度量 自调节 内点算法 aggregate function linear complementarity problems proximity measure self adjusting interior point algorithm
  • 相关文献

参考文献14

  • 1李兴斯.一类不可微优化问题的有效解法[J].中国科学(A辑),1994,24(4):371-377. 被引量:137
  • 2Pan S H, Li X S. A self-adjusting primal dual interior point method for linear programs[J]. Optimization Methods and Software, 2004,19 : 389-397.
  • 3He S Y, Li X S, Pan S H. A self-adjusting interior point algorithm for linear complementarity problemsEJ3. Computers and Mathematics with Applications ,2005,50: 33-40.
  • 4Ben-Tal A, Teloulle M. A smoothing technique for nondifferentiable optimization problems [C]//S. Deldeki, editor, Optimization. Lecture Notes in Mathematics 1405. Berlin : Springer-Verlag, 1989.1-11.
  • 5Billups S C, Murty K G. Complementarity problems[J]. Journal of Computational and Applied Mathematics, 2000,124:303- 318.
  • 6修乃华,高自友.互补问题算法的新进展[J].数学进展,1999,28(3):193-210. 被引量:30
  • 7Cottle R W, Pang J S, Stone R E. The Linear Complementarity Problems[M]. Boston: Academic Press,1992.
  • 8Wright S J. Primal-Dual Interior-Point Methods[M]. Philadelphia.. SIAM Publications, 1997.
  • 9Peng J M, Roos C, Terlaky T. Self-regular functions and new search directions for linear and semidefinite optimization[J]. Mathematical Programming, 2002,93 : 129-171.
  • 10Peng J M, Roos C, Terlaky T. New and efficient large update interior-point method for linear optimization[J]. Journal of Computational Technologies, 2001,4 : 61-80.

二级参考文献108

  • 1李兴斯.一类不可微优化问题的有效解法[J].中国科学(A辑),1994,24(4):371-377. 被引量:137
  • 2何炳生.论求解单调变分不等式的一些投影收缩算法[J].计算数学,1996,18(1):54-60. 被引量:20
  • 3Pan S H, Li X S. A self-adjusting primal dual interior point method for linear programs[J]. Optimization Methods and Software, 2004,19 : 389-397.
  • 4He S Y, Li X S, Pan S H. A self-adjusting interior point algorithm for linear complementarity problems [J]. Computers and Mathematics with Applications, 2005,50 : 33-40.
  • 5Ben-Tal A, Teloulle M. A smoothing technique for nondifferentiable optimization problems[-A]. In S. Deldeki, editor, Optimization. Lecture Notes in Mathematics 1405 [C]. Berlin : Springer-Verlag, 1989,1-11.
  • 6Billups S C, Murty K G. Complementarity problems[J]. Journal of Computational and Applied Mathematics, 2000,124: 303-318.
  • 7Cottle R W, Pang J S, Stone R E. The Linear Complementarity Problems[M]. Boston: Academic Press,1992.
  • 8Ferris M C, Kanzow C. Complementarity and related problems.. A survey[A]. In: P.M. Pardalos and M. G. C. Resende(eds): Handbook of Applied Optimization[C]. New York: Oxford University Press,2002. 514-530.
  • 9Chen C H, Mangasarian O L. Smoothing methods for convex inequalities and linear complementarity problems[J]. Mathematical Programming, 1995,71 : 51-69.
  • 10Burke J V, Xu S. The global linear convergence of a non-interior path following algorithm for linear complementarity problems[J]. Mathematics of Operations Research, 1998,23 : 719-734.

共引文献161

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部