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.     

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.     

"准"精确惩罚函数法的渐近性分析

1引言众所周知,罚函数法在最优化理论与数值计算中占据着极其重要的位置,作为求解约束优化问题的一类重要方法,在上世纪五、六十年代曾经历一次发展高潮．近十几年来,伴随着对数障碍函数法在内点法中取得的成功,罚函数法的研究又呈现出一个小高潮[2,3,4]．在罚函数方法里,精确惩罚函数法有着非常吸引人的性质,即,当罚参数大于某个有限门槛值时,仅通过求解单个无约束罚问题便可得到原问题的最优解,从而省去了一般罚函数法解系列无约束优化问题的工作量．     

Quadratic Convergence of a Primal-Dual Interior Point Method for Degenerate Nonlinear Optimization Problems

Recently studies of numerical methods for degenerate nonlinear optimization problems have been attracted much attention. Several authors have discussed convergence properties without the linear independence constraint qualification and/or the strict complementarity condition. In this paper, we are concerned with quadratic convergence property of a primal-dual interior point method, in which Newton’s method is applied to the barrier KKT conditions. We assume that the second order sufficient condition and the linear independence of gradients of equality constraints hold at the solution, and that there exists a solution that satisfies the strict complementarity condition, and that multiplier iterates generated by our method for inequality constraints are uniformly bounded, which relaxes the linear independence constraint qualification. Uniform boundedness of multiplier iterates is satisfied if the Mangasarian-Fromovitz constraint qualification is assumed, for example. By using the stability theorem by Hager and Gowda (1999), and Wright (2001), the distance from the current point to the solution set is related to the residual of the KKT conditions.By controlling a barrier parameter and adopting a suitable line search procedure, we prove the quadratic convergence of the proposed algorithm.     

A penalty-free method with line search for nonlinear equality constrained optimization

A new line search method is introduced for solving nonlinear equality constrained optimization problems. It does not use any penalty function or a filter. At each iteration, the trial step is determined such that either the value of the objective function or the measure of the constraint violation is sufficiently reduced. Under usual assumptions, it is shown that every limit point of the sequence of iterates generated by the algorithm is feasible, and there exists at least one limit point that is a stationary point for the problem. A simple modification of the algorithm by introducing second order correction steps is presented. It is shown that the modified method does not suffer from the Maratos’ effect, so that it converges superlinearly. The preliminary numerical results are reported.     

Infinite-horizon deterministic dynamic programming in discrete time: a monotone convergence principle and a penalty method

We consider infinite-horizon deterministic dynamic programming problems in discrete time. We show that the value function of such a problem is always a fixed point of a modified version of the Bellman operator. We also show that value iteration converges increasingly to the value function if the initial function is dominated by the value function, is mapped upward by the modified Bellman operator and satisfies a transversality-like condition. These results require no assumption except for the general framework of infinite-horizon deterministic dynamic programming. As an application, we show that the value function can be approximated by computing the value function of an unconstrained version of the problem with the constraint replaced by a penalty function.     

一类逼近l1精确罚函数的罚函数

本文对可微非线性规划问题提出了一个渐近算法,它是基于一类逼近l1精确罚函数的罚函数而提出的,我们证明了算法所得的极小点列的聚点均为原问题的最优解,并在Mangasarian-Fromovitz约束条件下,证明了有限次迭代之后,所有迭代均为可行的,即迭代所得的极小点为可行点.     

广义乘子交替方向法求解线性约束不可分非凸优化问题的收敛性

In this paper, we consider the convergence of the generalized alternating direction method of multipliers(GADMM) for solving linearly constrained nonconvex minimization model whose objective contains coupled functions. Under the assumption that the augmented Lagrangian function satisfies the Kurdyka-Lojasiewicz inequality, we prove that the sequence generated by the GADMM converges to a critical point of the augmented Lagrangian function when the penalty parameter in the augmented Lagrangian function is sufficiently large. Moreover, we also present some sufficient conditions guaranteeing the sublinear and linear rate of convergence of the algorithm.     

Convergence Analysis of a Class of Nonlinear Penalization Methods for Constrained Optimization via First-Order Necessary Optimality Conditions

We propose a scheme to solve constrained optimization problems by combining a nonlinear penalty method and a descent method. A sequence of nonlinear penalty optimization problems is solved to generate a sequence of stationary points, i.e., each point satisfies a first-order necessary optimality condition of a nonlinear penalty problem. Under some conditions, we show that any limit point of the sequence satisfies the first-order necessary condition of the original constrained optimization problem.     

求解非线性规划问题的一类对偶算法

本文提出了一类求解不等式约束非线性规划问题的构造性对偶算法,我们证明在适当的条件下,势函数的罚参数存在一个阀值,当罚参数小于这个阀值时,由这一方法所产生的序列局部收敛于问题的一个Kuhn-Tucker解,我们也建立了解的依赖于罚参数的误差上界,最后,我们给出了一个特残势函数的数值结果。     

求解约束规划的一个非线性Lagrange函数

本文提出了一个求解不等式约束优化问题的非线性Lagrange函数,并构造了基于该函数的对偶算法.证明了当参数σ小于某一阈值σ_0时,由算法生成的原始-对偶点列是局部收敛的,并给出了原始-对偶解的误差估计.此外,建立了基于该函数的对偶理论.最后给出了算法的数值结果.     

Trust region affine scaling algorithms for linearly constrained convex and concave programs

We study a trust region affine scaling algorithm for solving the linearly constrained convex or concave programming problem. Under primal nondegeneracy assumption, we prove that every accumulation point of the sequence generated by the algorithm satisfies the first order necessary condition for optimality of the problem. For a special class of convex or concave functions satisfying a certain invariance condition on their Hessians, it is shown that the sequences of iterates and objective function values generated by the algorithm convergeR-linearly andQ-linearly, respectively. Moreover, under primal nondegeneracy and for this class of objective functions, it is shown that the limit point of the sequence of iterates satisfies the first and second order necessary conditions for optimality of the problem. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.The work of these authors was based on research supported by the National Science Foundation under grant INT-9600343 and the Office of Naval Research under grants N00014-93-1-0234 and N00014-94-1-0340.     

Analysis on Newton projection method for the split feasibility problem

In this paper, based on a merit function of the split feasibility problem (SFP), we present a Newton projection method for solving it and analyze the convergence properties of the method. The merit function is differentiable and convex. But its gradient is a linear composite function of the projection operator, so it is nonsmooth in general. We prove that the sequence of iterates converges globally to a solution of the SFP as long as the regularization parameter matrix in the algorithm is chosen properly. Especially, under some local assumptions which are necessary for the case where the projection operator is nonsmooth, we prove that the sequence of iterates generated by the algorithm superlinearly converges to a regular solution of the SFP. Finally, some numerical results are presented.     

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.     

ABS算法在求解MPEC问题中的应用

应用ABS—隐式LU算法，简化MPEC问题的约束条件，将简化后的MPEC问题转化为目标函数带有罚函数子项的非线性无约束优化问题，给出收敛性定理，证明当罚因子足够大时，此非线性无约束问题的极小点就是简化后的MPEC问题的极小点，将此极小点代入本中给出的一个转换公式可得原MPEC问题的极小点，末给出一算例。     

张量方法在信赖域算法中的应用

信赖域算法是求解无约束优化问题的一种有效的算法.对于该算法的子问题,本文将原来目标函数的二次模型扩展成四次张量模型,提出了一个带信赖域约束的四次张量模型优化问题的求解算法.该方法的最大特点是:不仅在张量模型的非稳定点可以得到下降方向及相应的迭代步长,而且在非局部极小值点的稳定点也可以得到下降方向及相应的迭代步长,从而在算法产生的迭代点列中存在一个子列收敛到信赖域子问题的局部极小值点.     

A least-distance programming procedure for minimization problems under linear constraints

In this paper, an algorithm is developed for solving a nonlinear programming problem with linear contraints. The algorithm performs two major computations. First, the search vector is determined by projecting the negative gradient of the objective function on a polyhedral set defined in terms of the gradients of the equality constraints and the near binding inequality constraints. This least-distance program is solved by Lemke's complementary pivoting algorithm after eliminating the equality constraints using Cholesky's factorization. The second major calculation determines a stepsize by first computing an estimate based on quadratic approximation of the function and then finalizing the stepsize using Armijo's inexact line search. It is shown that any accumulation point of the algorithm is a Kuhn-Tucker point. Furthermore, it is shown that, if an accumulation point satisfies the second-order sufficiency optimality conditions, then the whole sequence of iterates converges to that point. Computational testing of the algorithm is presented.     

A trust-region and affine scaling algorithm for linearly constrained optimization

A new trust-region and affine scaling algorithm for linearly constrained optimization is presented in this paper. Under no nondegenerate assumption, we prove that any limit point of the sequence generated by the new algorithm satisfies the first order necessary condition and there exists at least one limit point of the sequence which satisfies the second order necessary condition. Some preliminary numerical experiments are reported. The work was done while visiting Institute of Applied Mathematics, AMSS, CAS.     

A New Trust-Region Algorithm for Equality Constrained Optimization

We present a new trust-region algorithm for solving nonlinear equality constrained optimization problems. Quadratic penalty functions are employed to obtain global convergence. At each iteration a local change of variables is performed to improve the ability of the algorithm to follow the constraint level set. Under certain assumptions we prove that this algorithm globally converges to a point satisfying the second-order necessary optimality conditions. Results of preliminary numerical experiments are reported.     

A penalty function approach for solving bi-level linear programs

The paper presents an approach to bi-level programming using a duality gap—penalty function format. A new exact penalty function exists for obtaining a global optimal solution for the linear case, and an algorithm is given for doing this, making use of some new theoretical properties. For each penalty parameter value, the central optimisation problem is one of maximising a convex function over a polytope, for which a modification of an algorithm of Tuy (1964) is used. Some numerical results are given. The approach has other features which assist the actual decisionmaking process, which make use of the natural roles of duality gaps and penalty parameters. The approach also allows a natural generalization to nonlinear problems.