Solving variational inequalities defined on a domain with infinitely many linear constraints. (English) Zbl 1116.49005
Summary: We study a variational inequality problem whose domain is defined by infinitely many linear inequalities. A discretization method and an analytic center based inexact cutting plane method are proposed. Under proper assumptions, the convergence results for both methods are given. We also provide numerical examples to illustrate the proposed methods.
MSC:
| 49J40 | Variational inequalities |
| 90C34 | Semi-infinite programming |
| 93C05 | Linear systems in control theory |
Keywords:
Variational inequality problem; Analytic center based cutting plane method; Discretization method; Semi-infinite programmingReferences:
| [1] | Anderson, E.J., Nash, P.: Linear Programming in Infinite-Dimensional Spaces. Wiley, Chichester (1987) · Zbl 0632.90038 |
| [2] | Birbil, S.I., Fang, S.-C.: An electromagnetism-like mechanism for global optimization. J. Glob. Optim. 25, 263–282 (2003) · Zbl 1047.90045 · doi:10.1023/A:1022452626305 |
| [3] | Cheney, E.W., Goldstein, A.A.: Newton’s method for convex programming and Tchebycheff approximation. Numer. Math. 1, 253–268 (1959) · Zbl 0113.10703 · doi:10.1007/BF01386389 |
| [4] | Eaves, B.C., Zangwill, W.I.: Generalized cutting plane algorithms. SIAM J. Control 9, 529–542 (1971) · doi:10.1137/0309037 |
| [5] | Elzinga, J., Moore, T.G.: A central cutting plane algorithm for the convex programming problem. Math. Program. 8, 134–145 (1975) · Zbl 0318.90048 · doi:10.1007/BF01580439 |
| [6] | Facchinei, F., Pang, J.-S.: Finite-Dimensional Variational Inequalities and Complementarity Problems. Springer, New York (2003) · Zbl 1062.90002 |
| [7] | Fang, S.-C., Rajasekera, J.R., Tsao, H.-S.J.: Entropy Optimization and Mathematical Programming. Kluwer Academic, Boston (1997) · Zbl 0933.90051 |
| [8] | Fang, S.-C., Wu, S.-Y., Sun, J.: An analytic center cutting plane method for solving semi-infinite variational inequality problems. J. Glob. Optim. 28, 141–152 (2004) · Zbl 1061.49008 · doi:10.1023/B:JOGO.0000015308.49676.ea |
| [9] | Goberna, M.A., Lopez, M.A.: A comprehensive survey of linear semi-infinite optimization theory. In: Reemsten, R., Ruckmann, J.-J. (eds.) Semi-Infinite Programming, pp. 3–27. Kluwer Academic, Dordrecht (1998) · Zbl 0909.90256 |
| [10] | Goffin, J.-L., Luo, Z.-Q., Ye, Y.: On the complexity of a column generation algorithm for convex or quasiconvex feasibility problems. In: Hager, W.W., Hearn, D.W., Pardalos, P.M. (eds.) Large Scale Optimization: State of the Art. Kluwer, New York (1993) |
| [11] | Goffin, J.-L., Luo, Z., Ye, Y.: Complexity analysis of an interior cutting plane method for convex feasibility problems. SIAM J. Optim. 6, 638–652 (1996) · Zbl 0856.90088 · doi:10.1137/S1052623493258635 |
| [12] | Goffin, J.-L., Marcotte, P., Zhu, D.: An analytic center cutting plane method for pseudomonotone variational inequalities. Oper. Res. Lett. 20, 1–6 (1997) · Zbl 0899.90157 · doi:10.1016/S0167-6377(96)00029-6 |
| [13] | Goffin, J.-L., Vial, J.-P.: Convex nondifferentiable optimization: a survey focused on the analytic center cutting plane method, Logilab Technical report, Department of Management Studies, University of Geneva, Switzerland (1999) |
| [14] | Han, J., Huang, Z.-H., Fang, S.-C.: Solvability of variational inequality problems. J. Optim. Theory Appl. 122, 501–520 (2004) · Zbl 1082.49009 · doi:10.1023/B:JOTA.0000042593.74934.b7 |
| [15] | Harker, P.T., Pang, J.-S.: Finite-dimensional variational inequality and nonlinear complementarity problems: a survey of theory, algorithms and applications. Math. Program. 48, 161–220 (1990) · Zbl 0734.90098 · doi:10.1007/BF01582255 |
| [16] | Horst, R.: Deterministic methods in constrained global optimization: some recent advances and new fields of application. J. SIAM 8, 703–712 (1960) |
| [17] | Kelley, J.E.: The cutting-plane method for solving convex programs. Numer. Math. 1, 253–268 (1959) · Zbl 0113.10703 · doi:10.1007/BF01386389 |
| [18] | Luo, Z.-Q., Sun, J.: An analytic center based column generation algorithm for convex quadratic feasibility problems. SIAM J. Optim. 9, 217–235 (1999) · Zbl 1032.90526 · doi:10.1137/S1052623495294943 |
| [19] | Luo, Z.-Q., Sun, J.: A polynomial cutting surfaces algorithm for the convex feasibility problem defined by self-concordant inequalities. Comput. Optim. Appl. 15, 167–191 (2000) · Zbl 0947.90128 · doi:10.1023/A:1008787027641 |
| [20] | Lüthi, H.-J., Bueler, B.: An analytical center quadratic cut method for strongly monotone variational inequality problems. SIAM J. Optim. 10, 415–426 (2000) · Zbl 1030.90084 · doi:10.1137/S1052623498338321 |
| [21] | Magnanti, T.L., Perakis, G.: A unifying geometric solution framework and complexity analysis for variational inequalities. Math. Program. 71, 327–351 (1995) · Zbl 0848.49009 |
| [22] | Marcotte, P., Zhu, D.: A cutting plane method for solving quasimonotone variational inequalities. Comput. Optim. Appl. 20, 317–324 (2001) · Zbl 1054.90073 · doi:10.1023/A:1011219303531 |
| [23] | Nesterov, Yu., Vial, J.-Ph.: Homogeneous analytic center cutting plane methods for convex problems and variational inequalities. SIAM J. Optim. 9, 708–728 (1999) · Zbl 0971.65060 · doi:10.1137/S1052623497324813 |
| [24] | Reemtsen, R., Ruckmann, J.-J. (eds.): Semi-Infinite Programming. Kluwer Academic, Dordrecht (1998) |
| [25] | Reemtsen, R., Ruckmann, J.-J.: Numerical methods for semi-infinite programming: a survey. In: Reemsten, R., Ruckmann, J.-J. (eds.) Semi-Infinite Programming, pp. 195–275. Kluwer Academic, Dordrecht (1998) · Zbl 0908.90255 |
| [26] | Tichatschke, R., Nobeling, V.: A cutting plane method for quadratic semi-infinite programming problems. Optimization 19, 803–817 (1988) · Zbl 0664.90073 · doi:10.1080/02331938808843393 |
| [27] | Veinott, A.F.: The supporting hyperplane method for unimodal programming. Oper. Res. 15, 147–152 (1967) · Zbl 0147.38604 · doi:10.1287/opre.15.1.147 |
| [28] | Wu, S.-Y., Fang, S.-C., Lin, C.-J.: Relaxed cutting plane method for solving linear semi-infinite programming problems. J. Optim. Theory Appl. 99, 759–779 (1998) · Zbl 0956.90056 · doi:10.1023/A:1021763419562 |
| [29] | Zhao, Y.B., Han, J.: Exceptional family of elements for variational inequality problem and its applications. J. Glob. Optim. 14, 313–330 (1998). · Zbl 0932.49012 · doi:10.1023/A:1008202323884 |
| [30] | Zhu, Y.J.: Generalization of some fundamental theorems on linear inequalities. Acta Math. Sinica 16, 25–40 (1966) · Zbl 0147.34102 |
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.
