Newton-type methods with generalized distances for constrained optimization. (English) Zbl 0905.49015

Iusem, Alfredo N.; Solodov, Michael V.

Optimization 41, No. 3, 257-278 (1997).

Authors’ abstract: “We consider a class of interior point algorithms for minimizing a twice continuously differentiable function over a closed convex set with nonempty interior. On one hand, our algorithms can be viewed as an approximate version of the generalized proximal point methods and, on the other hand, as an extension of unconstrained Newton-type methods to the constrained case. Each step consists of solving a strongly convex unconstrained program followed by a one-dimensional search along either a line or a curve segment in the interior of the feasible set. The information about the feasible set is contained in the generalized distance function whose gradient diverges on the boundary of this set. When the feasible set is the whole space, the standard regularized Newton method is a particular case in our framework. We show, under standard assumptions, that every accumulation point of the sequence of iterates satisfies a first-order necessary optimality condition for the problem and solves the problem if the objective function is convex. Some computational results are also reported”.

Reviewer: A.Shapiro (Pretoria)

MSC:

49M37	Numerical methods based on nonlinear programming
90C30	Nonlinear programming
65K05	Numerical mathematical programming methods
49K40	Sensitivity, stability, well-posedness

Keywords:

electrical networks; nonlinear optimization; interior point algorithms; proximal point methods; unconstrained Newton-type methods

References:

[1]	Armijo L., Pacific Journal of Mathematics 16 pp 1– (1996) · Zbl 0202.46105
[2]	Bregman L.M., USSR Computational Mathematics and Mathematical Physics 7 (3) pp 200– (1967)
[3]	Burachik R. S. Iusem A. N. A generalized proximal point algorithm for the variational inequality problem in a Hilbert space Pontificia Universidade Catolica Rio de Janeiro, Brazil 1995 Technical Report MAT- 07/95 S1A.V J. on Optimization, accepted for publication
[4]	Censor Y. Iusem A. N. Zenios S. A. An interior point method with Bregman functions for the variational inequality problem with paramonotone operators Department of Public and Business Administration, University of Cyprus Nicosia, Cyprus 1994 Technical Report 94-03 Mathematical Programming. accepted for publication
[5]	Censor Y., Journal of Optimization Theory and Applications 73 (3) pp 451– (1992) · Zbl 0794.90058
[6]	Chen G., SIAM Journal on Optimization 3 (3) pp 538– (1993) · Zbl 0808.90103
[7]	Cottle R.W., The Linear Complementarity Problem (1992)
[8]	De Pierro A.R., Journal of Optimization Theory and Applications 51 pp 421– (1986) · Zbl 0581.90069
[9]	Dennis J.E., Numerical Methods for Unconstrained Optimization and Nonlinear Equations (1983) · Zbl 0579.65058
[10]	Eckstein J., Mathematics of Operations Research 18 pp 202– (1993) · Zbl 0807.47036
[11]	Eggermong P.B., Linear Algebra and its Applications 130 pp 25– (1990) · Zbl 0715.65037
[12]	Friedlander A., Journal of Global Optimization 6 pp 253– (1995) · Zbl 0835.90101
[13]	Iusem A. N., Acta Applicandae Mathematicae (1994)
[14]	Iusem A.N., Journal of Optimization Theory and Applications 85 pp 596– (1995) · Zbl 0831.90092
[15]	Lemarie B., International Series of Numerical Mathematics pp 73– (1989)
[16]	Mangasarian O.L., Nonlinear Programming (1969)
[17]	Polyak B.T., Introduction to Optimization (1987) · Zbl 0708.90083
[18]	Rockafellar R.T., SIAM Journal on Control and Optimization 14 (5) pp 877– (1976) · Zbl 0358.90053
[19]	Solodov M.V., SIAM Journal on Control and Optimization 34 (5) pp 1814– (1996) · Zbl 0866.49018