Skip to main content
Log in

Nonlinear programming methods in the presence of noise

  • Published:
Mathematical Programming Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Similar content being viewed by others

References

  1. L.A. Rastrigin,Extremal control systems (Nauka, Moscow, 1974) [in Russian].

    Google Scholar 

  2. Ya.Z. Tsypkin,Adaptation and learning in automatic systems (Academic Press, New York, 1971).

    Google Scholar 

  3. M.B. Nevel'son and R.Z. Hasminskiy,Stochastic approximation and recurrent estimation (Nauka, Moscow, 1972) [in Russian].

    Google Scholar 

  4. 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).

  5. 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].

    Google Scholar 

  6. Yu. M. Ermol'ev, “On the stochastic gradient method and stochastic quasi-Fejerovskii sequences”,Kibernetika 2 (1969).

  7. Yu.M. Ermol'ev,Metody stokhasticheskogo programmirovaniia (Nauka, Moscow, 1976) [in Russian; Translated asStochastic programming methods].

    Google Scholar 

  8. H.J. Kushner, “Stochastic approximation algorithms for constrained optimization problems”,Annals of Statistics 2(4) 1974).

  9. 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).

  10. E. Polak,Computational methods in optimization. A unified approach (Academic Press, 1971).

  11. 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].

  12. K.J. Arrow, L. Hurwicz and H. Uzawa, eds.,Studies in linear and non-linear programming (Stanford University Press, Stanford, CA, 1958).

    Google Scholar 

  13. R. Courant, “Variational methods for the solution of problems of equilibrium and vibration”,Bulletin of the American Mathematical Society 49(1) (1943).

  14. M.R. Hestenes, “Multiplier and gradient methods”,Journal of Optimization Theory and Applications 4(5) (1969).

  15. M.J.D. Powell, “A method for nonlinear constraints in minimization problems”, in: R. Fletcher, ed.,Optimization (Academic Press, London, 1969).

    Google Scholar 

  16. 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).

  17. 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].

  18. 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].

  19. 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].

  20. 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].

    Google Scholar 

  21. 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).

  22. A.A. Goldstein, “Convex programming in Hilbert space”,Bulletin of the American Mathematical Society 70(5) (1964).

  23. 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].

  24. 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].

    Google Scholar 

  25. Yu.M. Ermol'ev, “Methods of solution of nonlinear extremal problems”,Kibernetika 4 (1966).

  26. 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.]

    Google Scholar 

  27. 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).

  28. N.Z. Shor, “Minimization of nondifferentiable functions”,Economics and Mathematical Methods (in Russian: Ekonomica i Matematičeskie Methody) 2 (1976).

  29. 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).

    Google Scholar 

  30. E.S. Levitin and B.T. Poljak, “Convergence of minimizing sequences in conditional extremum problems”,Doklady Akademii Nauk SSSR 168(5) (1966).

  31. A.B. Bakushinskiy and B.T. Poljak, “On a solution of variational inequalities”,Doklady Akademii Nauk SSSR 219(5) (1974).

  32. V.Ya. Katkovnik,Linear estimation and stochastic optimization problems (Nauka, Moscow 1976) [in Russian].

    Google Scholar 

  33. D.P. Bertsekas, “Multiplier methods: a survey”,Automatica 12(2) (1976).

  34. G.D. Maystrovsky, “On gradient methods for finding saddle points,”Ekonomika i Mathematicheski Metody, 12 (5) (1976).

Download references

Author information

Authors and Affiliations

Authors

Rights and permissions

Reprints 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

Download citation

  • Received:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF01588952

Key words

Navigation