L.D. Popov. On one method of increasing the smoothness of external penalty functions in linear and convex programming ... P. 88-101

We propose original constructions of external penalty functions in linear and convex programming, which asymptotically reduce constrained optimization problems to unconstrained ones with increased smoothness. The latter admit an effective solution by second-order methods and, at the same time, do not require the knowledge of an interior feasible point of the original problem to start the process. Moreover, the proposed approach is applicable to improper linear and convex programs (problems with contradictory constraint systems), for which they can generate some generalized (compromise) solutions. Convergence theorems and the data of numerical experiments are presented.

Keywords: linear programming, improper (ill-posed) problems, generalized solutions, penalty functions, Newton method

Received May 19, 2021

Revised July 20, 2021

Accepted July 26, 2021

Funding Agency: This study is a part of the research carried out at the Ural Mathematical Center and supported by the Ministry of Science and Higher Education of the Russian Federation (agreement no. 075-02-2021-1383).

Leonid Denisovich Popov, Dr. Phys.-Math. Sci., Krasovskii Institute of Mathematics and Mechanics of the Ural Branch of the Russian Academy of Sciences, Yekaterinburg, 620108 Russia; Ural Federal University, Yekaterinburg, 620000 Russia, e-mail: popld@imm.uran.ru

REFERENCES

1.   Eremin I. The “penalty” method in convex programming. Soviet Math. Dokl., 1967, vol. 8, pp. 459–462.

2.   Fiacco A., McCormick G. Nonlinear programming: Sequential unconstrained minimization techniques. New York: Wiley, 1968, 210 p. doi: 10.1137/1.9781611971316 . Translated to Russian under the title Nelineinoe programmirovanie: Metody posledovatel’noi bezuslovnoi minimizatsii, Moscow: Mir Publ., 1972, 240 p.

3.   Zangwill W.I. Nonlinear programming: A unified approach. Englewood Cliffs: Prentice-Hall, 1969, 356 p. ISBN: 0136235794 . Translated to Russian under the title Nelineinoe programmirovanie: Edinyi podkhod, Moscow: Sov. Radio Publ., 1973, 312 p.

4.   Polak E. Computational methods in optimization: A unified approach. NY: Acad. Press, 1971, 329 p. ISBN: 008096091X . Translated to Russian under the title Chislennye metody optimizatsii, Moscow: Mir Publ., 1974, 376 p.

5.   Moiseev N.N., Ivanilov Yu.P., Stolyarova E.M. Metody optimizatsii [Optimization methods]. Moscow: Nauka Publ., 1978, 351 p. ISBN: 978-5-9500751-2-4 .

6.   Evtushenko Yu.G. Numerical optimization techniques. NY: Springer-Verlag, 1985, 562 p. ISBN: 978-1-4612-9530-3 . Original Russian text published in Evtushenko Yu.G. Metody resheniya ekstremal’nykh zadach i ikh primenenie v sistemakh optimizatsii, Moscow: Nauka Publ., 1982, 432 p.

7.   Gill P., Murray W., Wright M. Practical optimization. London: Acad. Press, 1982, 401 p. ISBN: 0122839528 . Translated to Russian under the title Prakticheskaya optimizatsiya, Moscow: Mir Publ., 1985, 509 p.

8.   Vasil’ev F.P. Chislennye metody resheniya ekstremal’nykh zadach [Numerical methods for solving extremal problems]. Moscow: Nauka Publ., 1988, 552 p. ISBN: 5-02-013796-0 .

9.   Roos C., Terlaky T., Vial J.-Ph. Theory and algorithms for linear optimization. Chichester: John Wiley & Sons Ltd, 1997, 484 p. ISBN: 0471956767 .

10.   Eremin I.I. Duality for improper problems of linear and convex programming. Sov. Math. Dokl., 1981, vol. 23, pp. 62–66.

11.   Eremin I.I., Mazurov V.D., and Astaf’ev N.N. Nesobstvennye zadachi lineinogo i vypuklogo programmirovaniya [Improper problems of linear and convex programming]. Moscow: Nauka Publ., 1983, 336 p.

12.   Kochikov I.V., Matvienko A.N., Yagola A.G. The generalized residual principle for the solution of inconsistent equations. U.S.S.R. Comput. Math. Math. Phys., 1984, vol. 24, no. 4, pp. 78–80. doi: 10.1016/0041-5553(84)90233-7 

13.   Popov L.D. Combined penalties and generalized solutions for improper problems of linear and convex programming of the first kind. Trudy Inst. Mat. i Mekh. UrO RAN, 2010, vol. 16, no. 3, pp. 217–226 (in Russian).

14.   Popov L.D. Search of generalized solutions to improper linear and convex programming problems using barrier functions. The Bulletin of Irkutsk State University. Series Mathematics, 2011, vol. 4, no. 2, pp. 134–146 (in Russian).

15.   Popov L.D. Use of barrier functions for optimal correction of improper problems of linear programming of the 1st kind. Autom. Remote Control, 2012, vol. 73, no. 3, pp. 417–424. doi: 10.1134/S0005117912030010 

Cite this article as: L.D. Popov. On one method of increasing the smoothness of external penalty functions in linear and convex programming, Trudy Instituta Matematiki i Mekhaniki UrO RAN, 2021, vol. 27, no. 4, pp. 88–101.