We consider convex programming problems for which it is unknown in advance whether their constraints are consistent. For the numerical analysis of these problems, we propose to apply a multistep symmetric regularization of the classical Lagrange function with respect to both primal and dual variables and then to solve the arising minimax problems with a small parameter. The latter problems are always solvable and give either normal decisions of the original problems in the case of their propriety or, in the improper case, generalized solutions that minimize the discrepancies of the constraints and optimize the value of the objective function asymptotically with respect to the parameter. Minimax problems can also form a basis for the construction of new duality diagrams in convex programming, at least for improper settings. Regularization diagrams are provided, a primal minimax setting is written, theorems on the convergence and numerical stability of the method are proved, and an informal interpretation of the generalized solutions is given. The study develops the authors’ earlier results obtained for linear programming problems.
Keywords: convex programming, duality, generalized solutions, regularization method, penalty function method.
The paper was received by the Editorial Office on March 25, 2017.
Leonid Denisovich Popov, Dr. Phys.-Math. Sci., Krasovskii Institute of Mathematics and Mechanics, Ural Branch of the Russian Academy of Sciences, Yekaterinburg, 620990 Russia; Ural Federal University, Yekaterinburg, 620002 Russia, e-mail: popld@imm.uran.ru
Vladimir Dmitrievich Skarin, Dr. Phys.-Math. Sci., Krasovskii Institute of Mathematics and Mechanics, Ural Branch of the Russian Academy of Sciences, Yekaterinburg, 620990 Russia; Ural Federal University, Yekaterinburg, 620002 Russia, e-mail: skavd@imm.uran.ru
REFERENCES
1. Eremin I.I., Mazurov Vl.D., Astaf’ev N.N. Nesobstvennye zadachi linejnogo i vypuklogo programmirovanija [Improper problems of linear and convex programming]. Moscow, Nauka Publ., 1983, 336 p.
2. Vatolin A.A. Mnozhestva razreshimosti i korrektsiya sedlovykh funktsii i sistem neravenstv [Solvability sets and correction of saddle functions and inequality systems]. Preprint, Inst. Mat. Mech. Ural BranchAcad. Sci. USSR, Sverdlovsk, 1989, 90 p.
3. Popov L.D. Linear correction of ill-posed convex-concave minimax problems on a maximin criterion. Comput. Math. Math. Phys., 1986, vol. 26, no. 5, pp. 30–39. doi: 10.1016/0041-5553(86)90037-6 .
4. Skarin V.D. An approach to the analysis of improper problems of linear programming. U.S.S.R. Comput. Math. Math. Phys., 1986, vol. 26, no. 2, pp. 73–79. doi: 10.1016/0041-5553(86)90011-X .
5. McCormick S.T. How to compute least infeasible flows. Math. Programming, 1997, vol. 78, no. 2, pp. 179–194. doi: 10.1007/BF02614370 .
6. Vada J., Slupphaug O., Johansen T.A. Optimal prioritized infeasibility handling in model predictive control: parametric preemptive multiobjective linear programming approach. J. Optim. Theory Appl.,2001, vol. 109, no. 2, pp. 385–413. doi: 10.1023/A:1017570507125 .
7. Leon T., Liern V., Vercher E. Viability of infeasible portfolio selection problems: a fuzzy approach. European J. Oper. Res., 2002, vol. 139, no. 1, pp. 178–189. doi: 10.1016/S0377-2217(01)00175-8 .
8. Tikhonov A.N., Arsenin V.Ya. Metody resheniya nekorrektnykh zadach [Methods for the solution of ill-posed problems]. Moscow, Nauka Publ., 1979, 285 p.
9. Vasil’ev F.P. Metody resheniya ehkstremal’nykh zadach. Zadachi minimizatsii v funktsional’nykh prostranstvakh, regulyarizatsiya, approksimatsiya. Uchebnoe posobie [Methods for solving extremalproblems. Minimization problems in function spaces, regularization, approximation. Textbook.] Moscow, Nauka Publ., 1981, 400 p.
10. Eremin I.I. Problems of successive programming. Siberian Math. J., 1973, vol. 14, no. 1, pp. 36–43. doi: 10.1007/BF00967264 .
11. Fedorov V.V. Chislennye metody maksimina [Numerical methods of maximin]. Moscow, Nauka Publ., 1979, 280 p.
12. Gol’shtein E.G. Teoriya dvoistvennosti v matematicheskom programmirovanii i ee prilozheniya [Duality theory in mathematical programming and its applications]. Moscow, Nauka Publ., 1971, 352 p.
13. Popov L.D., Skarin V.D. On alternative duality and lexicographic correction of right-hand-side vector in improper linear programs of the 1st kind. Proc. V Internat. Conf. on Optimization Methods andApplications (OPTIMA-2014) (Petrovac, Montenegro, September 28 – October 4, 2014), Moscow, 2014, pp. 152–153.
