General primal-dual penalty/barrier path-following Newton methods for nonlinear programming

In the present article rather general penalty/barrier-methods are considered, that define a local continuously differentiable primal-dual path. The class of penalty/barrier terms includes most of the usual techniques like logarithmic barriers, SUMT, quadratic loss functions as well as exponential penalties, and the optimization problem which may contain inequality as well as equality constraints. The convergence of the corresponding general primal-dual path-following method is shown for local minima that satisfy strong second-order sufficiency conditions with linear independence constraint qualification (LICQ) and strict complementarity. A basic tool in the analysis of these methods is to estimate the radius of convergence of Newton's method depending on the penalty/barrier-parameter. Without using self-concordance properties convergence bounds are derived by direct estimations of the solutions of the Newton equations. Parameter selection rules are proposed which guarantee the local convergence of the considered penalty/barrier-techniques with only a finite number of Newton steps at each parameter level. Numerical examples illustrate the practical behavior of the proposed class of methods.     

Path-following barrier and penalty methods for linearly constrained problems

In the present paper some barrier and penalty methods (e.g. logarithmic barriers, SUMT, exponential penalties), which define a continuously differentiable primal and dual path, applied to linearly constrained convex problems are studied, in particular, the radius of convergence of Newton’s method depending on the barrier and penalty para-meter is estimated, Unlike using self-concordance properties the convergence bounds are derived by direct estimations of the solutions of the Newton equations. The obtained results establish parameter selection rules which guarantee the overall convergence of the considered barrier and penalty techniques with only a finite number of Newton steps at each parameter level. Moreover, the obtained estimates support scaling method which uses approximate dual multipliers as available in barrier and penalty methods     

A new penalty function algorithm for convex quadratic programming

In this paper, we develop an exterior point algorithm for convex quadratic programming using a penalty function approach. Each iteration in the algorithm consists of a single Newton step followed by a reduction in the value of the penalty parameter. The points generated by the algorithm follow an exterior path that we define. Convergence of the algorithm is established. The proposed algorithm was motivated by the work of Al-Sultan and Murty on nearest point problems, a special quadratic program. A preliminary implementation of the algorithm produced encouraging results. In particular, the algorithm requires a small and almost constant number of iterations to solve the small to medium size problems tested.     

On the Superlinear Convergence Order of the Logarithmic Barrier Algorithm

Since the pioneering work of Karmarkar, much interest was directed to penalty algorithms, in particular to the log barrier algorithm. We analyze in this paper the asymptotic convergence rate of a barrier algorithm when applied to non-linear programs. More specifically, we consider a variant of the SUMT method, in which so called extrapolation predictor steps allowing reducing the penalty parameter r_k +1}k are followed by some Newton correction steps. While obviously related to predictor-corrector interior point methods, the spirit differs since our point of view is biased toward nonlinear barrier algorithms; we contrast in details both points of view. In our context, we identify an asymptotically optimal strategy for reducing the penalty parameter r and show that if r_k+1=r _k with < 8/5, then asymptotically only 2 Newton corrections are required, and this strategy achieves the best overall average superlinear convergence order (1.1696). Therefore, our main result is to characterize the best possible convergence order for SUMT type methods.     

Improved convergence order for augmented penalty algorithms

We refine the speed of convergence analysis for the quadratic augmented penalty algorithm. We improve the convergence order from 4/3 to 3/2 for the first order multiplier iteration. For the second order iteration, we generalize the analysis, and consider a primal–dual variant which asymptotically reduces to a Newton step for the optimality conditions.     

A generalized Newton algorithm for quantile regression models

This paper formulates the quadratic penalty function for the dual problem of the linear programming associated with the \(L_1\) constrained linear quantile regression model. We prove that the solution of the original linear programming can be obtained by minimizing the quadratic penalty function, with the formulas derived. The obtained quadratic penalty function has no constraint, thus could be minimized efficiently by a generalized Newton algorithm with Armijo step size. The resulting algorithm is easy to implement, without requiring any sophisticated optimization package other than a linear equation solver. The proposed approach can be generalized to the quantile regression model in reproducing kernel Hilbert space with slight modification. Extensive experiments on simulated data and real-world data show that, the proposed Newton quantile regression algorithms can achieve performance comparable to state-of-the-art.     

A general class of penalty/barrier path-following Newton methods for nonlinear programming

In the present article rather general penalty/barrier-methods (e.g. logarithmic barriers, SUMT, exponential penalties), which define a local continuously differentiable primal and dual path, are analyzed in case of strict local minima of nonlinear problems with inequality as well as equality constraints. In particular, the radius of convergence of Newton's method depending on the penalty/barrier-parameter is estimated. Unlike using self-concordance properties, the convergence bounds are derived by direct estimations of the solutions of the Newton equations. By means of the obtained results parameter selection rules are studied which guarantee the local convergence of the considered penalty/barrier-techniques with only a finite number of Newton steps at each parameter level. Numerical examples illustrate the practical behavior of the proposed class of methods.     

Exterior point algorithms for nearest points and convex quadratic programs

We consider the problem of finding the nearest point (by Euclidean distance) in a simplicial cone to a given point, and develop an exterior penalty algorithm for it. Each iteration in the algorithm consists of a single Newton step following a reduction in the value of the penalty parameter. Proofs of convergence of the algorithm are given. Various other versions of exterior penalty algorithms for nearest point problems in nonsimplicial polyhedral cones and for convex quadratic programs, all based on a single descent step following a reduction in the value of the penalty parameter per iteration, are discussed. The performance of these algorithms in large scale computational experiments is very encouraging. It shows that the number of iterations grows very slowly, if at all, with the dimension of the problem.Partially supported by NSF Grant No. ECS-8521183, and by the two universities.     

Equality and inequality constrained optimization algorithms with convergent stepsizes

In this paper, we consider two algorithms for nonlinear equality and inequality constrained optimization. Both algorithms utilize stepsize strategies based on differentiable penalty functions and quadratic programming subproblems. The essential difference between the algorithms is in the stepsize strategies used. The objective function in the quadratic subproblem includes a linear term that is dependent on the penalty functions. The quadratic objective function utilizes an approximate Hessian of the Lagrangian augmented by the penalty functions. In this approximation, it is possible to ignore the second-derivative terms arising from the constraints in the penalty functions.The penalty parameter is determined using a strategy, slightly different for each algorithm, that ensures boundedness as well as a descent property. In particular, the boundedness follows as the strategy is always satisfied for finite values of the parameter.These properties are utilized to establish global convergence and the condition under which unit stepsizes are achieved. There is also a compatibility between the quadratic objective function and the stepsize strategy to ensure the consistency of the properties for unit steps and subsequent convergence rates.This research was funded by SERC and ESRC research contracts. The author is grateful to Professors Laurence Dixon and David Mayne for their comments. The numerical results in the paper were obtained using a program written by Mr. Robin Becker.     

广义精确可微罚函数

本文利用凝聚函数，构造了一个新的广义精确可微罚函数，并设计了一类具有全局收敛的算法．该算法允许任意初始点，并自动调整罚因子，调整步骤是有限的．新的广义精确可微罚函数不会有“零，一阶病态”发生．     

An RQP algorithm using a differentiable exact penalty function for inequality constrained problems

In this paper we propose a recursive quadratic programming algorithm for nonlinear programming problems with inequality constraints that uses as merit function a differentiable exact penalty function. The algorithm incorporates an automatic adjustment rule for the selection of the penalty parameter and makes use of an Armijo-type line search procedure that avoids the need to evaluate second order derivatives of the problem functions. We prove that the algorithm possesses global and superlinear convergence properties. Numerical results are reported.     

Nonlinear statics and dynamics of antisymmetric composite laminated square plates supported on nonlinear elastic subgrade

Non-linear static and dynamic analysis is presented for composite laminated anti-symmetric square plates supported on non-linear elastic foundation subjected to uniformly distributed transverse and step loading, respectively. The formulation is based on first order shear deformation theory (FSDT) and Von-Karman non-linearity, subgrade interaction is modeled as shear deformable with cubic nonlinearity. The methodology of solution is based on the Chebyshev series technique. The coupled non-linear partial differential equations are linearized using quadratic extrapolation technique. Houbolt time marching scheme is employed for temporal discretisation. An incremental iterative approach is employed for the solution. The effects of foundation stiffness parameters and boundary conditions on the non-linear static and dynamic analysis on the central response are studied.     

A PENALTY TECHNIQUE FOR NONLINEAR COMPLEMENTARITY PROBLEMS

1.IntroductionConsiderthefollowingnonlinearcomplementarityproblemsNCP(F)offindinganxER",suchthatwhereFisamappingfromR"intoitself.ItisanimportantformofthefollowingvariationalinequalityVI(F,X)offindinganxEX,suchthatwhereXCReisaclosedconvexset.WhenX=R7,(1.1)…     

A TRUST REGION-TYPE METHOD FOR SOLVINGMONOTONE VARIATIONAL INEQUALITY

1.IntroductionLetSbeanonemptyclosedconvexsubsetofR"andletF:R"-R"beacontinuousmapping.ThevariatiollalillequalityproblemFindx*6Ssuchthat(F(x*),x--x*)20forallxeS(VIP)iswidelyusedtostudyvariousequilibriummodelsarisingilleconomic,operatiollsresearch,transportatiollandregionalsciellces[2'3I?where(.,.)dellotestheinnerproductinR".Manyiterativemethodsfor(VIP)havebeendeveloped,forexample,projectionmethods[7ts],thenonlinearJacobimethod[5],thesuccessiveoverrelaxation.ethod[9]andgeneralizedgradient.…     

A Globally Convergent Method of Constrained Minimization by Solving Subproblems of the Conic Model

A new method for nonlinearly constrained optimization problems is proposed. The method consists of two steps. In the first step, we get a search direction by the linearly constrained subproblems based on conic functions. In the second step, we use a differentiable penalty function, and regard it as the metric function of the problem. From this, a new approximate solution is obtained. The global convergence of the given method is also proved.     

A dual differentiable exact penalty function

A new penalty function is associated with an inequality constrained nonlinear programming problem via its dual. This penalty function is globally differentiable if the functions defining the original problem are twice globally differentiable. In addition, the penalty parameter remains finite. This approach reduces the original problem to a simple problem of maximizing a globally differentiable function on the product space of a Euclidean space and the nonnegative orthant of another Euclidean space. Many efficient algorithms exist for solving this problem. For the case of quadratic programming, the penalty function problem can be solved effectively by successive overrelaxation (SOR) methods which can handle huge problems while preserving sparsity features. Sponsored by the United States Army under Contract No. DAAG 29-80-C-0041. This material is based upon work supported by the National Science Foundation under Grants No. MCS-790166 and ENG-7903881.     

Efficient Hybrid Algorithms for Finding Zeros of Convex Functions

We consider two hybrid algorithms for finding an ϵ-approximation of a root of a convex real function that is twice differentiable and satisfies a certain growth condition on the intervial [0, R]. The first algorithm combines a binary search procedure with Newton′s method. The binary search produces an interval contained in the region of quadratic convergence of Newton′s method. The computational cost of the binary search, as well as the computational cost of Newton′s method, is of order O(log log(R/ϵ)). The second algorithm combines a binary search with the secant method in a similar fashion. This results in a lower overall computational cost when the cost of evaluating the derivative is more than .44042 of the cost of evaluating the function. Our results generalize same recent results of Ye.     

A constrained min‐max algorithm for rival models of the same economic system

There are well established rival theories about the economy. These have, in turn, led to the development of rival models purporting to represent the economic system. The models are large systems of discrete-time nonlinear dynamic equations. Observed data of the real system does not, in general, provide sufficient information for statistical methods to invalidate all but one of the rival models. In such a circumstance, there is uncertainty about which model to use in the formulation of policy. Prudent policy design would suggest that a model-based policy should take into account all the rival models. This is achieved as a pooling of the models. The pooling that yields the policy which is robust to model choice is formulated as a constrained min-max problem. The minimization is over the decision variables and the maximization is over the rival models. Only equality constraints are considered.A successive quadratic programming algorithm is discussed for the solution of the min-max problem. The algorithm uses a stepsize strategy based on a differentiable penalty function for the constraints. Two alternative quadratic subproblems can be used. One is a quadratic min-max and the other a quadratic programming problem. The objective function of either subproblem includes a linear term which is dependent on the penalty function. The penalty parameter is determined at every iteration, using a strategy that ensures a descent property as well as the boundedness of the penalty term. The boundedness follows since the strategy is always satisfied for finite values of the parameter which needs to be increased a finite number of times.The global and local convergence of the algorithm is established. The conditions, involving projected Hessian approximations, are discussed under which the algorithm achieves unit stepsizes and subsequently Q-superlinear convergence.     

有界约束半光滑方程组的非单调投影信赖域方法

投影信赖域策略结合非单调线搜索算法解有界约束非线性半光滑方程组.基于简单有界约束的非线性优化问题构建信赖域子问题,半光滑类牛顿步在可行域投影得到投影牛顿的试探步,获得新的搜索方向,结合非单调线搜索技术得到回代步,获得新的步长.在合理的条件下,证明算法不仅具有整体收敛性且保持超线性收敛速率.引入非单调技术能克服高度非线性的病态问题,加速收敛性进程,得到超线性收敛速率.     

A recursive quadratic programming algorithm that uses differentiable exact penalty functions

In this paper, a recursive quadratic programming algorithm for solving equality constrained optimization problems is proposed and studied. The line search functions used are approximations to Fletcher's differentiable exact penalty function. Global convergence and local superlinear convergence results are proved, and some numerical results are given.