New primal-dual interior-point methods based on kernel functions

Abstract Two important classes of polynomial-time interior-point method(IPMs) are small- and large-update methods,respectively. The theoretical complexity bound for large-updatemethods is a factor $\sqrt{n}$ worse than the bound forsmall-update methods, where $n$ denotes the number of (linear) inequalitiesin the problem. In practice the situation is opposite:implementations of large-update methods are much more efficientthan those of small-update methods. This so-called irony of IPMsmotivated the present work.Recently J. Peng C. Roos and T. Terlaky were able to design new IPMswith large-updates whose complexity is only a factor $\log n$ worse thanfor small-update methods. This means that the factor$\sqrt{n}$ was reduced to $\log n$, thus significantly reducingthe gap between the theoretical behavior of large- andsmall-update methods.They made use of so-called self-regular barrier (orproximity) functions. Each such barrier function is determined byits (univariate) self-regular kernel function.In these thesis we introduce a new class of kernel functions whichdiffers from the class of self-regular kernel functions. The classis defined by some simple conditions on the kernel function whichconcern the growth and the barrier behavior of the kernelfunction. These properties enable us to derive many new and tightestimates that greatly simplify the analysis of IPMs based onthese kernel functions.In Chapter 2 we consider ten specific (classes of) kernelfunctions belonging to the new class, and using the new estimatespresent a complete complexity analysis for each of thesefunctions. Some of these functions are self-regular and others arenot. Iterations bounds both for large- and small-update methodsare derived. It is shown that small-update methods based on thenew kernel functions all have the same complexity as theclassical primal-dual IPM, namely $O(\sqrt{n}\,\log\frac{n}{\e})$.For large-update methods the best obtained bound is$O(\sqrt{n}\,\br{\log n}\,\log\frac{n}{\e})$, which is up till nowthe best known bound for such methods.The results of Chapter 2 for LO are extended to semidefinite optimization in Chapter 3, where weit is shown that at some point the analysis boils down to exactly the same analysis as for the LO case.In Chapter 4 some numerical results are presented. These resultsshow that one of the new kernel functions, with finitebarrier term and with the best possible theoretical complexity,performs surprisingly well in our experiments.