×

zbMATH — the first resource for mathematics

Some recent advances in projection-type methods for variational inequalities. (English) Zbl 1018.65083
Summary: Projection-type methods are a class of simple methods for solving variational inequalities, especially for complementarity problems. We review and summarize recent developments in this class of methods, and focus mainly on some new trends in projection-type methods.

MSC:
65K10 Numerical optimization and variational techniques
49J40 Variational inequalities
90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)
Software:
TRON
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Ahmad, K.; Kazmi, K.R.; Rehman, N., Fixed-point technique for implicit complementarity problem in Hilbert lattice, J. optim. theory appl., 93, 67-72, (1997) · Zbl 0899.90156
[2] Auslender, A., Optimization méthodes numériques, (1976), Masson Paris
[3] Bakusinskii, A.B.; Polyak, B.T., On the solution of variational inequalities, Sov. math. dokl., 15, 1705-1710, (1974) · Zbl 0311.49015
[4] Bauschke, H.; Combettes, P., A weak-to-strong convergence principle for Fejér-monotone methods in Hilbert spaces, Math. oper. res., 26, 248-264, (2001) · Zbl 1082.65058
[5] Bertsekas, D.P., Projected Newton methods for optimization problems with simple constraints, SIAM J. control optim., 20, 221-246, (1982) · Zbl 0507.49018
[6] Billups, S.; Murty, K., Complementarity problems, J. comput. appl. math., 124, 303-318, (2000) · Zbl 0982.90058
[7] Bregman, L.M., The relaxation method of finding the common point of convex sets and its applications to the solution of problem in convex programming, USSR comput. math. math. phys., 7, 200-217, (1967) · Zbl 0186.23807
[8] Bruck, R.E., An iterative solution of a variational inequality for certain monotone operators in Hilbert space, Bull. amer. math. soc., 81, 890-892, (1975) · Zbl 0332.49005
[9] Burachik, R.S.; Scheimberg, S., A proximal point method for the variational inequality problem in Banach spaces, SIAM J. control optim., 39, 1633-1649, (2001) · Zbl 0988.90045
[10] Burke, J.V.; Moré, J.J., On the identification of active constraints, SIAM J. numer. anal., 25, 1197-1211, (1988) · Zbl 0662.65052
[11] Burke, J.V.; Moré, J.J., Exposing constraints, SIAM J. optim., 4, 573-595, (1994) · Zbl 0809.65058
[12] Calamai, P.H.; Moré, J.J., Projected gradient methods for linearly constrained problems, Math. programming, 39, 93-116, (1987) · Zbl 0634.90064
[13] Chen, G.; Rockafellar, R.T., Convergence rates in forward – backward splitting, SIAM J. optim., 7, 421-444, (1997) · Zbl 0876.49009
[14] R.W. Cottle, Nonlinear programs with positively bounded jacobians, Ph.D. Dissertation, Department of Mathematics, University of California, Berkeley, 1964. · Zbl 0158.18903
[15] Cottle, R.W.; Giannessi, F.; Lions, J.L., Variational inequalities and complementarity problems: theory and applications, (1980), Wiley New York
[16] Cottle, R.W.; Pang, J.S.; Stone, R.E., The linear complementarity problem, (1992), Academic Press New York · Zbl 0757.90078
[17] H. Dan, N. Yamashita, M. Fukushima, A superlinearly convergent algorithm for the monotone nonlinear complementarity problem without uniqueness and nondegeneracy conditions, The Technical Report, Department of Applied Mathematics and Physics, Graduate School of Information, Kyoto University, Japan, 2001. · Zbl 1082.90568
[18] Ding, X.P.; Luo, C.L., Existence and algorithm for solving some generalized mixed variational inequalities, Comput. math. appl., 37, 23-30, (1999) · Zbl 0938.49007
[19] Douglas, J.; Rachford, H.H., On the numerical solution of the heat conduction problem in 2 and 3 space variables, Trans. amer. math. soc., 82, 421-439, (1956) · Zbl 0070.35401
[20] Dunn, J.C., On the convergence of projected gradient processes to singular critical points, J. optim. theory appl., 56, 203-216, (1987) · Zbl 0616.90060
[21] Eckstein, J.; Bertsekas, D.P., On the douglas – rachford splitting method and the proximal point algorithm for maximal monotone operator, Math. programming, 55, 293-318, (1992) · Zbl 0765.90073
[22] Facchinei, F.; Fischer, A.; Kanzow, C., On the accurate identification of active constraints, SIAM J. optim., 9, 14-32, (1999) · Zbl 0960.90080
[23] Facchinei, F.; Júdice, J.; Soares, J., An active set Newton algorithm for large-scale nonlinear programs with box constraints, SIAM J. optim., 8, 158-186, (1998) · Zbl 0911.90301
[24] Farouq, N.E., Pseudomonotone variational inequalitiesconvergence of proximal methods, J. optim. theory appl., 109, 311-326, (2001) · Zbl 0993.49006
[25] Ferris, M.C., Finite termination of the proximal point algorithm, Math. programming, 50, 359-366, (1991) · Zbl 0741.90051
[26] Ferris, M.C.; Kanzow, C., Complementarity and related problems, ()
[27] Ferris, M.C.; Kanzow, C.; Munson, T.S., Feasible descent algorithms for mixed complementarity problems, Math. programming, 86, 475-497, (1999) · Zbl 0946.90094
[28] Ferris, M.C.; Pang, J.S., Engineering and economic applications of complementarity problems, SIAM rev., 39, 669-713, (1997) · Zbl 0891.90158
[29] Ferris, M.C.; Pang, J.S., Nondegenerate solutions and related concepts in affine variational inequalities, SIAM J. control optim., 34, 244-263, (1996) · Zbl 0845.90118
[30] Fukushima, M., Equivalent differentiable optimization problems and descent methods for asymmetric variational inequality problems, Math. programming, 53, 99-110, (1992) · Zbl 0756.90081
[31] Fukushima, M., The primal douglas – rachford splitting algorithm for a class of monotone mappings with application to the traffic equilibrium problem, Math. programming, 72, 1-15, (1996) · Zbl 0851.90138
[32] Gafni, E.M.; Bertsekas, D.P., Two-metric projection methods for constrained optimization, SIAM J. control optim., 22, 936-964, (1984) · Zbl 0555.90086
[33] Glowinski, R., Numerical methods for nonlinear variational inequalities, (1984), Springer New York · Zbl 0575.65123
[34] R. Glowinski, P. Le Tallec, Augmented Lagrangian and Operator-Splitting Methods in Nonlinear Mechanics, SIAM Studies in Applied Mathematics, Philadelphia, Pennsylvania, 1989. · Zbl 0698.73001
[35] Goldstein, A.A., Convex programming in Hilbert space, Bull. amer. math. soc., 70, 709-710, (1964) · Zbl 0142.17101
[36] Harker, P.T.; Pang, J.S., Finite-dimensional variational inequality and nonlinear complementarity problemsa survey of theory, algorithms and applications, Math. programming, 48, 161-220, (1990) · Zbl 0734.90098
[37] Hartman, P.; Stampacchia, G., On some nonlinear elliptic differential functional equations, Acta math., 115, 153-188, (1966) · Zbl 0142.38102
[38] Haubruge, S.; Nguyen, V.H.; Strodiot, J.J., Convergence analysis and applications of the glowinski-le tallec splitting method for finding a zero of the sum of two maximal monotone operators, J. optim. theory appl., 97, 645-673, (1998) · Zbl 0908.90209
[39] He, B.S., A projection and contraction method for a class of linear complementarity problem and its application in convex quadratic programming, Appl. math. optim., 25, 247-262, (1992) · Zbl 0767.90086
[40] He, B.S., Further developments in an iterative projection and contraction method for linear programming, J. comput. math., 11, 350-364, (1993) · Zbl 0795.65032
[41] He, B.S., A new method for a class of linear variational inequalities, Math. programming, 66, 137-144, (1994) · Zbl 0813.49009
[42] He, B.S., Solving a class of linear projection equation, Numer. math., 68, 71-80, (1994) · Zbl 0822.65040
[43] He, B.S., A modified projection and contraction method for a class of linear complementarity problems, J. comput. math., 14, 54-63, (1996) · Zbl 0854.65047
[44] He, B.S., A class of projection and contraction methods for monotone variational inequalities, Appl. math. optim., 35, 69-76, (1997) · Zbl 0865.90119
[45] He, B.S., Inexact implicit methods for monotone general variational inequalities, Math. programming, 86, 199-217, (1999) · Zbl 0979.49006
[46] He, B.S.; Liao, L.Z.; Yang, H., Decomposition method for a class of monotone variational inequality problems, J. optim. theory appl., 103, 603-622, (1999) · Zbl 0953.65049
[47] He, B.S.; Stoer, J., Solution of projection problems over polytopes, Numer. math., 61, 73-90, (1992) · Zbl 0758.65046
[48] Huang, N.J.; Bai, M.R.; Cho, Y.J.; Kang, S.M., Generalized nonlinear mixed quasi-variational inequalities, Comput. math. appl., 40, 205-215, (2000) · Zbl 0960.47036
[49] Isac, G., Complementarity problems, Lecture notes in mathematics, Vol. 1528, (1992), Springer Berlin · Zbl 0761.90091
[50] Iusem, A.N., An iterative algorithm for the variational inequality problem, Math. appl. comput., 13, 103-114, (1994) · Zbl 0811.65049
[51] Iusem, A.N., A generalized proximal point algorithm for the variational inequality problem in Hilbert space, SIAM J. optim., 8, 197-216, (1998) · Zbl 0911.90273
[52] Iusem, A.N.; Monteiro, R.D.C., On dual convergence of the generalized proximal point method with Bregman distances, Math. oper. res., 25, 606-624, (2000) · Zbl 0980.90064
[53] Iusem, A.N.; Pérez, L.R., An extragradient-type algorithm for non-smooth variational inequalities, Optimization, 48, 309-332, (2000) · Zbl 0979.49009
[54] Iusem, A.N.; Svaiter, B.F., A variant of Korpelevich’s method for variational inequalities with a new search strategy, Optimization, 42, 309-321, (1997) · Zbl 0891.90135
[55] Kanzow, C., Strictly feasible equation-based methods for mixed complemetarity problems, Numer. math., 89, 135-160, (2001) · Zbl 0992.65070
[56] Kanzow, C., An active set-type Newton method for constrained nonlinear systems, (), 179-200 · Zbl 0983.90060
[57] Kaplan, A.; Tichatschke, R., Proximal point approach and approximation of vatriational inequalities, SIAM J. control optim., 39, 1136-1159, (2000) · Zbl 0997.47053
[58] Khobotov, E.N., Modification of the extragradient method for solving variational inequalities and certain optimization problem, USSR comput. math. phys., 27, 120-127, (1987) · Zbl 0665.90078
[59] Kinderlehrer, D.; Stampacchia, G., An introduction to variational inequalities and their applications, (1980), Academic Press New York · Zbl 0457.35001
[60] Kiwiel, K.C., Proximal minimization methods with generalized Bregman function, SIAM J. control optim., 35, 1142-1168, (1997) · Zbl 0890.65061
[61] Konnov, I.V., A class of combined iterative methods for solving variational inequalities, J. optim. theory appl., 94, 677-693, (1997) · Zbl 0892.90172
[62] Konnov, I.V., A combined relaxation method for variational inequalities with nonlinear constraints, Math. programming, 80, 239-252, (1998) · Zbl 0894.90145
[63] Konnov, I.V., On quasimonotone variational inequalities, J. optim. theory appl., 99, 165-181, (1998) · Zbl 0911.90325
[64] Korpelevich, G.M., The extragradient method for finding saddle points and other problems, Matecon, 12, 747-756, (1976) · Zbl 0342.90044
[65] Levitin, E.S.; Polyak, B.T., Constrained minimization problems, USSR comput. math. math. phys., 6, 1-50, (1966) · Zbl 0161.07002
[66] Li, W., Remarks on convergence of the matrix splitting algorithm for the symmetric linear complementarity problem, SIAM J. optim., 3, 155-165, (1993) · Zbl 0786.90074
[67] Lin, C.J.; Moré, J.J., Newton’s method for large bound-constrained optimization problems, SIAM J. optim., 9, 1100-1127, (1999) · Zbl 0957.65064
[68] Lions, P.L.; Mercier, B., Splitting algorithms for the sum of two nonlinear operators, SIAM J. numer. anal., 16, 964-979, (1979) · Zbl 0426.65050
[69] Luo, Z.Q.; Tseng, P., Error bound and convergence analysis of matrix splitting algorithm for the affine variational inequality problem, SIAM J. optim., 2, 43-54, (1992) · Zbl 0777.49010
[70] Luo, Z.Q.; Tseng, P., Error bounds and convergence analysis of feasible descent methodsa general approach, Ann. oper. res., 46, 157-178, (1993) · Zbl 0793.90076
[71] Luque, F.J., Asymptotic covergence analysis of the proximal point algorithm, SIAM J. control optim., 22, 277-293, (1984) · Zbl 0533.49028
[72] Mahey, P.; Oualibouch, S.; Pham, D.T., Proximal decomposition on the graph of maximal monotone operators, SIAM J. optim., 5, 454-466, (1995) · Zbl 0834.90105
[73] Mangasarian, O.L., Solution of symmetric linear complementarity problems by iterative methods, J. optim. theory appl., 22, 465-485, (1977) · Zbl 0341.65049
[74] Mangasarian, O.L.; Shiau, T.-H., Error bounds for monotone linear complementarity problems, Math. programming, 36, 81-89, (1986) · Zbl 0613.90095
[75] Marcotte, P., Application of Khobotov’s algorithm to variational inequalities and network equilibrium problems, Inform. systems oper. res., 29, 258-270, (1991) · Zbl 0781.90086
[76] Marcotte, P.; Wu, J.H., On the convergence of projection methodsapplication to the decomposition of affine variational inequalities, J. optim. theory appl., 85, 347-362, (1995) · Zbl 0831.90104
[77] Marcotte, P.; Zhu, D.L., Weak sharp solutions of variational inequalities, SIAM J. optim., 9, 179-189, (1998) · Zbl 1032.90050
[78] Martinet, B., Régularisation d’inéquations variationelles par approximations successives, Rev. francaise inform. rech. opér., 4, 154-158, (1970) · Zbl 0215.21103
[79] Murty, K.G., Linear complementarity, linear and nonlinear programming, (1988), Helderman Verlag Berlin · Zbl 0634.90037
[80] Noor, M.A., General variational inequalities, Appl. math. lett., 1, 119-121, (1988)
[81] Noor, M.A., Some recent advances in variational inequalities, part ibasic concepts, New Zealand J. math., 26, 53-80, (1997) · Zbl 0886.49004
[82] Noor, M.A., Some recent advances in variational inequalities, part iiother concepts, New Zealand J. math., 26, 229-255, (1997) · Zbl 0889.49006
[83] Noor, M.A., An implicit method for mixed variational inequalities, Appl. math. lett., 11, 109-113, (1998) · Zbl 0941.49005
[84] Noor, M.A., A modified extragradient method for general monotone variational inequalities, Comput. math. appl., 38, 19-24, (1999) · Zbl 0939.47055
[85] Noor, M.A., Some algorithms for general monotone mixed variational inequalities, Math. comput. model., 29, 1-9, (1999) · Zbl 0991.49004
[86] Noor, M.A., Algorithms for general mixed variational inequalities, J. math. anal. appl., 229, 330-343, (1999) · Zbl 0927.49004
[87] Noor, M.A., Iterative schemes for multivalues quasi variational inclusions, J. global optim., 19, 141-150, (2001) · Zbl 0982.49012
[88] Noor, M.A.; Wang, Y.J.; Xiu, N.H., Some projection methods for variational inequalities, Appl. math. comput., 137, 423-435, (2003) · Zbl 1031.65078
[89] Pang, J.S., On the convergence of a basic iterative method for the implicit complementarity problem, J. optim. theory appl., 37, 149-162, (1982) · Zbl 0482.90084
[90] Pang, J.S., A posteriori error bound for the linearly constrained variational inequality problem, Math. oper. res., 12, 474-484, (1987)
[91] Pang, J.S., Error bounds in mathematical programming, Math. programming, 79, 299-332, (1997) · Zbl 0887.90165
[92] Passty, G.B., Ergodic convergence to a zero of the sum of monotone operators in Hilbert space, J. math. anal. appl., 72, 383-390, (1979) · Zbl 0428.47039
[93] Peaceman, D.H.; Rachford, H.H., The numerical solution of parabolic elliptic differential equations, SIAM J. appl. math., 3, 28-41, (1955) · Zbl 0067.35801
[94] Peng, J.M.; Fukushima, M., A hybrid Newton method for solving the variational inequality problem via the D-gap function, Math. programming, 86, 367-386, (1999) · Zbl 0939.90023
[95] Robinson, S.M., Some continuity properties of polyhedral multifunctions, Math. programming stud., 14, 206-214, (1981) · Zbl 0449.90090
[96] Rockafellar, R.T., Monotone operators and the proximal point algorithm, SIAM J. control optim., 14, 877-898, (1976) · Zbl 0358.90053
[97] Schwartz, A.; Polak, E., Family of projected descent methods for optimization problems with simple bounds, J. optim. theory appl., 92, 1-31, (1997) · Zbl 0886.90140
[98] Sibony, M., Méthodes itératives pour LES équations et inéquations aux dérivées partielles nonlinéares de type monotone, Calcolo, 7, 65-183, (1970) · Zbl 0225.35010
[99] Solodov, M.V.; Svaiter, B.F., A new projection method for variational inequality problems, SIAM J. control optim., 37, 765-776, (1999) · Zbl 0959.49007
[100] Solodov, M.V.; Svaiter, B.F., A hybrid projection-proximal point algorithm, J. convex anal., 6, 59-70, (1999) · Zbl 0961.90128
[101] Solodov, M.V.; Svaiter, B.F., A hybrid approximate extragradient-proximal point algorithm using the enlargement of a maximal monotone operator, Set-valued anal., 7, 323-345, (1999) · Zbl 0959.90038
[102] Solodov, M.V.; Svaiter, B.F., A truly globally convergent Newton-type method for the monotone nonlinear complementarity problem, SIAM J. optim., 10, 605-625, (2000) · Zbl 0955.90133
[103] Solodov, M.V.; Tseng, P., Modified projection-type methods for monotone variational inequalities, SIAM J. control optim., 34, 1814-1830, (1996) · Zbl 0866.49018
[104] Solodov, M.V.; Tseng, P., Some methods based on the D-gap function for solving monotone variational inequalities, Comput. optim. appl., 17, 255-277, (2000) · Zbl 1168.49303
[105] Sun, D., An iterative method for solving variational inequality problems and complementarity problems, Numer. math.: J. chin. univ., 16, 145-153, (1994) · Zbl 0817.65048
[106] Sun, D., A projection and contraction method for the nonlinear complementarity problem and its extensions, Math. numer. sinica, 16, 183-194, (1994) · Zbl 0900.65188
[107] Sun, D., A new step-size skill for solving a class of nonlinear projection equations, J. comput. math., 13, 357-368, (1995) · Zbl 0854.65048
[108] Sun, D., A class of iterative methods for solving nonlinear projection equations, J. optim. theory appl., 91, 123-140, (1996) · Zbl 0871.90091
[109] Taji, K.; Fukushima, M.; Ibaraki, T., A globally convergent Newton method for solving strongly monotone variational inequalities, Math. programming, 58, 369-383, (1993) · Zbl 0792.49007
[110] Toint, PH.L., Global convergence of a class of trust region methods for nonconvex minimization in Hilbert space, IMA J. numer. anal., 8, 231-252, (1988) · Zbl 0698.65043
[111] Tseng, P., Further application of a splitting algorithm to decomposition in variational inequalities and convex programming, Math. programming, 48, 249-264, (1990) · Zbl 0725.90079
[112] Tseng, P., Applications of a splitting algorithm to decomposition in convex programming and variational inequalities, SIAM J. control optim., 29, 119-138, (1991) · Zbl 0737.90048
[113] Tseng, P., On linear convergence of iterative methods for the variational inequality problem, J. comput. appl. math., 60, 237-252, (1995) · Zbl 0835.65087
[114] Tseng, P., Alternating projection-proximal methods for variational inequality problem, SIAM J. optim., 7, 951-965, (1997) · Zbl 0914.90218
[115] Tseng, P., A modified forward – backward splitting method for maximal monotone mapping, SIAM J. control optim., 38, 431-446, (2000) · Zbl 0997.90062
[116] Verma, R.U., A class of projection-contraction methods applied to monotone variational inequalities, Appl. math. lett., 13, 55-62, (2000) · Zbl 0988.47041
[117] Verma, R.U., A new approach to the extragradient method for nonlinear variational inequalities, J. inequal. appl., 5, 407-418, (2000) · Zbl 0962.49005
[118] Wang, Y.J.; Xiu, N.H.; Wang, C.Y., Unified framework of extragradient-type methods for pseudomonotone variational inequalities, J. optim. theory appl., 111, 643-658, (2001) · Zbl 1039.49014
[119] Wang, Y.J.; Xiu, N.H.; Wang, C.Y., A new version of extragradient method for variational inequality problems, Comput. math. appl., 42, 969-979, (2001) · Zbl 0993.49005
[120] Xiu, N.H.; Wang, C.Y.; Zhang, J.Z., Convergence properties of projection and contraction methods for variational inequality problems, Appl. math. optim., 43, 147-168, (2001) · Zbl 0980.90093
[121] Xiu, N.H.; Zhang, J.Z., Local convergence analysis of projection-type algorithmsa unified approach, J. optim. theory appl., 115, 211-230, (2002) · Zbl 1091.49011
[122] Xiu, N.H.; Zhang, J.Z.; Noor, M.A., Tangent projection equations and general variational inequalities, J. math. anal. appl., 258, 755-762, (2001) · Zbl 1008.49010
[123] Yamashita, N.; Fukushima, M., The proximal point algorithm with genuine superlinear convergence for the monotone complementarity problem, SIAM J. optim., 11, 364-379, (2000) · Zbl 1004.47031
[124] J.C. Yao, Generalized quasi-variational inequality and implicit complementarity problem, Ph. D. Thesis, Stanford University, Stanford, USA, 1989.
[125] Zarantonello, E.H., Projections on convex sets in Hilbert space and spectral theory, () · Zbl 0059.19303
[126] Zhang, J.Z.; Xiu, N.H., Local convergence behavior of some projection-type methods for affine variational inequalities, J. optim. theory appl., 108, 205-216, (2001) · Zbl 0966.49007
[127] Zhang, J.Z.; Xiu, N.H., New projection-type methods for monotone LCP with finite termination, Numer. math., 92, 179-195, (2002) · Zbl 1040.65050
[128] Zhu, D.L.; Marcotte, P., Convergence properties of feasible descent methods for solving variational inequalities in Banach space, Comput. optim. appl., 10, 35-49, (1998) · Zbl 0904.90164
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.