TY - JOUR
T1 - An unconstrained smooth minimization reformulation of the second-order cone complementarity problem
AU - Chen, Jein Shan
AU - Tseng, Paul
PY - 2005/11
Y1 - 2005/11
N2 - A popular approach to solving the nonlinear complementarity problem (NCP) is to reformulate it as the global minimization of a certain merit function over ℝ n . A popular choice of the merit function is the squared norm of the Fischer-Burmeister function, shown to be smooth over ℝ n and, for monotone NCP, each stationary point is a solution of the NCP. This merit function and its analysis were subsequently extended to the semidefinite complementarity problem (SDCP), although only differentiability, not continuous differentiability, was established. In this paper, we extend this merit function and its analysis, including continuous differentiability, to the second-order cone complementarity problem (SOCCP). Although SOCCP is reducible to a SDCP, the reduction does not allow for easy translation of the analysis from SDCP to SOCCP. Instead, our analysis exploits properties of the Jordan product and spectral factorization associated with the second-order cone. We also report preliminary numerical experience with solving DIMACS second-order cone programs using a limited-memory BFGS method to minimize the merit function.
AB - A popular approach to solving the nonlinear complementarity problem (NCP) is to reformulate it as the global minimization of a certain merit function over ℝ n . A popular choice of the merit function is the squared norm of the Fischer-Burmeister function, shown to be smooth over ℝ n and, for monotone NCP, each stationary point is a solution of the NCP. This merit function and its analysis were subsequently extended to the semidefinite complementarity problem (SDCP), although only differentiability, not continuous differentiability, was established. In this paper, we extend this merit function and its analysis, including continuous differentiability, to the second-order cone complementarity problem (SOCCP). Although SOCCP is reducible to a SDCP, the reduction does not allow for easy translation of the analysis from SDCP to SOCCP. Instead, our analysis exploits properties of the Jordan product and spectral factorization associated with the second-order cone. We also report preliminary numerical experience with solving DIMACS second-order cone programs using a limited-memory BFGS method to minimize the merit function.
KW - Complementarity
KW - Error bound
KW - Jordan product
KW - Level set
KW - Merit function
KW - Second-order cone
KW - Spectral factorization
UR - http://www.scopus.com/inward/record.url?scp=27244436420&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=27244436420&partnerID=8YFLogxK
U2 - 10.1007/s10107-005-0617-0
DO - 10.1007/s10107-005-0617-0
M3 - Article
AN - SCOPUS:27244436420
SN - 0025-5610
VL - 104
SP - 293
EP - 327
JO - Mathematical Programming
JF - Mathematical Programming
IS - 2-3
ER -