Abstract
The problem of minimizing a nonlinear function with nonlinear constraints when the values of the objective, the constraints and their gradients have errors, is studied. This noise may be due to the stochastic nature of the problem or to numerical error.
Various previously proposed methods are reviewed. Generally, the minimization algorithms involve methods of subgradient optimization, with the constraints introduced through penalty, Lagrange, or extended Lagrange functions. Probabilistic convergence theorems are obtained. Finally, an algorithm to solve the general convex (nondifferentiable) programming problem with noise is proposed.
Similar content being viewed by others
References
L.A. Rastrigin,Extremal control systems (Nauka, Moscow, 1974) [in Russian].
Ya.Z. Tsypkin,Adaptation and learning in automatic systems (Academic Press, New York, 1971).
M.B. Nevel'son and R.Z. Hasminskiy,Stochastic approximation and recurrent estimation (Nauka, Moscow, 1972) [in Russian].
V. Fabian, “Stochastic approximation of constrained minima”, in:Transactions of the 4th Prague conference on information theory, statistical decision functions and random processes, 1965 (Prague, 1967).
Yu.M. Ermol'ev and Z.V. Nekrylova, “The method of stochastic subgradients and its application”, Notes, Seminar on the theory of optimal solutions, Academy of Sciences U.S.S.R., Kiev (1967) [in Russian].
Yu. M. Ermol'ev, “On the stochastic gradient method and stochastic quasi-Fejerovskii sequences”,Kibernetika 2 (1969).
Yu.M. Ermol'ev,Metody stokhasticheskogo programmirovaniia (Nauka, Moscow, 1976) [in Russian; Translated asStochastic programming methods].
H.J. Kushner, “Stochastic approximation algorithms for constrained optimization problems”,Annals of Statistics 2(4) 1974).
H.J. Kushner and T. Gavin, “Stochastic approximation type methods for constrained systems: algorithms and numerical results”,IEEE Transactions on Automatic Control 19(4) 1974).
E. Polak,Computational methods in optimization. A unified approach (Academic Press, 1971).
B.T. Poljak, “Convergence of feasible directions methods in extremal problems”,U.S.S.R. Computational Mathematics and Mathematical Physics 11(4) (1971) [in Russian: Žurnal Vyčisletel'noi Matematiki i Matematičeskoi].
K.J. Arrow, L. Hurwicz and H. Uzawa, eds.,Studies in linear and non-linear programming (Stanford University Press, Stanford, CA, 1958).
R. Courant, “Variational methods for the solution of problems of equilibrium and vibration”,Bulletin of the American Mathematical Society 49(1) (1943).
M.R. Hestenes, “Multiplier and gradient methods”,Journal of Optimization Theory and Applications 4(5) (1969).
M.J.D. Powell, “A method for nonlinear constraints in minimization problems”, in: R. Fletcher, ed.,Optimization (Academic Press, London, 1969).
P.C. Haarhoff and J.D. Buys, “A new method of optimization of a nonlinear function subject to nonlinear constraints”,Computer Journal 13(2) (1970).
B.T. Poljak, “Iterative methods using Lagrange multipliers for solving extremal problems with equality constraints”,U.S.S.R. Computational Mathematics and Mathematical Physics 10(5) (1970) [in Russian: Žurnal Vyčisletel'noi Mathematiki i Matematičeskoi].
B.T. Poljak, “On the rate of convergence of penalty function methods”,U.S.S.R. Computational Mathematics and Mathematical Physics 11(1) (1971) [in Russian: Žurnal Vyčisletel'noi Matematiki i Matematičeskoi].
B.T. Poljak, N.V. Tretjakov, “Method of penalty prices for conditional extremal problems”,U.S.S.R. Computational Mathematics and Mathematical Physics 13(1) (1973) [in Russian: Žurnal Vyčisletel'noi Matematiki i Matematičeskoi].
V.Z. Belen'kiy, A.V. Volkonskiy, S.A. Ivankov, A.B. Pomanskiy and A.D. Shapiro,Iterative methods in theory of games and programming (Nauka, Moscow, 1974) [in Russian].
B.T. Poljak, “Convergence and rate of convergence of iterative stochastic algorithms, I, General case”,Automation and Remote Control 12 (1976) [in Russian:Avtomatika i Telemekhanika).
A.A. Goldstein, “Convex programming in Hilbert space”,Bulletin of the American Mathematical Society 70(5) (1964).
E.S. Levitin and B.T. Poljak, “Minimization methods under constraints”,U.S.S.R. Computational Mathematics and Mathematical Physics 6(5) (1966) [in Russian: Žurnal Vyčisletel'noi Matematiki i Matematičeskoi].
N.Z. Shor, “Application of the gradient method for the solution of network transportation problems”, Notes, Scientific seminar on theory and application of cybernetics and operations research, Academy of Sciences U.S.S.R., Kiev (1962) [in Russian].
Yu.M. Ermol'ev, “Methods of solution of nonlinear extremal problems”,Kibernetika 4 (1966).
B.T. Poljak, “A general method for solving extremal problems”,Doklady Akademii Nauk SSSR 174(1) (1967). [Translation:Soviet Mathematics Doklady 8 (1967) 593–597.]
B.T. Poljak, “Minimization of unsmooth functionals”,U.S.S.R. Computational Mathematics and Mathematical Physics [in Russian: Žurnal Vyčislitel'noi Matematiki i Matematičeskoi) 9(3) (1969).
N.Z. Shor, “Minimization of nondifferentiable functions”,Economics and Mathematical Methods (in Russian: Ekonomica i Matematičeskie Methody) 2 (1976).
N.Z. Shor and P.R. Gamburd, “Some problems concerning the convergence of the generalized gradient method”, Notes, Seminar on the theory of optimal solutions, Academy of Sciences U.S.S.R., Kiev (1969) andKibernetika 6 (1971).
E.S. Levitin and B.T. Poljak, “Convergence of minimizing sequences in conditional extremum problems”,Doklady Akademii Nauk SSSR 168(5) (1966).
A.B. Bakushinskiy and B.T. Poljak, “On a solution of variational inequalities”,Doklady Akademii Nauk SSSR 219(5) (1974).
V.Ya. Katkovnik,Linear estimation and stochastic optimization problems (Nauka, Moscow 1976) [in Russian].
D.P. Bertsekas, “Multiplier methods: a survey”,Automatica 12(2) (1976).
G.D. Maystrovsky, “On gradient methods for finding saddle points,”Ekonomika i Mathematicheski Metody, 12 (5) (1976).
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Poljak, B.T. Nonlinear programming methods in the presence of noise. Mathematical Programming 14, 87–97 (1978). https://doi.org/10.1007/BF01588952
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF01588952