Cybernetics And Systems Analysis logo
Editorial Board Announcements Abstracts Authors Archive
Cybernetics And Systems Analysis
International Theoretical Science Journal
Volume 55 >>> № 3 MAY — JUNE 2019
UDC 519.853
Yu.P. Laptin1, T.O. Bardadym2


1 V.M. Glushkov Institute of Cybernetics of the National Academy
of Sciences of Ukraine, Kyiv, Ukraine

 yu.p.laptin@gmail.com

2 V.M. Glushkov Institute of Cybernetics of the National Academy
of Sciences of Ukraine, Kyiv, Ukraine

 tbardadym@gmail.com

PROBLEMS RELATED TO ESTIMATION OF THE COEFFICIENTS OF EXACT PENALTY
FUNCTIONS

Abstract. New approaches to estimation of the coefficients of exact penalty functions for constrained optimization problems are considered. The results of computational experiments on the use of simplified coefficient estimation procedures for solving certain classes of problems are presented. Such approaches are most relevant when using the methods of decomposition in variables (generalized Benders decomposition). This allows us to overcome the issues related to implicit description of feasible region in the master problem.

Keywords: exact penalty functions, structured optimization problems, decomposition methods.



FULL TEXT

REFERENCES

  1. Zangwill W. Non-linear programming via penalty function. Manag. Sci. 1967. Vol. 13, N 5. P. 344–358.

  2. Eremin I.I. The method of "penalties" in convex programming. Dokl. AN SSSR. 1967. Vol. 173, No. 4. P. 748–751.

  3. Demyanov V.F. Extremum conditions and calculus of variations (in Russian). Moscow: Vyssh. shk., 2005. 335 p.

  4. Demyanov V.F., Di Pillo G., Facchinei F. Exact penalization via Dini and Hadamars conditional derivatives. Optim. Methods and Software. 1998. Vol. 9. P. 19–36.

  5. Yevtushenko Yu.G. Methods for solving extremal problems and their application in optimization systems (in Russian). Moscow: Nauka, 1982. 432 p.

  6. Evtushenko Yu.G., Zhadan V.G. Exact auxiliary functions in optimization problems. Zhurn. Vychisl. Mat. i Mat. Fiz. 1990. Vol. 30, No. 1. P. 43–57.

  7. Shor N.Z. Nondifferentiable optimization and polynomial problems. Amsterdam; Dordrecht; London: Kluwer Academic Publishers, 1998. 381 p.

  8. Shor N.Z., Zhurbenko N.G. The minimization method using space expansion in the direction of the difference of two successive gradients. Kibernetika. 1971. No. 3. P. 51–59.

  9. Pshenichnyj B.N. Linearization method (in Russian). Moscow: Nauka. 1983. 136 p.

  10. Danilin Yu.M. Linearization and penalty functions. Kibernetika i sistemnyj analiz. 2002. No. 5. P. 65–79.

  11. Bertsekas D. Conditional optimization and Lagrange multipliers (Russian translation). Moscow: Radio i svyaz', 1987. 399 p.

  12. Byrd R.H., Nocedal J., Waltz R. Steering exact penalty methods. Optim. Methods Softw. 2008. Vol. 23, N 2. P. 197–213.

  13. Byrd R.H., Lopez-Calva G., Nocedal J. A line search exact penalty method using steering rules. Math. Program., Series A and B. 2012. Vol. 133. P. 39–73.

  14. Benders J.F. Partitioning procedures for solving mixed variables programming problems. Numerische Mathematik. 1962. N 4. P. 238–252.

  15. Geoffrion, A.M. Generalized Benders decomposition. Journal of Optimization Theory and Applications. 1972. Vol. 10, Iss. 4. P. 237–260,

  16. Flippo O.E., Rinnoy Kan A.H.G. Decomposition in general mathematical programming. Mathematical Programming. 1993. Vol 60, Iss. 1–3. P. 361–382.

  17. Ruszczynski A. A regularized decomposition method for minimizing a sum of polyhedral functions. Mathematical Programming. 1986. Vol. 35, Iss. 3. P. 309–333.

  18. Grothey A., Leyffer S., Mckinnon K.I.M. A note on feasibility in Benders decomposition. Numerical Analysis Report NA/188, Department of Mathematics, University of Dundee. 2000.

  19. Fabian C., Szoke Z. Solving two-stage stochastic programming problems with level decomposition. Computational Management Science. 2007. Vol. 4, Iss. 4. P. 313–353.

  20. Zverovich V., Fїbiїn C., Ellison E., Mitra G. A computational study of a solver system for processing two-stage stochastic LPs with enhanced Benders decomposition. Mathematical Programming Computation. 2012. Vol. 4, Iss. 3. P. 211–238.

  21. Laptin Yu.P. Questions build accurate penalty functions. Vestn. S.-Peterb. un-ta. Ser. 10: Prikladnaya matematika. 2013. Iss. 4. P. 21–31.

  22. Laptin Yu.P. Exact penalty functions and convex continuations of functions in variable decomposition schemes. Kibernetika i sistemnyj analiz. 2016. Vol. 52, No. 1. P. 96–108.

  23. Nurminsky E.A. Projection on externally defined polyhedra. Zhurn. Vychisl. Mat. i Mat. Fiz. 2008. Vol. 48, No. 3. P. 387–396.

  24. Zhurbenko N. G. Polytopic design algorithm. Teoriya optymalʹnykh rishenʹ. 2008. No. 7. P. 125–131.

  25. Laptin Yu.P. ε-subgradients in the methods of decomposition in variables for some optimization problems. Teoriya optymalʹnykh rishenʹ. 2003. No. 2. P. 75–82.

  26. Laptin Yu.P., Zhurbenko N.G. Some problems of solving block nonlinear optimization problems with connecting variables. Kibernetika i sistemnyj analiz. 2006. No. 2. P. 47–55.

  27. Stetsyuk P.I. Program ralgb5 to minimize convex functions. Mat. ta prohr. zabezpechennya intelektualʹnykh system. 2016. P. 185–197.
Editorial Board Announcements Abstracts Authors Archive
about scope office editorial board instructions for authors subscriptions contacts
© 2019 Kibernetika.org. All rights reserved.