×

An unconstrained smooth minimization reformulation of the second-order cone complementarity problem. (English) Zbl 1093.90063

Summary: A popular approach to solving the nonlinear complementarity problem (NCP) is to reformulate it as the global minimization of a certain merit function over \(\mathbb R^n\). A popular choice of the merit function is the squared norm of the Fischer-Burmeister function, shown to be smooth over \(\mathbb R^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.

MSC:

90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)
65K05 Numerical mathematical programming methods
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Alizadeh, F., Goldfarb, D.: Second-order cone programming. Math. Program. 95, 3–51 (2003) · Zbl 1153.90522
[2] 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 · Zbl 0957.90530
[3] 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) · Zbl 1030.90137
[4] 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) · Zbl 1030.90138
[5] Bertsekas, D.P.: Nonlinear Programming. 2nd ed., Athena Scientific, Belmont, 1999 · Zbl 1015.90077
[6] 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) · Zbl 1038.90084
[7] De Luca, T., Facchinei, F., Kanzow, C.: A semismooth equation approach to the solution of nonlinear complementarity problems. Math. Program. 75, 407–439 (1996) · Zbl 0874.90185
[8] Facchinei, F., Kanzow, C.: A nonsmooth inexact Newton method for the solution of large-scale nonlinear complementarity problems. Math. Program. 76, 493–512 (1997) · Zbl 0871.90096
[9] Facchinei, F., Pang, J.-S.: Finite-Dimensional Variational Inequalities and Complementarity Problems, Volumes I and II. Springer-Verlag, New York, 2003 · Zbl 1062.90002
[10] Facchinei, F., Soares, J.: A new merit function for nonlinear complementarity problems and a related algorithm. SIAM J. Optim. 7, 225–247 (1997) · Zbl 0873.90096
[11] Faraut, U., Korányi, A.: Analysis on Symmetric Cones. Oxford Mathematical Monographs, Oxford University Press, New York, 1994 · Zbl 0841.43002
[12] Ferris, M.C., Kanzow, C., Munson, T.S.: Feasible descent algorithms for mixed complementarity problems. Math. Program. 86, 475–497 (1999) · Zbl 0946.90094
[13] Ferris, M.C., Pang, J.-S., Engineering and economic applications of complementarity problems. SIAM Rev. 39, 669–713 (1997) · Zbl 0891.90158
[14] Ferris, M.C., Pang, J.-S., (eds.): Complementarity and Variational Problems: State of the Art. SIAM Publications, Philadelphia, 1996 · Zbl 0845.90118
[15] Ferris, M.C., Mangasarian, O.L., Pang, J.-S., eds.: Complementarity: Applications, Algorithms and Extensions. Kluwer Academic Publishers, Dordrecht, 2001 · Zbl 0966.00043
[16] Fischer, A.: A special Newton-type optimization methods. Optim. 24, 269–284 (1992) · Zbl 0814.65063
[17] Fischer, A.: Solution of the monotone complementarity problem with locally Lipschitzian functions. Math. Program. 76, 513–532 (1997) · Zbl 0871.90097
[18] Fletcher, R.: Practical Methods of Optimization. 2nd ed., Wiley-Interscience, Chichester, 1987 · Zbl 0905.65002
[19] Fukushima, M., Luo, Z.-Q., Tseng, P.: Smoothing functions for second-order cone complementarity problems. SIAM J. Optim. 12, 436–460 (2002) · Zbl 0995.90094
[20] Geiger, C., Kanzow, C.: On the resolution of monotone complentarity problems. Comput. Optim. Appl. 5, 155–173 (1996) · Zbl 0859.90113
[21] 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. · Zbl 1107.90036
[22] 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) · Zbl 1114.90139
[23] Isac, G.: Complementarity Problems. Springer-Verlag, Berlin, 1992 · Zbl 0795.90072
[24] Jiang, H., Qi, L.: A new nonsmooth equations approach to nonlinear complementarities. SIAM J. Control Optim. 35, 178–193 (1997) · Zbl 0872.90097
[25] Kanzow, C.: An unconstrained optimization technique for large scale linearly constrained convex minimization problems. Comput. 53, 101–117 (1994) · Zbl 0820.90099
[26] Kanzow, C.: Nonlinear complementarity as unconstrained optimization. J. Optim. Theory Appl. 88, 139–155 (1996) · Zbl 0845.90120
[27] Kanzow, C.: Global optimization techniques for mixed complementarity problems. J. Global Optim. 16, 1–21 (2000) · Zbl 1009.90119
[28] 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) · Zbl 0941.90070
[29] Kanzow, C., Kleinmichel, H.: A class of Newton-type methods for equality and inequality constrained optimization. Optim. Methods Softw. 5, 173–198 (1995)
[30] Kanzow, C., Pieper, H.: Jacobian smoothing methods for nonlinear complementarity problems. SIAM J. Optim. 9, 342–373 (1999) · Zbl 0986.90065
[31] Kanzow, C., Yamashita, Y., Fukushima, M.: New NCP functions and their properties. J. Optim. Theory Appl. 97, 115–135 (1997) · Zbl 0886.90146
[32] Liu, D.C., Nocedal, J.: On the limited memory BFGS method for large scale optimization. Math. Program. 45, 503–528 (1989) · Zbl 0696.90048
[33] Lobo, M.S., Vandenberghe, L., Boyd, S., Lebret, H.: Application of second-order cone programming. Lin. Algeb. Appl. 284, 193–228 (1998) · Zbl 0946.90050
[34] 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 · Zbl 0886.90158
[35] Mangasarian, O.L., Solodov, M.V.: Nonlinear complementarity as unconstrained and constrained minimization. Math. Program. 62, 277–297 (1993) · Zbl 0813.90117
[36] Mittelmann, H.D.: An independent benchmarking of SDP and SOCP solvers. Math. Program. 95, 407–430 (2003) · Zbl 1030.90080
[37] 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) · Zbl 0967.65077
[38] Nocedal, J., Wright, S.J.: Numerical Optimization. Springer-Verlag, New York, 1999 · Zbl 0930.65067
[39] 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/
[40] Peng, J.-M.: Equivalence of variational inequality problems to unconstrained minimization. Math. Program. 78, 347–355 (1997) · Zbl 0887.90171
[41] 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) · Zbl 0977.90064
[42] Schmieta, S., Alizadeh, F.: Associative and Jordan algebras, and polynomial time interior-point algorithms for symmetric cones. Math. Oper. Res. 26, 543–564 (2001) · Zbl 1073.90572
[43] 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. · Zbl 1111.90112
[44] 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) · Zbl 1059.90118
[45] Solodov, M.V.: Implicit Lagrangian. In: Floudas, C., Pardalos, P., (eds.), Encyclopedia of Optimization. Kluwer Academic Publishers, Dordrecht, 1999
[46] 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
[47] Sun, D., Qi, L.: On NCP functions. Comput. Optim. Appl. 13, 201–220 (1999) · Zbl 1040.90544
[48] Sun, D., Sun, J.: Strong semismoothness of Fischer-Burmeister SDC and SOC functions. Math. Program. 103, to appear (2005) · Zbl 1099.90062
[49] 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) · Zbl 0960.90086
[50] Tseng, P.: Merit function for semidefinite complementarity problems. Math. Program. 83, 159–185 (1998) · Zbl 0920.90135
[51] Tseng, P., Yamashita, N., Fukushima, M.: Equivalence of complementarity problems to differentiable minimization: a unified approach. SIAM J. Optim. 6, 446–460 (1996) · Zbl 0853.65067
[52] 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) · Zbl 0957.90129
[53] 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 · Zbl 0969.90087
[54] Yamashita, N., Taji, K., Fukushima, M.: Unconstrained optimization reformulations of variational inequality problems. J. Optim. Theory Appl. 92, 439–456 (1997) · Zbl 0879.90180
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.