Linear complementarity problems on extended second order cones. (English) Zbl 1390.90540
Summary: In this paper, we study the linear complementarity problems on extended second order cones. We convert a linear complementarity problem on an extended second order cone into a mixed complementarity problem on the non-negative orthant. We state necessary and sufficient conditions for a point to be a solution of the converted problem. We also present solution strategies for this problem, such as the Newton method and Levenberg-Marquardt algorithm. Finally, we present some numerical examples.
MSC:
| 90C33 | Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming) |
| 90C25 | Convex programming |
References:
| [1] | Karush, W.: Minima of functions of several variables with inequalities as side conditions. Master Thesis, University of Chicago (1939) · Zbl 0155.28403 |
| [2] | Dantzig, G.B., Cottle, R.W.: Positive (semi-) definite matrices and mathematical programming. Tech. Rep., California Univ Berkeley Operations Research Center (1963) · Zbl 0178.22801 |
| [3] | Cottle, R.W., Dantzig, G.B.: Complementary pivot theory of mathematical programming. Linear Algebra Appl. 1(1), 103-125 (1968) · Zbl 0155.28403 · doi:10.1016/0024-3795(68)90052-9 |
| [4] | Mangasarian, O.L.: Linear complementarity problems solvable by a single linear program. Math. Program. 10(1), 263-270 (1976) · Zbl 0355.90040 · doi:10.1007/BF01580671 |
| [5] | Garcia, C.B.: Some classes of matrices in linear complementarity theory. Math. Program. 5(1), 299-310 (1973) · Zbl 0284.90048 · doi:10.1007/BF01580135 |
| [6] | Borwein, J.M., Dempster, M.A.H.: The linear order complementarity problem. Math. Oper. Res. 14(3), 534-558 (1989) · Zbl 0694.90094 · doi:10.1287/moor.14.3.534 |
| [7] | Alizadeh, F., Goldfarb, D.: Second-order cone programming. Math. Program. 95(1), 3-51 (2003) · Zbl 1153.90522 · doi:10.1007/s10107-002-0339-5 |
| [8] | Facchinei, F., Pang, J.S.: Finite-Dimensional Variational Inequalities and Complementarity Problems, vol. II. Springer, New York (2003) · Zbl 1062.90002 |
| [9] | Konnov, I.: Equilibrium Models and Variational Inequalities, vol. 210. Elsevier, Amsterdam (2007) · Zbl 1140.91056 · doi:10.1016/S0076-5392(07)80022-1 |
| [10] | Jaillet, P., Lamberton, D., Lapeyre, B.: Variational inequalities and the pricing of american options. Acta Appl. Math. 21(3), 263-289 (1990) · Zbl 0714.90004 · doi:10.1007/BF00047211 |
| [11] | Yonekura, K., Kanno, Y.: Second-order cone programming with warm start for elastoplastic analysis with von Mises yield criterion. Optim. Eng. 13(2), 181-218 (2012). https://doi.org/10.1007/s11081-011-9144-4 · Zbl 1293.74039 · doi:10.1007/s11081-011-9144-4 |
| [12] | Zhang, L.L., Li, J.Y., Zhang, H.W., Pan, S.H.: A second order cone complementarity approach for the numerical solution of elastoplasticity problems. Comput. Mech. 51(1), 1-18 (2013). https://doi.org/10.1007/s00466-012-0698-6 · Zbl 1398.74484 · doi:10.1007/s00466-012-0698-6 |
| [13] | Luo, G., An, X., Xia, J.: Robust optimization with applications to game theory. Appl. Anal. 88(8), 1183-1195 (2009). https://doi.org/10.1080/00036810903157196 · Zbl 1175.90375 · doi:10.1080/00036810903157196 |
| [14] | Nishimura, R., Hayashi, S., Fukushima, M.: Robust Nash equilibria in \[NN\]-person non-cooperative games: uniqueness and reformulation. Pac. J. Optim. 5(2), 237-259 (2009) · Zbl 1162.91304 |
| [15] | Andreani, R., Friedlander, A., Mello, M.P., Santos, S.A.: Box-constrained minimization reformulations of complementarity problems in second-order cones. J. Global Optim. 40(4), 505-527 (2008). https://doi.org/10.1007/s10898-006-9109-x · Zbl 1138.90032 · doi:10.1007/s10898-006-9109-x |
| [16] | Németh, S.Z., Zhang, G.: Extended Lorentz cones and mixed complementarity problems. J. Glob. Optim. 62(3), 443-457 (2015) · Zbl 1358.90140 · doi:10.1007/s10898-014-0259-y |
| [17] | Sznajder, R.: The Lyapunov rank of extended second order cones. J. Glob. Optim. 66(3), 585-593 (2016) · Zbl 1351.90157 · doi:10.1007/s10898-016-0445-1 |
| [18] | Ferreira, O.P., Németh, S.Z.: How to project onto extended second order cones (2016). arXiv:1610.08887v2 · Zbl 1407.90319 |
| [19] | Németh, S.Z., Zhang, G.: Extended Lorentz cones and variational inequalities on cylinders. J. Optim. Theory Appl. 168(3), 756-768 (2016). https://doi.org/10.1007/s10957-015-0833-6 · Zbl 1336.90091 · doi:10.1007/s10957-015-0833-6 |
| [20] | Markowitz, H.: Portfolio selection. J. Finance 7(1), 77-91 (1952) |
| [21] | Roy, A.D.: Safety first and the holding of assets. Econ. J. Econ. Soc. 20(3), 431-449 (1952) · Zbl 0047.38805 |
| [22] | Facchinei, F., Pang, J.S.: Finite-Dimensional Variational Inequalities and Complementarity Problems, vol. I. Springer, New York (2003) · Zbl 1062.90002 |
| [23] | Karamardian, S.: Generalized complementarity problem. J. Optim. Theory Appl. 8, 161-168 (1971) · Zbl 0218.90052 · doi:10.1007/BF00932464 |
| [24] | Zhang, F.: The Schur Complement and Its Applications, vol. 4. Springer Science & Business Media, Berlin (2006) |
| [25] | Sohrab, H.H.: Basic Real Analysis, vol. 231. Springer, New York (2003) · Zbl 1035.26001 · doi:10.1007/978-0-8176-8232-3 |
| [26] | Fischer, A.: A special newton-type optimization method. Optimization 24(3-4), 269-284 (1992) · Zbl 0814.65063 · doi:10.1080/02331939208843795 |
| [27] | Fischer, A.: A newton-type method for positive-semidefinite linear complementarity problems. J. Optim. Theory Appl. 86(3), 585-608 (1995) · Zbl 0839.90121 · doi:10.1007/BF02192160 |
| [28] | Atkinson, K.E.: An Introduction to Numerical Analysis. Wiley, London (2008) |
| [29] | Karmarkar, N.: A new polynomial-time algorithm for linear programming. In: Proceedings of the 16th Annual ACM Symposium on Theory of Computing, pp. 302-311. ACM (1984) · Zbl 0557.90065 |
| [30] | Mangasarian, O.L.: Solution of symmetric linear complementarity problems by iterative methods. J. Optim. Theory Appl. 22(4), 465-485 (1977) · Zbl 0341.65049 · doi:10.1007/BF01268170 |
| [31] | O’Leary, D.P., White, R.E.: Multi-splittings of matrices and parallel solution of linear systems. SIAM J. Algebraic Discrete Methods 6(4), 630-640 (1985) · Zbl 0582.65018 · doi:10.1137/0606062 |
| [32] | Luenberger, D.G., Ye, Y.: Linear and Nonlinear Programming, vol. 228. Springer, New York (2015) · Zbl 1319.90001 |
| [33] | Marquardt, D.W.: An algorithm for least-squares estimation of nonlinear parameters. J. Soc. Ind. Appl. Math. 11(2), 431-441 (1963) · Zbl 0112.10505 · doi:10.1137/0111030 |
| [34] | Yamashita, N.; Fukushima, M.; Alefeld, G. (ed.); Chen, X. (ed.), On the rate of convergence of the Levenberg-Marquardt method, 239-249 (2001), New York · Zbl 1001.65047 · doi:10.1007/978-3-7091-6217-0_18 |
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.
