An augmented Lagrangian method for binary quadratic programming based on a class of continuous functions

In this paper, an augmented Lagrangian method is proposed for binary quadratic programming (BQP) problems based on a class of continuous functions. The binary constraints are converted into a class of continuous functions. The approach reformulates the BQP problem as an equivalent augmented Lagrangian function, and then seeks its minimizer via an augmented Lagrangian method, in which the subproblem is solved by Barzilai–Borwein type method. Numerical results are reported for max-cut problem. The results indicate that the augmented Lagrangian approach is promising for large scale binary quadratic programming by the quality of the near optimal values and the low computational time.     

The augmented Lagrangian method for a type of inverse quadratic programming problems over second-order cones

The focus of this paper is on studying an inverse second-order cone quadratic programming problem, in which the parameters in the objective function need to be adjusted as little as possible so that a known feasible solution becomes the optimal one. We formulate this problem as a minimization problem with cone constraints, and its dual, which has fewer variables than the original one, is a semismoothly differentiable (SC ¹) convex programming problem with both a linear inequality constraint and a linear second-order cone constraint. We demonstrate the global convergence of the augmented Lagrangian method with an exact solution to the subproblem and prove that the convergence rate of primal iterates, generated by the augmented Lagrangian method, is proportional to 1/r, and the rate of multiplier iterates is proportional to $1/\sqrt{r}$ , where r is the penalty parameter in the augmented Lagrangian. Furthermore, a semismooth Newton method with Armijo line search is constructed to solve the subproblems in the augmented Lagrangian approach. Finally, numerical results are reported to show the effectiveness of the augmented Lagrangian method with both an exact solution and an inexact solution to the subproblem for solving the inverse second-order cone quadratic programming problem.     

An accelerated augmented Lagrangian method for linearly constrained convex programming with the rate of convergence O(1/k~2)

In this paper, we propose and analyze an accelerated augmented Lagrangian method(denoted by AALM) for solving the linearly constrained convex programming. We show that the convergence rate of AALM is O(1/k~2) while the convergence rate of the classical augmented Lagrangian method(ALM) is O(1/k). Numerical experiments on the linearly constrained l_1-l_2minimization problem are presented to demonstrate the effectiveness of AALM.     

Computing exact solution to nonlinear integer programming: Convergent Lagrangian and objective level cut method

In this paper, we propose a convergent Lagrangian and objective level cut method for computing exact solution to two classes of nonlinear integer programming problems: separable nonlinear integer programming and polynomial zero-one programming. The method exposes an optimal solution to the convex hull of a revised perturbation function by successively reshaping or re-confining the perturbation function. The objective level cut is used to eliminate the duality gap and thus to guarantee the convergence of the Lagrangian method on a revised domain. Computational results are reported for a variety of nonlinear integer programming problems and demonstrate that the proposed method is promising in solving medium-size nonlinear integer programming problems.     

A primal majorized semismooth Newton-CG augmented Lagrangian method for large-scale linearly constrained convex programming

In this paper, we propose a primal majorized semismooth Newton-CG augmented Lagrangian method for large-scale linearly constrained convex programming problems, especially for some difficult problems. The basic idea of this method is to apply the majorized semismooth Newton-CG augmented Lagrangian method to the primal convex problem. And we take two special nonlinear semidefinite programming problems as examples to illustrate the algorithm. Furthermore, we establish the global convergence and the iteration complexity of the algorithm. Numerical experiments demonstrate that our method works very well for the testing problems, especially for many ill-conditioned ones.     

An Augmented Lagrangian Method for a Class of Inverse Quadratic Programming Problems

We consider an inverse quadratic programming (QP) problem in which the parameters in the objective function of a given QP problem are adjusted as little as possible so that a known feasible solution becomes the optimal one. We formulate this problem as a minimization problem with a positive semidefinite cone constraint and its dual is a linearly constrained semismoothly differentiable (SC¹) convex programming problem with fewer variables than the original one. We demonstrate the global convergence of the augmented Lagrangian method for the dual problem and prove that the convergence rate of primal iterates, generated by the augmented Lagrange method, is proportional to 1/r, and the rate of multiplier iterates is proportional to  $1/\sqrt{r}$ , where r is the penalty parameter in the augmented Lagrangian. As the objective function of the dual problem is a SC¹ function involving the projection operator onto the cone of symmetrically semi-definite matrices, the analysis requires extensive tools such as the singular value decomposition of matrices, an implicit function theorem for semismooth functions, and properties of the projection operator in the symmetric-matrix space. Furthermore, the semismooth Newton method with Armijo line search is applied to solve the subproblems in the augmented Lagrange approach, which is proven to have global convergence and local quadratic rate. Finally numerical results, implemented by the augmented Lagrangian method, are reported.     

Augmented Lagrangian Objective Penalty Function

Augmented Lagrangian function is one of the most important tools used in solving some constrained optimization problems. In this article, we study an augmented Lagrangian objective penalty function and a modified augmented Lagrangian objective penalty function for inequality constrained optimization problems. First, we prove the dual properties of the augmented Lagrangian objective penalty function, which are at least as good as the traditional Lagrangian function's. Under some conditions, the saddle point of the augmented Lagrangian objective penalty function satisfies the first-order Karush-Kuhn-Tucker condition. This is especially so when the Karush-Kuhn-Tucker condition holds for convex programming of its saddle point existence. Second, we prove the dual properties of the modified augmented Lagrangian objective penalty function. For a global optimal solution, when the exactness of the modified augmented Lagrangian objective penalty function holds, its saddle point exists. The sufficient and necessary stability conditions used to determine whether the modified augmented Lagrangian objective penalty function is exact for a global solution is proved. Based on the modified augmented Lagrangian objective penalty function, an algorithm is developed to find a global solution to an inequality constrained optimization problem, and its global convergence is also proved under some conditions. Furthermore, the sufficient and necessary calmness condition on the exactness of the modified augmented Lagrangian objective penalty function is proved for a local solution. An algorithm is presented in finding a local solution, with its convergence proved under some conditions.     

一类新的Lagrangian乘子法

本文提出了求解光滑不等式约束最优化问题新的乘子法,在增广Lagrangian函数中,使用了新的NCP函数的乘子法．该方法在增广Lagrangian函数和原问题之间存在很好的等价性;同时该方法具有全局收敛性,且在适当假设下,具有超线性收敛率．本文给出了一个有效选择参数C的方法．     

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

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

Some Results about Duality and Exact Penalization

In this paper, we introduce the concept of the valley at 0 augmenting function and apply it to construct a class of valley at 0 augmented Lagrangian functions. We establish the existence of a path of optimal solutions generated by valley at 0 augmented Lagrangian problems and its convergence toward the optimal set of the original problem and obtain the zero duality gap property between the primal problem and the valley at 0 augmented Lagrangian dual problem. Moreover, we establish the exact penalization representation results in the framework of valley at 0 augmented Lagrangian.     

无限多类别网络均衡问题中的收费计算

对于一个多类别的网络均衡问题,可以通过计算某个辅助问题的容量限制约束相应的乘子向量得到有效收费.本文通过计算拉格朗日函数的鞍点来计算乘子向量.借助于广义拉格朗日函数的稳定性和Uzawa算法非精确解的收敛性,得到鞍点序列的收敛性.其中离散化方法用于最小化广义拉格朗日函数的计算.     

Nonlinear separation approach for the augmented Lagrangian in nonlinear semidefinite programming

This paper aims at showing that the class of augmented Lagrangian functions for nonlinear semidefinite programming problems can be derived, as a particular case, from a nonlinear separation scheme in the image space associated with the given problem. By means of the image space analysis, a global saddle point condition for the augmented Lagrangian function is investigated. It is shown that the existence of a saddle point is equivalent to a regular nonlinear separation of two suitable subsets of the image space. Without requiring the strict complementarity, it is proved that, under second order sufficiency conditions, the augmented Lagrangian function admits a local saddle point. The existence of global saddle points is then obtained under additional assumptions that do not require the compactness of the feasible set. Motivated by the result on global saddle points, we propose two modified primal-dual methods based on the augmented Lagrangian using different strategies and prove their convergence to a global solution and the optimal value of the original problem without requiring the boundedness condition of the multiplier sequence.     

A Globally Convergent Lagrangian Barrier Algorithm for Optimization with General Inequality Constraints and Simple Bounds

We consider the global and local convergence properties of a class of Lagrangian barrier methods for solving nonlinear programming problems. In such methods, simple bound constraints may be treated separately from more general constraints. The objective and general constraint functions are combined in a Lagrangian barrier function. A sequence of such functions are approximately minimized within the domain defined by the simple bounds. Global convergence of the sequence of generated iterates to a first-order stationary point for the original problem is established. Furthermore, possible numerical difficulties associated with barrier function methods are avoided as it is shown that a potentially troublesome penalty parameter is bounded away from zero. This paper is a companion to previous work of ours on augmented Lagrangian methods.

     

A Continuation Algorithm for Max-Cut Problem

A continuation algorithm for the solution of max-cut problems is proposed in this paper. Unlike the available semi-definite relaxation, a max-cut problem is converted into a continuous nonlinear programming by employing NCP functions, and the resulting nonlinear programming problem is then solved by using the augmented Lagrange penalty function method. The convergence property of the proposed algorithm is studied. Numerical experiments and comparisons with the Geomeans and Williamson randomized algorithm made on some max-cut test problems show that the algorithm generates satisfactory solutions for all the test problems with much less computation costs.     

带有不等式约束的非线性规划问题的一个精确增广Lagrange函数

对求解带有不等式约束的非线性非凸规划问题的一个精确增广Lagrange函数进行了研究．在适当的假设下,给出了原约束问题的局部极小点与增广Lagrange函数,在原问题变量空间上的无约束局部极小点之间的对应关系．进一步地,在对全局解的一定假设下,还提供了原约束问题的全局最优解与增广Lagrange函数,在原问题变量空间的一个紧子集上的全局最优解之间的一些对应关系．因此,从理论上讲,采用该文给出的增广Lagrange函数作为辅助函数的乘子法,可以求得不等式约束非线性规划问题的最优解和对应的Lagrange乘子．     

Augmented lagrangian nonlinear programming algorithm that uses SQP and trust region techniques

An augmented Lagrangian nonlinear programming algorithm has been developed. Its goals are to achieve robust global convergence and fast local convergence. Several unique strategies help the algorithm achieve these dual goals. The algorithm consists of three nested loops. The outer loop estimates the Kuhn-Tucker multipliers at a rapid linear rate of convergence. The middle loop minimizes the augmented Lagrangian functions for fixed multipliers. This loop uses the sequential quadratic programming technique with a box trust region stepsize restriction. The inner loop solves a single quadratic program. Slack variables and a constrained form of the fixed-multiplier middleloop problem work together with curved line searches in the inner-loop problem to allow large penalty wieghts for rapid outer-loop convergence. The inner-loop quadratic programs include quadratic onstraint terms, which complicate the inner loop, but speed the middle-loop progress when the constraint curvature is large.The new algorithm compares favorably with a commercial sequential quadratic programming algorithm on five low-order test problems. Its convergence is more robust, and its speed is not much slower.This research was supported in part by the National Aeronautics and Space Administration under Grant No. NAG-1-1009.     

基于增广Lagrange函数的RQP方法

Recursive quadratic programming is a family of techniques developd by Bartholomew-Biggs and other authors for solving nonlinear programming problems.This paperdescribes a new method for constrained optimization which obtains its search di-rections from a quadratic programming subproblem based on the well-known aug-mented Lagrangian function.It avoids the penalty parameter to tend to infinity.We employ the Fletcher‘s exact penalty function as a merit function and the use of an approximate directional derivative of the function that avoids the need toevaluate the second order derivatives of the problem functions.We prove that thealgorithm possesses global and superlinear convergence properties.At the sametime, numerical results are reported.     

Erratum to: An abstract model for branching and its application to mixed integer programming

Stabilized sequential quadratic programming (sSQP) methods for nonlinear optimization generate a sequence of iterates with fast local convergence regardless of whether or not the active-constraint gradients are linearly dependent. This paper concerns the local convergence analysis of an sSQP method that uses a line search with a primal-dual augmented Lagrangian merit function to enforce global convergence. The method is provably well-defined and is based on solving a strictly convex quadratic programming subproblem at each iteration. It is shown that the method has superlinear local convergence under assumptions that are no stronger than those required by conventional stabilized SQP methods. The fast local convergence is obtained by allowing a small relaxation of the optimality conditions for the quadratic programming subproblem in the neighborhood of a solution. In the limit, the line search selects the unit step length, which implies that the method does not suffer from the Maratos effect. The analysis indicates that the method has the same strong first- and second-order global convergence properties that have been established for augmented Lagrangian methods, yet is able to transition seamlessly to sSQP with fast local convergence in the neighborhood of a solution. Numerical results on some degenerate problems are reported.     

Zero-one integer programs with few constraints —Lower bounding theory

The zero-one integer programming problem and its special case, the multiconstraint knapsack problem frequently appear as subproblems in many combinatorial optimization problems. We present several methods for computing lower bounds on the optimal solution of the zero-one integer programming problem. They include Lagrangean, surrogate and composite relaxations. New heuristic procedures are suggested for determining good surrogate multipliers. Based on theoretical results and extensive computational testing, it is shown that for zero-one integer problems with few constraints surrogate relaxation is a viable alternative to the commonly used Lagrangean and linear programming relaxations. These results are used in a follow up paper to develop an efficient branch and bound algorithm for solving zero-one integer programming problems.     

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.