Enhancing Lagrangian dual optimization for linear programs by obviating nondifferentiability

Simple item page
dc.contributorVirginia Techen
dc.contributor.authorSherali, Hanif D.en
dc.contributor.authorLim, C.en
dc.contributor.departmentIndustrial and Systems Engineeringen
dc.date.accessed2014-02-05en
dc.date.accessioned2014-03-05T14:00:24Zen
dc.date.available2014-03-05T14:00:24Zen
dc.date.issued2007en
dc.description.abstractWe consider non differentiable optimization problems that arise when solving Lagrangian duals of large-scale linear programs. Different from traditional subgradient-based approaches, we design two new methods that attempt to circumvent or obviate the nondifferentiability of the objective function, so that standard differentiable optimization techniques could be used. These methods, called the perturbation technique and the barrier-Lagrangian reformulation, are implemented as initialization procedures to provide a warm start to a theoretically convergent nondifferentiable optimization algorithm. Our computational study reveals that this two-phase strategy produces much better solutions with less computation in comparison with both the stand-alone nondifferentiable optimization procedure employed, and the popular Held-Wolfe-Crowder subgradient heuristic. Furthermore, the best version of this composite algorithm is shown to consume only about 3.19% of the CPU time required by the commercial linear programming solver CPLEX 8.1 (using the dual simplex option) to produce the same quality solutions. We also demonstrate that this initialization technique greatly facilitates quick convergence in the primal space when used as a warm start for ergodic-type primal recovery schemes.en
dc.description.sponsorshipNSF DMI-0094462en
dc.format.mimetypeapplication/pdfen
dc.identifier.citationSherali, Hanif D.; Lim, Churlzu. Enhancing Lagrangian dual optimization for linear programs by obviating nondifferentiability. INFORMS Journal on Computing 2007 19:1, 3-13. doi: 10.1287/ijoc.1050.0158en
dc.identifier.doihttps://doi.org/10.1287/ijoc.1050.0158en
dc.identifier.issn1091-9856en
dc.identifier.urihttp://hdl.handle.net/10919/25834en
dc.identifier.urlhttp://pubsonline.informs.org/doi/pdf/10.1287/ijoc.1050.0158en
dc.language.isoenen
dc.publisherINFORMSen
dc.rightsIn Copyrighten
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/en
dc.subjectNondifferentiable optimizationen
dc.subjectLagrangian relaxationen
dc.subjectLagrangian dualen
dc.subjectPerturbation techniqueen
dc.subjectBarrier-lagrangian reformulationen
dc.subjectVariable target valueen
dc.subjectPrimal solutionsen
dc.subjectSubgradienten
dc.subjectMinimizationen
dc.subjectConvergenceen
dc.subjectRelaxationsen
dc.subjectAlgorithmsen
dc.titleEnhancing Lagrangian dual optimization for linear programs by obviating nondifferentiabilityen
dc.title.serialInforms Journal on Computingen
dc.typeArticle - Refereeden
dc.type.dcmitypeTexten

Files

Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
ijoc%2E1050%2E0158.pdf
Size:
260.92 KB
Format:
Adobe Portable Document Format
Description:
Main article
Download

Collections

Scholarly Works, Industrial and Systems Engineering