Primal-dual Interior-point Methods Based On Self-concordant Exponential Kernel Function

Linear conic programming (LCP) is one of the most popular research topicin the field of optimization. Nemirovskii reported in the International Congressof Mathematicians (ICM) in2006[72] that conic programming was the majordevelopment in convex optimization during the last two decades, primarily fo-cused on linear optimization (LO), second-order cone optimization (SOCO) andsemidefinite optimization (SDO). These three families of symmetric cone opti-mizations possess a general-type linear conic representation. LCP not only hasgood structure and duality theory, but also has strong expressive abilities and ap-plications. Many problems in the field of practical applications can be expressedby LCP, such as optimization problems in management science and engineering,financial optimization, image processing and signal processing. Moreover, thereexist polynomial time interior-point algorithms for solving LCP, and the primal-dual interior-point methods (IPMs) are one of the most important polynomialtime interior-point algorithms. Primal-dual IPMs are strong tools for solvingLO, SOCO and SDO, it can be used to solve the large-scale conic programmingproblems fast and efciently. Many excellent optimization software are developedbased on primal-dual IPMs. Hence, it is important and significant to present ef-ficient primal-dual IPMs for solving LCP problems.A suitable barrier function is crucial for designing and analyzing the primal-dual IPMs. It can be used to define the search direction, to simplify the analysis ofalgorithm and to improve the iteration bounds. In kernel function-based primal-dual IPMs, the barrier function is defined by a univariate kernel function.We first propose a new self-concordant (SC) exponential kernel function,which is constructed originally based on exponential function. We then inves-tigate the properties of this SC exponential kernel function and its derivatives.We verify that this function does not satisfy all ‘Eligible’ conditions as a kernelfunction. We further prove that this function satisfies SC property. Based on this function, we present primal-dual IPMs for LO, SOCO and SDO, respectively. Weanalyze the algorithm and obtain the iteration bounds for large-update methods.Our main work contains:1. We present primal-dual IPMs for LO based on SC exponential kernelfunction. We use the real-valued barrier function defined by this SC exponentialkernel function to define the search direction and to measure the distance betweenthe iteration points and μ-center. We use Newton methods to minimize uncon-straint problems with SC objective function to estimate the decrease of barrierfunction during the inner iteration. We get the upper bound of the barrier func-tion after μ-update and obtain the iteration bounds for large-update methods.Finally, we give some numerical examples to show the efciency of algorithm.2. We present primal-dual IPMs for SOCO based on SC exponential kernelfunction. We make use of the vector-valued function defined by the SC expo-nential kernel function to define the corresponding barrier function. We furtherdefine the search direction and measure the distance between the iteration pointsand μ-center by this barrier function. We analyze the central path of SOCO withthe Jordan algebra framework. Under the inner product of second-order cones,we use Newton methods to minimize unconstraint problems with SC objectivefunction to estimate the decrease of barrier function during the inner iteration.We get the upper bound of the barrier function after μ-update and obtain theiteration bounds for large-update methods. Finally, we give some numerical ex-amples to show the efciency of algorithm.3. We present primal-dual IPMs for SDO based on SC exponential kernelfunction. We first give the corresponding barrier function through matrix-valuedfunction which is defined by the SC exponential kernel function. We further definethe search direction and measure the distance between the iteration points and μ-center by this barrier function. We use Newton methods to minimize unconstraintproblems with SC objective function to estimate the decrease of barrier functionduring the inner iteration. We get the upper bound of the barrier function afterμ-update and obtain the iteration bounds for large-update methods. Finally, we give some numerical examples to show the efciency of algorithm.