On the generalized Fischer-Burmeister merit function for the second-order cone complementarity problem
HTML articles powered by AMS MathViewer
- by Shaohua Pan, Sangho Kum, Yongdo Lim and Jein-Shan Chen PDF
- Math. Comp. 83 (2014), 1143-1171 Request permission
Abstract:
It has been an open question whether the family of merit functions $\psi _p\ (p>1)$, the generalized Fischer-Burmeister (FB) merit function, associated to the second-order cone is smooth or not. In this paper we answer it partly, and show that $\psi _p$ is smooth for $p\in (1,4)$, and we provide the condition for its coerciveness. Numerical results are reported to illustrate the influence of $p$ on the performance of the merit function method based on $\psi _p$.References
- F. Alizadeh and D. Goldfarb, Second-order cone programming, Math. Program. 95 (2003), no. 1, Ser. B, 3–51. ISMP 2000, Part 3 (Atlanta, GA). MR 1971381, DOI 10.1007/s10107-002-0339-5
- E. D. Andersen, C. Roos, and T. Terlaky, On implementing a primal-dual interior-point method for conic quadratic optimization, Math. Program. 95 (2003), no. 2, Ser. B, 249–277. Computational semidefinite and second order cone programming: the state of the art. MR 1976481, DOI 10.1007/s10107-002-0349-3
- Rajendra Bhatia, Matrix analysis, Graduate Texts in Mathematics, vol. 169, Springer-Verlag, New York, 1997. MR 1477662, DOI 10.1007/978-1-4612-0653-8
- Jein-Shan Chen, Two classes of merit functions for the second-order cone complementarity problem, Math. Methods Oper. Res. 64 (2006), no. 3, 495–519. MR 2264798, DOI 10.1007/s00186-006-0098-9
- Jein-Shan Chen, Shaohua Pan, and Ching-Yu Yang, Numerical comparisons of two effective methods for mixed complementarity problems, J. Comput. Appl. Math. 234 (2010), no. 3, 667–683. MR 2606654, DOI 10.1016/j.cam.2010.01.004
- Jein-Shan Chen and Shaohua Pan, A one-parametric class of merit functions for the second-order cone complementarity problem, Comput. Optim. Appl. 45 (2010), no. 3, 581–606. MR 2600897, DOI 10.1007/s10589-008-9182-9
- Jein-Shan Chen, Xin Chen, and Paul Tseng, Analysis of nonsmooth vector-valued functions associated with second-order cones, Math. Program. 101 (2004), no. 1, Ser. B, 95–117. MR 2085260, DOI 10.1007/s10107-004-0538-3
- Jein-Shan Chen, Hung-Ta Gao, and Shaohua Pan, An $R$-linearly convergent derivative-free algorithm for nonlinear complementarity problems based on the generalized Fischer-Burmeister merit function, J. Comput. Appl. Math. 232 (2009), no. 2, 455–471. MR 2555414, DOI 10.1016/j.cam.2009.06.022
- Jein-Shan Chen and Shaohua Pan, A family of NCP functions and a descent method for the nonlinear complementarity problem, Comput. Optim. Appl. 40 (2008), no. 3, 389–404. MR 2411201, DOI 10.1007/s10589-007-9086-0
- Jein-Shan Chen, Defeng Sun, and Jie Sun, The $SC^1$ property of the squared norm of the SOC Fischer-Burmeister function, Oper. Res. Lett. 36 (2008), no. 3, 385–392. MR 2424468, DOI 10.1016/j.orl.2007.08.005
- X. D. Chen, D. Sun, and J. Sun, Complementarity functions and numerical experiments on some smoothing Newton methods for second-order-cone complementarity problems, Comput. Optim. Appl. 25 (2003), no. 1-3, 39–56. A tribute to Elijah (Lucien) Polak. MR 1996662, DOI 10.1023/A:1022996819381
- Jein-Shan Chen and Paul Tseng, An unconstrained smooth minimization reformulation of the second-order cone complementarity problem, Math. Program. 104 (2005), no. 2-3, Ser. B, 293–327. MR 2179239, DOI 10.1007/s10107-005-0617-0
- F. Facchinei and J.-S. Pang, Finite-Dimensional Variational Inequalities and Complementarity Problems, Volumes I and II, Springer-Verlag, New York, 2003.
- Jacques Faraut and Adam Korányi, Analysis on symmetric cones, Oxford Mathematical Monographs, The Clarendon Press, Oxford University Press, New York, 1994. Oxford Science Publications. MR 1446489
- Masao Fukushima, Zhi-Quan Luo, and Paul Tseng, Smoothing functions for second-order-cone complementarity problems, SIAM J. Optim. 12 (2001/02), no. 2, 436–460. MR 1885570, DOI 10.1137/S1052623400380365
- M. Seetharama Gowda, Roman Sznajder, and J. Tao, Some $\mathbf P$-properties for linear transformations on Euclidean Jordan algebras, Linear Algebra Appl. 393 (2004), 203–232. MR 2098615, DOI 10.1016/j.laa.2004.03.028
- L. Grippo, F. Lampariello, and S. Lucidi, A nonmonotone line search technique for Newton’s method, SIAM J. Numer. Anal. 23 (1986), no. 4, 707–716. MR 849278, DOI 10.1137/0723046
- Shunsuke Hayashi, Nobuo Yamashita, and Masao Fukushima, A combined smoothing and regularization method for monotone second-order cone complementarity problems, SIAM J. Optim. 15 (2004/05), no. 2, 593–615. MR 2144183, DOI 10.1137/S1052623403421516
- Shunsuke Hayashi, Nobuo Yamashita, and Masao Fukushima, Robust Nash equilibria and second-order cone complementarity problems, J. Nonlinear Convex Anal. 6 (2005), no. 2, 283–296. MR 2159841
- R. A. Horn and C. R. Johnson, Matrix Analyis. Cambridge University Press, Cambridge, 1986.
- Y. Kanno, J. A. C. Martins, and A. Pinto da Costa, Three-dimensional quasi-static frictional contact by using second-order cone linear complementarity problem, Internat. J. Numer. Methods Engrg. 65 (2006), no. 1, 62–83. MR 2185946, DOI 10.1002/nme.1493
- Christian Kanzow, Izabella Ferenczi, and Masao Fukushima, On the local convergence of semismooth Newton methods for linear and nonlinear second-order cone programs without strict complementarity, SIAM J. Optim. 20 (2009), no. 1, 297–320. MR 2496902, DOI 10.1137/060657662
- Adam Korányi, Monotone functions on formally real Jordan algebras, Math. Ann. 269 (1984), no. 1, 73–76. MR 756776, DOI 10.1007/BF01455996
- Yongdo Lim, Applications of geometric means on symmetric cones, Math. Ann. 319 (2001), no. 3, 457–468. MR 1819877, DOI 10.1007/PL00004442
- Miguel Sousa Lobo, Lieven Vandenberghe, Stephen Boyd, and Hervé Lebret, Applications of second-order cone programming, Linear Algebra Appl. 284 (1998), no. 1-3, 193–228. ILAS Symposium on Fast Algorithms for Control, Signals and Image Processing (Winnipeg, MB, 1997). MR 1655138, DOI 10.1016/S0024-3795(98)10032-0
- Renato D. C. Monteiro and Takashi Tsuchiya, Polynomial convergence of primal-dual algorithms for the second-order cone program based on the MZ-family of directions, Math. Program. 88 (2000), no. 1, Ser. A, 61–83. MR 1765893, DOI 10.1007/PL00011378
- Jorge Nocedal and Stephen J. Wright, Numerical optimization, Springer Series in Operations Research, Springer-Verlag, New York, 1999. MR 1713114, DOI 10.1007/b98874
- Jiming Peng, Cornelis Roos, and Tamás Terlaky, Primal-dual interior-point methods for second-order conic optimization based on self-regular proximities, SIAM J. Optim. 13 (2002), no. 1, 179–203. MR 1922760, DOI 10.1137/S1052623401383236
- G. Pataki and S. Schmieta, The DIMACS library of semidefinite-quadratic-linear programs, Computational Optimization Research Center, Columbia University, New York. http://dimacs.rutgers.edu/Challenges/
- Chee-Khian Sim, Jie Sun, and Daniel Ralph, A note on the Lipschitz continuity of the gradient of the squared norm of the matrix-valued Fischer-Burmeister function, Math. Program. 107 (2006), no. 3, Ser. A, 547–553. MR 2221830, DOI 10.1007/s10107-005-0697-x
- Takashi Tsuchiya, A convergence analysis of the scaling-invariant primal-dual path-following algorithms for second-order cone programming, Optim. Methods Softw. 11/12 (1999), no. 1-4, 141–182. Interior point methods. MR 1777456, DOI 10.1080/10556789908805750
- Paul Tseng, Merit functions for semi-definite complementarity problems, Math. Programming 83 (1998), no. 2, Ser. A, 159–185. MR 1647837, DOI 10.1016/S0025-5610(98)00004-5
- Akiko Yoshise, Interior point trajectories and a homogeneous model for nonlinear complementarity problems over symmetric cones, SIAM J. Optim. 17 (2006), no. 4, 1129–1153. MR 2274506, DOI 10.1137/04061427X
- Yun Wang and Liwei Zhang, Properties of equation reformulation of the Karush-Kuhn-Tucker condition for nonlinear second order cone optimization problems, Math. Methods Oper. Res. 70 (2009), no. 2, 195–218. MR 2558410, DOI 10.1007/s00186-008-0241-x
Additional Information
- Shaohua Pan
- Affiliation: School of Mathematical Sciences, South China University of Technology, Guangzhou 510640, People’s Republic of China
- Email: shhpan@scut.edu.cn
- Sangho Kum
- Affiliation: Department of Mathematics Education, Chungbuk National University, Cheongju 361-763, South Korea
- Email: shkum@chungbuk.ac.kr
- Yongdo Lim
- Affiliation: Department of Mathematics, Sungkyunkwan University, Suwan 440-746, South Korea
- Email: ylim@knu.ac.kr
- Jein-Shan Chen
- Affiliation: Department of Mathematics, National Taiwan Normal University, Taipei 11677, Taiwan
- Email: jschen@math.ntnu.edu.tw
- Received by editor(s): August 15, 2010
- Received by editor(s) in revised form: April 18, 2011, and August 7, 2012
- Published electronically: July 15, 2013
- Additional Notes: The first author’s work was supported by National Young Natural Science Foundation (No. 10901058) and the Fundamental Research Funds for the Central Universities (SCUT)
The second author’s work was supported by Basic Science Research Program through NRF Grant No. 2012-0001740.
The third author’s work was supported by the National Research Foundation of Korea (NRF) grant funded by the Korea government (MEST) (No.2012-005191).
Corresponding author: The fourth author is a member of the Mathematics Division, National Center for Theoretical Sciences, Taipei Office. The fourth author’s work was supported by National Science Council of Taiwan. - © Copyright 2013 American Mathematical Society
- Journal: Math. Comp. 83 (2014), 1143-1171
- MSC (2010): Primary 90C33, 90C25
- DOI: https://doi.org/10.1090/S0025-5718-2013-02742-1
- MathSciNet review: 3167453