Theoretical and Numerical Result for Linear Optimization Problem Based on a New Kernel Function

Abstract

The propose of this paper is to improve the complexity results of primal-dual interior-point methods for linear optimization (LO) problem. We define a new proximity function for (LO) by a new kernel function wich is a combination of the classic kernel function and a barrier term. We present various proprieties of this new kernel function. Futhermore, we formilate an algorithm for a large-update primal-dual interior-point method (IPM) for (LO). It is shown that the iteration bound for large-update and smal- update primal-dual interior points methods based on this function is a good as the currently best know iteration bounds for these type of methods. This result decreases the gap between the practical behaviour of the large-update algorithms and their theoretical performance, which is an open problem.The primal-dual algorithm is implemented with different choices of the step size. Numerical results show that the algorithm with practical and dynamic step sizes is more efficient than that with fixed (theoretical) step size

Целью данной работы является улучшение результатов сложности первично-двойственных методов внутренней точки для задачи линейной оптимизации (LO). Мы определим новую функцию близости для (LO) новой функцией ядра, которая является комбинацией классической функции ядра и барьерного члена. Мы представляем различные свойства этой новой функции ядра. Кроме того, мы сформулируем алгоритм для большого обновления метода первичной-двойной внутренней точки (IPM) для (LO). Показано, что оценка итераций для методов простого обновления и малых обновлений, основанных на этой функции, наилучшая из известных в настоящее время границ итераций для методов этого типа. Этот результат уменьшает разрыв между практическим поведением алгоритмов с большим обновлением и их теоретической эффективностью, что является открытой проблемой. Алгоритм первичного двойственного типа реализован с различными вариантами выбора размера шага. Численные результаты показывают, что алгоритм с практическим и динамическим размером шага более эффективен, чем алгоритм с фиксированным (теоретическим) размером шага