Vol. 25, no. 1, 2019
We continue the study of alternative duality formation schemes in linear programming based on the symmetric regularization of the Lagrange function simultaneously in the primal and dual variables. A feature of this work is the use of non-Euclidean stabilizing norms. Symmetric bounds for the error of the resulting solution are obtained for the new schemes. The properties of the method are investigated in the case where the constraint system of the original problem is inconsistent. For such problems (improper problems of the first kind), the method gives their generalized solution with an appropriate interpretation. For the improper case, we derive similar estimates for the deviation of the regularized solution from the generalized solution.
Keywords: linear programming, duality, regularization methods, accuracy of the solution
Received September 19, 2018
Revised December 21, 2018
Accepted December 24, 2018
Funding Agency: This work was supported by the Russian Science Foundation (project no. 14-11-00109).
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, 620002 Russia, e-mail: popld@imm.uran.ru
Cite this article as: L.D. Popov. On a regularization method for improper linear programs, Trudy Instituta Matematiki i Mekhaniki URO RAN, 2019, vol. 25, no. 1, pp. 196-206.
REFERENCES
1. Tikhonov A.N., Arsenin V.Ya. Methods for solutions of ill-posed problems. N Y: Wiley, 1981, 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.
2. Vasil’ev F.P. Metody optimizatsii [Optimization Methods]. Moscow: MTsNMO Publ., 2011, vol. 1: 620 p. ISBN: 978-5-94057-707-2 ; vol. 2: 433 p. ISBN: 978-5-94057-708-9 .
3. Rockafellar R.T. Augmented Lagrange multiplier functions and duality in nonconvex programming. SIAM J. Contr., 1974, vol. 12, no. 2, pp. 268–285. doi: 10.1137/0312021 .
4. Evtushenko Yu.G. Numerical optimization techniques. N Y: Springer-Verlag, 1985, 562 p. ISBN: 978-1-4612-9530-3 .
5. Gol’shtein E.G., Tret’yakov N.V. Modified Lagrangians and monotone maps in optimization. New York: Wiley. 1996, 438 p. ISBN: 0471548219 . Original Russian text published in Gol’shtein E.G., Tret’yakov N.V. Modifitsirovannye funktsii Lagranzha. Teoriya i metody optimizatsii. Moscow: Nauka Publ., 1989, 400 p.
6. Roos C., Terlaky T., Vial J.-Ph. Theory and algorithms for linear optimization: An interior point approach. N Y: Wiley, 1997, 454 p. ISBN: 0471956767 .
7. Eremin I.I. Dvojstvennost’ v linejnoj optimizacii (Duality theory in linear optimization). Ekaterinburg: UrO RAN Publ., 2001, 180 p. ISBN: 5-7691-1131-3 .
8. 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.
9. Eremin I.I. Theory of linear optimization. Inverse and ill-posed problems series. Utrecht; Boston; Koln; Tokyo: VSP, 2002, 248 p. ISBN: 906764353X .
10. Skarin V.D. On the optimal correction of inconsistent problems of convex programming. Tr. Inst. Mat. Mekh., 2013, vol. 19, no. 2, pp. 267–274. (in Russian)
11. Skarin V.D. Regularization of the min-max problems occurring in convex programming. Comput. Math. Math. Phys., 1977, vol. 17, no. 6, pp. 65–78. doi: 10.1016/0041-5553(77)90173-2
12. Skarin V.D. On method of regularization for infeasible problems of convex programming. Russian Math. (Iz. VUZ), 1995, vol. 39, no. 12, pp. 78–85.
13. Popov L.D. On Accuracy estimates for one regularization method in linear programming. In: A. Eremeev, M. Khachay, Y. Kochetov, P. Pardalos (eds.) Optimization Problems and Their Applications (OPTA 2018), Communications in Computer and Information Science, vol. 871, Cham, Springer, 2018, pp. 170–182. doi: 10.1007/978-3-319-93800-4_14
14. Guddat J. Stability in Convex Quadratic Programming. Mathematische Operationsforschung und Statistik, 1976, vol. 8, no. 2, pp. 223–245. doi: 10.1080/02331887608801291
15. Dorn W.S. Duality in quadratic programming. Quart. Appl. Math., 1960, vol. 18, no. 2, pp. 155–162. doi: 10.1090/qam/112751
16. Hoffman A.J. On approximate solutions of systems of linear inequalities. J. Res. Nat. Bur. Standards, 1952, vol. 49, no. 4, pp. 263–265. doi: 10.1142/9789812796936_0018
