Solving convex programs via Lagrangian decomposition
We consider general convex large-scale optimization problems with finite dimensional decision variables. Under usual assumptions concerning the structure of the constraint functions, the considered problems axe suitable for decomposition approaches. Lagrangian-dual problems axe formulated and solved by applying a well-known cutting-plane method of level-type. The proposed method is also capable to handle infinite function values. Therefore it is no longer necessary to assume that the feasible set with respect to the non-dualized constraints is bounded. The paper primarily deals with the description of an appropriate oracle. We first discuss the realization of the oracle under appropriate assumptions for generic convex problems. Afterwards we show that for convex quadratic programs the algorithm of the oracle is universally applicable.
convex programming cutting-plane methods level method decomposition methods nonsmooth programming