A primal-dual conjugate subgradient algorithm for specially structured linear and convex programming problems

DOI10.1007/BF01447654zbMath0675.90069MaRDI QIDQ1122488

Hanif D. Sherali, Osman Ulular

Publication date: 1989

Published in: Applied Mathematics and Optimization (Search for Journal in Brave)

zbMATH Keywords

Lagrangian dual functionprimal penalty functionprimal-dual conjugate subgradient algorithm

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Convex programming (90C25)

Related Items (23)

A localization and reformulation discrete programming approach for the rectilinear distance location-allocation problem ⋮ Unrelated machine scheduling with time-window and machine downtime constraints: An application to a naval battle-group problem ⋮ Approximations in proximal bundle methods and decomposition of convex programs ⋮ The two-machine flowshop total completion time problem: branch-and-bound algorithms based on network-flow formulation ⋮ Convergence and computational analyses for some variable target value and subgradient deflection methods ⋮ A trust region target value method for optimizing nondifferentiable Lagrangian duals of linear programs ⋮ An exact algorithm for the single-machine total weighted tardiness problem with sequence-dependent setup times ⋮ A reformulation-convexification approach for solving nonconvex quadratic programming problems ⋮ Exact makespan minimization of unrelated parallel machines ⋮ Dynamic Lagrangian dual and reduced RLT constructs for solving \(0-1\) mixed-integer programs ⋮ The prize collecting Steiner tree problem: models and Lagrangian dual optimization approaches ⋮ An enhanced response surface methodology (RSM) algorithm using gradient deflection and second-order search strategies. ⋮ A Lagrangian relaxation approach to an electricity system investment model with a high temporal resolution ⋮ A dynamic-programming-based exact algorithm for general single-machine scheduling with machine idle time ⋮ A variable target value method for nondifferentiable optimization ⋮ Lagrangian relaxation based algorithm for trigeneration planning with storages ⋮ Higher-level RLT or disjunctive cuts based on a partial enumeration strategy for 0-1 mixed-integer programs ⋮ On embedding the volume algorithm in a variable target value method. ⋮ On using exterior penalty approaches for solving linear programming problems ⋮ A Lagrangian relaxation approach to large-scale flow interception problems ⋮ Enumeration approach for linear complementarity problems based on a reformulation-linearization technique ⋮ Recovery of primal solutions when using subgradient optimization methods to solve Lagrangian duals of linear programs ⋮ An exact algorithm for the precedence-constrained single-machine scheduling problem

Uses Software

• RELAX4

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A Lagrangean relaxation heuristic for vehicle routing
• Conjugate gradient methods using quasi-Newton updates with inexact line searches
• Dual formulations and subgradient optimization strategies for linear programming relaxations of mixed-integer programs
• A penalty linear programming method using reduced-gradient basis-exchange techniques
• On the choice of step size in subgradient optimization
• Multiplier methods: A survey
• The multiplier method of Hestenes and Powell applied to convex programming
• An aggregate subgradient method for nonsmooth convex minimization
• Modelling with integer variables
• Decomposition Principle for Linear Programs
• The Cutting-Plane Method for Solving Convex Programs
• A descent algorithm for nonsmooth convex optimization
• Experimental Results on the New Techniques for Integer Programming Formulations
• A class of convergent primal-dual subgradient algorithms for decomposable convex programs
• A Tight Linearization and an Algorithm for Zero-One Quadratic Programming Problems
• Relaxation Methods for Linear Programs
• The Lagrangian Relaxation Method for Solving Integer Programming Problems
• The simplex SON algorithm for LP/embedded network problems
• Linear Programming via a Nondifferentiable Penalty Function
• The Set-Covering Problem: A New Implicit Enumeration Algorithm
• Cross decomposition for mixed integer programming
• A dual approach to solving nonlinear programming problems by unconstrained optimization
• Validation of subgradient optimization
• Some Algorithms for Minimizing a Function of Several Variables
• Minimization of unsmooth functionals
• The Relaxation Method for Linear Inequalities
• The Relaxation Method for Linear Inequalities

This page was built for publication: A primal-dual conjugate subgradient algorithm for specially structured linear and convex programming problems