1,721,044 research outputs found
CODOSOL: a bound-constrained nonlinear equations solver
No full textCoDoSol is a Matlab code for medium scale constrained nonlinear systems of equations F(x)=0, l R^n, l and u are vectors of dimension n. Non-existent lower and upper bounds, i.e. entries of l and u equal to minus o plus infinity, are allowed.
The code is based on an affine scaling trust region algorithm. The algorithm combines Newton method and trust region procedures where the merit function used is the norm of the nonlinear residual. The trust region and the corresponding scaled gradient are defined by suitable diagonal scaling avoiding the problem of running directly into a bound. The trust region problem is approximately solved by a constrained dogleg method. Only strictly feasible iterates are generated.
A great flexibility in choosing the scaling matrix is allowed for application dependent purposes.
If the problem has sparse Jacobians and a relatively big size, the user can choose to work with sparse memory storage. Then, the Newton step is computed via the built-in Matlab function LU with the syntax for calling the UMFPACK package when Matlab 6.5 or later versions are used.
Various input/output options are provided, and we refer to the code itself for further documentation.
Accompanying paper:
Bellavia S., Macconi M., Pieraccini S. (2012), Constrained dogleg methods for nonlinear systems with simple bounds. In: COMPUTATIONAL OPTIMIZATION AND APPLICATIONS, vol. 53 n. 3, pp. 771-794. - ISSN 0926-600
Numerical solution of KKT systems in PDE-constrained optimization problems via the affine scaling trust-region approach
No full textOn affine scaling inexact dogleg methods for bound-constrained nonlinear systems
Full text linkWithin the framework of affine scaling trust-region methods for bound constrained problems, we discuss the use of a inexact dogleg method as a tool for simultaneously handling the trust-region and the bound constraints while seeking for an approximate minimizer of the model. Focusing on bound-constrained systems of nonlinear equations, an inexact affine scaling method for large scale problems, employing the inexact dogleg procedure, is described. Global convergence results are established without any Lipschitz assumption on the Jacobian matrix, and locally fast convergence is shown under standard assumptions. Convergence analysis is performed without specifying the scaling matrix used to handle the bounds, and a rather general class of scaling matrices is allowed in actual algorithms. Numerical results showing the performance of the method are also given
Convergence analysis of an Inexact Infeasible Interior Point method for Semidefinite Programming
Full text linkIn this paper we present an extension to SDP of the well known infeasible Interior Point method for linear programming of Kojima,Megiddo and Mizuno (A primal-dual infeasible-interior-point algorithm for Linear Programming, Math. Progr., 1993). The extension developed here allows the use of inexact search directions; i.e., the linear systems defining the search directions can be solved with an accuracy that increases as the solution is approached. A convergence analysis is carried out and the global convergence of the method is prove
Constrained dogleg methods for nonlinear systems with simple bounds
Full text linkWe focus on the numerical solution of medium scale bound-constrained systems of nonlinear equations. In this context, we consider an affine-scaling trust region approach that allows a great flexibility in choosing the scaling matrix used to handle the bounds. The method is based on a dogleg procedure tailored for constrained problems and so, it is named Constrained Dogleg method. It generates only strictly feasible iterates. Global and locally fast convergence is ensured under standard assumptions. The method has been implemented in the Matlab solver CoDoSol that supports several diagonal scalings in both spherical and elliptical trust region frameworks. We give a brief account of CoDoSol and report on the computational experience performed on a number of representative test problem
Quasi Matrix Free Preconditioners in Optimization and Nonlinear Least-Squares
No full textThe approximate solution of several nonlinear optimization problems requires solving sequences of symmetric
linear systems. When the number of variables is large, it is advisable to use an iterative linear solver for the Newton correction
step. On the other hand, the underlying linear solver can converge slowly and the calculation of a preconditioner requires the
computation of the Hessian matrix which usually represents a major task in the implementation. We propose here a way to
overcome at least in part this two preconditioning issue
On the Convergence Properties of a Stochastic Trust-Region Method with Inexact Restoration
Full text linkWe study the convergence properties of SIRTR, a stochastic inexact restoration trust-region method suited for the minimization of a finite sum of continuously differentiable functions. This method combines the trust-region methodology with random function and gradient estimates formed by subsampling. Unlike other existing schemes, it forces the decrease of a merit function by combining the function approximation with an infeasibility term, the latter of which measures the distance of the current sample size from its maximum value. In a previous work, the expected iteration complexity to satisfy an approximate first-order optimality condition was given. Here, we elaborate on the convergence analysis of SIRTR and prove its convergence in probability under suitable accuracy requirements on random function and gradient estimates. Furthermore, we report the numerical results obtained on some nonconvex classification test problems, discussing the impact of the probabilistic requirements on the selection of the sample sizes
A Relaxed Interior Point Method for Low-Rank Semidefinite Programming Problems with Applications to Matrix Completion
Full text linkA new relaxed variant of interior point method for low-rank semidefinite programming problems is proposed in this paper. The method is a step outside of the usual interior point framework. In anticipation to converging to a low-rank primal solution, a special nearly low-rank form of all primal iterates is imposed. To accommodate such a (restrictive) structure, the first order optimality conditions have to be relaxed and are therefore approximated by solving an auxiliary least-squares problem. The relaxed interior point framework opens numerous possibilities how primal and dual approximated Newton directions can be computed. In particular, it admits the application of both the first- and the second-order methods in this context. The convergence of the method is established. A prototype implementation is discussed and encouraging preliminary computational results are reported for solving the SDP-reformulation of matrix-completion problems
On the update of constraint preconditioners for regularized KKT systems
No full textWe address the problem of preconditioning sequences of regularized KKT systems, such as those arising in interior point methods for convex quadratic programming. In this case, constraint preconditioners (CPs) are very effective and widely used; however, when solving large-scale problems, the computational cost for their factorization may be high, and techniques for approximating them appear as a convenient alternative. Here, given a block LDLT factorization of the CP associated with a KKT matrix of the sequence, called seed matrix, we present a technique for updating the factorization and building inexact CPs for subsequent matrices of the sequence. We have recently proposed an updating procedure that performs a low-rank correction of the Schur complement of the (1,1) block of the CP for the seed matrix. Now we focus on KKT sequences with nonzero (2,2) blocks and make a step further, by enriching the low-rank correction of the Schur complement by an additional cheap update. The latter update takes into account information not included in the former one and expressed as a diagonal modification of the low-rank correction. Theoretical results and numerical experiments show that the new strategy can be more effective than the procedure based on the low-rank modification alone
- …
