Abstract
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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Alizadeh, F., Goldfarb, D.: Second-order cone programming. Math. Program. 95, 3–51 (2003)
Alizadeh, F., Schmieta, S.: Symmetric cones, potential reduction methods, and word-by-word extensions. In: Wolkowicz, H., Saigal, R., Vandenberghe, L., (eds.), Handbook of Semidefinite Programming, Kluwer, Boston, 2000, pp. 195–233
Andersen, E.D., Roos, C., Terlaky, T.: On implementing a primal-dual interior-point method for conic quadratic optimization. Math. Program. Ser. B, 95, 249–277 (2003)
Benson, H.Y., Vanderbei, R.J.: Solving problems with semidefinite and related constraints using interior-point methods for nonlinear programming. Math. Program. Ser. B, 95, 279–302 (2003)
Bertsekas, D.P.: Nonlinear Programming. 2nd ed., Athena Scientific, Belmont, 1999
Chen, X.-D., Sun, D., Sun, J.: Complementarity functions and numerical experiments for second-order cone complementarity problems. Comput. Optim. Appl. 25, 39–56 (2003)
De Luca, T., Facchinei, F., Kanzow, C.: A semismooth equation approach to the solution of nonlinear complementarity problems. Math. Program. 75, 407–439 (1996)
Facchinei, F., Kanzow, C.: A nonsmooth inexact Newton method for the solution of large-scale nonlinear complementarity problems. Math. Program. 76, 493–512 (1997)
Facchinei, F., Pang, J.-S.: Finite-Dimensional Variational Inequalities and Complementarity Problems, Volumes I and II. Springer-Verlag, New York, 2003
Facchinei, F., Soares, J.: A new merit function for nonlinear complementarity problems and a related algorithm. SIAM J. Optim. 7, 225–247 (1997)
Faraut, U., Korányi, A.: Analysis on Symmetric Cones. Oxford Mathematical Monographs, Oxford University Press, New York, 1994
Ferris, M.C., Kanzow, C., Munson, T.S.: Feasible descent algorithms for mixed complementarity problems. Math. Program. 86, 475–497 (1999)
Ferris, M.C., Pang, J.-S., Engineering and economic applications of complementarity problems. SIAM Rev. 39, 669–713 (1997)
Ferris, M.C., Pang, J.-S., (eds.): Complementarity and Variational Problems: State of the Art. SIAM Publications, Philadelphia, 1996
Ferris, M.C., Mangasarian, O.L., Pang, J.-S., eds.: Complementarity: Applications, Algorithms and Extensions. Kluwer Academic Publishers, Dordrecht, 2001
Fischer, A.: A special Newton-type optimization methods. Optim. 24, 269–284 (1992)
Fischer, A.: Solution of the monotone complementarity problem with locally Lipschitzian functions. Math. Program. 76, 513–532 (1997)
Fletcher, R.: Practical Methods of Optimization. 2nd ed., Wiley-Interscience, Chichester, 1987
Fukushima, M., Luo, Z.-Q., Tseng, P.: Smoothing functions for second-order cone complementarity problems. SIAM J. Optim. 12, 436–460 (2002)
Geiger, C., Kanzow, C.: On the resolution of monotone complentarity problems. Comput. Optim. Appl. 5, 155–173 (1996)
Hayashi, S., Yamaguchi, T., Yamashita, N., Fukushima, M.: A matrix splitting method for symmetric affine second-order cone complementarity problems. Report, Department of Applied Mathematics and Physics, Kyoto University, Kyoto, Japan, June 2003; revised February 2004; to appear in J. Comput. Appl. Math.
Hayashi, S., Yamashita, N., Fukushima, M.: A combined smoothing and regularization method for monotone second-order cone complementarity problems. SIAM J. Optim. 15, 593–615 (2005)
Isac, G.: Complementarity Problems. Springer-Verlag, Berlin, 1992
Jiang, H., Qi, L.: A new nonsmooth equations approach to nonlinear complementarities. SIAM J. Control Optim. 35, 178–193 (1997)
Kanzow, C.: An unconstrained optimization technique for large scale linearly constrained convex minimization problems. Comput. 53, 101–117 (1994)
Kanzow, C.: Nonlinear complementarity as unconstrained optimization. J. Optim. Theory Appl. 88, 139–155 (1996)
Kanzow, C.: Global optimization techniques for mixed complementarity problems. J. Global Optim. 16, 1–21 (2000)
Kanzow, C., Fukushima, M.: Solving box constrained variational inequalities by using the natural residual with D-gap function globalization. Oper. Res. Letters 23, 45–51 (1998)
Kanzow, C., Kleinmichel, H.: A class of Newton-type methods for equality and inequality constrained optimization. Optim. Methods Softw. 5, 173–198 (1995)
Kanzow, C., Pieper, H.: Jacobian smoothing methods for nonlinear complementarity problems. SIAM J. Optim. 9, 342–373 (1999)
Kanzow, C., Yamashita, Y., Fukushima, M.: New NCP functions and their properties. J. Optim. Theory Appl. 97, 115–135 (1997)
Liu, D.C., Nocedal, J.: On the limited memory BFGS method for large scale optimization. Math. Program. 45, 503–528 (1989)
Lobo, M.S., Vandenberghe, L., Boyd, S., Lebret, H.: Application of second-order cone programming. Lin. Algeb. Appl. 284, 193–228 (1998)
Luo, Z.-Q., Tseng, P.: A new class of merit functions for the nonlinear complementarity problem. In: Ferris, M.C., Pang, J.-S., (eds.), Complementarity and Variational Problems: State of the Art, SIAM Publications, Philadelphia, 1997, pp. 204–225
Mangasarian, O.L., Solodov, M.V.: Nonlinear complementarity as unconstrained and constrained minimization. Math. Program. 62, 277–297 (1993)
Mittelmann, H.D.: An independent benchmarking of SDP and SOCP solvers. Math. Program. 95, 407–430 (2003)
Monteiro, R.D.C., Tsuchiya, T.: Polynomial convergence of primal-dual algorithms for the second-order cone programs based on the MZ-family of directions. Math. Program. 88, 61–83 (2000)
Nocedal, J., Wright, S.J.: Numerical Optimization. Springer-Verlag, New York, 1999
Pataki, G., Schmieta, S.: The DIMACS library of semidefinite-quadratic-linear programs. Preliminary draft, Computational Optimization Research Center, Columbia University, New York, July 2002. http://dimacs.rutgers.edu/Challenges/Seventh/Instances/
Peng, J.-M.: Equivalence of variational inequality problems to unconstrained minimization. Math. Program. 78, 347–355 (1997)
Qi, L.: Regular pseudo-smooth NCP and BVIP functions and globally and quadratically convergent generalized Newton methods for complementarity and variational inequality problems. Math. Oper. Res. 24, 440–471 (1999)
Schmieta, S., Alizadeh, F.: Associative and Jordan algebras, and polynomial time interior-point algorithms for symmetric cones. Math. Oper. Res. 26, 543–564 (2001)
Sim, C.-K., Sun, J., Ralph, D.: A note on the Lipschitz continuity of the gradient of the squared norm of the matrix-valued Fischer-Burmeister function. Report, Department of Mathematics, National University of Singapore, Singapore, November 2004; submitted to Math. Program.
Sim, C.-K., Zhao, G.: A note on treating a second order cone program as a special case of a semidefinite program. Math. Program. 102, 609–613 (2005)
Solodov, M.V.: Implicit Lagrangian. In: Floudas, C., Pardalos, P., (eds.), Encyclopedia of Optimization. Kluwer Academic Publishers, Dordrecht, 1999
Sturm, J.F.: Using Sedumi 1.02, A Matlab* toolbox for optimization over symmetric cones (updated for Version 1.05). Report, Department of Econometrics, Tilburg University, Tilburg, The Netherlands, August 1998–October 2001
Sun, D., Qi, L.: On NCP functions. Comput. Optim. Appl. 13, 201–220 (1999)
Sun, D., Sun, J.: Strong semismoothness of Fischer-Burmeister SDC and SOC functions. Math. Program. 103, to appear (2005)
Sun, D., Womersley, R.S.: A new unconstrained differentiable merit function for box constrained variational inequality problems and a damped Gauss-Newton method. SIAM J. Optim. 9, 388–413 (1999)
Tseng, P.: Merit function for semidefinite complementarity problems. Math. Program. 83, 159–185 (1998)
Tseng, P., Yamashita, N., Fukushima, M.: Equivalence of complementarity problems to differentiable minimization: a unified approach. SIAM J. Optim. 6, 446–460 (1996)
Tsuchiya, T.: A convergence analysis of the scaling-invariant primal-dual path-following algorithms for second-order cone programming. Optim. Methods Softw. 11, 141–182 (1999)
Yamashita, N., Fukushima, M.: A new merit function and a descent method for semidefinite complementarity problems. In: Fukushima, M., Qi, L., (eds.), Reformulation - Nonsmooth, Piecewise Smooth, Semismooth and Smoothing Methods, Kluwer Academic Publishers, Boston, 1999, pp. 405–420
Yamashita, N., Taji, K., Fukushima, M.: Unconstrained optimization reformulations of variational inequality problems. J. Optim. Theory Appl. 92, 439–456 (1997)
Author information
Authors and Affiliations
Corresponding author
Additional information
In honor of Terry Rockafellar on his 70th birthday
Rights and permissions
About this article
Cite this article
Chen, JS., Tseng, P. An unconstrained smooth minimization reformulation of the second-order cone complementarity problem. Math. Program. 104, 293–327 (2005). https://doi.org/10.1007/s10107-005-0617-0
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10107-005-0617-0
Keywords
- Second-order cone
- Complementarity
- Merit function
- Spectral factorization
- Jordan product
- Level set
- Error bound