American Journal of Applied Mathematics
Volume 4, Issue 6, December 2016, Pages: 316-323

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:

(Xiyao Luo)

*Corresponding author

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

  1. Anjos M. F., Lasserre, J. B.: Handbook on Semidefinite, Conic and Polynomial Optimization: Theory, Algorithms, Software and Applications. International Series in Operational Research and Management Science. Volume 166, Springer, New York, USA (2012)
  2. De Klerk, E.: Aspects of Semidefinite Programming: Interior Point Algorithms and Selected Applications. Kluwer Academic Publishers, Dordrecht, The Netherlands (2002)
  3. Cai X. Z., Wang G. Q., Zhang Z. H.: Complexity analysis and numerical implementation of primal-dual interior-point methods for convex quadratic optimization based on a finite barrier. Numer. Algorithms 62(2), 289-306 (2013)
  4. Cho G. M.: Large-update primal-dual interior-point algorithm for semidefinite optimization. Pac. J. Optim. 11(1), 29-36 (2015)
  5. El Ghami M., Bai Y. Q., Roos C.: Kernel-function based Algorithms for semidefinite optimization. RAIRO Oper. Res. 43(2), 189-199 (2009)
  6. Lee Y. H., Cho Y. Y., Jin J. H., Cho G. M.: Interior-point algorithms for LO and SDO based on a new class of kernel functions. J. Nonlinear Convex Anal. 13(3), 555-573 (2012)
  7. Liu, H. W., Liu, C. H., Yang X. M.: New complexity analysis of a Mehrotra-type predictor-corrector algorithm for semidefinite programming. Optim. Methods Softw. 28(6), 1179-1194 (2013)
  8. Wang G. Q., Bai Y. Q.: A new primal-dual path-following interior-point algorithm for semidefinite optimization. J. Math. Anal. Appl. 353(1), 339-349 (2009)
  9. Wang G. Q., Bai Y. Q.: Primal-dual interior-point algorithms for convex quadratic semidefinite optimization. Nonlinear Anal. 71(7-8), 3389-3402 (2009)
  10. Wang G. Q., Bai Y. Q., Gao X. Y., Wang D. Z.: Improved complexity analysis of full Nesterov-Todd step interior-point methods for semidefinite optimization. J. Optim. Theory Appl. 165(1), 242-262 (2015)
  11. Wang G. Q., Bai Y. Q., Roos C.: Primal-dual interior-point algorithms for semidefinite optimization based on a simple kernel function. J. Math. Model. Algorithms 4(4), 409-433 (2005)
  12. Wang G. Q., Zhu D.T.: A unified kernel function approach to primal-dual interior-point algorithms for convex quadratic SDO. Numer. Algorithms 57(4), 537-558 (2011)
  13. Yang X. M., Liu H. W., Zhang Y. K.: A second-order Mehrotra-type predictor-corrector algorithm with a new wide neighbourhood for semidefinite programming. Int. J. Comput. Math. 91(5), 1082-1096 (2014)
  14. Zhang M. W.: A large-update interior-point algorithm for convex quadratic semidefinite optimization based on a new kernel function. Acta Math. Sin. (Engl. Ser.) 28(11), 2313-2328 (2012)
  15. Bai, Y. Q., El Ghami, M., Roos, C.: A comparative study of kernel functions for primal-dual interior-point algorithms in linear optimization. SIAM J. Optim. 15(1), 101-128 (2004)
  16. Achache M.: A new parameterized kernel function for LO yielding the best known iteration bound for a large-update interior point algorithm. Afrika Mat. 27(3), 591-601 (2015)
  17. Bai, Y. Q., El Ghami, M., Roos, C.: A new efficient large-dual interior-point method based on a finite barrier. SIAM J. Optim. 13(3), 766-782 (2003)
  18. Cai X. Z., Wang G. Q., El Ghami M., Yue Y. J.: Complexity analysis of primal-dual interior-point methods for linear optimization based on a parametric kernel function with a trigonometric barrier term. Abstr. Appl. Anal. 2014, 710158 (2014)
  19. Wang G. Q., Bai Y.Q.: Interior-Point Methods for Symmetric Cone Complementarity Problems: Theoretical Analysis and Algorithm Implementation. Harbin Institute of Technology Press, Harbin (2014)
  20. Horn, R. A., Johnson, C. R.: Topics in Matrix Analysis. Cambridge University Press, UK (1991)
  21. Peng, J., Roos, C., Terlaky, T.: Self-regular functions and new search directions for linear and semidefinite optimization. Math. Program. 93(1), 129-171 (2002)
  22. Zhang, Y.: On extending some primal-dual interior-point algorithms from linear programming to semidefinite programming. SIAM J. Optim. 8(2), 365-386 (1998)
  23. Roos, C., Terlaky, T., Vial, J.-Ph.: Theory and Algorithms for Linear Optimization. Springer, Chichester, UK (1st Edition, Theory and Algorithms for Linear Optimization. An Interior-Point Approach. John Wiley & Sons, 1997) (2005)

Article Tools
  Abstract
  PDF(240K)
Follow on us
ADDRESS
Science Publishing Group
548 FASHION AVENUE
NEW YORK, NY 10018
U.S.A.
Tel: (001)347-688-8931