Numerical Comparison of Augmented Lagrangian Algorithms for Nonconvex Problems

Augmented Lagrangian algorithms are very popular tools for solving nonlinear programming problems. At each outer iteration of these methods a simpler optimization problem is solved, for which efficient algorithms can be used, especially when the problems are large. The most famous Augmented Lagrangian algorithm for minimization with inequality constraints is known as Powell-Hestenes-Rockafellar (PHR) method. The main drawback of PHR is that the objective function of the subproblems is not twice continuously differentiable. This is the main motivation for the introduction of many alternative Augmented Lagrangian methods. Most of them have interesting interpretations as proximal point methods for solving the dual problem, when the original nonlinear programming problem is convex. In this paper a numerical comparison between many of these methods is performed using all the suitable problems of the CUTE collection.This author was supported by ProNEx MCT/CNPq/FAPERJ 171.164/2003, FAPESP (Grants 2001/04597-4 and 2002/00094-0 and 2003/09169-6) and CNPq (Grant 302266/2002-0).This author was partially supported by CNPq-Brasil and CDCHT-Venezuela.This author was supported by ProNEx MCT/CNPq/FAPERJ 171.164/2003, FAPESP (Grant 2001/04597-4) and CNPq.     

Augmented Lagrangian methods under the constant positive linear dependence constraint qualification

Two Augmented Lagrangian algorithms for solving KKT systems are introduced. The algorithms differ in the way in which penalty parameters are updated. Possibly infeasible accumulation points are characterized. It is proved that feasible limit points that satisfy the Constant Positive Linear Dependence constraint qualification are KKT solutions. Boundedness of the penalty parameters is proved under suitable assumptions. Numerical experiments are presented. The authors were supported by PRONEX - CNPq / FAPERJ E-26 / 171.164/2003 - APQ1, FAPESP (Grants 2001/04597-4, 2002/00094-0, 2003/09169-6, 2002/00832-1 and 2005/56773-1) and CNPq.     

Neighborhood-following algorithms for linear programming

In this paper, we present neighborhood-following algorithms for linear programming. When the neighborhood is a wide neighborhood, our algorithms are wide neighborhood primal-dual interior point algorithms. If the neighborhood degenerates into the central path, our algorithms also degenerate into path-following algorithms. We prove that our algorithms maintain the O(n~(1/2)L)-iteration complexity still, while the classical wide neighborhood primal-dual interior point algorithms have only the O(nL)-iteration complexity. We also proved that the algorithms are quadratic convergence if the optimal vertex is nondegenerate. Finally, we show some computational results of our algorithms.     

Conical projection algorithms for linear programming

The Linear Programming Problem is manipulated to be stated as a Non-Linear Programming Problem in which Karmarkar's logarithmic potential function is minimized in the positive cone generated by the original feasible set. The resulting problem is then solved by a master algorithm that iteratively rescales the problem and calls an internal unconstrained non-linear programming algorithm. Several different procedures for the internal algorithm are proposed, giving priority either to the reduction of the potential function or of the actual cost. We show that Karmarkar's algorithm is equivalent to this method in the special case in which the internal algorithm is reduced to a single steepest descent iteration. All variants of the new algorithm have the same complexity as Karmarkar's method, but the amount of computation is reduced by the fact that only one projection matrix must be calculated for each call of the internal algorithm.Research partly sponsored by CNPq-Brazilian National Council for Scientific and Technological Development, by National Science Foundation grant ECS-857362, Office of Naval Research contract N00014-86-K-0295, and AFOSR grant 86-0116.On leave from COPPE-Federal University of Rio de Janeiro, Cx. Postal 68511, 21941 Rio de Janeiro, RJ, Brasil.     

A modified predictor-corrector method for linear programming

In the predictor-corrector method of Mizuno, Todd and Ye [1], the duality gap is reduced only at the predictor step and is kept unchanged during the corrector step. In this paper, we modify the corrector step so that the duality gap is reduced by a constant fraction, while the predictor step remains unchanged. It is shown that this modified predictor-corrector method retains the iteration complexity as well as the local quadratic convergence property.     

On a Modified Subgradient Algorithm for Dual Problems via Sharp Augmented Lagrangian*

We study convergence properties of a modified subgradient algorithm, applied to the dual problem defined by the sharp augmented Lagrangian. The primal problem we consider is nonconvex and nondifferentiable, with equality constraints. We obtain primal and dual convergence results, as well as a condition for existence of a dual solution. Using a practical selection of the step-size parameters, we demonstrate the algorithm and its advantages on test problems, including an integer programming and an optimal control problem. *Partially Supported by 2003 UniSA ITEE Small Research Grant Ero2. Supported by CAPES, Brazil, Grant No. 0664-02/2, during her visit to the School of Mathematics and Statistics, UniSA.     

A combined Lagrangian, linear programming, and implication heuristic for large-scale set partitioning problems

Given a finite ground set, a set of subsets, and costs on the subsets, the set partitioning problem is to find a minimum cost partition of the ground set. Many combinatorial optimization problems can be formulated as set partitioning problems. We present an approximation algorithm that produces high-quality solutions in an acceptable amount of computation time. The algorithm is iterative and combines problem size-reduction techniques, such as logical implications derived from feasibility and optimality conditions and reduced cost fixing, with a primal heuristic based on cost perturbations embedded in a Lagrangian dual framework, and cutting planes. Computational experiments illustrate the effectiveness of the approximation algorithm.     

A one-phase algorithm for semi-infinite linear programming

We present an algorithm for solving a large class of semi-infinite linear programming problems. This algorithm has several advantages: it handles feasibility and optimality together; it has very weak restrictions on the constraints; it allows cuts that are not near the most violated cut; and it solves the primal and the dual problems simultaneously. We prove the convergence of this algorithm in two steps. First, we show that the algorithm can find an-optimal solution after finitely many iterations. Then, we use this result to show that it can find an optimal solution in the limit. We also estimate how good an-optimal solution is compared to an optimal solution and give an upper bound on the total number of iterations needed for finding an-optimal solution under some assumptions. This algorithm is generalized to solve a class of nonlinear semi-infinite programming problems. Applications to convex programming are discussed.     

On the finite convergence of interior-point algorithms for linear programming

It has been shown [8] that numerous interior-point algorithms for linear programming (LP) generate solution sequences that converge to strict complementarity solutions, or interior solutions on the optimal face. In this note we further establish a theoretical base for Gay's test (Gay, 1989) to identify the optimal face, and develop a new termination procedure to obtain an exact solution on the optimal face. We also report some numerical results for solving a set of LP test problems, each of which has a highly degenerate and unbounded optimal face.Research supported in part by NSF Grant DDM-8922636, The Iowa Business School Summer Grant, and the Interdisciplinary Research Grant of the University of Iowa Center for Advanced Studies.     

Convergence behavior of decomposition algorithms for linear programs

This paper discusses plausible explanations of the somewhat folkloric, ‘tailing off’ convergence behavior of the Dantzig-Wolfe decomposition algorithm for linear programs. Is is argued that such beahvior may be used to numerical inaccuracy. Procedures to identify and mitigate such difficulties are outlined.     

非线性半定规划若干算法介绍

介绍近几年国际上求解非线性半定规划的若干有效新算法, 包括增广Lagrangian函数法、序列半定规划法、序列线性方程组法以及交替方向乘子法. 最后, 对非线性半定规划的算法研究前景进行了探讨.     

On convergence properties of a least-distance programming procedure for minimization problems under linear constraints

In Ref. 1, Bazaraa and Goode provided an algorithm for solving a nonlinear programming problem with linear constraints. In this paper, we show that this algorithm possesses good convergence properties.This paper was written under the guidance of Associate Professor C. Y. Wang. The author takes great pleasure in thanking him.     

Polynomial affine algorithms for linear programming

The method of steepest descent with scaling (affine scaling) applied to the potential functionq logcx — _i=1 ⁿ logx _i solves the linear programming problem in polynomial time forq n. Ifq = n, then the algorithm terminates in no more than O(n ² L) iterations; if q n + withq = O(n) then it takes no more than O(nL) iterations. A modified algorithm using rank-1 updates for matrix inversions achieves respectively O(n ⁴ L) and O(n ^3.5 L) arithmetic computions.     

Steepest-edge simplex algorithms for linear programming

We present several new steepest-edge simplex algorithms for solving linear programming problems, including variants of both the primal and the dual simplex method. These algorithms differ depending upon the space in which the problem is viewed as residing, and include variants in which this space varies dynamically. We present computational results comparing steepest-edge simplex algorithms and approximate versions of them against simplex algorithms that use standard pivoting rules on truly large-scale realworld linear programs with as many as tens of thousands of rows and columns. These results demonstrate unambiguously the superiority of steepest-edge pivot selection criteria to other pivot selection criteria in the simplex method.The research of this author was supported in part by NSF Grants DMS 85-12277, DMS 91-0619 and CDR 84-21402.     

On the convergence of inexact augmented Lagrangian methods for problems with convex constraints

We consider the augmented Lagrangian method (ALM) for constrained optimization problems in the presence of convex inequality and convex abstract constraints. We focus on the case where the Lagrangian sub-problems are solved up to approximate stationary points, with increasing accuracy. We analyze two different criteria of approximate stationarity for the sub-problems and we prove the global convergence to stationary points of ALM in both cases.     

A randomized scheme for speeding up algorithms for linear and convex programming problems with high constraints-to-variables ratio

We extend Clarkson's randomized algorithm for linear programming to a general scheme for solving convex optimization problems. The scheme can be used to speed up existing algorithms on problems which have many more constraints than variables. In particular, we give a randomized algorithm for solving convex quadratic and linear programs, which uses that scheme together with a variant of Karmarkar's interior point method. For problems withn constraints,d variables, and input lengthL, ifn = (d ²), the expected total number of major Karmarkar's iterations is O(d ²(logn)L), compared to the best known deterministic bound of O( L). We also present several other results which follow from the general scheme.     

A unified approach to the feasible point method type for nonlinear programming with linear constraints under degeneracy and the convergence properties

In this paper, we introduce a general class of feasible point algorithms for solving nonlinear programming problems with linear constraints under degeneracy. Many wellknown algorithms are its special cases. Also, many new algorithms can be derived from this general class. Under rather simple conditions, we prove the global convergence property for this class of algorithms.This research was partially supported by the National Natural Science Foundation of China. The first author's research was partially also supported by the National Science Foundation of the United States of America under Grant DCR-86-96135.     

Partial Lagrangian relaxation for general quadratic programming

We give a complete characterization of constant quadratic functions over an affine variety. This result is used to convexify the objective function of a general quadratic programming problem (Pb) which contains linear equality constraints. Thanks to this convexification, we show that one can express as a semidefinite program the dual of the partial Lagrangian relaxation of (Pb) where the linear constraints are not relaxed. We apply these results by comparing two semidefinite relaxations made from two sets of null quadratic functions over an affine variety.      

Approximate Augmented Lagrangian Functions and Nonlinear Semidefinite Programs

In this paper, an approximate augmented Lagrangian function for nonlinear semidefinite programs is introduced. Some basic properties of the approximate augmented Lagrange function such as monotonicity and convexity are discussed. Necessary and sufficient conditions for approximate strong duality results are derived. Conditions for an approximate exact penalty representation in the framework of augmented Lagrangian are given. Under certain conditions, it is shown that any limit point of a sequence of stationary points of approximate augmented Lagrangian problems is a KKT point of the original semidefinite program and that a sequence of optimal solutions to augmented Lagrangian problems converges to a solution of the original semidefinite program.     

A cutting-plane algorithm with linear and geometric rates of convergence

This paper presents a cutting-plane algorithm for nonlinear programming which, under suitable conditions, exhibits a linear or geometric global rate of convergence. Other known rates of convergence for cutting-plane algorithms are no better than arithmetic for problems not satisfying a Haar condition. The feature responsible for this improved rate of convergence is the addition at each iteration of a new cut for each constraint, rather than adding only one new cut corresponding to the most violated constraint as is typically the case. Certain cuts can be dropped at each iteration, and there is a uniform upper bound on the number of old cuts retained. Geometric convergence is maintained if the subproblems at each iteration are approximated, rather than solved exactly, so the algorithm is implementable. The algorithm is flexible with respect to the point used to generate new cuts.The author is grateful to W. Oettli for bringing to his attention the linearly convergent cutting-plane algorithm of Ref. 15 and to the referee for a comment that stimulated an extension of the convergence rate results from an earlier version where _k depended on certain parameters of the problem.