A chordal preconditioner for large-scale optimization

We propose an automatic preconditioning scheme for large sparse numerical optimization. The strategy is based on an examination of the sparsity pattern of the Hessian matrix: using a graph-theoretic heuristic, a block-diagonal approximation to the Hessian matrix is induced. The blocks are submatrices of the Hessian matrix; furthermore, each block is chordal. That is, under a positive definiteness assumption, the Cholesky factorization can be applied to each block without creating any new nonzeros (fill). Therefore the preconditioner is space efficient. We conduct a number of numerical experiments to determine the effectiveness of the preconditioner in the context of a linear conjugate-gradient algorithm for optimization.     

Convergence analysis of truncated incomplete Hessian Newton minimization method and application in biomolecular potential energy minimization

This paper gives a general convergence analysis to the truncated incomplete Hessian Newton method (T-IHN). It shows that T-IHN is globally convergent even with an indefinite incomplete Hessian matrix or an indefinite preconditioner, which may happen in practice. It also proves that when the T-IHN iterates are close enough to a minimum point, T-IHN has a Q-linear rate of convergence, and an admissible line search steplength of one. Moreover, a particular T-IHN algorithm is constructed for minimizing a biomolecular potential energy function, and numerically tested for a protein model problem based on a widely used molecular simulation package, CHARMM. Numerical results confirm the theoretical results, and demonstrate that T-IHN can have a better performance (in terms of computer CPU time) than most CHARMM minimizers.     

A preconditioning technique for a class of PDE-constrained optimization problems

We investigate the use of a preconditioning technique for solving linear systems of saddle point type arising from the application of an inexact Gauss?CNewton scheme to PDE-constrained optimization problems with a hyperbolic constraint. The preconditioner is of block triangular form and involves diagonal perturbations of the (approximate) Hessian to insure nonsingularity and an approximate Schur complement. We establish some properties of the preconditioned saddle point systems and we present the results of numerical experiments illustrating the performance of the preconditioner on a model problem motivated by image registration.     

Proximal point algorithm with Schur decomposition on the cone of symmetric semidefinite positive matrices

In this work, we propose a proximal algorithm for unconstrained optimization on the cone of symmetric semidefinite positive matrices. It appears to be the first in the proximal class on the set of methods that convert a Symmetric Definite Positive Optimization in Nonlinear Optimization. It replaces the main iteration of the conceptual proximal point algorithm by a sequence of nonlinear programming problems on the cone of diagonal definite positive matrices that has the structure of the positive orthant of the Euclidian vector space. We are motivated by results of the classical proximal algorithm extended to Riemannian manifolds with nonpositive sectional curvature. An important example of such a manifold is the space of symmetric definite positive matrices, where the metrics is given by the Hessian of the standard barrier function −lndet(X). Observing the obvious fact that proximal algorithms do not depend on the geodesics, we apply those ideas to develop a proximal point algorithm for convex functions in this Riemannian metric.     

Matrix probing: A randomized preconditioner for the wave-equation Hessian

This paper considers the problem of approximating the inverse of the wave-equation Hessian, also called normal operator, in seismology and other types of wave-based imaging. An expansion scheme for the pseudodifferential symbol of the inverse Hessian is set up. The coefficients in this expansion are found via least-squares fitting from a certain number of applications of the normal operator on adequate randomized trial functions built in curvelet space. It is found that the number of parameters that can be fitted increases with the amount of information present in the trial functions, with high probability. Once an approximate inverse Hessian is available, application to an image of the model can be done in very low complexity. Numerical experiments show that randomized operator fitting offers a compelling preconditioner for the linearized seismic inversion problem.     

Preconditioning the Pressure Tracking in Fluid Dynamics by Shape Hessian Information

Potential flow pressure matching is a classical inverse design aerodynamic problem. The resulting loss of regularity during the optimization poses challenges for shape optimization with normal perturbation of the surface mesh nodes. Smoothness is not enforced by the parameterization but by a proper choice of the scalar product based on the shape Hessian, which is derived in local coordinates for starshaped domains. Significant parts of the Hessian are identified and combined with an aerodynamic panel solver. The resulting shape Hessian preconditioner is shown to lead to superior convergence properties of the resulting optimization method. Additionally, preconditioning gives the potential for level independent convergence.     

Strong Convergence of an Inexact Proximal Point Algorithm for Equilibrium Problems in Banach Spaces

We develop an inexact proximal point algorithm for solving equilibrium problems in Banach spaces which consists of two principal steps and admits an interesting geometric interpretation. At a certain iterate, first we solve an inexact regularized equilibrium problem with a flexible error criterion to obtain an axillary point. Using this axillary point and the inexact solution of the previous iterate, we construct two appropriate hyperplanes which separate the current iterate from the solution set of the given problem. Then the next iterate is defined as the Bregman projection of the initial point onto the intersection of two halfspaces obtained from the two constructed hyperplanes containing the solution set of the original problem. Assuming standard hypotheses, we present a convergence analysis for our algorithm, establishing that the generated sequence strongly and globally converges to a solution of the problem which is the closest one to the starting point of the algorithm.     

Algebraic multigrid preconditioning of the Hessian in optimization constrained by a partial differential equation

We construct an algebraic multigrid (AMG) based preconditioner for the reduced Hessian of a linear‐quadratic optimization problem constrained by an elliptic partial differential equation. While the preconditioner generalizes a geometric multigrid preconditioner introduced in earlier works, its construction relies entirely on a standard AMG infrastructure built for solving the forward elliptic equation, thus allowing for it to be implemented using a variety of AMG methods and standard packages. Our analysis establishes a clear connection between the quality of the preconditioner and the AMG method used. The proposed strategy has a broad and robust applicability to problems with unstructured grids, complex geometry, and varying coefficients. The method is implemented using the Hypre package and several numerical examples are presented.     

二维Helmholtz方程的联合紧致差分离散方程组的预处理方法

对于二维的Helmholtz方程,本文用联合紧致差分格式(CCD)离散,该差分格式具有六阶精度,三点差分和隐式的特点.本文基于CCD格式离散得到的线性系统和循环矩阵的快速傅里叶变换,提出了一种循环型预处理算子用于广义极小残量迭代算法(GMRES).给出了循环型预处理子的求解算法,证明了该预处理算子能使迭代算法具有较快的收敛速度.本文还与其他算法的预处理算子作比较,数值结果表明本文提出的循环型预处理算子具有更好的稳定性,并且对于较大的波数k,收敛速度也更快.     

Matrix-free interior point method

In this paper we present a redesign of a linear algebra kernel of an interior point method to avoid the explicit use of problem matrices. The only access to the original problem data needed are the matrix-vector multiplications with the Hessian and Jacobian matrices. Such a redesign requires the use of suitably preconditioned iterative methods and imposes restrictions on the way the preconditioner is computed. A two-step approach is used to design a preconditioner. First, the Newton equation system is regularized to guarantee better numerical properties and then it is preconditioned. The preconditioner is implicit, that is, its computation requires only matrix-vector multiplications with the original problem data. The method is therefore well-suited to problems in which matrices are not explicitly available and/or are too large to be stored in computer memory. Numerical properties of the approach are studied including the analysis of the conditioning of the regularized system and that of the preconditioned regularized system. The method has been implemented and preliminary computational results for small problems limited to 1 million of variables and 10 million of nonzero elements demonstrate the feasibility of the approach.     

Uzawa type algorithms for nonsymmetric saddle point problems

In this paper, we consider iterative algorithms of Uzawa type for solving linear nonsymmetric saddle point problems. Specifically, we consider systems, written as usual in block form, where the upper left block is an invertible linear operator with positive definite symmetric part. Such saddle point problems arise, for example, in certain finite element and finite difference discretizations of Navier-Stokes equations, Oseen equations, and mixed finite element discretization of second order convection-diffusion problems. We consider two algorithms, each of which utilizes a preconditioner for the operator in the upper left block. Convergence results for the algorithms are established in appropriate norms. The convergence of one of the algorithms is shown assuming only that the preconditioner is spectrally equivalent to the inverse of the symmetric part of the operator. The other algorithm is shown to converge provided that the preconditioner is a sufficiently accurate approximation of the inverse of the upper left block. Applications to the solution of steady-state Navier-Stokes equations are discussed, and, finally, the results of numerical experiments involving the algorithms are presented.

     

An efficient curvilinear method for the minimization of a nonlinear function subject to linear inequality constraints

An algorithm is presented that minimizes a continuously differentiable function in several variables subject to linear inequality constraints. At each step of the algorithm an arc is generated along which a move is performed until either a point yielding a sufficient descent in the function value is determined or a constraint boundary is encountered. The decision to delite a constraint from the list of active constraints is based upon periodic estimates of the Kuhn-Tucker multipliers. The curvilinear search paths are obtained by solving a linear approximation to the differential equation of the continuous steepest descent curve for the objective function on the equality constrained region defined by the constraints which are required to remain binding. If the Hessian matrix of the objective function has certain properties and if the constraint gradients are linearly independent, the sequence generated by the algorithm converges to a point satisfying the Kuhn-Tucker optimality conditions at a rate that is at least quadratic.     

An Accelerated Inexact Proximal Point Algorithm for Convex Minimization

The proximal point algorithm is classical and popular in the community of optimization. In practice, inexact proximal point algorithms which solve the involved proximal subproblems approximately subject to certain inexact criteria are truly implementable. In this paper, we first propose an inexact proximal point algorithm with a new inexact criterion for solving convex minimization, and show its O(1/k) iteration-complexity. Then we show that this inexact proximal point algorithm is eligible for being accelerated by some influential acceleration schemes proposed by Nesterov. Accordingly, an accelerated inexact proximal point algorithm with an iteration-complexity of O(1/k ²) is proposed.     

Robust regression for mixed Poisson–Gaussian model

This paper focuses on efficient computational approaches to compute approximate solutions of a linear inverse problem that is contaminated with mixed Poisson–Gaussian noise, and when there are additional outliers in the measured data. The Poisson–Gaussian noise leads to a weighted minimization problem, with solution-dependent weights. To address outliers, the standard least squares fit-to-data metric is replaced by the Talwar robust regression function. Convexity, regularization parameter selection schemes, and incorporation of non-negative constraints are investigated. A projected Newton algorithm is used to solve the resulting constrained optimization problem, and a preconditioner is proposed to accelerate conjugate gradient Hessian solves. Numerical experiments on problems from image deblurring illustrate the effectiveness of the methods.     

Simultaneous Pseudo-Timestepping for PDE-Model Based Optimization Problems

In this paper we present a new method for the solution of optimization problems with PDE constraints. It is based on simultaneous pseudo-time stepping for evolution equations. The new method can be viewed as a continuous reduced SQP method in the sense that it uses a preconditioner derived from that method. The reduced Hessian in the preconditioner is approximated by a pseudo-differential operator, whose symbol can be investigated analytically. We apply our method to a boundary control model problem. The new optimization method needs 3.2-times the overall computational effort of the solution of simulation problem alone.     

Combining a hybrid preconditioner and a optimal adjustment algorithm to accelerate the convergence of interior point methods

In this work, the optimal adjustment algorithm for p coordinates, which arose from a generalization of the optimal pair adjustment algorithm is used to accelerate the convergence of interior point methods using a hybrid iterative approach for solving the linear systems of the interior point method. Its main advantages are simplicity and fast initial convergence. At each interior point iteration, the preconditioned conjugate gradient method is used in order to solve the normal equation system. The controlled Cholesky factorization is adopted as the preconditioner in the first outer iterations and the splitting preconditioner is adopted in the final outer iterations. The optimal adjustment algorithm is applied in the preconditioner transition in order to improve both speed and robustness. Numerical experiments on a set of linear programming problems showed that this approach reduces the total number of interior point iterations and running time for some classes of problems. Furthermore, some problems were solved only when the optimal adjustment algorithm for p coordinates was used in the change of preconditioners.     

Superlinearly convergent variable metric algorithms for general nonlinear programming problems

In this paper sufficient conditions for local and superlinear convergence to a Kuhn—Tucker point are established for a class of algorithms which may be broadly defined and comprise a quadratic programming algorithm for repeated solution of a subproblem and a variable metric update to develop the Hessian in the subproblem. In particular the DFP update and an update attributed to Powell are shown to provide a superlinear convergent subclass of algorithms provided a start is made sufficiently close to the solution and the initial Hessian in the subproblem is sufficiently close to the Hessian of the Lagrangian at this point.This research was supported in part by the National Science Foundation under Grants ENG 75-10486 and GJ 35292.     

广义鞍点问题的松弛维数分解预条件子

本文将Benzi等提出的松弛维数分解(Relaxed dimensionalfactorization, RDF)预条件子进一步推广到广义鞍点问题上,并称为GRDF(Generalized RDF)预条件子.该预条件子可看做是用维数分裂迭代法求解广义鞍点问题而导出的改进维数分裂(Modified dimensional split, MDS)预条件子的松弛形式, 它相比MDS预条件子更接近于系数矩阵, 因而结合Krylov子空间方法(如GMRES)有更快的收敛速度.文中分析了GRDF预处理矩阵特征值的一些性质,并用数值算例验证了新预条件子的有效性.     

Shape optimisation analysing the inner structure of sensitivity matrices

This contribution deals with sensitivity analysis in nodal based shape optimisation. Sensitivity analysis is one of the most important parts of a structural optimisation algorithm. The efficiency of the algorithm mainly depends on the obtained sensitivity information. The pseudo load and sensitivity matrices which appear in sensitivity analysis are commonly used to derive and to calculate the gradients and the Hessian matrices of objective functions and of constraints. The aim of this contribution is to show that these matrices contain additional useful information which is not used in structural optimisation until now. We demonstrate the opportunities and capabilities of the new information which are obtained by singular value decomposition (SVD) of the pseudo load and sensitivity matrices and by eigenvalue decomposition of the Hessian matrix. Furthermore, we avoid jagged boundaries in shape optimisation by applying a density filtering technique well-known in topology optimisation. Numerical examples illustrate the advocated theoretical concept. (© 2011 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Frequency based preconditioning and smoothing for shape optimization

In this paper, we present a smoothing technique which can be understood as a Quasi-Newton method. The idea of this preconditioner is that it approximates the symbol of the inverse Hessian, which has smoothing behavior. This symbol is derived analytically for the Stokes equations and investigated numerically for a flow with a Reynolds number of 80. The resulting symbol is then approximated by differential operators, which will lead to a method similar to Sobolev Smoothing. (© 2016 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)