Monotone and nonmonotone trust-region-based algorithms for large scale unconstrained optimization problems

Two trust regions algorithms for unconstrained nonlinear optimization problems are presented: a monotone and a nonmonotone one. Both of them solve the trust region subproblem by the spectral projected gradient (SPG) method proposed by Birgin, Martínez and Raydan (in SIAM J. Optim. 10(4):1196?C1211, 2000). SPG is a nonmonotone projected gradient algorithm for solving large-scale convex-constrained optimization problems. It combines the classical projected gradient method with the spectral gradient choice of steplength and a nonmonotone line search strategy. The simplicity (only requires matrix-vector products, and one projection per iteration) and rapid convergence of this scheme fits nicely with globalization techniques based on the trust region philosophy, for large-scale problems. In the nonmonotone algorithm the trial step is evaluated by acceptance via a rule which can be considered a generalization of the well known fraction of Cauchy decrease condition and a generalization of the nonmonotone line search proposed by Grippo, Lampariello and Lucidi (in SIAM J. Numer. Anal. 23:707?C716, 1986). Convergence properties and extensive numerical results are presented. Our results establish the robustness and efficiency of the new algorithms.     

A smoothing inexact Newton method for nonlinear complementarity problems

In this article, we propose a new smoothing inexact Newton algorithm for solving nonlinear complementarity problems (NCP) base on the smoothed Fischer-Burmeister function. In each iteration, the corresponding linear system is solved only approximately. The global convergence and local superlinear convergence are established without strict complementarity assumption at the NCP solution. Preliminary numerical results indicate that the method is effective for large-scale NCP.     

Preconditioning by Projectors in the Solution of Contact Problems: A Parallel Implementation

A non-overlapping domain decomposition algorithm of the Neumann–Neumann type for solving contact problems of elasticity is presented. Using the duality theory of convex programming, the discretized problem turns into a quadratic one with equality and bound constraints. The dual problem is modified by orthogonal projectors to the natural coarse space. The resulting problem is solved by an augmented Lagrangian algorithm. The projectors ensure an optimal convergence rate for the solution of the auxiliary linear problems by the preconditioned conjugate gradient method. Relevant aspects on the numerical linear algebra of these problems are presented, together with an efficient parallel implementation of the method.     

解可分离结构变分不等式的一种新的交替方向法

交替方向法是求解可分离结构变分不等式问题的经典方法之一, 它将一个大型的变分不等式问题分解成若干个小规模的变分不等式问题进行迭代求解. 但每步迭代过程中求解的子问题仍然摆脱不了求解变分不等式子问题的瓶颈. 从数值计算上来说, 求解一个变分不等式并不是一件容易的事情.因此, 本文提出一种新的交替方向法, 每步迭代只需要求解一个变分不等式子问题和一个强单调的非线性方程组子问题. 相对变分不等式问题而言, 我们更容易、且有更多的有效算法求解一个非线性方程组问题. 在与经典的交替方向法相同的假设条件下, 我们证明了新算法的全局收敛性. 进一步的数值试验也验证了新算法的有效性.     

Preconditioning and iterative solution of symmetric indefinite linear systems arising from interior point methods for linear programming

We propose to compute the search direction at each interior-point iteration for a linear program via a reduced augmented system that typically has a much smaller dimension than the original augmented system. This reduced system is potentially less susceptible to the ill-conditioning effect of the elements in the (1,1) block of the augmented matrix. A preconditioner is then designed by approximating the block structure of the inverse of the transformed matrix to further improve the spectral properties of the transformed system. The resulting preconditioned system is likely to become better conditioned toward the end of the interior-point algorithm. Capitalizing on the special spectral properties of the transformed matrix, we further proposed a two-phase iterative algorithm that starts by solving the normal equations with PCG in each IPM iteration, and then switches to solve the preconditioned reduced augmented system with symmetric quasi-minimal residual (SQMR) method when it is advantageous to do so. The experimental results have demonstrated that our proposed method is competitive with direct methods in solving large-scale LP problems and a set of highly degenerate LP problems. Research supported in parts by NUS Research Grant R146-000-076-112 and SMA IUP Research Grant.     

Interior-Point Methods with Decomposition for Solving Large-Scale Linear Programs

This paper deals with an algorithm incorporating the interior-point method into the Dantzig–Wolfe decomposition technique for solving large-scale linear programming problems. The algorithm decomposes a linear program into a main problem and a subproblem. The subproblem is solved approximately. Hence, inexact Newton directions are used in solving the main problem. We show that the algorithm is globally linearly convergent and has polynomial-time complexity.     

On the iterative solution of KKT systems in potential reduction software for large-scale quadratic problems

Iterative solvers appear to be very promising in the development of efficient software, based on Interior Point methods, for large-scale nonlinear optimization problems. In this paper we focus on the use of preconditioned iterative techniques to solve the KKT system arising at each iteration of a Potential Reduction method for convex Quadratic Programming. We consider the augmented system approach and analyze the behaviour of the Constraint Preconditioner with the Conjugate Gradient algorithm. Comparisons with a direct solution of the augmented system and with MOSEK show the effectiveness of the iterative approach on large-scale sparse problems. Work partially supported by the Italian MIUR FIRB Project Large Scale Nonlinear Optimization, grant no. RBNE01WBBB.     

Tensor-Krylov methods for large nonlinear equations

In this paper, we describe tensor methods for large systems of nonlinear equations based on Krylov subspace techniques for approximately solving the linear systems that are required in each tensor iteration. We refer to a method in this class as a tensor-Krylov algorithm. We describe comparative testing for a tensor-Krylov implementation versus an analogous implementation based on a Newton-Krylov method. The test results show that tensor-Krylov methods are much more efficient and robust than Newton-Krylov methods on hard nonlinear equations problems.Part of this work was performed while the author was research associate at CERFACS (Centre Européen de Recherche et de Formation Avancée en Calcul Scientifique).Research supported in part by the Office of Scientific Computing, U.S. Department of Energy, under Contract W-31-109-Eng-38.     

Multipoint Boundary-Value Solution of Two-Point Boundary-Value Problems

An iterative scheme, in which two-point boundary-value problems (TPBVP) are solved as multipoint boundary-value problems (MPBVP), which are independent TPBVPs in each iteration and on each subdomain, is derived for second-order ordinary differential equations. Several equations are solved for illustration. In particular, the algorithm is described in detail for the first boundary-value problem (FBVP) and second boundary-value problem (SBVP). A possible extension to higher-order BVPs is discussed briefly. The procedure may be used when the original TPBVP cannot be solved (does not converge) in a single long domain. It is suitable for implementation on computers with parallel processing. However, that issue is beyond the scope of this paper. The long domain is cut into a large number of subdomains and, based on assumed boundary conditions at the interface points, the resulting local BVPs are solved by any convenient conventional method. The local solutions are then patched by using simple matching formulas, which are derived below, rather than solving large systems of algebraic equations, as it is done in similar existing methods. Assuming that the local solutions are obtained by the most efficient methods, the overall convergence speed depends on the speed of matching. The proposed matching algorithm is based on a fixed-point iteration and has only a linear convergence rate. The rate can be made quadratic by applying standard accelerating schemes, which is beyond the scope of this article.     

On certain optimization methods with finite-step inner algorithms for convex finite-dimensional problems with inequality constraints

Numerical methods are proposed for solving finite-dimensional convex problems with inequality constraints satisfying the Slater condition. A method based on solving the dual to the original regularized problem is proposed and justified for problems having a strictly uniformly convex sum of the objective function and the constraint functions. Conditions for the convergence of this method are derived, and convergence rate estimates are obtained for convergence with respect to the functional, convergence with respect to the argument to the set of optimizers, and convergence to the g-normal solution. For more general convex finite-dimensional minimization problems with inequality constraints, two methods with finite-step inner algorithms are proposed. The methods are based on the projected gradient and conditional gradient algorithms. The paper is focused on finite-dimensional problems obtained by approximating infinite-dimensional problems, in particular, optimal control problems for systems with lumped or distributed parameters.     

Spectral projected gradient and variable metric methods for optimization with linear inequalities

A family of variable metric methods for convex constrained optimizationwas introduced recently by Birgin, Martínez and Raydan.One of the members of this family is the inexact spectral projectedgradient (ISPG) method for minimization with convex constraints.At each iteration of these methods a strictly convex quadraticfunction with convex constraints must be (inexactly) minimized.In the case of the ISPG method it was shown that, in some importantapplications, iterative projection methods can be used for thisminimization. In this paper the particular case in which theconvex domain is a polytope described by a finite set of linearinequalities is considered. For solving the linearly constrainedconvex quadratic subproblem a dual approach is adopted, by meansof which subproblems become (not necessarily strictly) convexquadratic minimization problems with box constraints. Thesesubproblems are solved by means of an active-set box-constraintquadratic optimizer with a proximal-point type unconstrainedalgorithm for minimization within the current faces. Convergenceresults and numerical experiments are presented.     

An adaptive nonmonotone global Barzilai–Borwein gradient method for unconstrained optimization

The Barzilai–Borwein (BB) gradient method has received many studies due to its simplicity and numerical efficiency. By incorporating a nonmonotone line search, Raydan (SIAM J Optim. 1997;7:26–33) has successfully extended the BB gradient method for solving general unconstrained optimization problems so that it is competitive with conjugate gradient methods. However, the numerical results reported by Raydan are poor for very ill-conditioned problems because the effect of the degree of nonmonotonicity may be noticeable. In this paper, we focus more on the nonmonotone line search technique used in the global Barzilai–Borwein (GBB) gradient method. We improve the performance of the GBB gradient method by proposing an adaptive nonmonotone line search based on the morphology of the objective function. We also prove the global convergence and the R-linear convergence rate of the proposed method under reasonable assumptions. Finally, we give some numerical experiments made on a set of unconstrained optimization test problems of the CUTEr collection. The results show the efficiency of the proposed method in the sense of the performance profile introduced (Math Program. 2002;91:201–213) by Dolan and Moré.     

非线性特征值问题的二次近似方法

本文研究求解非线性特征值问题的数值方法.基于矩阵值函数的二次近似,将非线性特征值问题转化为二次特征值问题,提出了求解非线性特征值问题的逐次二次近似方法,分析了该方法的收敛性.结合求解二次特征值问题的Arnoldi方法和Jacobi-Davidson方法,给出求解非线性特征值问题的一些二次近似方法.数值结果表明本文所给算法是有效的.     

Inexact Operator Splitting Methods with Selfadaptive Strategy for Variational Inequality Problems

The Peaceman-Rachford and Douglas-Rachford operator splitting methods are advantageous for solving variational inequality problems, since they attack the original problems via solving a sequence of systems of smooth equations, which are much easier to solve than the variational inequalities. However, solving the subproblems exactly may be prohibitively difficult or even impossible. In this paper, we propose an inexact operator splitting method, where the subproblems are solved approximately with some relative error tolerance. Another contribution is that we adjust the scalar parameter automatically at each iteration and the adjustment parameter can be a positive constant, which makes the methods more practical and efficient. We prove the convergence of the method and present some preliminary computational results, showing that the proposed method is promising. This work was supported by the NSFC grant 10501024.     

Parallel algorithms for nonlinear programming problems

This paper describes several parallel algorithms for solving nonlinear programming problems. Two approaches where parallelism can successfully be introduced have been explored: a quadratic approximation method based on penalty function and a dual method. These methods are improved by using two algorithms originally proposed for solving unconstrained problems: the parallel variable metric algorithm and the parallel Jacobson-Oksman algorithm. Even though general problems are dealt with, particular emphasis is placed on the potential of these parallel methods for separable programming problems. The numerical effectiveness of the algorithms is demonstrated on a set of test problems using a Cray-1S vector computer and serial computers (with respect to sequential versions of the same methods).These studies were sponsored in part by the CERT. The author would particularly like to thank Ph. Berger (LSI-ENSEEIHT), the researchers of the DERI (CERT) and of the Groupe Structures, Aerospatiale, for their assistance.     

Krylov subspace methods with deflation and balancing preconditioners for least squares problems

For solving least squares problems, the CGLS method is a typical method in the point of view of iterative methods. When the least squares problems are ill-conditioned, the convergence behavior of the CGLS method will present a deteriorated result. We expect to select other iterative Krylov subspace methods to overcome the disadvantage of CGLS. Here the GMRES method is a suitable algorithm for the reason that it is derived from the minimal residual norm approach, which coincides with least squares problems. Ken Hayami proposed BAGMRES for solving least squares problems in [\emph{GMRES Methods for Least Squares Problems, SIAM J. Matrix Anal. Appl., 31(2010)}, pp.2400-2430]. The deflation and balancing preconditioners can optimize the convergence rate through modulating spectral distribution. Hence, in this paper we utilize preconditioned iterative Krylov subspace methods with deflation and balancing preconditioners in order to solve ill-conditioned least squares problems. Numerical experiments show that the methods proposed in this paper are better than the CGLS method.     

A generalization of parameterized inexact Uzawa method for generalized saddle point problems

Recently, a class of parameterized inexact Uzawa methods has been proposed for generalized saddle point problems by Bai and Wang [Z.-Z. Bai, Z.-Q. Wang, On parameterized inexact Uzawa methods for generalized saddle point problems, Linear Algebra Appl. 428 (2008) 2900–2932], and a generalization of the inexact parameterized Uzawa method has been studied for augmented linear systems by Chen and Jiang [F. Chen, Y.-L. Jiang, A generalization of the inexact parameterized Uzawa methods for saddle point problems, Appl. Math. Comput. (2008)]. This paper is concerned about a generalization of the parameterized inexact Uzawa method for solving the generalized saddle point problems with nonzero (2, 2) blocks. Some new iterative methods are presented and their convergence are studied in depth. By choosing different parameter matrices, we derive a series of existing and new iterative methods, including the preconditioned Uzawa method, the inexact Uzawa method, the SOR-like method, the GSOR method, the GIAOR method, the PIU method, the APIU method and so on. Numerical experiments are used to demonstrate the feasibility and effectiveness of the generalized parameterized inexact Uzawa methods.     

Augmented Lagrangian Active Set Methods for Obstacle Problems

Active set strategies for two-dimensional and three-dimensional, unilateral and bilateral obstacle problems are described. Emphasis is given to algorithms resulting from the augmented Lagrangian (i.e., primal-dual formulation of the discretized obstacle problems), for which convergence and rate of convergence are considered. For the bilateral case, modifications of the basic primal-dual algorithm are also introduced and analyzed. Finally, efficient computer realizations that are based on multigrid and multilevel methods are suggested and different aspects of the proposed techniques are investigated through numerical experiments.     

Algorithms for large scale set covering problems

This paper is concerned with the set covering problem (SCP), and in particular with the development of a new algorithm capable of solving large-scale SCPs of the size found in real-life situations. The set covering problem has a wide variety of practical applications which, in general, yield large and sparse instances, normally with hundreds of rows and thousands of columns. In this paper, we present an algorithm capable of solving problems of this size and test problems up to 400 rows and 4000 columns are solved. The method developed in this paper consists of a tree-search procedure based on a combination of decomposition and state space relaxation which is a technique developed for obtaining lower bounds on the dynamic program associated with a combinatorial optimization problem. The large size SCPs are decomposed into many smaller SCPs which are then solved or bounded by state space relaxation (SSR). Before using the decomposition and SSR, reductions both in the number of columns and the number of rows of the problem are made by applying Lagrangian relaxation, linear programming and heuristic methods.     

An ODE-Based Trust Region Filter Algorithm for Unconstrained Optimization

In this article, an ODE-based trust region filter algorithm for unconstrained optimization is proposed. It can be regarded as a combination of trust region and filter techniques with ODE-based methods. Unlike the existing trust-region-filter methods and ODE-based methods, a distinct feature of this method is that at each iteration, a reduced linear system is solved to obtain a trial step, thus avoiding solving a trust region subproblem. Under some standard assumptions, it is proven that the algorithm is globally convergent. Preliminary numerical results show that the new algorithm is efficient for large scale problems.