Abstract
We present a new method for solving variational inequalities on polyhedra. The method is proximal based, but uses a very special logarithmic-quadratic proximal term which replaces the usual quadratic, and leads to an interior proximal type algorithm. We allow for computing the iterates approximately and prove that the resulting method is globally convergent under the sole assumption that the optimal set of the variational inequality is nonempty.
Similar content being viewed by others
References
A. Auslender and M. Haddou, “An interior proximal method for convex linearly constrained problems and its extension to variational inequalities,” Mathematical Programming, vol. 71, pp. 77–100, 1995.
A. Auslender, M. Teboulle, and S. Ben-Tiba, “Interior proximal and multiplier methods based on second order homogeneous functionals,” Submitted 1998.
R.D. Bruck, “An iterative solution of a variational inequality for certain monotone operators in Hilbert space,” Bulletin of the American Math. Soc., vol. 81, pp. 890–892, 1975 (With corrigendum, in vol. 82, p. 353, 1976).
R.S. Burachik and A.N. Iusem, “A generalized proximal point algorithm for the variational inequality problem in a Hilbert space,” SIAM Journal on Optimization, vol. 8, pp. 197–216, 1998.
Y. Censor, A.N. Iusem, and S.A. Zenios, “An interior-point method with Bregman functions for the variational inequality problem with paramonotone operators,” Working paper, University of Haifa, 1994.
J. Eckstein, “Approximate iterations in Bregman-function-based proximal algorithms,” RRR, 12–96, January 97, Rutgers University.
Z.Q. Luo and P. Tseng, “Error bounds and convergence analysis of feasible descent methods: A general approach,” Annals of Operations Research, vol. 46, pp. 157–178, 1993.
B. Martinet, “Regularisation d'inéquations variationnelles par approximations successives, Revue Francaise d'Automatique et Informatique recherche Opérationnelle,” vol. 4, pp. 154–159, 1970.
A. Nemirovski, “On self-concordant convex-concave functions,” Research Report 3/97, Optimization Laboratory Faculty of Industrial Engineering and Management, Technion Haifa.
Y. Nesterov and A. Nemirovski, Interior Point Polynomial Algorithms in Convex Programming, SIAM Publications: Philadelphia, PA, 1994.
B.T. Polyak, Introduction to Optimization, Optimization Software Inc.: New York, 1987.
R.T. Rockafellar, “On the maximality of sums of nonlinear monotone operators, Transactions of the American Mathematical Society,” vol. 149, pp. 75–88, 1970.
R.T. Rockafellar, Convex Analysis, Princeton University Press: Princeton, NJ, 1970.
R.T. Rockafellar, “Monotone operators and the proximal point algorithm,” SIAM J. of Control and Optimization, vol. 14, pp. 877–898, 1976.
R.T. Rockafellar, “Augmented Lagrangians and applications of the proximal point algorithm in convex programming,” Mathematics of Operations Research, vol. 1, pp. 97–116, 1976.
M. Teboulle, “Convergence of proximal-like algorithms,” SIAM J. of Optimization, vol. 7, pp. 1069–1083, 1997.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Auslender, A., Teboulle, M. & Ben-Tiba, S. A Logarithmic-Quadratic Proximal Method for Variational Inequalities. Computational Optimization and Applications 12, 31–40 (1999). https://doi.org/10.1023/A:1008607511915
Issue Date:
DOI: https://doi.org/10.1023/A:1008607511915