An Efficient Parameterized Logarithmic Kernel Function for Semidefinite Optimization
- PDF / 216,811 Bytes
- 18 Pages / 612 x 792 pts (letter) Page_size
- 83 Downloads / 249 Views
Acta Mathemacae Applicatae Sinica, English Series The Editorial Office of AMAS & Springer-Verlag GmbH Germany 2020
An Efficient Parameterized Logarithmic Kernel Function for Semidefinite Optimization Louiza DERBAL† , Zakia KEBBICHE University of Ferhat Abbas Setif 1, Algeria († E-mail: [email protected])
Abstract
In this paper, we present a primal-dual interior point algorithm for semidefinite optimization prob-
lems based on a new class of kernel functions. These functions constitute a combination of the classic kernel function and a barrier term. We derive the complexity bounds for large and small-update methods respectively. We show that the best √ √ q+1 ) result of iteration bounds for large and small-update methods can be achieved, namely O(q n(log n) q log n ε 3 √ √ q+1 n q for large-update methods and O(q 2 (log q) n log ε ) for small-update methods. We test the efficiency and the validity of our algorithm by running some computational tests, then we compare our numerical results with results obtained by algorithms based on different kernel functions. Keywords kernel function; interior-point algorithms; semidefinite optimization; complexity bound; primaldual methods 2000 MR Subject Classification
1
90C22; 90C31; 90C51
Introduction
Primal-dual interior-point methods (IPMs) have been well known as the most effective methods for solving wide classes of optimization problems, for example, linear optimization (LO), quadratic optimization problem (QOP), semidefinite optimization (SDO), second-order cone optimization (SOCO) and symmetric optimization (SO). SDO has wide applications in continuous and combinatorial optimization [1]. It has become a popular research area in mathematical programming when it is clear that the IPMs for LO can often be extended to the more general SDO case. Many researchers have studied SDO and achieved plentiful and beautiful results. For an overview of these results we refer to the book [27] and its references. Among them, IPMs based on kernel functions have been designed. Recently, a new variant of primal-dual IPM for LO and SDO based on the so-called selfregular (SR) barrier functions was presented by Peng et al. [16] and aforementioned gap was narrowed. Each such barrier function is determined by its (univariate) self-regular kernel func√ tion. They obtained so far the best iteration bound, namely, O( n log n log nϵ ), for large-update IPMs for LO and SDO. Subsequently, Bai et al. [3, 4] developed a class of primal-dual IPMs for LO based on non-self-regular barrier functions and obtained the same favorable iteration bounds for the algorithms with large-update strategy as [16]. Similar algorithms for SDO also were presented (see [7, 26]).
Manuscript received April 30, 2019. Accepted on January 31, 2020. † Corresponding author.
L. DERBAL, Z. KEBBICHE
754
Table 1. Complexity Results for the Eligible Kernel Functions i 1 2 3 4 5 6 7 8 9 10 11 12 13
Kernel functions ψi (t) 1−t2 − log t 2 1 1 2 (t − ) 2 t 2 t1−q −1 t −1 + q−1 , q > 1 2 t2 −1 t1−q −1 + − q−1 ,q 2 q(q−1)
Data Loading...
