Epsilon-subgradient optimization techniques in convex programming and Lagrangian duality (Q1079495)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Epsilon-subgradient optimization techniques in convex programming and Lagrangian duality |
scientific article |
Statements
Epsilon-subgradient optimization techniques in convex programming and Lagrangian duality (English)
0 references
1986
0 references
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.
0 references
approximately solving convex programs
0 references
\(\epsilon \) -subgradient
0 references
relaxed Lagrangian dual
0 references
heuristic
0 references
cutting planes
0 references