Maximum Penalty Function in Linear Programming

Fìz.-mat. model. ìnf. tehnol. 2021, 33:156-160

Abstract

A linear program can be equivalently reformulated as an unconstrained nonsmooth minimization problem, whose objective is the sum of the original objective and a penalty function with a sufficiently large penalty parameter. The article presents two methods for choosing this parameter. The first one applies to linear programs with usual linear inequality constraints. Then, we use a corresponding theorem by N.Z. Shor on the equivalence of a convex program to an unconstrained nonsmooth minimization problem. The second method is for linear programs of a special type. This means that all inequalities are of the form that a linear expression on the left-hand side is less or equal to a positive constant on the right-hand side. For this special type, we use a corresponding theorem of B.N. Pshenichny on establishing a penalty parameter for convex programs. For differently sized linear programs of the special type, we demonstrate that suitable penalty parameters can be computed by a procedure in GNU Octave based on GLPK software.

References

1. Eremin, I. I. (1967). Method of the penalties in convex programming. Doklady Academy Nauk USSR, 173(4), 748–751.
2. Polyakova, L. N. (2000). Nonsmooth Penalty Functions. IFAC Proceedings Volumes, 33(16), 287-291.
   DOI https://doi.org/10.1016/s1474-6670(17)39644-1
3. Shor, N. Z. (1985). Minimization methods for nondifferentiable functions. Springer-Verlag, Berlin.
4. Shor, N. Z. (1998). Nondifferentiable optimization and polynomial problems. Kluwer Academic Publishers, Dordrecht.
5. Pshenichnyi, B. N. (1983). The Linearization Method. Nauka, Moscow. (in Russian)
6. Eaton, J. W., Bateman, D., Hauberg, S. (2008). GNU Octave Manual Version 3. Network Theory Ltd.
7. Stetsyuk, P., Fischer, A. (2017). Shor's r-algorithms and octave-function ralgb5a. In: International Conference “Modern Informatics: Problems, Achievements and Prospects for Development”. V.M. Glushkov Institute of Cybernetics of the NAS of Ukraine, Kyiv, 143–146. (in Russian).