V. D. Skarin. On the construction of regularizing algorithms for the correction of improper convex programming problems ... P. 234-243.

We consider convex programming methods with a possibly inconsistent constraint system. Such problems constitute an important class of improper models of convex optimization and often arise in the mathematical modeling of real-life operations research statements. Since improper problems arise rather frequently, the theory and methods of their numerical approximation (correction) should be developed, which would allow to design objective procedures that resolve inconsistent constraints, turn an improper model into a family of feasible problems, and choose an optimal correction among them. In the present paper, an approximating problem is constructed by the variation of the right-hand sides of the constraints with respect to some vector norm. The type of the norm defines the form of a penalty function, and the minimization of the penalty function together with a stabilizing term is the core of each specific method of optimal correction of improper problems. The Euclidean norm implies the application of a quadratic penalty, whereas a piecewise linear (Chebyshev of octahedral) norm is concerned with the use of an exact penalty function. The proposed algorithms may also be interpreted as (Tikhonov) regularization methods for convex programming problems with inaccurate input information. Convergence conditions are formulated for the methods under consideration and convergence bounds are established.

Keywords: convex programming, improper problem, optimal correction, Tikhonov regularization method, penalty function methods.

The paper was received by the Editorial Office on June 1, 2017.

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


1.   Eremin I.I., Mazurov Vl.D., Astaf’ev N.N. Nesobstvennye zadachi linejnogo i vypuklogo programmirovaniya [Improper problems of linear and convex programming]. Moscow, Nauka Publ. 1983. 336 p.

2.   Vasil’ev F.P. Metody optimizatsii [Optimization methods]. Moscow, Factorial Press. 2002. 824 p.

3.   Skarin V.D. On the application of regularization method for correction of improper problems of convex programming. Proc. Steklov Inst. Math. 2013, vol. 283, suppl. 1, pp. 126–138.doi: 10.1134/S0081543813090137 .

4.   Antipin A.S. A regularization method for the problems of convex programming. Economic and Math. Methods. 1975, vol. 11, no. 2, pp. 336–342. (in Russian).

5.   Eremin I.I., Astaf’ev N.N. Vvedenie v teoriyu linejnogo i vypuklogo programmirovaniya [An introduction to the theory of linear and convex programming]. Moscow, Nauka Publ. 1976. 192 p.

6.   Skarin V.D. On a regularization method for inconsistent convex programming problems. Russian Math. (Izv. VUZ). 1995, vol. 39, no. 12, pp. 78–85.

7.   Eremin I.I. On the penalty method in mathematical programming. Dokl. Math. 1996. vol. 53, no. 1, pp. 138–140.

8.   Zukhovitskii S.I., Avdeeva L.I. Lineinoe i vypukloe programmirovanie [Linear and convex programming]. Moscow, Nauka Publ. 1967, 460 p.

9.   Skarin V.D. Barrier function method and correction algorithms for improper convex programming problems. Proc. Steklov Inst. Math. (Suppl.), 2008, vol. 263, suppl. 2, pp. S120–S134.
doi:10.1134/S0081543808060126 .