Solving obstacle problems by using a new infeasible interior point algorithm

Abstract

Obstacle problems are typical problems in engineering and Physics. After finite approximation, the obstacle problem can be reduced to a QP problem with box constraints. In this paper, a new infeasible path-following algorithm, which follows a path on the complementarity surface, is proposed for solving obstacle problems. The sequence of iterates generated by the algorithm does not satisfy the primal-dual feasibilities as do the other path-following algorithms which follow the central path, but satisfies the complementarity equations at each iteration. In our test obstacle problems, the total number of variables for the Karush-Kuhn-Tucker equations is up to 2,500. Limited numerical results show that this new path-following algorithm can efficiently solve such quadratic problems with requiring only few iterations.

摘要

薄膜障礙問題是工程和物理上的典型問題，經過冇限估算後，薄胶障礙問题可简化爲二次規劃問題。本文探討一個沿著互補平面(complementarity surface) 路徑的非可行内邡點演算法來解此薄膜障礙問題，此法和以往沿著中心路徑的內部點法不同的是路徑上的點滿足互補方程式(complementarity equations) 而非原始。對偶可行性方裎式(primal-dual feasibility equations) 。在本文的薄膜障礙測試問題中，KKT方程式所含的變数達到2,500個，有限的測試結果顯示，此新的非可行內部點演算法解薄膜障礙問題只需少次的運算次數(iterations)。

Keywords:

• Infeasible Interior Point algorithm
• Obstacle Problems
• Quadratic Programming

Keywords:

• 關鍵詞:非可行內部點演算法
• 薄膜障礙問题
• 二次規劃

Additional information

Notes on contributors

Yi-Chih Hsieh

Correspondence addressee