zbMATH — the first resource for mathematics

Geometry Search for the term Geometry in any field. Queries are case-independent.
Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact.
"Topological group" Phrases (multi-words) should be set in "straight quotation marks".
au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted.
Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff.
"Quasi* map*" py: 1989 The resulting documents have publication year 1989.
so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14.
"Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic.
dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles.
py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses).
la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

a & b logic and
a | b logic or
!ab logic not
abc* right wildcard
"ab c" phrase
(ab c) parentheses
any anywhere an internal document identifier
au author, editor ai internal author identifier
ti title la language
so source ab review, abstract
py publication year rv reviewer
cc MSC code ut uncontrolled term
dt document type (j: journal article; b: book; a: book article)
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 $\Bbb R^n$. A popular choice of the merit function is the squared norm of the Fischer-Burmeister function, shown to be smooth over $\Bbb 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.

90C33Complementarity and equilibrium problems; variational inequalities (finite dimensions)
65K05Mathematical programming (numerical methods)
Full Text: DOI
[1] Alizadeh, F., Goldfarb, D.: Second-order cone programming. Math. Program. 95, 3--51 (2003) · Zbl 1153.90522 · doi:10.1007/s10107-002-0339-5
[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 · doi:10.1007/s10107-002-0349-3
[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 · doi:10.1007/s10107-002-0350-x
[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 · doi:10.1023/A:1022996819381
[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 · doi:10.1007/BF02592192
[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 · doi:10.1137/S1052623494279110
[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 · doi:10.1007/s101070050101
[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 · doi:10.1080/02331939208843795
[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 · doi:10.1137/S1052623400380365
[20] Geiger, C., Kanzow, C.: On the resolution of monotone complentarity problems. Comput. Optim. Appl. 5, 155--173 (1996) · Zbl 0859.90113 · doi:10.1007/BF00249054
[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 · doi:10.1137/S1052623403421516
[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 · doi:10.1137/S0363012994276494
[25] Kanzow, C.: An unconstrained optimization technique for large scale linearly constrained convex minimization problems. Comput. 53, 101--117 (1994) · Zbl 0820.90099 · doi:10.1007/BF02252984
[26] Kanzow, C.: Nonlinear complementarity as unconstrained optimization. J. Optim. Theory Appl. 88, 139--155 (1996) · Zbl 0845.90120 · doi:10.1007/BF02192026
[27] Kanzow, C.: Global optimization techniques for mixed complementarity problems. J. Global Optim. 16, 1--21 (2000) · Zbl 1009.90119 · doi:10.1023/A:1008331803982
[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 · doi:10.1016/S0167-6377(98)00023-6
[29] Kanzow, C., Kleinmichel, H.: A class of Newton-type methods for equality and inequality constrained optimization. Optim. Methods Softw. 5, 173--198 (1995) · doi:10.1080/10556789508805608
[30] Kanzow, C., Pieper, H.: Jacobian smoothing methods for nonlinear complementarity problems. SIAM J. Optim. 9, 342--373 (1999) · Zbl 0986.90065 · doi:10.1137/S1052623497328781
[31] Kanzow, C., Yamashita, Y., Fukushima, M.: New NCP functions and their properties. J. Optim. Theory Appl. 97, 115--135 (1997) · Zbl 0886.90146 · doi:10.1023/A:1022659603268
[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 · doi:10.1007/BF01589116
[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 · doi:10.1016/S0024-3795(98)10032-0
[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 · doi:10.1007/BF01585171
[36] Mittelmann, H.D.: An independent benchmarking of SDP and SOCP solvers. Math. Program. 95, 407--430 (2003) · Zbl 1030.90080 · doi:10.1007/s10107-002-0355-5
[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 · doi:10.1007/PL00011378
[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 · doi:10.1287/moor.24.2.440
[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 · doi:10.1287/moor.26.3.543.10582
[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 · doi:10.1007/s10107-004-0546-3
[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 · doi:10.1023/A:1008669226453
[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 · doi:10.1137/S1052623496314173
[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 · doi:10.1137/0806024
[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 · doi:10.1080/10556789908805750
[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 · doi:10.1023/A:1022660704427