×

A linearly convergent derivative-free descent method for the second-order cone complementarity problem. (English) Zbl 1229.90239

Summary: We consider a class of derivative-free descent methods for solving the second-order cone complementarity problem (SOCCP). The algorithm is based on the Fischer-Burmeister (FB) unconstrained minimization reformulation of the SOCCP, and utilizes a convex combination of the negative partial gradients of the FB merit function \(\psi _{\text{FB}}\) as the search direction. We establish the global convergence results of the algorithm under monotonicity and the uniform Jordan \(P\)-property, and show that under strong monotonicity the merit function value sequence generated converges at a linear rate to zero. Particularly, the rate of convergence is dependent on the structure of second-order cones. Numerical comparisons are also made with the limited BFGS method used by J.-S. Chen and P. Tseng [Math. Program. 104, No. 2–3 (B), 293–327 (2005; Zbl 1093.90063)], which confirm the theoretical results and the effectiveness of the algorithm.

MSC:

90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)
90C56 Derivative-free methods and methods using generalized derivatives

Citations:

Zbl 1093.90063
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] DOI: 10.1007/s10107-002-0339-5 · Zbl 1153.90522 · doi:10.1007/s10107-002-0339-5
[2] Chen J-S, J. Nonlinear Convex Anal. 6 pp 297– (2005)
[3] Chen J-S, J. Comput. Appl. Mathematics 64 pp 495– (2008)
[4] DOI: 10.1016/j.orl.2007.08.005 · Zbl 1152.90621 · doi:10.1016/j.orl.2007.08.005
[5] DOI: 10.1007/s10107-005-0617-0 · Zbl 1093.90063 · doi:10.1007/s10107-005-0617-0
[6] DOI: 10.1023/A:1022996819381 · Zbl 1038.90084 · doi:10.1023/A:1022996819381
[7] DOI: 10.1137/S1052623494279110 · Zbl 0873.90096 · doi:10.1137/S1052623494279110
[8] Faraut J, Oxford Mathematical Monographs (1994)
[9] DOI: 10.1023/A:1017580126509 · Zbl 1064.90048 · doi:10.1023/A:1017580126509
[10] DOI: 10.1137/S1052623400380365 · Zbl 0995.90094 · doi:10.1137/S1052623400380365
[11] DOI: 10.1007/BF00249054 · Zbl 0859.90113 · doi:10.1007/BF00249054
[12] DOI: 10.1137/S1052623403421516 · Zbl 1114.90139 · doi:10.1137/S1052623403421516
[13] Horn RA, Matrix Analysis (1986)
[14] Horn RA, Topics in Matrix Analysis (1991)
[15] DOI: 10.1007/BF00121662 · Zbl 0868.90122 · doi:10.1007/BF00121662
[16] Kanzow C, Tech. Rep., in: Semismooth Newton methods for linear and nonlinear second-order cone programs (2006)
[17] DOI: 10.1023/A:1022659603268 · Zbl 0886.90146 · doi:10.1023/A:1022659603268
[18] DOI: 10.1016/S0024-3795(98)10032-0 · Zbl 0946.90050 · doi:10.1016/S0024-3795(98)10032-0
[19] DOI: 10.1023/A:1008752626695 · Zbl 1017.90115 · doi:10.1023/A:1008752626695
[20] DOI: 10.1007/s00245-008-9054-9 · Zbl 1169.49031 · doi:10.1007/s00245-008-9054-9
[21] DOI: 10.1007/s10107-005-0577-4 · Zbl 1099.90062 · doi:10.1007/s10107-005-0577-4
[22] DOI: 10.1007/BF02192639 · Zbl 0866.90127 · doi:10.1007/BF02192639
[23] Yamada K, Nonlinear Optimization and Related Topics pp 463– (2000) · doi:10.1007/978-1-4757-3226-9_25
[24] DOI: 10.1007/BF02191990 · Zbl 0824.90131 · doi:10.1007/BF02191990
[25] DOI: 10.1137/04061427X · Zbl 1136.90039 · doi:10.1137/04061427X
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.