Theoretical Efficiency of an Inexact Newton Method

We propose a local algorithm for smooth unconstrained optimization problems with n variables. The algorithm is the optimal combination of an exact Newton step with Choleski factorization and several inexact Newton steps with preconditioned conjugate gradient subiterations. The preconditioner is taken as the inverse of the Choleski factorization in the previous exact Newton step. While the Newton method is converging precisely with Q-order 2, this algorithm is also precisely converging with Q-order 2. Theoretically, its average number of arithmetic operations per step is much less than the corresponding number of the Newton method for middle-scale and large-scale problems. For instance, when n=200, the ratio of these two numbers is less than 0.53. Furthermore, the ratio tends to zero approximately at a rate of log 2/logn when n approaches infinity.     

Error estimate for the modified Newton method with applications to the solution of nonlinear,two-point boundary-value problems

The solution of nonlinear, two-point boundary value problems by Newton's method requires the formation and factorization of a Jacobian matrix at every iteration. For problems in which the cost of performing these operations is a significant part of the cost of the total calculation, it is natural to consider using the modified Newton method. In this paper, we derive an error estimate which enables us to determine an upper bound for the size of the sequence of modified Newton iterates, assuming that the Kantorovich hypotheses are satisfied. As a result, we can efficiently determine when to form a new Jacobian and when to continue the modified Newton algorithm. We apply the result to the solution of several nonlinear, two-point boundary value problems occurring in combustion.     

A Newton Acceleration of the Weiszfeld Algorithm for Minimizing the Sum of Euclidean Distances

The Weiszfeld algorithm for continuous location problems can be considered as an iteratively reweighted least squares method. It generally exhibits linear convergence. In this paper, a Newton algorithm with similar simplicity is proposed to solve a continuous multifacility location problem with the Euclidean distance measure. Similar to the Weiszfeld algorithm, the main computation can be solving a weighted least squares problem at each iteration. A Cholesky factorization of a symmetric positive definite band matrix, typically with a small band width (e.g., a band width of two for a Euclidean location problem on a plane) is performed. This new algorithm can be regarded as a Newton acceleration to the Weiszfeld algorithm with fast global and local convergence. The simplicity and efficiency of the proposed algorithm makes it particularly suitable for large-scale Euclidean location problems and parallel implementation. Computational experience suggests that the proposed algorithm often performs well in the absence of the linear independence or strict complementarity assumption. In addition, the proposed algorithm is proven to be globally convergent under similar assumptions for the Weiszfeld algorithm. Although local convergence analysis is still under investigation, computation results suggest that it is typically superlinearly convergent.     

A filter line search algorithm based on an inexact Newton method for nonconvex equality constrained optimization

We propose an inexact Newton method with a filter line search algorithm for nonconvex equality constrained optimization. Inexact Newton’s methods are needed for large-scale applications which the iteration matrix cannot be explicitly formed or factored. We incorporate inexact Newton strategies in filter line search, yielding algorithm that can ensure global convergence. An analysis of the global behavior of the algorithm and numerical results on a collection of test problems are presented.     

A matrix-free implementation of Riemannian Newton’s method on the Stiefel manifold

Newton’s method for unconstrained optimization problems on the Euclidean space can be generalized to that on Riemannian manifolds. The truncated singular value problem is one particular problem defined on the product of two Stiefel manifolds, and an algorithm of the Riemannian Newton’s method for this problem has been designed. However, this algorithm is not easy to implement in its original form because the Newton equation is expressed by a system of matrix equations which is difficult to solve directly. In the present paper, we propose an effective implementation of the Newton algorithm. A matrix-free Krylov subspace method is used to solve a symmetric linear system into which the Newton equation is rewritten. The presented approach can be used on other problems as well. Numerical experiments demonstrate that the proposed method is effective for the above optimization problem.     

关于酉对称矩阵的QR分解及其算法

为了简化大型行(列)酉对称矩阵的QR分解,研究了行(列)酉对称矩阵的性质,获得了一些新的结果,给出了行(列)酉对称矩阵的QR分解的公式和快速算法,它们可极大地减少行(列)酉对称矩阵的QR分解的计算量与存储量,并且不会丧失数值精度.同时推广和丰富了邹红星等(2002)的研究内容,拓宽了实际应用领域的范围.     

A curvilinear method based on minimal-memory BFGS updates

We present a new matrix-free method for the computation of negative curvature directions based on the eigenstructure of minimal-memory BFGS matrices. We determine via simple formulas the eigenvalues of these matrices and we compute the desirable eigenvectors by explicit forms. Consequently, a negative curvature direction is computed in such a way that avoids the storage and the factorization of any matrix. We propose a modification of the L-BFGS method in which no information is kept from old iterations, so that memory requirements are minimal. The proposed algorithm incorporates a curvilinear path and a linesearch procedure, which combines two search directions; a memoryless quasi-Newton direction and a direction of negative curvature. Results of numerical experiments for large scale problems are also presented.     

The use of approximate factorization in stiff ODE solvers

We consider implicit integration methods for the numerical solution of stiff initial-value problems. In applying such methods, the implicit relations are usually solved by Newton iteration. However, it often happens that in subintervals of the integration interval the problem is nonstiff or mildly stiff with respect to the stepsize. In these nonstiff subintervals, we do not need the (expensive) Newton iteration process. This motivated us to look for an iteration process that converges in mildly stiff situations and is less costly than Newton iteration. The process we have in mind uses modified Newton iteration as the outer iteration process and a linear solver for solving the linear Newton systems as an inner iteration process. This linear solver is based on an approximate factorization of the Newton system matrix by splitting this matrix into its lower and upper triangular part. The purpose of this paper is to combine fixed point iteration, approximate factorization iteration and Newton iteration into one iteration process for use in initial-value problems where the degree of stiffness is changing during the integration.     

An alternating direction and projection algorithm for structure-enforced matrix factorization

Structure-enforced matrix factorization (SeMF) represents a large class of mathematical models appearing in various forms of principal component analysis, sparse coding, dictionary learning and other machine learning techniques useful in many applications including neuroscience and signal processing. In this paper, we present a unified algorithm framework, based on the classic alternating direction method of multipliers (ADMM), for solving a wide range of SeMF problems whose constraint sets permit low-complexity projections. We propose a strategy to adaptively adjust the penalty parameters which is the key to achieving good performance for ADMM. We conduct extensive numerical experiments to compare the proposed algorithm with a number of state-of-the-art special-purpose algorithms on test problems including dictionary learning for sparse representation and sparse nonnegative matrix factorization. Results show that our unified SeMF algorithm can solve different types of factorization problems as reliably and as efficiently as special-purpose algorithms. In particular, our SeMF algorithm provides the ability to explicitly enforce various combinatorial sparsity patterns that, to our knowledge, has not been considered in existing approaches.     

A total least squares method for Toeplitz systems of equations

A Newton method to solve total least squares problems for Toeplitz systems of equations is considered. When coupled with a bisection scheme, which is based on an efficient algorithm for factoring Toeplitz matrices, global convergence can be guaranteed. Circulant and approximate factorization preconditioners are proposed to speed convergence when a conjugate gradient method is used to solve linear systems arising during the Newton iterations. The work of the second author was partially supported by a National Science Foundation Postdoctoral Research Fellowship.     

A lifting and recombination algorithm for rational factorization of sparse polynomials

We propose a new lifting and recombination scheme for rational bivariate polynomial factorization that takes advantage of the Newton polytope geometry. We obtain a deterministic algorithm that can be seen as a sparse version of an algorithm of Lecerf, with a polynomial complexity in the volume of the Newton polytope. We adopt a geometrical point of view, the main tool being derived from some algebraic osculation criterion in toric varieties.     

A PREDICTOR-CORRECTOR INTERIOR-POINT ALGORITHM FOR CONVEX QUADRATIC PROGRAMMING

The simplified Newton method, at the expense of fast convergence, reduces the work required by Newton method by reusing the initial Jacobian matrix. The composite Newton method attempts to balance the trade-off between expense and fast convergence by composing one Newton step with one simplified Newton step. Recently, Mehrotra suggested a predictor-corrector variant of primal-dual interior point method for linear programming. It is currently the interior-point method of the choice for linear programming. In this work we propose a predictor-corrector interior-point algorithm for convex quadratic programming. It is proved that the algorithm is equivalent to a level-1 perturbed composite Newton method. Computations in the algorithm do not require that the initial primal and dual points be feasible. Numerical experiments are made.     

A fast algorithm for equality-constrained quadratic programming on the alliant FX/8

An efficient implementation of the null-space method for quadratic programming on the Alliant FX/8 computer is described. The most computationally significant operations in this method are the orthogonal factorization of the constraint matrix and corresponding similarity transformation of the Hessian, and the Cholesky factorization of the reduced Hessian matrix. It is shown how these can be implemented in such a way as to take full advantage of the Alliant's parallel/vector capabilities and memory hierarchy. Timing results are given on a set of test problems for which the data can be easily accommodated in core memory. Note: Research partially supported by the Air Force office of Scientific Research under grant AFOSR-ISSA-870092 and the National Science Foundation under grant DMS-8619903.     

Pivoting strategy for rank-one modification ofLDM t-like factorization

The rank-one modification algorithm of theLDM ^t factorization was given by Bennett [1]. His method, however, could break down even when the matrix is nonsingular and well-conditioned. We introduce a pivoting strategy for avoiding possible break-down as well as for suppressing error growth in the modification process. The method is based on a symbolic formula of the rank-one modification of the factorization of a possibly singular nonsymmetric matrix. A new symbolic formula is also obtained for the inverses of the factor matrices. Repeated application of our method produces theLDM ^t-like product form factorization of a matrix. A numerical example is given to illustrate our pivoting method. An incomplete factorization algorithm is also introduced for updating positive definite matrix useful in quasi-Newton methods, in which the Fletcher and Powell algorithm [2] and the Gill, Murray and Saunders algorithm [4] are usually used.This paper is presented at the Japan SIAM Annual Meeting held at University of Tokyo, Japan, October 7–9, 1991.     

Hierarchical Interpolative Factorization for Elliptic Operators: Integral Equations

This paper introduces the hierarchical interpolative factorization for integral equations (HIF‐IE) associated with elliptic problems in two and three dimensions. This factorization takes the form of an approximate generalized LU decomposition that permits the efficient application of the discretized operator and its inverse. HIF‐IE is based on the recursive skeletonization algorithm but incorporates a novel combination of two key features: (1) a matrix factorization framework for sparsifying structured dense matrices and (2) a recursive dimensional reduction strategy to decrease the cost. Thus, higher‐dimensional problems are effectively mapped to one dimension, and we conjecture that constructing, applying, and inverting the factorization all have linear or quasilinear complexity. Numerical experiments support this claim and further demonstrate the performance of our algorithm as a generalized fast multipole method, direct solver, and preconditioner. HIF‐IE is compatible with geometric adaptivity and can handle both boundary and volume problems.© 2016 Wiley Periodicals, Inc.     

Sparse quadratic programming in chemical process optimization

The quadratic programming aspects of a full space successive quadratic programming (SQP) method are described. In particular, fill-in, matrix factor and active set updating, numerical stability, and indefiniteness of the Hessian matrix are discussed in conjunction with a sparse modification of Bunch and Parlett factorization of symmetric indefinite (Kuhn-Tucker) matrices of the type often encountered in optimization. A new pivoting strategy, called constrained pivoting, is proposed to reduce fill-in and compared with complete, partial and threshold pivoting. It is shown that constrained pivoting often significantly reduces fill-in and thus the iterative computational burdens associated with the factorization and solution of Kuhn-Tucker conditions within the QP subproblem. A numerical algorithm for updating the lower triangular and diagonal factors is presented and shown to be very fast, usually requiring only about 5% of the cost of refactorization. Two active set strategies are also presented. These include the options of adding inequalities either one or several at a time. In either case, the effects on matrix factor updating is shown to be small. Finally, a simple test is used to maintain iterative descent directions in the quadratic program. Our sparse symmetric indefinite QP algorithm is tested in the context of a family of SQP algorithms that include a full space Newton method with analytical derivatives, a full space BFGS method and a Range and Null space Decomposition (RND) method in which the projected Hessian is calculated from either analytical second derivatives or the BFGS update. Several chemical process optimization problems, with small and large degrees of freedom, are used as test problems. These include minimum work calculations for multistage isothermal compression, minimum area targeting for heat exchanger networks, and distillation optimizations involving some azeotropic and extractive distillations. Numerical results show uniformly that both the proposed QP and SQP algorithms, particularly the full space Newton method, are reliable and efficient. No failures were experienced at either level.     

Scaled Optimal Path Trust-Region Algorithm

Trust-region algorithms solve a trust-region subproblem at each iteration. Among the methods solving the subproblem, the optimal path algorithm obtains the solution to the subproblem in full-dimensional space by using the eigenvalues and eigenvectors of the system. Although the idea is attractive, the existing optimal path method seems impractical because, in addition to factorization, it requires either the calculation of the full eigensystem of a matrix or repeated factorizations of matrices at each iteration. In this paper, we propose a scaled optimal path trust-region algorithm. The algorithm finds a solution of the subproblem in full-dimensional space by just one Bunch–Parlett factorization for symmetric matrices at each iteration and by using the resulting unit lower triangular factor to scale the variables in the problem. A scaled optimal path can then be formed easily. The algorithm has good convergence properties under commonly used conditions. Computational results for small-scale and large-scale optimization problems are presented which show that the algorithm is robust and effective.     

An alternating direction algorithm for matrix completion with nonnegative factors

This paper introduces an algorithm for the nonnegative matrix factorization-and-completion problem, which aims to find nonnegative low-rank matrices X and Y so that the product XY approximates a nonnegative data matrix M whose elements are partially known (to a certain accuracy). This problem aggregates two existing problems: (i) nonnegative matrix factorization where all entries of M are given, and (ii) low-rank matrix completion where nonnegativity is not required. By taking the advantages of both nonnegativity and low-rankness, one can generally obtain superior results than those of just using one of the two properties. We propose to solve the non-convex constrained least-squares problem using an algorithm based on the classical alternating direction augmented Lagrangian method. Preliminary convergence properties of the algorithm and numerical simulation results are presented. Compared to a recent algorithm for nonnegative matrix factorization, the proposed algorithm produces factorizations of similar quality using only about half of the matrix entries. On tasks of recovering incomplete grayscale and hyperspectral images, the proposed algorithm yields overall better qualities than those produced by two recent matrix-completion algorithms that do not exploit nonnegativity.     

Determination of a matrix function using the divided difference method of Newton and the interpolation technique of Hermite

Computing a function f(A) of an n-by-n matrix A is a frequently occurring problem in control theory and other applications. In this paper we introduce an effective approach for the determination of matrix function f(A). We propose a new technique which is based on the extension of Newton divided difference and the interpolation technique of Hermite and using the eigenvalues of the given matrix A. The new algorithm is tested on several problems to show the efficiency of the presented method. Finally, the application of this method in control theory is highlighted.     

Canonical Wiener–Hopf and spectral factorization of large-degree matrix polynomials

We present a novel Newton method for canonical Wiener–Hopf and spectral factorization of matrix polynomials. The initial vector results from solving a block Toeplitz-like system, and the Jacobi matrix governing the Newton iteration has nice structural and numerical properties. The local quadratic convergence of the method is proved and was tested numerically. For scalar polynomials of degree 20000, a superfast version of the method implemented on a laptop typically reqired about half a minute to produce an initial vector and then performed the Newton iteration within one second. In the matrix case, the method worked reproachless on a laptop with 8 Gigabyte RAM if the degree of the polynomial times the squared matrix dimension did not exceed 20000. (© 2014 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)