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
Email address:
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
1. Introduction
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. [14] 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 [19] on the subject and the references therein.
In this paper, we consider the following parametric kernel function [8]
(1)
which is a generalization of the finite kernel function considered in [15] for (LO), namely,
(2)
The purpose of the paper is to extend the primal-dual large-update (IPMs) for (LO) based on the parametric function considered in [15] 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. Preliminaries
2.1. Some Results on Matrices and Matrix Functions
In this section, some well known results on matrices and matrix functions from linear algebra are considered. Our presentation is mainly based on the monograph [20] and the references [8,21].
Letand
(3)
where is any orthonormal matrix that diagonalizes The matrix valued function is defined by
(4)
Let be differentiable, i.e., the derivative exists. Then the matrix valued function is well defined, namely
(5)
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
(6)
(7)
(8)
For any function , let us denote by the divided difference of as follows
(9)
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 [21]) 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
(10)
and
(11)
where
(12)
is a number depending on and with
(13)
2.2. The Parametric Kernel (Barrier) Function
The first three derivatives of defined by (1) with respect to are given by
(14)
(15)
(16)
In what follows, we recall some useful results in [15, 16] without proofs.
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
(17)
(18)
(19)
The following property, i.e., the exponential convexity, which plays an important role in the analysis of kernel-function based (IPMs) [15,21].
Lemma 2.3 (Lemma 2.1 in [15]) Let and . Then
Now, we define the barrier function according to the kernel function as follows
(20)
From (16), we have
(21)
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 [21]) 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 [15].
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
(22)
The lower bound on in terms of can be obtained from the following theorem, which is a reformulation of Theorem 4.8 in [15].
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
(23)
The Karush-Kuhn-Tucker conditions for (P) and (D) are equivalent to the following system
(24)
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
(25)
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., [2].
In order to provide the scaled Newton system has a unique symmetric solution, Zhang [22] introduced the following symmetrization operator
(26)
One can easily verify that
(27)
for any nonsingular matrix any matrix with real spectrum and any For any given nonsingular matrix the system (25) is equivalent to
(28)
By using Newton method to the system (28), this yields
(29)
The search direction obtained through the system (29) is called the Monteiro-Zhang unified direction. Different choices of the matrix result in different search directions (see, e.g., [2, 22]).
In this paper, we consider the so-called NT-symmetrization scheme [11, 21], which yields the NT search direction. Let
(30)
and . The matrix can be used to rescale and to the same matrix defined by
(31)
From (31), after some elementary reductions, we have
(32)
Here
and
(33)
One can easily verify that
(34)
where denotes the gradient of is given by
(35)
Hence, the system (29) is equivalent to
(36)
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
(37)
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
(38)
One can easily verify that
(39)
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
begin
while
begin
while do
begin
computer the search directions
choose a suitable step size
update
end
end
end
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
(40)
Then, we have
(41)
and
(42)
It follows from (31) that
(43)
One can easily verify that is unitarily similar to the matrix and thus to
(44)
This implies that the eigenvalues of are precisely the same as those of the matrix
(45)
From the definition of , one obtains . Hence, by Theorem 2.2, we have
(46)
Now, we consider the decrease in as a function of and define
(47)
Let define
(48)
It follows that and
By Theorem 2.1, one has
(49)
and
(50)
where
(51)
and
(52)
Hence, using the third equation of the system (37), one has
(53)
In order to facilitate discussion, we denote and we have the following result [8].
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 [8], we briefly recall how to choose the default step size. Suppose that the step size satisfies
(54)
Then . The largest possible value of the step size of satisfying (53) is given by
(55)
Furthermore, we can conclude that
(56)
After some elementary reductions, we have
(57)
In the sequel, let
(58)
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
(59)
According to the decrease of in Lemma 4.2, we have
(60)
where
and (61)
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 [23]
(62)
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,
(63)
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.
5. Conclusion
In this paper, we have investigated a class of large-update primal-dual (IPMs) for (LO) based on a parametric kernel function presented in [16] 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.
Acknowledgements
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 [21]) 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 [21]) Suppose is a sequence of positive numbers such that
,
where and . Then
References