Augmented Lagrangian algorithms for linear programming

We introduce new augmented Lagrangian algorithms for linear programming which provide faster global convergence rates than the augmented algorithm of Polyak and Treti'akov. Our algorithm shares the same properties as the Polyak-Treti'akov algorithm in that it terminates in finitely many iterations and obtains both primal and dual optimal solutions. We present an implementable version of the algorithm which requires only approximate minimization at each iteration. We provide a global convergence rate for this version of the algorithm and show that the primal and dual points generated by the algorithm converge to the primal and dual optimal set, respectively.     

A class of convergent primal-dual subgradient algorithms for decomposable convex programs

In this paper we develop a primal-dual subgradient algorithm for preferably decomposable, generally nondifferentiable, convex programming problems, under usual regularity conditions. The algorithm employs a Lagrangian dual function along with a suitable penalty function which satisfies a specified set of properties, in order to generate a sequence of primal and dual iterates for which some subsequence converges to a pair of primal-dual optimal solutions. Several classical types of penalty functions are shown to satisfy these specified properties. A geometric convergence rate is established for the algorithm under some additional assumptions. This approach has three principal advantages. Firstly, both primal and dual solutions are available which prove to be useful in several contexts. Secondly, the choice of step sizes, which plays an important role in subgradient optimization, is guided more determinably in this method via primal and dual information. Thirdly, typical subgradient algorithms suffer from the lack of an appropriate stopping criterion, and so the quality of the solution obtained after a finite number of steps is usually unknown. In contrast, by using the primal-dual gap, the proposed algorithm possesses a natural stopping criterion.     

Primal-dual proximal point algorithm for linearly constrained convex programming problems

A primal-dual version of the proximal point algorithm is developed for linearly constrained convex programming problems. The algorithm is an iterative method to find a saddle point of the Lagrangian of the problem. At each iteration of the algorithm, we compute an approximate saddle point of the Lagrangian function augmented by quadratic proximal terms of both primal and dual variables. Specifically, we first minimize the function with respect to the primal variables and then approximately maximize the resulting function of the dual variables. The merit of this approach exists in the fact that the latter function is differentiable and the maximization of this function is subject to no constraints. We discuss convergence properties of the algorithm and report some numerical results for network flow problems with separable quadratic costs.     

Comparison of bundle and classical column generation

When a column generation approach is applied to decomposable mixed integer programming problems, it is standard to formulate and solve the master problem as a linear program. Seen in the dual space, this results in the algorithm known in the nonlinear programming community as the cutting-plane algorithm of Kelley and Cheney-Goldstein. However, more stable methods with better theoretical convergence rates are known and have been used as alternatives to this standard. One of them is the bundle method; our aim is to illustrate its differences with Kelley’s method. In the process we review alternative stabilization techniques used in column generation, comparing them from both primal and dual points of view. Numerical comparisons are presented for five applications: cutting stock (which includes bin packing), vertex coloring, capacitated vehicle routing, multi-item lot sizing, and traveling salesman. We also give a sketchy comparison with the volume algorithm. This research has been supported by Inria New Investigation Grant “Convex Optimization and Dantzig-Wolfe Decomposition”.     

On embedding the volume algorithm in a variable target value method

We employ the volume algorithm as a subgradient deflection strategy in a variable target value method for solving nondifferentiable optimization problems. Focusing on Lagrangian duals for LPs, we exhibit primal nonconvergence of the original method, establish convergence of the proposed algorithm in the dual space, and present related computational results.     

Primal-dual row-action method for convex programming

We present a primal-dual row-action method for the minimization of a convex function subject to general convex constraints. Constraints are used one at a time, no changes are made in the constraint functions and their Jacobian matrix (thus, the row-action nature of the algorithm), and at each iteration a subproblem is solved consisting of minimization of the objective function subject to one or two linear equations. The algorithm generates two sequences: one of them, called primal, converges to the solution of the problem; the other one, called dual, approximates a vector of optimal KKT multipliers for the problem. We prove convergence of the primal sequence for general convex constraints. In the case of linear constraints, we prove that the primal sequence converges at least linearly and obtain as a consequence the convergence of the dual sequence.The research of the first author was partially supported by CNPq Grant No. 301280/86.     

A Trust Region Target Value Method for Optimizing Nondifferentiable Lagrangian Duals of Linear Programs

In this paper, we design a new variable target value procedure, the trust region target value (TRTV) method, for optimizing nondifferentiable Lagrangian dual formulations of large-scale, ill-conditioned linear programming problems. Such problems typically arise in the context of Lagrangian relaxation approaches and branch-and-bound/cut algorithms for solving linear mixed-integer programs. Subgradient optimization strategies are well-suited for this purpose and are popularly used, particularly in Lagrangian relaxation contexts, because of their simplicity in computation and mild memory requirements. However, they lack robustness and can often stall while yet remote from optimality. With this motivation, we design our proposed TRTV method to retain simplicity in computations, be theoretically convergent, as well as yield an effective and robust performance in practice. Furthermore, we augment this approach with dual refinement and primal recovery procedures based on outer-linearization and trust region strategies to further improve the accuracy of the resulting solutions and to derive primal solutions as well. Our computational study reveals a highly competitive performance of the proposed TRTV algorithm among several implemented nondifferentiable optimization procedures. Moreover, the dual refinement and primal recovery procedures help further reduce the optimality gap and promote attaining a relatively greater degree of primal feasibility as compared with several alternative ergodic primal recovery schemes. Also, the proposed method displays significantly lesser computational requirement than that of a commercial linear programming solver CPLEX.This research has been supported by the National Science Foundation under Grant Number DMI-0094462.     

Ergodic,primal convergence in dual subgradient schemes for convex programming,II: the case of inconsistent primal problems

Consider the utilization of a Lagrangian dual method which is convergent for consistent convex optimization problems. When it is used to solve an infeasible optimization problem, its inconsistency will then manifest itself through the divergence of the sequence of dual iterates. Will then the sequence of primal subproblem solutions still yield relevant information regarding the primal program? We answer this question in the affirmative for a convex program and an associated subgradient algorithm for its Lagrange dual. We show that the primal–dual pair of programs corresponding to an associated homogeneous dual function is in turn associated with a saddle-point problem, in which—in the inconsistent case—the primal part amounts to finding a solution in the primal space such that the Euclidean norm of the infeasibility in the relaxed constraints is minimized; the dual part amounts to identifying a feasible steepest ascent direction for the Lagrangian dual function. We present convergence results for a conditional \(\varepsilon \)-subgradient optimization algorithm applied to the Lagrangian dual problem, and the construction of an ergodic sequence of primal subproblem solutions; this composite algorithm yields convergence of the primal–dual sequence to the set of saddle-points of the associated homogeneous Lagrangian function; for linear programs, convergence to the subset in which the primal objective is at minimum is also achieved.     

求解带线性约束的凸优化的一类自适应不定线性化增广拉格朗日方法

增广拉格朗日方法是求解带线性约束的凸优化问题的有效算法.线性化增广拉格朗日方法通过线性化增广拉格朗日函数的二次罚项并加上一个临近正则项,使得子问题容易求解,其中正则项系数的恰当选取对算法的收敛性和收敛速度至关重要.较大的系数可保证算法收敛性,但容易导致小步长.较小的系数允许迭代步长增大,但容易导致算法不收敛.本文考虑求解带线性等式或不等式约束的凸优化问题.我们利用自适应技术设计了一类不定线性化增广拉格朗日方法,即利用当前迭代点的信息自适应选取合适的正则项系数,在保证收敛性的前提下尽量使得子问题步长选择范围更大,从而提高算法收敛速度.我们从理论上证明了算法的全局收敛性,并利用数值实验说明了算法的有效性.     

A trust region method for minimization of nonsmooth functions with linear constraints

We introduce a trust region algorithm for minimization of nonsmooth functions with linear constraints. At each iteration, the objective function is approximated by a model function that satisfies a set of assumptions stated recently by Qi and Sun in the context of unconstrained nonsmooth optimization. The trust region iteration begins with the resolution of an “easy problem”, as in recent works of Martínez and Santos and Friedlander, Martínez and Santos, for smooth constrained optimization. In practical implementations we use the infinity norm for defining the trust region, which fits well with the domain of the problem. We prove global convergence and report numerical experiments related to a parameter estimation problem. Supported by FAPESP (Grant 90/3724-6), FINEP and FAEP-UNICAMP. Supported by FAPESP (Grant 90/3724-6 and grant 93/1515-9).     

On the global optimality of generalized trust region subproblems

Quadratically constrained quadratic programming is an important class of optimization problems. We consider the case with one quadratic constraint. Since both the objective function and its constraint can be neither convex nor concave, it is also known as the ‘generalized trust region subproblem.’ The theory and algorithms for this problem have been well studied under the Slater condition. In this article, we analyse the duality property between the primal problem and its Lagrangian dual problem, and discuss the attainability of the optimal primal solution without the Slater condition. The relations between the Lagrangian dual and semidefinite programming dual is also given.     

The traveling salesman problem: A duality approach

In this study we formulate the dual of the traveling salesman problem, which extends in a natural way the dual problem of Held and Karp to the nonsymmetric case. The dual problem is solved by a subgradient optimization technique. A branch and bound scheme with stepped fathoming is then used to find optimal and suboptimal tours. Computational experience for the algorithm is presented.This author's work was partially supported by NSF Grant #GK-38337.     

一类Lagrangian对偶问题的零对偶间隙性质及其最优路径的收敛性

针对一般的非线性规划问题,利用某些Lagrange型函数给出了一类Lagrangian对偶问题的一般模型,并证明它与原问题之间存在零对偶间隙．针对具体的一类增广La- grangian对偶问题以及几类由非线性卷积函数构成的Lagrangian对偶问题,详细讨论了零对偶间隙的存在性．进一步,讨论了在最优路径存在的前提下,最优路径的收敛性质．     

Convergence and polynomiality of primal-dual interior-point algorithms for linear programming with selective addition of inequalities

This paper presents the convergence proof and complexity analysis of an interior-point framework that solves linear programming problems by dynamically selecting and adding relevant inequalities. First, we formulate a new primal–dual interior-point algorithm for solving linear programmes in non-standard form with equality and inequality constraints. The algorithm uses a primal–dual path-following predictor–corrector short-step interior-point method that starts with a reduced problem without any inequalities and selectively adds a given inequality only if it becomes active on the way to optimality. Second, we prove convergence of this algorithm to an optimal solution at which all inequalities are satisfied regardless of whether they have been added by the algorithm or not. We thus provide a theoretical foundation for similar schemes already used in practice. We also establish conditions under which the complexity of such algorithm is polynomial in the problem dimension and address remaining limitations without these conditions for possible further research.     

An Inexact Modified Subgradient Algorithm for Primal-Dual Problems via Augmented Lagrangians

We consider a primal optimization problem in a reflexive Banach space and a duality scheme via generalized augmented Lagrangians. For solving the dual problem (in a Hilbert space), we introduce and analyze a new parameterized Inexact Modified Subgradient (IMSg) algorithm. The IMSg generates a primal-dual sequence, and we focus on two simple new choices of the stepsize. We prove that every weak accumulation point of the primal sequence is a primal solution and the dual sequence converges weakly to a dual solution, as long as the dual optimal set is nonempty. Moreover, we establish primal convergence even when the dual optimal set is empty. Our second choice of the stepsize gives rise to a variant of IMSg which has finite termination.     

A primal dual modified subgradient algorithm with sharp Lagrangian

We apply a modified subgradient algorithm (MSG) for solving the dual of a nonlinear and nonconvex optimization problem. The dual scheme we consider uses the sharp augmented Lagrangian. A desirable feature of this method is primal convergence, which means that every accumulation point of a primal sequence (which is automatically generated during the process), is a primal solution. This feature is not true in general for available variants of MSG. We propose here two new variants of MSG which enjoy both primal and dual convergence, as long as the dual optimal set is nonempty. These variants have a very simple choice for the stepsizes. Moreover, we also establish primal convergence when the dual optimal set is empty. Finally, our second variant of MSG converges in a finite number of steps.     

An SQP algorithm for extended linear-quadratic problems in stochastic programming

Extended Linear-Quadratic Programming (ELQP) problems were introduced by Rockafellar and Wets for various models in stochastic programming and multistage optimization. Several numerical methods with linear convergence rates have been developed for solving fully quadratic ELQP problems, where the primal and dual coefficient matrices are positive definite. We present a two-stage sequential quadratic programming (SQP) method for solving ELQP problems arising in stochastic programming. The first stage algorithm realizes global convergence and the second stage algorithm realizes superlinear local convergence under a condition calledB-regularity.B-regularity is milder than the fully quadratic condition; the primal coefficient matrix need not be positive definite. Numerical tests are given to demonstrate the efficiency of the algorithm. Solution properties of the ELQP problem underB-regularity are also discussed.Supported by the Australian Research Council.     

A geometric framework for nonconvex optimization duality using augmented lagrangian functions

We provide a unifying geometric framework for the analysis of general classes of duality schemes and penalty methods for nonconvex constrained optimization problems. We present a separation result for nonconvex sets via general concave surfaces. We use this separation result to provide necessary and sufficient conditions for establishing strong duality between geometric primal and dual problems. Using the primal function of a constrained optimization problem, we apply our results both in the analysis of duality schemes constructed using augmented Lagrangian functions, and in establishing necessary and sufficient conditions for the convergence of penalty methods.     

Subgradient Methods for Saddle-Point Problems

We study subgradient methods for computing the saddle points of a convex-concave function. Our motivation comes from networking applications where dual and primal-dual subgradient methods have attracted much attention in the design of decentralized network protocols. We first present a subgradient algorithm for generating approximate saddle points and provide per-iteration convergence rate estimates on the constructed solutions. We then focus on Lagrangian duality, where we consider a convex primal optimization problem and its Lagrangian dual problem, and generate approximate primal-dual optimal solutions as approximate saddle points of the Lagrangian function. We present a variation of our subgradient method under the Slater constraint qualification and provide stronger estimates on the convergence rate of the generated primal sequences. In particular, we provide bounds on the amount of feasibility violation and on the primal objective function values at the approximate solutions. Our algorithm is particularly well-suited for problems where the subgradient of the dual function cannot be evaluated easily (equivalently, the minimum of the Lagrangian function at a dual solution cannot be computed efficiently), thus impeding the use of dual subgradient methods.     

Towards Strong Duality in Integer Programming

We consider in this paper the Lagrangian dual method for solving general integer programming. New properties of Lagrangian duality are derived by a means of perturbation analysis. In particular, a necessary and sufficient condition for a primal optimal solution to be generated by the Lagrangian relaxation is obtained. The solution properties of Lagrangian relaxation problem are studied systematically. To overcome the difficulties caused by duality gap between the primal problem and the dual problem, we introduce an equivalent reformulation for the primal problem via applying a pth power to the constraints. We prove that this reformulation possesses an asymptotic strong duality property. Primal feasibility and primal optimality of the Lagrangian relaxation problems can be achieved in this reformulation when the parameter p is larger than a threshold value, thus ensuring the existence of an optimal primal-dual pair. We further show that duality gap for this partial pth power reformulation is a strictly decreasing function of p in the case of a single constraint. Dedicated to Professor Alex Rubinov on the occasion of his 65th birthday. Research supported by the Research Grants Council of Hong Kong under Grant CUHK 4214/01E, and the National Natural Science Foundation of China under Grants 79970107 and 10571116.