The paper considers the problem of constructing approximations for a wide class of improper convex programs (ICPs). The original problem with an inconsistent system of constraints is immersed in a parametric family of feasible convex programming models, where the norm of the discrepancy of the constraint functions serves as a parameter. The minimum value of the parameter at which the feasible set of the problem becomes nonempty determines an optimal correction of the ICP. To solve the correction problem, one of the classical methods of regularization of ill-posed extremal problems is used — the method of stabilizing functions (Tikhonov’s method). In this case, the original problem with constraints is initially reduced to the problem of unconstrained minimization of a certain penalty function. Instead of conventional external penalty functions, the paper uses the method of internal (barrier) functions. The design features of barrier functions can provide certain advantages in the numerical implementation of the correction method. Conditions for the solvability of problems arising at various stages of the proposed correction method are formulated, and the issues of matching the process parameters that ensure the required convergence are studied. The capabilities of the method when working with perturbed data are analyzed.
Keywords: convex programming, improper problem, optimal correction, Tikhonov regularization method, barrier function methods
Received July 8, 2024
Revised August 5, 2024
Accepted August 12, 2024
Vladimir Dmitrievich Skarin, Dr. Phys.-Math. Sci., Krasovskii Institute of Mathematics and Mechanics of the Ural Branch of the Russian Academy of Sciences, Yekaterinburg, 620108 Russia, e-mail: skavd@imm.uran.ru
REFERENCES
1. Eremin I.I. Duality for improper problems of linear and convex programming. Sov. Math., Dokl., 1981, vol. 23, pp. 62–66.
2. Eremin I.I., Mazurov V.D., Astaf’ev N.N. Nesobstvennye zadachi lineinogo i vypuklogo programmirovaniya [Improper problems of linear and convex programming]. Moscow, Nauka Publ., 1983, 336 p.
3. Eremin I.I. Protivorechivye modeli optimal’nogo planirovaniya [Contradictory models of optimal planning]. Moscow, Nauka Publ., 1988, 160 p. ISBN: 5-02-013773-1 .
4. Kochikov I.V., Matvienko A.N., Yagola A.G. The generalized residual principle for the solution of inconsistent equations. USSR Comput. Math. Math. Phys., 1984, vol. 24, no. 4, pp. 78–80. doi: 10.1016/0041-5553(84)90233-7
5. Parametricheskaya optimizatsiya i metody approksimatsii nesobstvennykh zadach matematicheskogo programmirovaniya [Sb. st.] [Parametric optimization and methods of apiroximation of improper problems of mathematical programming. Sb. Art.], USSR Academy of Sciences, Ural. Sci. Center; [Ans. ed. I. I. Eremin, L. D. Popov], Sverdlovsk, UC USSR Academy of Sciences, 1985, 135 p.
6. Skarin V.D. An approach to the analysis of improper linear programming problems. USSR Comput. Math. Math. Phys., 1986, vol. 26, no. 2, pp. 73–79. doi: 10.1016/0041-5553(86)90011-X
7. 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
8. Volkov V.V., Erokhin V.I., Krasnikov A.S., Razumov A.V., Khvostov M.N. Minimum-Euclidean-norm matrix correction for a pair of dual linear programming problems. Comput. Math. Math. Phys., 2017, vol. 57, no. 11, pp. 1757–1770. doi: 10.1134/S0965542517110148
9. Artem’eva L.A., Vasil’ev F.P., Potapov M.M. Extragradient method for correction of inconsistent linear programming problems. Comput. Math. Math. Phys., 2018, vol. 58, no. 12, pp. 1919–1925. doi: 10.1134/S0965542518120163
10. Dax A. The smallest correction of an inconsistent system of linear inequalities. Optimization and Engineering, 2001, vol. 2, pp. 349–359. doi: 10.1023/A:1015370617219
11. Renaut R.A., Guo N. Efficient algorithms for solution of regularized total least squares. SIAM J. Matrix Anal. Appl., 2005, vol. 26, no. 2, pp. 457–476. doi: 10.1137/S0895479802419889
12. Mazurov V.D. Metod komitetov v zadachakh optimizatsii i klassifikatsii [Committee method in optimization and classification problems]. Moscow, Nauka Publ., 1990, 245 p. ISBN: 5-02-013976-9 .
13. Khachai M.Yu. On an estimate for the number of members in the minimal committee of a system of linear inequalities. Comput. Math. Math. Phys., 1997, vol. 37, no. 11, pp. 1356–1361.
14. Tikhonov A.N., Arsenin V.Ya. Methods for solutions of ill-posed problems. Transl. from the 2nd Russian ed., NY, Wiley, 1977, 258 p. ISBN: 0470991240 . Original Russian text published in Tikhonov A.N., Arsenin V.Ya. Metody resheniya nekorrektnykh zadach, Moscow, Nauka Publ., 1979, 285 p.
15. Vasil’ev F.P. Metody optimizatsii [Optimization methods]. Moscow, MCNMO Publ., 2011, vol. 1, 620 p., ISBN: 978-5-94057-707-2; vol. 2, 433 p. ISBN: 978-5-94057-708-9 .
16. Golub G.N., Hansen P.C., O’Leary D.P. Tikhonov regularization and total least squares. SIAM J. Matrix Anal. Appl., 1999, vol. 21, no. 1, pp. 185–194. doi: 10.1137/s0895479897326432
17. Skarin V.D. On some universal methods of correction of the improper convex programming problems. Automat. Remote Control, 2012, vol. 73, no. 2, pp. 300–309. doi: 10.1134/S0005117912020087
18. Fiacco A.V., McCormick G.P. Nonlinear programming: sequential unconstrained minimization techniques. Classics in applied mathematics, vol. 4. Philadelphia, SIAM, 1987, 226 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.
19. Eremin I.I., Astaf’ev N.N. Vvedenie v teoriyu lineinogo i vypuklogo programmirovaniya [Introduction to the theory of linear and convex programming]. Moscow, Nauka Publ., 1976, 196 p.
20. 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.
21. Skarin V.D. Barrier function method and correction algorithms for improper convex programming problems. Proc. Steklov Inst. Math., 2008, vol. 263, no. 2, pp. S120–S134. doi: 10.1134/S0081543808060126
22. Popov L.D. Search for generalized solutions of improper problems of linear and convex programming using barrier functions. Iz. Irkutsk State Univ. Ser. Math., 2011, vol. 4, no. 2, pp. 134–146 (in Russian).
23. Elster K.-H., Reinhardt R., Schaulle M., Donath У. Einführung in die nichtlineare optimierung. Leipzig, 1977. Translated to Russian under the title Vvedeniye v nelineynoye programmirovaniye, Moscow, Nauka Publ., 1985, 264 p.
Cite this article as: V.D. Skarin. The method of quasi-solutions based on barrier functions in the analysis of improper convex programming problems. Trudy Instituta Matematiki i Mekhaniki URO RAN, 2024, vol. 30, no. 4, pp. 234–250.
