IDEAS home Printed from https://ideas.repec.org/a/wly/navres/v34y1987i3p399-416.html
   My bibliography  Save this article

Algorithmic insights and a convergence analysis for a Karmarkar‐type of algorithm for linear programming problems

Author

Listed:
  • Hanif D. Sherali

Abstract

This paper is concerned with a modification of a recently proposed variant of Karmarkar's algorithm for solving linear programming problems. In analyzing this variant, we exhibit interesting and useful relationships of these types of algorithms with barrier function methods, and subgradient optimization procedures involving space dilation techniques, which subsume the well‐known ellipsoidal type of algorithms. Convergence of this variant is established under certain regularity conditions. We also provide remarks on how to obtain dual variables or Lagrange multipliers at optimality.

Suggested Citation

  • Hanif D. Sherali, 1987. "Algorithmic insights and a convergence analysis for a Karmarkar‐type of algorithm for linear programming problems," Naval Research Logistics (NRL), John Wiley & Sons, vol. 34(3), pages 399-416, June.
    • Handle: RePEc:wly:navres:v:34:y:1987:i:3:p:399-416
    DOI: 10.1002/1520-6750(198706)34:33.0.CO;2-6
    as

    Download full text from publisher

    File URL: https://doi.org/10.1002/1520-6750(198706)34:33.0.CO;2-6
    Download Restriction: no
    File URL: https://libkey.io/10.1002/1520-6750(198706)34:33.0.CO;2-6?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Nickels, W. & Rodder, W. & Xu, L. & Zimmermann, H. -J., 1985. "Intelligent gradient search in linear programming," European Journal of Operational Research, Elsevier, vol. 22(3), pages 293-303, December.
    2. Bazaraa, Mokhtar S. & Sherali, Hanif D., 1981. "On the choice of step size in subgradient optimization," European Journal of Operational Research, Elsevier, vol. 7(4), pages 380-388, August.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Hanif D. Sherali & Bradley O. Skarpness & Buyong Kim, 1988. "An assumption‐free convergence analysis for a perturbation of the scaling algorithm for linear programs, with application to the L1 estimation problem," Naval Research Logistics (NRL), John Wiley & Sons, vol. 35(5), pages 473-492, October.
    2. K. O. Kortanek & Zhu Jishan, 1988. "New purification algorithms for linear programming," Naval Research Logistics (NRL), John Wiley & Sons, vol. 35(4), pages 571-583, August.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Nadjib Brahimi & Stéphane Dauzère-Pérès & Najib M. Najid, 2006. "Capacitated Multi-Item Lot-Sizing Problems with Time Windows," Operations Research, INFORMS, vol. 54(5), pages 951-967, October.
    2. Krzysztof C. Kiwiel & Torbjörn Larsson & P. O. Lindberg, 1999. "The Efficiency of Ballstep Subgradient Level Methods for Convex Optimization," Mathematics of Operations Research, INFORMS, vol. 24(1), pages 237-254, February.
    3. Liu, Fuh-Hwa Franklin & Huang, Chueng-Chiu & Yen, Yu-Lee, 2000. "Using DEA to obtain efficient solutions for multi-objective 0-1 linear programs," European Journal of Operational Research, Elsevier, vol. 126(1), pages 51-68, October.
    4. Tragantalerngsak, Suda & Holt, John & Ronnqvist, Mikael, 1997. "Lagrangian heuristics for the two-echelon, single-source, capacitated facility location problem," European Journal of Operational Research, Elsevier, vol. 102(3), pages 611-625, November.
    5. J. Bello Cruz & W. Oliveira, 2014. "Level bundle-like algorithms for convex optimization," Journal of Global Optimization, Springer, vol. 59(4), pages 787-809, August.
    6. Dirk Lorenz & Marc Pfetsch & Andreas Tillmann, 2014. "An infeasible-point subgradient method using adaptive approximate projections," Computational Optimization and Applications, Springer, vol. 57(2), pages 271-306, March.
    7. Kaj Holmberg & Di Yuan, 2000. "A Lagrangian Heuristic Based Branch-and-Bound Approach for the Capacitated Network Design Problem," Operations Research, INFORMS, vol. 48(3), pages 461-481, June.
    8. Gzara, Fatma & Erkut, Erhan, 2009. "A Lagrangian relaxation approach to large-scale flow interception problems," European Journal of Operational Research, Elsevier, vol. 198(2), pages 405-411, October.
    9. Fumero, Francesca & Vercellis, Carlo, 1997. "Integrating distribution, machine assignment and lot-sizing via Lagrangean relaxation," International Journal of Production Economics, Elsevier, vol. 49(1), pages 45-54, March.
    10. Lorena, Luiz Antonio N. & Goncalves Narciso, Marcelo, 2002. "Using logical surrogate information in Lagrangean relaxation: An application to symmetric traveling salesman problems," European Journal of Operational Research, Elsevier, vol. 138(3), pages 473-483, May.
    11. Helsgaun, Keld, 2000. "An effective implementation of the Lin-Kernighan traveling salesman heuristic," European Journal of Operational Research, Elsevier, vol. 126(1), pages 106-130, October.
    12. Bai, Yun & Ouyang, Yanfeng & Pang, Jong-Shi, 2016. "Enhanced models and improved solution for competitive biofuel supply chain design under land use constraints," European Journal of Operational Research, Elsevier, vol. 249(1), pages 281-297.

    More about this item

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:wly:navres:v:34:y:1987:i:3:p:399-416. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Wiley Content Delivery (email available below). General contact details of provider: https://doi.org/10.1002/(ISSN)1520-6750 .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.