Geodesic
On a regularization method for improper linear programs
Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 25 (2019) no. 1, pp. 196-206 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

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. 
@article{TIMM_2019_25_1_a14,
     author = {L. D. Popov},
     title = {On a regularization method for improper linear programs},
     journal = {Trudy Instituta matematiki i mehaniki},
     pages = {196--206},
     year = {2019},
     volume = {25},
     number = {1},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/TIMM_2019_25_1_a14/}
}
TY  - JOUR
AU  - L. D. Popov
TI  - On a regularization method for improper linear programs
JO  - Trudy Instituta matematiki i mehaniki
PY  - 2019
SP  - 196
EP  - 206
VL  - 25
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/TIMM_2019_25_1_a14/
LA  - ru
ID  - TIMM_2019_25_1_a14
ER  - 
%0 Journal Article
%A L. D. Popov
%T On a regularization method for improper linear programs
%J Trudy Instituta matematiki i mehaniki
%D 2019
%P 196-206
%V 25
%N 1
%U http://geodesic.mathdoc.fr/item/TIMM_2019_25_1_a14/
%G ru
%F TIMM_2019_25_1_a14
L. D. Popov. On a regularization method for improper linear programs. Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 25 (2019) no. 1, pp. 196-206. http://geodesic.mathdoc.fr/item/TIMM_2019_25_1_a14/

[1] Tikhonov A. N., Arsenin V. Ya., Metody resheniya nekorrektnykh zadach, Nauka, M., 1979, 285 pp.

[2] Vasilev F. P., Metody optimizatsii, v 2 kn., v. 1, MTsNMO, Moskva, 2011, 620 pp.; v. 2, 433 pp.

[3] Rockafellar R. T., “Augmented lagrange multiplier functions and duality in nonconvex programming”, SIAM J. Contr., 12:2 (1974), 268–285 | DOI | MR | Zbl

[4] Evtushenko Ju., Numerical optimization technique. Optimization Software, Inc. Publ. Division, N Y, 1985, 562 pp. | MR

[5] Golshtein E.G., Tretyakov N.V., Modifitsirovannye funktsii Lagranzha. Teoriya i metody optimizatsii, Nauka. Glavnaya redaktsiya fiz.-mat. literatury, Moskva, 1989, 400 pp.

[6] Roos C., Terlaky T., Theory and algorithms for linear optimization: An interior point approach, Wiley, N Y, 1997, 454 pp. | MR | Zbl

[7] Eremin I. I., Dvoistvennost v lineinoi optimizatsii, Izd-vo UrO RAN, Ekaterinburg, 2001, 180 pp.

[8] Eremin I.I., Mazurov Vl.D., Astafev N.N., Nesobstvennye zadachi lineinogo i vypuklogo programmirovaniya, Nauka, M., 1983, 336 pp.

[9] Eremin I. I., Theory of linear optimization. Inverse and ill-posed problems series, VSP, Utrecht; Boston; Koln; Tokyo, 2002, 248 pp. | MR

[10] Skarin V. D., “Ob optimalnoi korrektsii protivorechivykh zadach vypuklogo programmirovaniya”, Tr. In-ta matematiki i mekhaniki UrO RAN, 19:2 (2013), 267–274 | MR

[11] Skarin V. D., “Regularization of the min-max problems occurring in convex programming”, Comput. Math. Math. Physics, 17:6 (1977), 65–78 | DOI | MR

[12] Skarin V. D., “O metode regulyarizatsii dlya protivorechivykh zadach vypuklogo programmirovaniya”, Izv. vuzov. Matematika, 1995, no. 12, 81–88 | MR | Zbl

[13] Popov L. D., “On Accuracy estimates for one regularization method in linear programming”, Optimization Problems and Their Applications (OPTA 2018), Communications Comp. Inform. Sci., 871, eds. eds. A. Eremeev, M. Khachay, Y. Kochetov, P. Pardalos, Springer, Cham, 2018, 170–182 | DOI

[14] Guddat J., “Stability in convex quadratic programming”, Mathematische Operationsforschung und Statistik, 8:2 (1976), 223–245 | DOI | MR

[15] Dorn W. S., “Duality in quadratic programming”, Quart. Appl. Math., 18:2 (1960), 407–413 | DOI | MR

[16] Hoffman A. J., “On approximate solutions of systems of linear inequalities”, J. Res. Nat. Bur. Standards, 49:4 (1952), 263–265 | DOI | MR