半定规划的光滑化方法研究
|
摘要
半定规划是线性规划的一种推广。近年来其理论和算法取得了很大的进展,并且在组合优化、系统工程和电子工程等领域得到了广泛的应用,已经成为数学规划领域中一个非常活跃的研究方向。
本文首先介绍了半定规划的理论、算法、研究现状和意义,然后引入了求解半定规划问题的非内点光滑化方法。本文的主要工作包括以下三个方面:
1.利用光滑熵函数对半定规划的最优性条件进行转化,得到与其等价的光滑方程组,并应用牛顿法求解该方程组,从而构造了求解半定规划问题的一种光滑化方法。对算法的可行性和收敛性进行了理论分析,并通过数值实验验证了算法的有效性。
2.将光滑熵函数中的光滑参数看作独立的变量求解,构造了一种新的算法。证明了算法的全局收敛性和在合适条件下的局部超线性收敛性,并通过数值实验验证了算法的有效性。
3.通过改进迭代点及参数的更新方法,减少了求解线性方程组的次数,构造了求解半定规划问题的一种崭新的算法,提高了算法的执行效率。理论分析和数值结果均表明该算法比已有的相关算法优越。
Semidefinite programming (SDP) is an extension of linear programming. In recent years, the theory and algorithm for SDP have developed greatly, and its numerous applications are found in combinatorial optimization, system engineering and electrical engineering. SDP is a very important research field in mathematical programming.
In this paper, we first summarize the theory, algorithm, research state and significance of SDP. Then, a non-interior smoothing method is proposed for solving the SDP problems. The main work includes the following three aspects:
1. The equivalent smoothing equations of the optimal condition are obtained by exploiting the smoothing entropy function. Applying Newton’s method to solve the equations, a smoothing method for the solution of SDP is derived. The feasibility and convergence of the algorithm are analyzed theoretically. Some numerical results are also included which indicate that the proposed method is efficient.
2. By regarding the smoothing parameter of the smoothing entropy function as a independent variable, a new algorithm is proposed. The method is shown to be globally and locally superlinearly convergent under suitable assumptions. Numerical experiments show that the method is efficient.
3. Through improving the update methods of iterative points and parameters, the number of solving linear equations is reduced and a new method for solving SDP problems is derived. Theoretical analysis and numerical results are included which show that the method is very promising and comparable to several correlative methods.
本文首先介绍了半定规划的理论、算法、研究现状和意义,然后引入了求解半定规划问题的非内点光滑化方法。本文的主要工作包括以下三个方面:
1.利用光滑熵函数对半定规划的最优性条件进行转化,得到与其等价的光滑方程组,并应用牛顿法求解该方程组,从而构造了求解半定规划问题的一种光滑化方法。对算法的可行性和收敛性进行了理论分析,并通过数值实验验证了算法的有效性。
2.将光滑熵函数中的光滑参数看作独立的变量求解,构造了一种新的算法。证明了算法的全局收敛性和在合适条件下的局部超线性收敛性,并通过数值实验验证了算法的有效性。
3.通过改进迭代点及参数的更新方法,减少了求解线性方程组的次数,构造了求解半定规划问题的一种崭新的算法,提高了算法的执行效率。理论分析和数值结果均表明该算法比已有的相关算法优越。
Semidefinite programming (SDP) is an extension of linear programming. In recent years, the theory and algorithm for SDP have developed greatly, and its numerous applications are found in combinatorial optimization, system engineering and electrical engineering. SDP is a very important research field in mathematical programming.
In this paper, we first summarize the theory, algorithm, research state and significance of SDP. Then, a non-interior smoothing method is proposed for solving the SDP problems. The main work includes the following three aspects:
1. The equivalent smoothing equations of the optimal condition are obtained by exploiting the smoothing entropy function. Applying Newton’s method to solve the equations, a smoothing method for the solution of SDP is derived. The feasibility and convergence of the algorithm are analyzed theoretically. Some numerical results are also included which indicate that the proposed method is efficient.
2. By regarding the smoothing parameter of the smoothing entropy function as a independent variable, a new algorithm is proposed. The method is shown to be globally and locally superlinearly convergent under suitable assumptions. Numerical experiments show that the method is efficient.
3. Through improving the update methods of iterative points and parameters, the number of solving linear equations is reduced and a new method for solving SDP problems is derived. Theoretical analysis and numerical results are included which show that the method is very promising and comparable to several correlative methods.
引文
[1] R. Bellman and K. Fan. On systems of linear inequalities in Hermitian matrix variables. In: Convexity, Proceedings of Symposia in Pure Mathematics. American Mathematical Society, Providence, RI. 1963, 7. 1-11.
[2] S. Boyd, E. Ghaoui, E. Feron etal. Linear matrix inequalities in system and control theory Studies in applied mathematics. SIAM. Philadelphia. 1994, 15.
[3] W. E. Donath and A. J. Hoffman. Lower bonds for the partitioning of graphs. IBM J. of Research and Development. 1973, 17. 420-425.
[4] J. Cullum, W. E. Donath and P. Wolfe. The minimization of certain nondifferentiable sums of eigenvalues of symmetric matrices. Mathematical Programming Study. 1975, 3. 35-55.
[5] L. Lovasz. On the Shannon capacity of a graph. IEEE Trans. On Information Theory. 1979, 25. 1-7.
[6] M. Grotschel, L. Lovasz and A. Schrijver. The ellipsoid method and its consequences in combinatorial optimization. Combinatorica. 1981, 1. 169-179.
[7] M. Grotschel, L. Lovasz and A. Schrijver. Geometric algorithms and combinatorial optimization. Springer-Verlag, Berlin. 1988.
[8] N. Z. Shor. Quadratic optimization problems. Soviet Journal of Circuits and System Sciences. 1987, 25. 1-11.
[9] Yu. E. Nesterov and A. S. Nemirovski. Conic formulation of a convex programming problem and duality. Optim. Methods Software. 1992, 1. 95-115.
[10] Yu. E. Nesterov and A. S. Nemirovski. Interior point polynomial algorithms in convex programming. SIAM Studies in Applied Mathematics. Vol. 13. SIAM. Philadelphia, USA. 1994.
[11] F. N. K. Karmarkar. A new polynomial-time algorithm for linear programming. Combinatorica. 1984, 4. 373-395.
[12] F. Alizadeh. Interior-point methods in semidefinite programming with applications to combinatorial optimization. SIAM J. Optimization. 1995, 5(1). 13-51.
[13] S.-P. Wu, S. Boyd, and L. Vandenberghe. FIR filter design via semidefinite programming and spectral factorization. Kobe. Japan: Proc. 35 Conf. Decision and Control, Dec. 1996. 271-276,
[14] Huitian Peng and Lars K. Rasmussen. The application of semidefiniteprogramming for detection in CDMA. IEEE Selected areas in Communication. 2001, 19(8). 1442-1449.
[15] M. J. Todd. Semidefinite optimization. Acta. Numerica. 2001, 10. 515-560.
[16] M. V. Ramana. An exact duality theory for semidefinite programming and its complexity implications. Mathematical Programming. 1997, 77(2). 129-162.
[17] M. V. Ramana, L. Tuncel and H. Wolkowicz. Strong duality for semidefinite programming. SIAM J. Optimization. 1997, 7(3). 641-662.
[18] M. Shida, S. Shindoh and M. Kojima. Existence and uniqueness of search directions in interior-point algorithms for the SDP and the monotone SDLCP. SIAM. J. Optimization. 1998, 8(2). 387-396.
[19] F. Alizadeh, J.-P. Haeberly and M. V. Nayakkankuppam etc. SDP packuser’s guide 0.9Betal. Technical Report TR1997-737. Courant Institute of Mathematical Science. NYU., New York, NY. 1999, June.
[20] R. H. Tütünü, K. C. Toh and M. J. Todd. Solving semidefinite-quadratic-linear programs using SDP3. Mathematical Programming. 2003, 95(B). 189-217.
[21] F. Alizadeh. Combinatorial optimization with interior point methods and semidefinite matrices. PhD thesis. University of Minnesota. Minneapolis, USA. 1991.
[22] M. J. Todd. A study of search direction in primal-dual interior-point algorithm for semidefinite programming. Optimization methods and Software. 1999, 11. 1-46.
[23] M. J. Todd, K. C. Toh and R. H. Tütünü.On the Nesterov-Todd direction in semidefinite programming. SIAM J. Optimization. 1998, 8. 769-796.
[24] C. Helmberg and F. Rendl. An interior-point method for semidefinite programming. SIAM J. Optimization. 1996, 6(2). 342-361.
[25] F. Alizadeh J. P. Haeberly and M. L. Overton. Primal-dual interior-point methods for semidefinite programming: Convergence rates, stability and numerical results. SIAM J. Optimization. 1998, 8(3). 746-768.
[26] Y. Zhang. On extending some primal-dual interior-point algorithms from linear programming to semidefinite programming. SIAM J. Optimization. 1998, 8(2). 356-386.
[27] C. Helmberg. Semidefinite programming for combinatorial optimization. Konrad-Zuse-Zentrum for information stechnik Berlin, Germany. October 2000.
[28] Etienne de Klerk. Interior Point Methods for Semidefinite Programming. PhD thesis, Delft University of Technology, Delft, The Netherlands. 1997.
[29] M. X. Goemans and D. P. Williamson. Improved approximation algorithms formaximum cut and satisfiability problems using semidefinite programming. Journal of the ACM. 1995, 42(6). 1115-1145.
[30] A. Frieze and M. Jerrum. Improved approximation algorithms for MAX k-cut and MAX BISECTIONL. In Proc. 4th IPCO conference. 1995. 1-13.
[31] E. de Klerk, D. V. Pasechnik and J. P. Warners. On approximate graph colouring and MAX-k-CUT algorithms based on the ? -function. Submitted to Journal of Combinatorial Optimization. 2000.
[32] Y. Ye. A. 0.699 approximation algorithm for max-bisection. Mathematical Programming. 2001, 90. 101-111.
[33] D. Karger, R. Motwani, and M. Sudan. Approximate graph coloring by semidefinite programming. In 35th Symposium on Foundations of Computer Science, page 2-13. IEEE Computer Society Press, 1994.
[34] C. Helmberg, F. Rendl and Weismantel. A semidefinite programming Approach to the Quadratic Knapsack problem, J. of Combinatorial Optimization. 2000, 4. 197-215.
[35] D. Cvetkovic, M. Cangalovic. Semidefinite programming and traveling Salesman problem. In: petrovic, R, Radojebic, D.: Proceedings of Yugoslav Symposium on Operations Research. Herceg Novi, Yugoslavia. 1998. 239-242.
[36] D. Cvetkovic, M. Cangalovic. Semidefinite programming methods for the symmetric traveling Salesman problem. IPCO’99, LNCS, 1610. 1999. 126-136.
[37] A. Shapiro. First and second order analysis of nonlinear semidefinite programs. Mathematical Programming. 1997, 77(A). 301-320.
[38] A. Forsgren. Optimality conictions for nonconvex semidefinite programming. Mathematical Programming. 2000, 88(A). 105-128.
[39] L. M. Grana Drummond, Alfredo Noel Iusem and B. F. Svaiter. On the central path for nonlinear semidefinite programming. Rairo Oper. Research. 2000, 34. 331-345.
[40] 韩乔明.解半定规划的二次摄动方法.应用数学学报.1999, 2(1). 84-90.
[41] E. de Klerk. Aspects of Semidefinite Programming. Published by Kluwer Academic Publishers. 2002.
[42] L. Vandenberghe, S. Boyd. Semidefinite Programming. SIAM Review. 1996, 38(1). 49-95.
[43] F. Alizadeh. Semidefinite programming home page (Download link http://karush.Rutgers.edu/~alizadeh/sdppage/index.html).
[44] C. Helmberg. Semidefinite programming home page(Download link http://www.user.tu-chemnita.de/~helmberg).
[45] A. Fischer. A special Newton-type optimization method. Optimization 24, 1992. 269-284.
[46] Christian Kanzow and Christian Nagel. Semidefinite programs: New search directions, smoothing-type methods, and numerical results. SIAM Journal on Optimization. 2003, 13. 1-23.
[47] C. Kanzow. Some noninterior continuation methods for linear complementarity problems. SIAM Journal on Matrix Analysis and Applications 17. 1996. 851-868.
[48] R. A. Horn and C. R. Johnson. Topics in Matrix Analysis. Cambridge University Press. 1991.
[49] H. Jiang. Smoothed Fischer-Burmeister equation methods for the complementarity problem. Technical Report, Department of Mathematics, University of Melbourne, Melbourne, Australia. 1997 June.
[50] X. Chen, P. Tseng. Non-interior continuation methods for solving semidefinite complementarity problems. Technical Report, Department of Mathematics, University of Washington, Seattle, WA. 1999.
[51] P. Tseng. Analysis of a non-interior continuation method based on Chen- Mangasarian smoothing functions for complementarity problems. Reformulation-Nonsmooth, Piecewise Smooth, Semismooth and Smoothing Methods, M. Fukushima, L. Qi(eds), Kluwer Academic Publishers, Boston. 1999. 381-404.
[52] P. Tseng. Merit functions for semi-definite complementarity problems. Mathematical Programming. 1998, 83. 159-185.
[53] Bhatia, R. Matrix Analysis, Springer-Verlag, New York. 1997.
[54] K. C. Toh, M. J. Todd and R. H. Tütüncü. SDPT3 — a Matlab software package for semidefinite programming, version 2.1. Optimization Methods and Software. 1999, 11. 545–581.
[55] Lieven Vandenberghe, Stephen Boyd. Semidefinite programming. SIAM Review. 1996, 38(1). 49-95.
[56] Brian Borchers. SDPLIB1.2, a library of semidefinite programming test problems. Optimization Methods and Software. 1999, 11 & 12. 683–690. Available at http://www.nmt.edu/~borchers/sdplib.html.
[2] S. Boyd, E. Ghaoui, E. Feron etal. Linear matrix inequalities in system and control theory Studies in applied mathematics. SIAM. Philadelphia. 1994, 15.
[3] W. E. Donath and A. J. Hoffman. Lower bonds for the partitioning of graphs. IBM J. of Research and Development. 1973, 17. 420-425.
[4] J. Cullum, W. E. Donath and P. Wolfe. The minimization of certain nondifferentiable sums of eigenvalues of symmetric matrices. Mathematical Programming Study. 1975, 3. 35-55.
[5] L. Lovasz. On the Shannon capacity of a graph. IEEE Trans. On Information Theory. 1979, 25. 1-7.
[6] M. Grotschel, L. Lovasz and A. Schrijver. The ellipsoid method and its consequences in combinatorial optimization. Combinatorica. 1981, 1. 169-179.
[7] M. Grotschel, L. Lovasz and A. Schrijver. Geometric algorithms and combinatorial optimization. Springer-Verlag, Berlin. 1988.
[8] N. Z. Shor. Quadratic optimization problems. Soviet Journal of Circuits and System Sciences. 1987, 25. 1-11.
[9] Yu. E. Nesterov and A. S. Nemirovski. Conic formulation of a convex programming problem and duality. Optim. Methods Software. 1992, 1. 95-115.
[10] Yu. E. Nesterov and A. S. Nemirovski. Interior point polynomial algorithms in convex programming. SIAM Studies in Applied Mathematics. Vol. 13. SIAM. Philadelphia, USA. 1994.
[11] F. N. K. Karmarkar. A new polynomial-time algorithm for linear programming. Combinatorica. 1984, 4. 373-395.
[12] F. Alizadeh. Interior-point methods in semidefinite programming with applications to combinatorial optimization. SIAM J. Optimization. 1995, 5(1). 13-51.
[13] S.-P. Wu, S. Boyd, and L. Vandenberghe. FIR filter design via semidefinite programming and spectral factorization. Kobe. Japan: Proc. 35 Conf. Decision and Control, Dec. 1996. 271-276,
[14] Huitian Peng and Lars K. Rasmussen. The application of semidefiniteprogramming for detection in CDMA. IEEE Selected areas in Communication. 2001, 19(8). 1442-1449.
[15] M. J. Todd. Semidefinite optimization. Acta. Numerica. 2001, 10. 515-560.
[16] M. V. Ramana. An exact duality theory for semidefinite programming and its complexity implications. Mathematical Programming. 1997, 77(2). 129-162.
[17] M. V. Ramana, L. Tuncel and H. Wolkowicz. Strong duality for semidefinite programming. SIAM J. Optimization. 1997, 7(3). 641-662.
[18] M. Shida, S. Shindoh and M. Kojima. Existence and uniqueness of search directions in interior-point algorithms for the SDP and the monotone SDLCP. SIAM. J. Optimization. 1998, 8(2). 387-396.
[19] F. Alizadeh, J.-P. Haeberly and M. V. Nayakkankuppam etc. SDP packuser’s guide 0.9Betal. Technical Report TR1997-737. Courant Institute of Mathematical Science. NYU., New York, NY. 1999, June.
[20] R. H. Tütünü, K. C. Toh and M. J. Todd. Solving semidefinite-quadratic-linear programs using SDP3. Mathematical Programming. 2003, 95(B). 189-217.
[21] F. Alizadeh. Combinatorial optimization with interior point methods and semidefinite matrices. PhD thesis. University of Minnesota. Minneapolis, USA. 1991.
[22] M. J. Todd. A study of search direction in primal-dual interior-point algorithm for semidefinite programming. Optimization methods and Software. 1999, 11. 1-46.
[23] M. J. Todd, K. C. Toh and R. H. Tütünü.On the Nesterov-Todd direction in semidefinite programming. SIAM J. Optimization. 1998, 8. 769-796.
[24] C. Helmberg and F. Rendl. An interior-point method for semidefinite programming. SIAM J. Optimization. 1996, 6(2). 342-361.
[25] F. Alizadeh J. P. Haeberly and M. L. Overton. Primal-dual interior-point methods for semidefinite programming: Convergence rates, stability and numerical results. SIAM J. Optimization. 1998, 8(3). 746-768.
[26] Y. Zhang. On extending some primal-dual interior-point algorithms from linear programming to semidefinite programming. SIAM J. Optimization. 1998, 8(2). 356-386.
[27] C. Helmberg. Semidefinite programming for combinatorial optimization. Konrad-Zuse-Zentrum for information stechnik Berlin, Germany. October 2000.
[28] Etienne de Klerk. Interior Point Methods for Semidefinite Programming. PhD thesis, Delft University of Technology, Delft, The Netherlands. 1997.
[29] M. X. Goemans and D. P. Williamson. Improved approximation algorithms formaximum cut and satisfiability problems using semidefinite programming. Journal of the ACM. 1995, 42(6). 1115-1145.
[30] A. Frieze and M. Jerrum. Improved approximation algorithms for MAX k-cut and MAX BISECTIONL. In Proc. 4th IPCO conference. 1995. 1-13.
[31] E. de Klerk, D. V. Pasechnik and J. P. Warners. On approximate graph colouring and MAX-k-CUT algorithms based on the ? -function. Submitted to Journal of Combinatorial Optimization. 2000.
[32] Y. Ye. A. 0.699 approximation algorithm for max-bisection. Mathematical Programming. 2001, 90. 101-111.
[33] D. Karger, R. Motwani, and M. Sudan. Approximate graph coloring by semidefinite programming. In 35th Symposium on Foundations of Computer Science, page 2-13. IEEE Computer Society Press, 1994.
[34] C. Helmberg, F. Rendl and Weismantel. A semidefinite programming Approach to the Quadratic Knapsack problem, J. of Combinatorial Optimization. 2000, 4. 197-215.
[35] D. Cvetkovic, M. Cangalovic. Semidefinite programming and traveling Salesman problem. In: petrovic, R, Radojebic, D.: Proceedings of Yugoslav Symposium on Operations Research. Herceg Novi, Yugoslavia. 1998. 239-242.
[36] D. Cvetkovic, M. Cangalovic. Semidefinite programming methods for the symmetric traveling Salesman problem. IPCO’99, LNCS, 1610. 1999. 126-136.
[37] A. Shapiro. First and second order analysis of nonlinear semidefinite programs. Mathematical Programming. 1997, 77(A). 301-320.
[38] A. Forsgren. Optimality conictions for nonconvex semidefinite programming. Mathematical Programming. 2000, 88(A). 105-128.
[39] L. M. Grana Drummond, Alfredo Noel Iusem and B. F. Svaiter. On the central path for nonlinear semidefinite programming. Rairo Oper. Research. 2000, 34. 331-345.
[40] 韩乔明.解半定规划的二次摄动方法.应用数学学报.1999, 2(1). 84-90.
[41] E. de Klerk. Aspects of Semidefinite Programming. Published by Kluwer Academic Publishers. 2002.
[42] L. Vandenberghe, S. Boyd. Semidefinite Programming. SIAM Review. 1996, 38(1). 49-95.
[43] F. Alizadeh. Semidefinite programming home page (Download link http://karush.Rutgers.edu/~alizadeh/sdppage/index.html).
[44] C. Helmberg. Semidefinite programming home page(Download link http://www.user.tu-chemnita.de/~helmberg).
[45] A. Fischer. A special Newton-type optimization method. Optimization 24, 1992. 269-284.
[46] Christian Kanzow and Christian Nagel. Semidefinite programs: New search directions, smoothing-type methods, and numerical results. SIAM Journal on Optimization. 2003, 13. 1-23.
[47] C. Kanzow. Some noninterior continuation methods for linear complementarity problems. SIAM Journal on Matrix Analysis and Applications 17. 1996. 851-868.
[48] R. A. Horn and C. R. Johnson. Topics in Matrix Analysis. Cambridge University Press. 1991.
[49] H. Jiang. Smoothed Fischer-Burmeister equation methods for the complementarity problem. Technical Report, Department of Mathematics, University of Melbourne, Melbourne, Australia. 1997 June.
[50] X. Chen, P. Tseng. Non-interior continuation methods for solving semidefinite complementarity problems. Technical Report, Department of Mathematics, University of Washington, Seattle, WA. 1999.
[51] P. Tseng. Analysis of a non-interior continuation method based on Chen- Mangasarian smoothing functions for complementarity problems. Reformulation-Nonsmooth, Piecewise Smooth, Semismooth and Smoothing Methods, M. Fukushima, L. Qi(eds), Kluwer Academic Publishers, Boston. 1999. 381-404.
[52] P. Tseng. Merit functions for semi-definite complementarity problems. Mathematical Programming. 1998, 83. 159-185.
[53] Bhatia, R. Matrix Analysis, Springer-Verlag, New York. 1997.
[54] K. C. Toh, M. J. Todd and R. H. Tütüncü. SDPT3 — a Matlab software package for semidefinite programming, version 2.1. Optimization Methods and Software. 1999, 11. 545–581.
[55] Lieven Vandenberghe, Stephen Boyd. Semidefinite programming. SIAM Review. 1996, 38(1). 49-95.
[56] Brian Borchers. SDPLIB1.2, a library of semidefinite programming test problems. Optimization Methods and Software. 1999, 11 & 12. 683–690. Available at http://www.nmt.edu/~borchers/sdplib.html.