Decomposition and Nondifferentiable Optimization with the Projective Algorithm

J. L. Goffin, A. Haurie and J. P. Vial
Additional contact information
J. L. Goffin: GERAD, Faculty of Management, McGill University, Montreal, Quebec, Canada H3A 1G5
A. Haurie: GERAD, Ecole des Hautes Etudes Commerciales de Montreal, Montreal, Quebec, Canada and Departement d'Economie Commerciale et Industrielle, Université de Genève, Geneva, Switzerland
J. P. Vial: Departement d'Economie Commerciale et Industrielle, Université de Genève, Geneva, Switzerland

Management Science, 1992, vol. 38, issue 2, 284-302

Abstract: This paper deals with an application of a variant of Karmarkar's projective algorithm for linear programming to the solution of a generic nondifferentiable minimization problem. This problem is closely related to the Dantzig-Wolfe decomposition technique used in large-scale convex programming. The proposed method is based on a column generation technique defining a sequence of primal linear programming maximization problems. Associated with each problem one defines a weighted potential function which is minimized using a variant of the projective algorithm. When a point close to the minimum of the potential function is reached, a corresponding point in the dual space is constructed, which is close to the analytic center of a polytope containing the solution set of the nondifferentiable optimization problem. An admissible cut of the polytope, corresponding to a new supporting hyperplane of the epigraph of the function to minimize, is then generated at this approximate analytic center. In the primal space this new cut translates into a new column for the associated linear programming problem. The algorithm has performed well on a set of convex nondifferentiable programming problems.

Keywords: projective algorithm; interior point method; cutting plane; decomposition; nondifferentiable optimization (search for similar items in EconPapers)
Date: 1992
References: Add references at CitEc
Citations: View citations in EconPapers (38)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.38.2.284 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormnsc:v:38:y:1992:i:2:p:284-302

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().