Epsilon-subgradient optimization techniques in convex programming and Lagrangian duality (Q1079495)

The paper studies two algorithms for approximately solving convex programs when function values can be computed only approximately, but an \(\epsilon\)-subgradient is available. Such type of problems arise for instance if integer programming problems are handled by formulating Lagrangian dual problems. The second section gives a review about integer programming problems, in which \(\epsilon\)-optimal solutions of relaxed Lagrangian dual problems were be applied successfully in heuristic methods. The third and fourth section contain the theoretical basis of the algorithms to determine Lagrangian \(\epsilon\)-subgradients. In the first algorithm an inexact solution of a relaxed Lagrangian dual problem has to be determined, whereas the second algorithm applies cutting planes.