A Parametric Kernel Function Yielding the Best Known Iteration Bound of Interior-Point Methods for Semidefinite Optimization
Xiyao Luo*, Gang Ma, Xiaodong Hu, Yuqing Fu
College of Fundamental Studies, Shanghai University of Engineering Science, Shanghai, China
To cite this article:
Xiyao Luo, Gang Ma, Xiaodong Hu, Yuqing Fu. A Parametric Kernel Function Yielding the Best Known Iteration Bound of Interior-Point Methods for Semidefinite Optimization. American Journal of Applied Mathematics. Vol. 4, No. 6, 2016, pp. 316-323. doi: 10.11648/j.ajam.20160406.18
Received: November 2, 2016; Accepted: December 6, 2016; Published: December 26, 2016
Abstract: In this paper, a class of large-update primal-dual interior-point methods for semidefinite optimization based on a parametric kernel function are presented. The proposed kernel function is not only used for determining the search directions but also for measuring the distance between the given iterate and the center for the algorithms. By means of the Nesterov and Todd scaling scheme, the currently best known iteration bounds for large-update methods is established.
Keywords: Interior-Point Methods, Semidefinite Optimization, Large-Update Methods, Polynomial Complexity
In this paper, we focus on the primal problem of semidefinite optimization (SDO) in the standard form
and its dual problem
Here, each Throughout the paper, we assume that the matrices are linearly independent. Recently, (SDO) has been one of the most active research areas in mathematical programming.
Many interior-point methods (IPMs) for linear optimization (LO) are successfully extended to (SDO) due to their polynomial complexity and practical efficiency. For an overview of these results, we refer to [1, 2] and the references [3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13].
Kernel functions play an important role in the design and analysis of primal-dual (IPMs) for optimization and complementarity problems. They are not only used for determining the search directions but also for measuring the distance between the given iterate and the -center for the algorithms. Currently, (IPM) based on kernel function is one of the most effective methods for (LO) and (SDO) and is a very active research areas in mathematical programming. Particularly, Bai et al.  introduced a variety of non-self-regular kernel functions, i.e., the so-called eligible kernel functions, which is defined by some simple conditions on the kernel functions and their derivatives. They provided a simple and unified computational scheme for the complexity analysis of primal-dual kernel function based (IPMs) for (LO). Consequently, a series of eligible kernel functions are considered for various optimization problems and complementarity problems, see, e.g., [15, 16, 17, 18]. For a survey, we refer to the monograph  on the subject and the references therein.
In this paper, we consider the following parametric kernel function 
which is a generalization of the finite kernel function considered in  for (LO), namely,
The purpose of the paper is to extend the primal-dual large-update (IPMs) for (LO) based on the parametric function considered in  to (SDO) by using the NT-scaling scheme [11, 21]. Furthermore, the complexity results match the currently best result of iteration bounds for large-update methods is established, namely, , by choosing .
The outline of the rest of the paper is as follows. In Section 2, we recall some basic concepts and results on matrix theory, the properties of the parametric kernel (and barrier) function. Primal-dual kernel function-based (IPMs) for (SDO) are presented in Section 3. In Section 4, we give the complexity analysis of the primal-dual (IPMs) for (SDO). Finally, some concluding remarks are made in Section 5.
Some of the notations used throughout the paper are as follows. and denote the set of vectors with components, the set of nonnegative vectors and the set of positive vectors, respectively. denotes the set of real matrices. denotes the identity matrix. and denote the Frobenius norm and the spectral norm for matrices, respectively. , and denote the cone of symmetric, symmetric positive semidefinite and symmetric positive definite matrices, respectively. denotes the matrix inner product of two matrices and, respectively. The Lwner partial order (or) on positive semidefinite (or positive definite) matrices means (or) if is positive semidefinite (or positive definite). Finally, if is a real valued function of a real nonnegative variable, the notation means that for some positive constant and that for two positive constants and.
2.1. Some Results on Matrices and Matrix Functions
where is any orthonormal matrix that diagonalizes The matrix valued function is defined by
Let be differentiable, i.e., the derivative exists. Then the matrix valued function is well defined, namely
Recall that a matrix is said to be a matrix of functions if each entry of is a function of , i.e., . Let and be two matrices of functions. Then
For any function , let us denote by the divided difference of as follows
If , we simply write .
The following theorem provides to measure the first-order directional derivative of a general function and bound its second-order derivative with respect to .
Theorem 2.1 (Lemma 16 in ) Suppose that is a matrix of functions such that the matrix is positive definite with eigenvalues . If is twice differentiable with respect to and is twice continuously differentiable function in a domain that contains all the eigenvalues of , then
is a number depending on and with
2.2. The Parametric Kernel (Barrier) Function
The first three derivatives of defined by (1) with respect to are given by
Lemma 2.1 Let be the inverse function of for . Then
Lemma 2.1 Let be the barrier term of , be the inverse function of for and be the inverse function of the restriction of for , respectively. Then
Lemma 2.3 (Lemma 2.1 in ) Let and . Then
Now, we define the barrier function according to the kernel function as follows
From (16), we have
One can easily verify that the derivative of the barrier function exactly equal to , which is defined by (5). Furthermore, we know that is strictly convex with respect to and vanishes at its global minimal point , i.e., , and .
We have the following theorem, by Lemma 2.3.
Theorem 2.2 (Proposition 3 (II) in ) Let . Then
The following theorem provides an estimate for the effect of a -update on the value of , which is a reformulation of Theorem 3.2 in .
Theorem 2.3 Let and . Then
Corollary 2.1 Let and . If , then
Proof: With and , the result follows immediately from Theorem 2.3. This completes the proof.
The norm-based proximity measure is given by
The lower bound on in terms of can be obtained from the following theorem, which is a reformulation of Theorem 4.8 in .
Theorem 2.4 Let . Then
Corollary 2.2 Let . Then
Proof: We have
This completes the proof.
3. Primal-Dual Kernel Function-Based (IPMs) for (SDO)
Without loss of generality, we assume that both the primal problem and its dual problem of (SDO) satisfy the interior-point condition (IPC), i.e., there exists such that
The Karush-Kuhn-Tucker conditions for (P) and (D) are equivalent to the following system
The standard approach is to replace the third equation in (24), i.e., the so-called complementarity condition for (P) and (D), by the parameterized equation with This yields
Under the assumption that (P) and (D) satisfy the (IPC), the system (25) has a unique solution, denoted by . Let be the -center of (P) and be the -center of (D). The set of -centers (with running through positive real numbers) gives a homotopy path, which is called the central path of (P) and (D).
If , then the limit of the central path exists, and since the limit points satisfy the complementarity condition, i.e., it naturally yields an optimal solution for (P) and (D), see, e.g., .
In order to provide the scaled Newton system has a unique symmetric solution, Zhang  introduced the following symmetrization operator
One can easily verify that
for any nonsingular matrix any matrix with real spectrum and any For any given nonsingular matrix the system (25) is equivalent to
By using Newton method to the system (28), this yields
and . The matrix can be used to rescale and to the same matrix defined by
From (31), after some elementary reductions, we have
One can easily verify that
where denotes the gradient of is given by
Hence, the system (29) is equivalent to
This means that the logarithmic barrier function essentially determines the classical NT search direction.
In this paper, we replace the right-hand side in the third equation in (36) by i.e., This yields
The scaled new search direction is computed by solving the system (37) so that and are obtained through (33). If , then is nonzero.
By taking a default step size along the search directions, we get the new iterate according to
One can easily verify that
Hence, the value of can be considered as a measure for the distance between the given iterate and the -center .
The generic form of primal-dual kernel function-based (IPMs) for (SDO) is shown in Algorithm 1.
Algorithm 1 Primal-Dual Interior-Point Algorithm for (SDO)
Input: a threshold parameter
an accuracy parameter
a fixed barrier update parameter
a strictly feasible pair and such that
computer the search directions
choose a suitable step size
4. Complexity Analysis of Large-Update Methods
In each inner iteration the search direction is obtained by solving the system (37) and via (33). After a step with size the new iterate is given by
Then, we have
It follows from (31) that
One can easily verify that is unitarily similar to the matrix and thus to
This implies that the eigenvalues of are precisely the same as those of the matrix
From the definition of , one obtains . Hence, by Theorem 2.2, we have
Now, we consider the decrease in as a function of and define
It follows that and
By Theorem 2.1, one has
Hence, using the third equation of the system (37), one has
In order to facilitate discussion, we denote and we have the following result .
Theorem 3.1 One has
The default step size for the algorithm should be chosen such that and are feasible and decreases sufficiently. For the details we leave it for the interested readers (see, e.g., [8,15]. Following the strategy considered in , we briefly recall how to choose the default step size. Suppose that the step size satisfies
Then . The largest possible value of the step size of satisfying (53) is given by
Furthermore, we can conclude that
After some elementary reductions, we have
In the sequel, let
be the default step size.
As a consequence of Lemma A.1 and the fact that which is a twice differentiable convex function with and the following lemma is obtained.
Lemma 4.1 Let the step size be such that Then
The following theorem shows that the default step size yields sufficient decrease of the barrier function during each inner iteration.
Theorem 4.2 Let and be the default step size as given by (57). Then
Proof: From Lemma 4.1 with (56) and Corollary 2.2, we have
This completes the proof.
At the start of an outer iteration and just before updating the parameter one has
It follows that the value of exceeds from the threshold after updating of . Therefore, one need to count how many inner iterations are required to return to the situation where Let denote the value of after the -update be the subsequent values in the same outer iteration are denoted as where denotes the total number of inner iterations in the outer iteration.
Since for we have
According to the decrease of in Lemma 4.2, we have
The following lemma provides an estimate for the number of inner iterations between two successive barrier parameter updates.
Lemma 4.2 One has
Proof: From Lemma A.2 and (59), the result of the lemma follows. This completes the proof.
It is well known that an upper bound of the number of outer iterations is bounded above by 
By multiplying the number of outer iterations and the number of inner iterations, we get an upper bound for the total number of iterations, namely,
Note that By choosing the best total iteration bound is obtained.
Theorem 4.3 For large-update methods, we set and Then the iteration bound becomes
which matches the currently best well-known complexity for large-update methods.
In this paper, we have investigated a class of large-update primal-dual (IPMs) for (LO) based on a parametric kernel function presented in  can be extended to the context of (SDO). Furthermore, the best result of iteration bounds for large-update methods is derived. In our future study, the generalizations of the primal-dual (IPMs) for (LO) to symmetric cone optimization (SCO) and symmetric cone complementarity problems (SCCP) are interesting.
The authors would like to thank the editor and the anonymous referees for their useful comments and suggestions, which helped to improve the presentation of this paper. This work was supported by University Students' Innovative Training Program of Shanghai (No. CS1621001).
Appendix(Some technical lemmas)
Lemma A.1 (Lemma 12 in ) Let be a twice differentiable convex function with , and let attain its (global) minimum at . If is increasing for , then
Lemma A.2 (Lemma 14 in ) Suppose is a sequence of positive numbers such that
where and . Then