Some investigations in a new algorithm for nonlinear optimization based on conic models of the objective function

An appealing approach to the solution of nonlinear optimization problems based on conic models of the objective function has been recently introduced by Davidon. It leads to a broad class of algorithms which, in some sense, can be considered to generalize the existing quasi-Newton algorithms. One particular member of this class has been deeply examined by Sorensen, who has proved some interesting theoretical properties. A new interpretation of this algorithm is suggested in this paper from a more straightforward and somewhat familiar point of view. In addition, numerical experiments have been carried out to compare the Sorensen algorithm with a straightforward BFGS implementation of the classical quasi-Newton method with the final aim to assess the real merits and benefits of the new algorithm. Although some challenging test functions are used in computational experiments, the results are not particularly favorable to the new algorithm. As a matter of fact they do not exhibit any jump of quality, as it might be expected. Lastly, it is pointed out that a difficulty may affect the new method in situations in which it is necessary to exploit the special structure of large-scale problems.This work was supported by the National Research Council of Italy under Grant No. 80-01144.     

Generalization of Primal—Dual Interior-Point Methods to Convex Optimization Problems in Conic Form

We generalize primal—dual interior-point methods for linear programming (LP) problems to the convex optimization problems in conic form. Previously, the most comprehensive theory of symmetric primal—dual interior-point algorithms was given by Nesterov and Todd for feasible regions expressed as the intersection of a symmetric cone with an affine subspace. In our setting, we allow an arbitrary convex cone in place of the symmetric cone. Even though some of the impressive properties attained by Nesterov—Todd algorithms are impossible in this general setting of convex optimization problems, we show that essentially all primal—dual interior-point algorithms for LP can be extended easily to the general setting. We provide three frameworks for primal—dual algorithms, each framework corresponding to a different level of sophistication in the algorithms. As the level of sophistication increases, we demand better formulations of the feasible solution sets. Our algorithms, in return, attain provably better theoretical properties. We also make a very strong connection to quasi-Newton methods by expressing the square of the symmetric primal—dual linear transformation (the so-called scaling) as a quasi-Newton update in the case of the least sophisticated framework. August 25, 1999. Final version received: March 7, 2001.     

Quasi-Newton ABS methods for solving nonlinear algebraic systems of equations

This paper is concerned with the solution of nonlinear algebraic systems of equations. For this problem, we suggest new methods, which are combinations of the nonlinear ABS methods and quasi-Newton methods. Extensive numerical experiments compare particular algorithms and show the efficiency of the proposed methods.The authors are grateful to Professors C. G. Broyden and E. Spedicato for many helpful discussions.     

Matrix conditioning and nonlinear optimization

In a series of recent papers, Oren, Oren and Luenberger, Oren and Spedicato, and Spedicato have developed the self-scaling variable metric algorithms. These algorithms alter Broyden's single parameter family of approximations to the inverse Hessian to a double parameter family. Conditions are given on the new parameter to minimize a bound on the condition number of the approximated inverse Hessian while insuring improved step-wise convergence.Davidon has devised an update which also minimizes the bound on the condition number while remaining in the Broyden single parameter family.This paper derives initial scalings for the approximate inverse Hessian which makes members of the Broyden class self-scaling. The Davidon, BFGS, and Oren—Spedicato updates are tested for computational efficiency and stability on numerous test functions, with the results indicating strong superiority computationally for the Davidon and BFGS update over the self-scaling update, except on a special class of functions, the homogeneous functions.     

Optimally conditioned scaled ABS algorithms for linear systems

Using a strict bound of Spedicato to the condition number of bordered positive-definite matrices, we show that the scaling parameter in the ABS class for linear systems can always be chosen so that the bound of a certain update matrix is globally minimized. Moreover, if the scaling parameter is so chosen at every iteration, then the condition number itself is globally minimized. The resulting class of optimally conditioned algorithms contains as a special case the class of optimally stable algorithms in the sense of Broyden.This work was done in the framework of research supported by MPI, Rome, Italy, 60% Program.     

The local convergence of ABS methods for nonlinear algebraic equations

Summary In this paper we consider an extension to nonlinear algebraic systems of the class of algorithms recently proposed by Abaffy, Broyden and Spedicato for general linear systems. We analyze the convergence properties, showing that under the usual assumptions on the function and some mild assumptions on the free parameters available in the class, the algorithm is locally convergent and has a superlinear rate of convergence (per major iteration, which is computationally comparable to a single Newton's step). Some particular algorithms satisfying the conditions on the free parameters are considered.     

Computational experiments with scaled initial hessian approximation for the broyden family methods ∗

In this paper we consider two alternative choices for the factor used to scale the initial Hessian approximation, before updating by a member of the Broyden family of updates for quasi-Newton optimization methods. By extensive computational experiments carried out on a set of standard test problems from the CUTE collection, using efficient implemen-tations of the quasi-Newton method, we show that the proposed new scaling factors are better, in terms of efficiency achieved (number of iterations, number of function and gradient evaluations), than the standard choice proposed in the literature     

A class of primal affine scaling algorithms

We obtain a class of primal affine scaling algorithms which generalize some known algorithms. This class, depending on a r-parameter, is constructed through a family of metrics generated by −r power, r ? 1, of the diagonal iterate vector matrix. We prove the so-called weak convergence of the primal class for nondegenerate linearly constrained convex programming. We observe the computational performance of the class of primal affine scaling algorithms, accomplishing tests with linear programs from the NETLIB library and with some quadratic programming problems described in the Maros and Mészáros repository.     

Line search termination criteria for collinear scaling algorithms for minimizing a class of convex functions

Summary. Many successful quasi-Newton methods for optimization are based on positive definite local quadratic approximations to the objective function that interpolate the values of the gradient at the current and new iterates. Line search termination criteria used in such quasi-Newton methods usually possess two important properties. First, they guarantee the existence of such a local quadratic approximation. Second, under suitable conditions, they allow one to prove that the limit of the component of the gradient in the normalized search direction is zero. This is usually an intermediate result in proving convergence. Collinear scaling algorithms proposed initially by Davidon in 1980 are natural extensions of quasi-Newton methods in the sense that they are based on normal conic local approximations that extend positive definite local quadratic approximations, and that they interpolate values of both the gradient and the function at the current and new iterates. Line search termination criteria that guarantee the existence of such a normal conic local approximation, which also allow one to prove that the component of the gradient in the normalized search direction tends to zero, are not known. In this paper, we propose such line search termination criteria for an important special case where the function being minimized belongs to a certain class of convex functions. Received February 1, 1997 / Revised version received September 8, 1997     

Solution of linear least squares via the ABS algorithm

The ABS class for linear and nonlinear systems has been recently introduced by Abaffy, Broyden, Galantai and Spedicato. Here we consider various ways of applying these algorithms to the determination of the minimal euclidean norm solution of over-determined linear systems in the least squares sense. Extensive numerical experiments show that the proposed algorithms are efficient and that one of them usually gives better accuracy than standard implementations of the QR orthogonalization algorithm with Householder reflections.     

ABS methods and ABSPACK for linear systems and optimization: A review

ABS methods are a large class of methods, based upon the Egervary rank reducing algebraic process, first introduced in 1984 by Abaffy, Broyden and Spedicato for solving linear algebraic systems, and later extended to nonlinear algebraic equations, to optimization problems and other fields; software based upon ABS methods is now under development. Current ABS literature consists of about 400 papers. ABS methods provide a unification of several classes of classical algorithms and more efficient new solvers for a number of problems. In this paper we review ABS methods for linear systems and optimization, from both the point of view of theory and the numerical performance of ABSPACK.Work partially supported by ex MURST 60% 2001 funds.E. Spedicato     

CONVERGENCE PROPERTIES OF MULTI-DIRECTIONAL PARALLEL ALGORITHMS FOR UNCONSTRAINED MINIMIZATION

Convergence properties of a class of multi-directional parallel quasi-Newton algorithmsfor the solution of unconstrained minimization problems are studied in this paper.At eachiteration these algorithms generate several different quasi-Newton directions,and thenapply line searches to determine step lengths along each direction,simultaneously.Thenext iterate is obtained among these trail points by choosing the lowest point in the sense offunction reductions.Different quasi-Newton updating formulas from the Broyden familyare used to generate a main sequence of Hessian matrix approximations.Based on theBFGS and the modified BFGS updating formulas,the global and superlinear convergenceresults are proved.It is observed that all the quasi-Newton directions asymptoticallyapproach the Newton direction in both direction and length when the iterate sequenceconverges to a local minimum of the objective function,and hence the result of superlinearconvergence follows.     

Disguised and new quasi-Newton methods for nonlinear eigenvalue problems

In this paper, we take a quasi-Newton approach to nonlinear eigenvalue problems (NEPs) of the type M(λ)v =?0, where \(M:\mathbb {C}\rightarrow \mathbb {C}^{n\times n}\) is a holomorphic function. We investigate which types of approximations of the Jacobian matrix lead to competitive algorithms, and provide convergence theory. The convergence analysis is based on theory for quasi-Newton methods and Keldysh’s theorem for NEPs. We derive new algorithms and also show that several well-established methods for NEPs can be interpreted as quasi-Newton methods, and thereby, we provide insight to their convergence behavior. In particular, we establish quasi-Newton interpretations of Neumaier’s residual inverse iteration and Ruhe’s method of successive linear problems.     

Optimal scaling of random-walk metropolis algorithms on general target distributions

One main limitation of the existing optimal scaling results for Metropolis–Hastings algorithms is that the assumptions on the target distribution are unrealistic. In this paper, we consider optimal scaling of random-walk Metropolis algorithms on general target distributions in high dimensions arising from practical MCMC models from Bayesian statistics. For optimal scaling by maximizing expected squared jumping distance (ESJD), we show the asymptotically optimal acceptance rate 0.234 can be obtained under general realistic sufficient conditions on the target distribution. The new sufficient conditions are easy to be verified and may hold for some general classes of MCMC models arising from Bayesian statistics applications, which substantially generalize the product i.i.d. condition required in most existing literature of optimal scaling. Furthermore, we show one-dimensional diffusion limits can be obtained under slightly stronger conditions, which still allow dependent coordinates of the target distribution. We also connect the new diffusion limit results to complexity bounds of Metropolis algorithms in high dimensions.     

A combined conjugate-gradient quasi-Newton minimization algorithm

Although quasi-Newton algorithms generally converge in fewer iterations than conjugate gradient algorithms, they have the disadvantage of requiring substantially more storage. An algorithm will be described which uses an intermediate (and variable) amount of storage and which demonstrates convergence which is also intermediate, that is, generally better than that observed for conjugate gradient algorithms but not so good as in a quasi-Newton approach. The new algorithm uses a strategy of generating a form of conjugate gradient search direction for most iterations, but it periodically uses a quasi-Newton step to improve the convergence. Some theoretical background for a new algorithm has been presented in an earlier paper; here we examine properties of the new algorithm and its implementation. We also present the results of some computational experience.This research was supported by the National Research Council of Canada grant number A-8962.     

The M-band cardinal orthogonal scaling function

The M-band symmetric cardinal orthogonal scaling function with compact support is of interest in several applications such as sampling theory, signal processing, computer graphics, and numerical algorithms. In this paper, we provide a complete mathematical analysis for the M-band symmetric cardinal orthogonal scaling function. Firstly, we generalize some results of the cardinal orthogonal scaling function from the special case M=2 to the most general case M?2. Also, we find some new results. Secondly, we obtain the characterizations of the M-band symmetric cardinal orthogonal scaling function and revisit some known examples to prove our theory.     

Global Convergence Property of Scaled Two-Step BFGS Method

This paper is aimed to extend the scheme of self scaling, appropriate for the quasi-Newton methods, to the two-step quasi-Newton methods. The scaling scheme has been performed during the main approach of updating the current Hessian approximation and prior to the computation of the next quasi-Newton direction whenever necessary. Global convergence property of the new method is explored on uniformly convex functions with the standard Wolfe line search. Preliminary numerical testing has been performed showing that this technique improves the performance of the two-step method substantially.     

A variable-metric method for function minimization derived from invariancy to nonlinear scaling

The effect of nonlinearly scaling the objective function on the variable-metric method is investigated, and Broyden's update is modified so that a property of invariancy to the scaling is satisfied. A new three-parameter class of updates is generated, and criteria for an optimal choice of the parameters are given. Numerical experiments compare the performance of a number of algorithms of the resulting class.The author is indebted to Professor S. S. Oren, Economic Engineering Department, Stanford University, Stanford, California, for stimulating discussions during the development of this paper. He also recognizes the financial support by the National Research Council of Italy (CNR) for his stay at Stanford University.     

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.     

Variable selection via generalized SELO-penalized linear regression models

The seamless-L_0(SELO) penalty is a smooth function on [0, ∞) that very closely resembles the L_0 penalty, which has been demonstrated theoretically and practically to be effective in nonconvex penalization for variable selection. In this paper, we first generalize SELO to a class of penalties retaining good features of SELO, and then propose variable selection and estimation in linear models using the proposed generalized SELO(GSELO) penalized least squares(PLS) approach. We show that the GSELO-PLS procedure possesses the oracle property and consistently selects the true model under some regularity conditions in the presence of a diverging number of variables. The entire path of GSELO-PLS estimates can be efficiently computed through a smoothing quasi-Newton(SQN) method. A modified BIC coupled with a continuation strategy is developed to select the optimal tuning parameter. Simulation studies and analysis of a clinical data are carried out to evaluate the finite sample performance of the proposed method. In addition, numerical experiments involving simulation studies and analysis of a microarray data are also conducted for GSELO-PLS in the high-dimensional settings.