L.D. Popov. On a regularization method for improper linear programs ... P. 196-206

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