An improved search direction based on algebraic equivalent transformation technique for convex quadratic optimization

Iranian Journal of Numerical Analysis and Optimization

مقالات آماده انتشار، پذیرفته شده، انتشار آنلاین از تاریخ 01 آذر 1404

نوع مقاله: Research Article

شناسه دیجیتال (DOI): 10.22067/ijnao.2025.94069.1670

نویسندگان

Aicha Kraria^* ؛ Bachir Merikhi؛ Djamel Benterki

Laboratory of Fundamental and Numerical Mathematics, Department of Mathematics, Faculty of Sciences, Setif 1 University-Ferhat Abbas, Setif, 19000, Algeria.

چکیده

This work presents an improved interior point algorithm with full Newton step for convex quadratic optimization. Based on the technique of algebraic equivalent transformation, we first propose a new search direction for convex quadratic optimization with the aim of improving the algorithmic complexity of the proposed algorithm. We then perform a complete theoretical study of convergence and complexity, proving that our algorithm is well-defined, converge quadratically and achieves the best known polynomial complexity bounds established for primal-dual interior point methods. Following this, we conduct comparative numerical tests to evaluate the efficiency of the algorithm. The theoretical and numerical results are encouraging and clearly confirm our purpose.

کلیدواژه‌ها

Interior point algorithm؛ Convex quadratic programming؛ Algebraic transformation؛ Search direction