Planar quasi-Newton algorithms for unconstrained saddlepoint problems

A new class of quasi-Newton methods is introduced that can locate a unique stationary point of ann-dimensional quadratic function in at mostn steps. When applied to positive-definite or negative-definite quadratic functions, the new class is identical to Huang's symmetric family of quasi-Newton methods (Ref. 1). Unlike the latter, however, the new family can handle indefinite quadratic forms and therefore is capable of solving saddlepoint problems that arise, for instance, in constrained optimization. The novel feature of the new class is a planar iteration that is activated whenever the algorithm encounters a near-singular direction of search, along which the objective function approaches zero curvature. In such iterations, the next point is selected as the stationary point of the objective function over a plane containing the problematic search direction, and the inverse Hessian approximation is updated with respect to that plane via a new four-parameter family of rank-three updates. It is shown that the new class possesses properties which are similar to or which generalize the properties of Huang's family. Furthermore, the new method is equivalent to Fletcher's (Ref. 2) modified version of Luenberger's (Ref. 3) hyperbolic pairs method, with respect to the metric defined by the initial inverse Hessian approximation. Several issues related to implementing the proposed method in nonquadratic cases are discussed.An earlier version of this paper was presented at the 10th Mathematical Programing Symposium, Montreal, Canada, 1979.     

Convergence theory for the structured BFGS secant method with an application to nonlinear least squares

In 1981, Dennis and Walker developed a convergence theory for structured secant methods which included the PSB and the DFP secant methods but not the straightforward structured version of the BFGS secant method. Here, we fill this gap in the theory by establishing a convergence theory for the structured BFGS secant method. A direct application of our new theory gives the first proof of local andq-superlinear convergence of the important structured BFGS secant method for the nonlinear least-squares problem, which is used by Dennis, Gay, and Welsh in the current version of the popular and successful NL2SOL code.This research was sponsored by SDIO/IST/ARO, AFOSR-85-0243, and DOE-DEFG05-86 ER-25017.A portion of this work is contained in the second author's doctoral thesis under the supervision of the other two authors in the Department of Mathematical Sciences, Rice University. The second author would like to thank Universidad del Valle, Cali, Columbia, for support during his graduate studies.An early draft of this work was presented at the SIAM 35th Anniversary Meeting, October 12–15, 1987, Denver, Colorado.     

Modified proximal point algorithm for extended linear-quadratic programming

Extended linear-quadratic programming arises as a flexible modeling scheme in dynamic and stochastic optimization, which allows for penalty terms and facilitates the use of duality. Computationally it raises new challenges as well as new possibilities in large-scale applications. Recent efforts have been focused on the fully quadratic case ([15] and [23]), while relying on the fundamental proximal point algorithm (PPA) as a shell of outer iterations when the problem is not fully quadratic. In this paper, we focus on the nonfully quadratic cases by proposing some new variants of the fundamental PPA. We first construct a continuously differentiable saddle function S(u, v) through infimal convolution in such a way that the optimal primal-dual pairs of the original problem are just the saddle points of S(u, v) on the whole space. Then the original extended linear-quadratic-programming problem reduces to solving the nonlinear equation S(u, v)=0. We then embed the fundamental PPA and some of its previous variants in the framework of a Newton-like iteration for this equation. After revealing the local quadratic structure of S near the solution, we derive new extensions of the fundamental PPA. In numerical tests, the modified iteration scheme based on the quasi-Newton update formula outperforms the fundamental PPA considerably.     

BROYDEN'S METHOD FOR SOLVING VARIATIONAL INEQUALITIES WITH GLOBAL AND SUPERLINEAR CONVERGENCE

1. IntroductionWe are concerned with the following variational inequality problem of finding amx E X such thatwhere f: R" - R" is assumed to be a continuously differentiable function, and X g R"is specified bywhere gi: R" -- R and h,-: R" - R are twice continuously differentiable functions.The variational inequality (1.1) is denoted by VI(X, f). An important special case ofVI(X, f) is the so--called nonlinear complementarity problem (NCP(f)) with X ~ R7 {x E R" I x 2 0}. Variational…     

一类超线性收敛的广义拟Newton算法

１引言考虑无约束最优化问题其中目标函数ｆ（ｘ）二阶连续可微,记ｆｋ＝ｆ（ｘ）,当充分小时,有如下近似关系：它们对二次函数皆严格成立．考虑选代其中Ｂ（Ｇ的近似）已知,为某种线搜索确定的步长．对Ｂ修正产生Ｂ,即Ｕ为待定ｎ阶矩阵．若要求Ｂ＋满足关系即Ｂ满足拟Ｎｅｗｔｏｎ方程,由它可导出许多著名的拟Ｎｅｗｔｏｎ算法［１－［４］）．若要求Ｂ满足关系则可导出伪Ｎｅｗｔｏｎ－δ族校正公式,它不再是Ｈｕａｎｇ族成员［６］．从信息资源的利用看,（１．６）仅利用了与信息,（１．７）仅利用了与信息．一般而言,较多的信…     

Higher order curvature information and its application in a modified diagonal Secant method

ABSTRACT

A secant equation (quasi-Newton) has one of the most important rule to find an optimal solution in nonlinear optimization. Curvature information must satisfy the usual secant equation to ensure positive definiteness of the Hessian approximation. In this work, we present a new diagonal updating to improve the Hessian approximation with a modifying weak secant equation for the diagonal quasi-Newton (DQN) method. The gradient and function evaluation are utilized to obtain a new weak secant equation and achieve a higher order accuracy in curvature information in the proposed method. Modified DQN methods based on the modified weak secant equation are globally convergent. Extended numerical results indicate the advantages of modified DQN methods over the usual ones and some classical conjugate gradient methods.     

Some new three-term Hestenes–Stiefel conjugate gradient methods with affine combination

In this paper, a modified Hestenes–Stiefel conjugate gradient method for unconstrained problems is developed, which can achieves the twin goals of generating sufficient descent direction at each iteration as well as being close to the Newton direction. In our methods, the hybridization parameter can also be obtained based on other kinds of conjugacy conditions. Under mild condition, we establish their global convergence for general objective functions. Numerical experimentation with the new method indicates that it efficiently solves the test problems and therefore is promising.     

A New Diagonal Quasi-Newton Updating Method With Scaled Forward Finite Differences Directional Derivative for Unconstrained Optimization

A new diagonal quasi-Newton updating algorithm for unconstrained optimization is presented. The elements of the diagonal matrix approximating the Hessian are determined as scaled forward finite differences directional derivatives of the components of the gradient. Under mild classical assumptions, the convergence of the algorithm is proved to be linear. Numerical experiments with 80 unconstrained optimization test problems, of different structures and complexities, as well as five applications from MINPACK-2 collection, prove that the suggested algorithm is more efficient and more robust than the quasi-Newton diagonal algorithm retaining only the diagonal elements of the BFGS update, than the weak quasi-Newton diagonal algorithm, than the quasi-Cauchy diagonal algorithm, than the diagonal approximation of the Hessian by the least-change secant updating strategy and minimizing the trace of the matrix, than the Cauchy with Oren and Luenberger scaling algorithm in its complementary form (i.e. the Barzilai-Borwein algorithm), than the steepest descent algorithm, and than the classical BFGS algorithm. However, our algorithm is inferior to the limited memory BFGS algorithm (L-BFGS).     

一类新拟牛顿非单调信赖域算法

提出了一类新的求解无约束最优化问题的新拟牛顿非单调信赖域算法.采用加权的r_k用以调整信赖域半径,在适当的条件下,证明了算法的全局收敛性.数值结果表明算法的有效性.     

A NEW FAMILY OF TRUST REGION ALGORITHMS FOR UNCONSTRAINED OPTIMIZATION

Trust region (TR) algorithms are a class of recently developed algorithms for nonlinear optimization. A new family of TR algorithms for unconstrained optimization, which is the extension of the usual TR method, is presented in this paper. When the objective function is bounded below and continuously, differentiable, and the norm of the Hesse approximations increases at most linearly with the iteration number, we prove the global convergence of the algorithms. Limited numerical results are reported, which indicate that our new TR algorithm is competitive.