Abstract
We consider convex programming problems 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 the minimum of 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 or 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.
Similar content being viewed by others
References
I. I. Eremin, Vl. D. Mazurov, and N. N. Astaf’ev, Improper Problems of Linear and Convex Programming (Nauka, Moscow, 1983) [in Russian].
F. P. Vasil’ev, Optimization Methods (Faktorial, Moscow, 2002) [in Russian].
V. D. Skarin, “On the application of the regularization method for the correction of improper problems of convex programming,” Proc. Steklov Inst. Math. 283 (Suppl. 1), S126–S138 (2013).
A. S. Antipin, “The regularization method in convex programming problems,” Ekonom. Mat. Metody 11 (2), 336–342 (1975) [in Russian].
I. I. Eremin and N. N. Astaf’ev, Introduction to the Theory of Linear and Convex Programming (Nauka, Moscow, 1976) [in Russian].
V. D. Skarin, “On a regularization method for inconsistent convex programming problems,” Russ. Math. (Iz. VUZ) 39 (12), 78–85 (1995).
I. I. Eremin, “On the penalty method in mathematical programming,” Dokl. Math. 53 (1), 138–140 (1996).
S. I. Zukhovitskii and L. I. Avdeeva, Linear and Convex Programming (Nauka, Moscow, 1967) [in Russian].
V. D. Skarin, “Barrier function method and correction algorithms for improper convex programming problems,” Proc. Steklov Inst. Math. 263 (Suppl. 2), S120–S134 (2008).
Author information
Authors and Affiliations
Corresponding author
Additional information
Original Russian Text © V.D. Skarin, 2017, published in Trudy Instituta Matematiki i Mekhaniki UrO RAN, 2017, Vol. 23, No. 3, pp. 234–243.
Rights and permissions
About this article
Cite this article
Skarin, V.D. On the Construction of Regularizing Algorithms for the Correction of Improper Convex Programming Problems. Proc. Steklov Inst. Math. 303 (Suppl 1), 203–212 (2018). https://doi.org/10.1134/S0081543818090213
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1134/S0081543818090213