We introduce a new primal-dual IPMs based on new class of kernel functions which differs from the class of self-regular kernel functions. The class is defined by some simple conditions on the kernel function. These properties enable us to derive many new and tight estimates that greatly simplify the analysis of IPMs based on these kernel functions and reduce the gap from small-update and Large-update. A generalizations of the methods that ere developed for linear optimization to the very important cases of semidefinite optimization and linear complementarity problems.
We also consider the effect of solving the primal-dual system using an iterative method. We give an efficient preconditioner and show how the accuracy of the approximate solution of the linear systems influences the convergence of the IPM.
M. El Ghami Z. A. Guennoun, S. Bouali and T. Steihaug,
Primal-Dual Interior-Point Methods for Linear Optimization
Based on a Kernel Function with Trigonometric Barrier Term.
Submitted, 2009.
Mohamed El Ghami and Trond Steihaug,
Kernel-function Based Primal-Dual Algorithms for P
Mohamed El Ghami, Cornelis Roos and Trond Steihaug,
A generic primal-dual interior-point method for semidefinite optimization based on a new class of kernel functions.
Optimization Methods and Software 2010.
Paper (pdf).
Mohamed El Ghami and Trond Steihaug,
Interior Point Methods for Self-Dual Linear Optimization Problems Based on Kernel Functions.
Mathematica Balkanica; Volume 23.(3-4). pp. 229-248. 2009.
Paper.
Mohamed El Ghami, Yanqin Bai and Cornelis Roos,
Kernel-function Based Algorithms for Semidefinite Optimization.
RAIRO. Recherche operationnelle; Volume 43.(2). pp. 189-199. 2009.
Paper (pdf).
Mohamed El Ghami, Ivan Ivanov, Hans Melissen Cornelis Roos and Trond Steihaug,
A polynomial-time algorithm for linear optimization based on a new class of kernel functions.
Journal of Computational and Applied Mathematics; Volume 224.(2). pp. 500-513. 2009.
Paper (pdf).
Mohamed El Ghami and Trond Steihaug,
An Implementation of Interior-Point Methods Based on Kernel Functions for Linear Optimization.
NIK 2009. Tapir Akademisk Forlag 2009 ISBN 978-82-519-2491-7, pp. 159-170. 2009.
Conference 2009.
Mohamed El Ghami, Ivan Ivanov and Trond Steihaug,
Primal-dual interior-point methods solver based on kernel functions for Linear Optimization.
IEEE CNF Proceedings of the International Multiconference on Computer Science and Information Technology;
pp. 743-749. 2009.
Paper (pdf).
Yangin Bai, Goran Lesaja, Cornelis Roos, Guo-Qiang and Mohamed El Ghami,
A class of large-update and small-update primal-dual interior-point algorithms for linear optimization.
Journal of Optimization Theory and Applications; Volume 138.(3). pp. 341-359. 2008.
Paper (pdf).
Mohamed El Ghami, Ivan Ivanov, Cornelis Roos and Trond Steihaug,
A polynomial-time algorithm for LO based on generalized logarithmic barrier functions.
International Journal of Applied Mathematics; Volume 21.(1). pp. 99-115. 2008.
Paper (pdf).
Mohamed El Ghami, Ivan Ivanov, Hans Melissen Cornelis Roos and Trond Steihaug,
Primal-Dual Algorithm for Linear Optimization Problems Based on a New Class of Kernel Functions.
Proceedings of the IEEE Symposium on Computers and Communications 2008, pp. 722-729. 2008.
Paper (pdf).
Mohamed El Ghami and Cornelis Roos,
Generic primal-dual interior point methods based on a new kernel function.
RAIRO. Recherche operationnelle; Volume 42.(2), pp. 199-213. 2008.
Paper (pdf).
Mohamed El Ghami, Trond Steihaug and Cornelis Roos,
Primal-Dual IPMS for semidefinite optimization based on finite barrier functions.
I: Conférence scientific conjointe en Recherche Opérationelle et Aide à la Décision FRANCORO V / ROADEF 2007.
Grenoble: Presses universitaires de Grenoble 2007 ISBN 978-2-7061-1397-0. pp. 69-82. 2007.
Conference
Paper (pdf).
Venansius Baryamureeba and Trond Steihaug,
On the Properties of Preconditioners for Robust Linear Regression.
International Journal of Computing and ICT Research, Volume 1.(2). 2007.
Paper (pdf).
Venansius Baryamureeba and Trond Steihaug,
On the Convergence of an Inexact Primal-Dual Interior Point
Method for Linear Programming
Technical Report No. 188, Department of Informatics, University of Bergen,
5020 Bergen, Norway.March 2000.
Abstract and
report (Postscript).
Venansius Baryamureeba and Trond Steihaug,
Properties and Computational Issues of a
Preconditioner for Interior Point Methods,
Technical Report No. 180, Department of Informatics,
University of Bergen, 5020 Bergen, Norway, November 1, 1999.
Paper (Postscript).
Venansius Baryamureeba and Trond Steihaug,
Computational Issues for a New Class of Preconditioners,
Presented at 2nd Workshop on
Large-Scale Scientific Computations
(WLSSC'99), June 2-6, 1999 Sozopol,
Bulgaria.
Michael Griebel, Svetozar Margenov,
Plamen Yalamov, eds.,
Large-Scale Scientific Computations of Engineering and
Environmental Problems II,
In Series Notes on Numerical Fluid Mechanics,
Vol. 73, pp. 128--135, Vieweg.
Paper (Postscript).
Venansius Baryamureeba.
On Solving Large-Scale Weighted Least Squares Problems.
Lecture Notes in Computer Science Publisher Springer Berlin / Heidelberg
Volume 1988/2001 Book Numerical Analysis and Its Applications.
Paper (pdf).
Venansius Baryamureeba, Trond Steihaug and Yin Zhang, Application of a Class of Preconditioners to Large Scale Linear Programming Problems, LNCS 1685, pp. 1044 -1048, 1999. Paper (pdf).
Venansius Baryamureeba, Trond Steihaug and Yin Zhang,
Properties of a Class of Preconditioners for Weighted
Least Squares Problems,
Technical Report No. 170, Department of Informatics,
University of Bergen, 5020 Bergen, Norway, April 30, 1999.
Abstract.html and Report (postscript) and (pdf).
Last modified: February 5, 2010 by M. El Ghami