An algorithm for solving large nonlinear optimization problems with simple bounds is described. It is based on the gradient projection method and uses a limited memory BFGS matrix to approximate âŠ
An algorithm for solving large nonlinear optimization problems with simple bounds is described. It is based on the gradient projection method and uses a limited memory BFGS matrix to approximate the Hessian of the objective function. It is shown how to take advantage of the form of the limited memory approximation to implement the algorithm efficiently. The results of numerical tests on a set of large problems are reported.
L-BFGS-B is a limited-memory algorithm for solving large nonlinear optimization problems subject to simple bounds on the variables. It is intended for problems in which information on the Hessian matrix âŠ
L-BFGS-B is a limited-memory algorithm for solving large nonlinear optimization problems subject to simple bounds on the variables. It is intended for problems in which information on the Hessian matrix is difficult to obtain, or for large dense problems. L-BFGS-B can also be used for unconstrained problems and in this case performs similarly to its predessor, algorithm L-BFGS (Harwell routine VA15). The algorithm is implemented in Fortran 77.
Many large-scale problems in dynamic and stochastic optimization can be modeled with extended linear-quadratic programming, which admits penalty terms and treats them through duality. In general, the objective functions in âŠ
Many large-scale problems in dynamic and stochastic optimization can be modeled with extended linear-quadratic programming, which admits penalty terms and treats them through duality. In general, the objective functions in such problems are only piecewise smooth and must be minimized or maximized relative to polyhedral sets of high dimensionality. This paper proposes a new class of numerical methods for âfully quadraticâ problems within this framework, which exhibit second-order nonsmoothness. These methods, combining the idea of finite-envelope representation with that of modified gradient projection, work with local structure in the primal and dual problems simultaneously, feeding information back and forth to trigger advantageous restarts. Versions resembling steepest descent methods and conjugate gradient methods are presented. When a positive threshold of $\varepsilon $-optimality is specified, both methods converge in a finite number of iterations. With threshold 0, it is shown under mild assumptions that the steepest descent version converges linearly, while the conjugate gradient version still has a finite termination property. The algorithms are designed to exploit features of primal and dual decomposability of the Lagrangian, which are typically available in a large-scale setting, and they are open to considerable parallelization.
The asymptotic convergence of the forward-backward splitting algorithm for solving equations of type 0 â T(z) is analyzed, where T is a multivalued maximal monotone operator in the n-dimensional Euclidean âŠ
The asymptotic convergence of the forward-backward splitting algorithm for solving equations of type 0 â T(z) is analyzed, where T is a multivalued maximal monotone operator in the n-dimensional Euclidean space. When the problem has a nonempty solution set, and T is split in the form T = â± + h with â± being maximal monotone and h being co-coercive with modulus greater than Âœ, convergence rates are shown, under mild conditions, to be linear, superlinear or sublinear depending on how rapidly â± â1 and h â1 grow in the neighborhoods of certain specific points. As a special case, when both â± and h are polyhedral functions, we get R-linear convergence and 2-step Q-linear convergence without any further assumptions on the strict monotonicity on T or on the uniqueness of the solution. As another special case when h = 0, the splitting algorithm reduces to the proximal point algorithm, and we get new results, which complement R. T. Rockafellar's and F. J. Luque's earlier results on the proximal point algorithm.
The aim of this paper is two-fold. First, new variants are proposed for the primal-dual steepest descent algorithm as one in the family of primal-dual projected gradient algorithms developed by âŠ
The aim of this paper is two-fold. First, new variants are proposed for the primal-dual steepest descent algorithm as one in the family of primal-dual projected gradient algorithms developed by Zhu and Rockafellar [SIAM J. Optim., 3 (1993), pp. 751â783] for large-scale extended linear-quadratic programming. The variants include a second update scheme for the iterates, where the primal-dual feedback is arranged in a new pattern, as well as alternatives for the âperfect line searchâ in the original version of the reference. Second, new linear convergence results are proved for all these variants of the algorithm, including the original version as a special case, without the additional assumptions used by Zhu and Rockafellar. For the variants with the second update scheme, a much sharper estimation for the rate of convergence is obtained due to the new primal-dual feedback pattern.
The number $\gamma : = \| {\hat Q^{ - \frac{1}{2}} \hat R\hat P^{ - \frac{1} {2}} } \|$ is an important parameter for the extended linear-quadratic programming (ELQP) problem associated âŠ
The number $\gamma : = \| {\hat Q^{ - \frac{1}{2}} \hat R\hat P^{ - \frac{1} {2}} } \|$ is an important parameter for the extended linear-quadratic programming (ELQP) problem associated with the Lagrangian $L(\hat u,\hat v) = \hat p\cdot \hat u + \frac{1}{2}\hat u \cdot \hat P\hat u + \hat q \cdot \hat v - \frac{1}{2}\hat v \cdot \hat Q\hat v - \hat v \cdot \hat R\hat u$ over polyhedral sets $\hat U \times \hat V$. Some fundamental properties of the problem, as well as the convergence rates of certain newly developed algorithms for large-scale ELQP, are all related to $\gamma $. In this paper, we derive an estimate of $\gamma $ for the ELQP problems resulting from discretization of an optimal control problem. We prove that the parameter $\gamma $ of the discretized problem is bounded independently of the number of subintervals in the discretization.
L-BFGS-B is a limited-memory algorithm for solving large nonlinear optimization problems subject to simple bounds on the variables. It is intended for problems in which information on the Hessian matrix âŠ
L-BFGS-B is a limited-memory algorithm for solving large nonlinear optimization problems subject to simple bounds on the variables. It is intended for problems in which information on the Hessian matrix is difficult to obtain, or for large dense problems. L-BFGS-B can also be used for unconstrained problems and in this case performs similarly to its predessor, algorithm L-BFGS (Harwell routine VA15). The algorithm is implemented in Fortran 77.
The number $\gamma : = \| {\hat Q^{ - \frac{1}{2}} \hat R\hat P^{ - \frac{1} {2}} } \|$ is an important parameter for the extended linear-quadratic programming (ELQP) problem associated âŠ
The number $\gamma : = \| {\hat Q^{ - \frac{1}{2}} \hat R\hat P^{ - \frac{1} {2}} } \|$ is an important parameter for the extended linear-quadratic programming (ELQP) problem associated with the Lagrangian $L(\hat u,\hat v) = \hat p\cdot \hat u + \frac{1}{2}\hat u \cdot \hat P\hat u + \hat q \cdot \hat v - \frac{1}{2}\hat v \cdot \hat Q\hat v - \hat v \cdot \hat R\hat u$ over polyhedral sets $\hat U \times \hat V$. Some fundamental properties of the problem, as well as the convergence rates of certain newly developed algorithms for large-scale ELQP, are all related to $\gamma $. In this paper, we derive an estimate of $\gamma $ for the ELQP problems resulting from discretization of an optimal control problem. We prove that the parameter $\gamma $ of the discretized problem is bounded independently of the number of subintervals in the discretization.
An algorithm for solving large nonlinear optimization problems with simple bounds is described. It is based on the gradient projection method and uses a limited memory BFGS matrix to approximate âŠ
An algorithm for solving large nonlinear optimization problems with simple bounds is described. It is based on the gradient projection method and uses a limited memory BFGS matrix to approximate the Hessian of the objective function. It is shown how to take advantage of the form of the limited memory approximation to implement the algorithm efficiently. The results of numerical tests on a set of large problems are reported.
The asymptotic convergence of the forward-backward splitting algorithm for solving equations of type 0 â T(z) is analyzed, where T is a multivalued maximal monotone operator in the n-dimensional Euclidean âŠ
The asymptotic convergence of the forward-backward splitting algorithm for solving equations of type 0 â T(z) is analyzed, where T is a multivalued maximal monotone operator in the n-dimensional Euclidean space. When the problem has a nonempty solution set, and T is split in the form T = â± + h with â± being maximal monotone and h being co-coercive with modulus greater than Âœ, convergence rates are shown, under mild conditions, to be linear, superlinear or sublinear depending on how rapidly â± â1 and h â1 grow in the neighborhoods of certain specific points. As a special case, when both â± and h are polyhedral functions, we get R-linear convergence and 2-step Q-linear convergence without any further assumptions on the strict monotonicity on T or on the uniqueness of the solution. As another special case when h = 0, the splitting algorithm reduces to the proximal point algorithm, and we get new results, which complement R. T. Rockafellar's and F. J. Luque's earlier results on the proximal point algorithm.
The aim of this paper is two-fold. First, new variants are proposed for the primal-dual steepest descent algorithm as one in the family of primal-dual projected gradient algorithms developed by âŠ
The aim of this paper is two-fold. First, new variants are proposed for the primal-dual steepest descent algorithm as one in the family of primal-dual projected gradient algorithms developed by Zhu and Rockafellar [SIAM J. Optim., 3 (1993), pp. 751â783] for large-scale extended linear-quadratic programming. The variants include a second update scheme for the iterates, where the primal-dual feedback is arranged in a new pattern, as well as alternatives for the âperfect line searchâ in the original version of the reference. Second, new linear convergence results are proved for all these variants of the algorithm, including the original version as a special case, without the additional assumptions used by Zhu and Rockafellar. For the variants with the second update scheme, a much sharper estimation for the rate of convergence is obtained due to the new primal-dual feedback pattern.
Many large-scale problems in dynamic and stochastic optimization can be modeled with extended linear-quadratic programming, which admits penalty terms and treats them through duality. In general, the objective functions in âŠ
Many large-scale problems in dynamic and stochastic optimization can be modeled with extended linear-quadratic programming, which admits penalty terms and treats them through duality. In general, the objective functions in such problems are only piecewise smooth and must be minimized or maximized relative to polyhedral sets of high dimensionality. This paper proposes a new class of numerical methods for âfully quadraticâ problems within this framework, which exhibit second-order nonsmoothness. These methods, combining the idea of finite-envelope representation with that of modified gradient projection, work with local structure in the primal and dual problems simultaneously, feeding information back and forth to trigger advantageous restarts. Versions resembling steepest descent methods and conjugate gradient methods are presented. When a positive threshold of $\varepsilon $-optimality is specified, both methods converge in a finite number of iterations. With threshold 0, it is shown under mild assumptions that the steepest descent version converges linearly, while the conjugate gradient version still has a finite termination property. The algorithms are designed to exploit features of primal and dual decomposability of the Lagrangian, which are typically available in a large-scale setting, and they are open to considerable parallelization.
A generalized approach is taken to linear and quadratic programming in which dual as well as primal variables may be subjected to bounds, and constraints may be represented through penalties. âŠ
A generalized approach is taken to linear and quadratic programming in which dual as well as primal variables may be subjected to bounds, and constraints may be represented through penalties. Corresponding problem models in optimal control related to continuous-time programming are then set up and theorems on duality and the existence of solutions are derived. Optimality conditions are obtained in the form of a global saddle point property which decomposes into an instantaneous saddle point condition on the primal and dual control vectors at each time, along with an endpoint condition.
Many large-scale problems in dynamic and stochastic optimization can be modeled with extended linear-quadratic programming, which admits penalty terms and treats them through duality. In general, the objective functions in âŠ
Many large-scale problems in dynamic and stochastic optimization can be modeled with extended linear-quadratic programming, which admits penalty terms and treats them through duality. In general, the objective functions in such problems are only piecewise smooth and must be minimized or maximized relative to polyhedral sets of high dimensionality. This paper proposes a new class of numerical methods for âfully quadraticâ problems within this framework, which exhibit second-order nonsmoothness. These methods, combining the idea of finite-envelope representation with that of modified gradient projection, work with local structure in the primal and dual problems simultaneously, feeding information back and forth to trigger advantageous restarts. Versions resembling steepest descent methods and conjugate gradient methods are presented. When a positive threshold of $\varepsilon $-optimality is specified, both methods converge in a finite number of iterations. With threshold 0, it is shown under mild assumptions that the steepest descent version converges linearly, while the conjugate gradient version still has a finite termination property. The algorithms are designed to exploit features of primal and dual decomposability of the Lagrangian, which are typically available in a large-scale setting, and they are open to considerable parallelization.
For the problem of minimizing a lower semicontinuous proper convex function f on a Hilbert space, the proximal point algorithm in exact form generates a sequence $\{ z^k \} $ âŠ
For the problem of minimizing a lower semicontinuous proper convex function f on a Hilbert space, the proximal point algorithm in exact form generates a sequence $\{ z^k \} $ by taking $z^{k + 1} $ to be the minimizes of $f(z) + ({1 / {2c_k }})\| {z - z^k } \|^2 $, where $c_k > 0$. This algorithm is of interest for several reasons, but especially because of its role in certain computational methods based on duality, such as the Hestenes-Powell method of multipliers in nonlinear programming. It is investigated here in a more general form where the requirement for exact minimization at each iteration is weakened, and the subdifferential $\partial f$ is replaced by an arbitrary maximal monotone operator T. Convergence is established under several criteria amenable to implementation. The rate of convergence is shown to be âtypicallyâ linear with an arbitrarily good modulus if $c_k $ stays large enough, in fact superlinear if $c_k \to \infty $. The case of $T = \partial f$ is treated in extra detail. Application is also made to a related case corresponding to minimax problems.
Two fundamental classes of problems in large-scale linear and quadratic programming are described. Multistage problems covering a wide variety of models in dynamic programming and stochastic programming are represented in âŠ
Two fundamental classes of problems in large-scale linear and quadratic programming are described. Multistage problems covering a wide variety of models in dynamic programming and stochastic programming are represented in a new way. Strong properties of duality are revealed which support the development of iterative approximate techniques of solution in terms of saddlepoints. Optimality conditions are derived in a form that emphasizes the possibilities of decomposition.
The asymptotic convergence of the proximal point algorithm (PPA), for the solution of equations of type $0 \in Tz$, where T is a multivalued maximal monotone operator in a real âŠ
The asymptotic convergence of the proximal point algorithm (PPA), for the solution of equations of type $0 \in Tz$, where T is a multivalued maximal monotone operator in a real Hilbert space, is analyzed. When $0 \in Tz$ has a nonempty solution set $\bar Z$, convergence rates are shown to depend on how rapidly $T^{ - 1} $ grows away from $\bar Z$ in a neighbourhood of 0. When this growth is bounded by a power function with exponent s, then for a sequence $\{ z^k \} $ generated by the PPA, $\{ | {z^k - \bar Z} |\} $ converges to zero, like $o(k^{ - {s / 2}} )$, linearly, superlinearly, or in a finite number of steps according to whether, $s \in (0,1)$, $s = 1$, $s \in (1, + \infty )$, or $s = + \infty $.
Nondegeneracy conditions that guarantee that the optimal active constraints are identified in a finite number of iterations are studied. Results of this type have only been established for a few âŠ
Nondegeneracy conditions that guarantee that the optimal active constraints are identified in a finite number of iterations are studied. Results of this type have only been established for a few algorithms, and then under restrictive hypothesis. The main result is a characterization of those algorithms that identify the optimal constraints in a finite number of iterations. This result is obtained with a nondegeneracy assumption which is equivalent, in the standard nonlinear programming problem, to the assumption that there is a set of strictly complementary Lagrange multipliers. As an important consequence of the authors' results the way that this characterization applies to gradient projection and sequential quadratic programming algorithms is shown.
Recently Han and Lou proposed a highly parallelizable decomposition algorithm for minimizing a strongly convex cost over the intersection of closed convex sets. It is shown that their algorithm is âŠ
Recently Han and Lou proposed a highly parallelizable decomposition algorithm for minimizing a strongly convex cost over the intersection of closed convex sets. It is shown that their algorithm is in fact a special case of a splitting algorithm analyzed by Gabay for finding a zero of the sum of two maximal monotone operators. Gabayâs convergence analysis for the splitting algorithm is sharpened, and new applications of this algorithm to variational inequalities, convex programming, and the solution of linear complementarily problems are proposed. For convex programs with a certain separable structure, a multiplier method that is closely related to the alternating direction method of multipliers of GabayâMercier and of GlowinskiâMarrocco, but which uses both ordinary and augmented Lagrangians, is obtained.
We consider the problem $\min \{ f(x)|x \geqq 0\} $, and propose algorithms of the form $x_{k + 1} = [x_k - \alpha _k D_k \nabla f(x_k )]^ + $, âŠ
We consider the problem $\min \{ f(x)|x \geqq 0\} $, and propose algorithms of the form $x_{k + 1} = [x_k - \alpha _k D_k \nabla f(x_k )]^ + $, where $[ \cdot ]^ + $ denotes projection on the positive orthant, $\alpha _k $ is a stepsize chosen by an Armijo-like rule and $D_k $ is a positive definite symmetric matrix which is partly diagonal. We show that $D_k $ can be calculated simply on the basis of second derivatives of f so that the resulting Newton-like algorithm has a typically superlinear rate of convergence. With other choices of $D_k $ convergence at a typically linear rate is obtained. The algorithms are almost as simple as their unconstrained counterparts. They are well suited for problems of large dimension such as those arising in optimal control while being competitive with existing methods for low-dimensional problems. The effectiveness of the Newton-like algorithm is demonstrated via computational examples involving as many as 10,000 variables. Extensions to general linearly constrained problems are also provided. These extensions utilize a notion of an active generalized rectangle patterned after the notion of an active manifold used in manifold suboptimization methods. By contrast with these methods, many constraints can be added or subtracted from the binding set at each iteration without the need to solve a quadratic programming problem.
We study how to use the BFGS quasi-Newton matrices to precondition minimization methods for problems where the storage is critical. We give an update formula which generates matrices using information âŠ
We study how to use the BFGS quasi-Newton matrices to precondition minimization methods for problems where the storage is critical. We give an update formula which generates matrices using information from the last <italic>m</italic> iterations, where <italic>m</italic> is any number supplied by the user. The quasi-Newton matrix is updated at every iteration by dropping the oldest information and replacing it by the newest information. It is shown that the matrices generated have some desirable properties. The resulting algorithms are tested numerically and compared with several well-known methods.
The aim of this paper is two-fold. First, new variants are proposed for the primal-dual steepest descent algorithm as one in the family of primal-dual projected gradient algorithms developed by âŠ
The aim of this paper is two-fold. First, new variants are proposed for the primal-dual steepest descent algorithm as one in the family of primal-dual projected gradient algorithms developed by Zhu and Rockafellar [SIAM J. Optim., 3 (1993), pp. 751â783] for large-scale extended linear-quadratic programming. The variants include a second update scheme for the iterates, where the primal-dual feedback is arranged in a new pattern, as well as alternatives for the âperfect line searchâ in the original version of the reference. Second, new linear convergence results are proved for all these variants of the algorithm, including the original version as a special case, without the additional assumptions used by Zhu and Rockafellar. For the variants with the second update scheme, a much sharper estimation for the rate of convergence is obtained due to the new primal-dual feedback pattern.
The development of software for minimization problems is often based on a line search method. We consider line search methods that satisfy sufficient decrease and curvature conditions, and formulate the âŠ
The development of software for minimization problems is often based on a line search method. We consider line search methods that satisfy sufficient decrease and curvature conditions, and formulate the problem of determining a point that satisfies these two conditions in terms of finding a point in a set T(Ό) . We describe a search algorithm for this problem that produces a sequence of iterates that converge to a point in T(Ό) and that, except for pathological cases, terminates in a finite number of steps. Numerical results for an implementation of the search algorithm on a set of test functions show that the algorithm terminates within a small number of iterations.
We describe the results of a series of tests for a class of new methods of trust region type for solving the simple bound constrained minimization problem. The results are âŠ
We describe the results of a series of tests for a class of new methods of trust region type for solving the simple bound constrained minimization problem. The results are encouraging and lead us to believe that the methods will prove useful in solving large-scale problems.
This paper examines the numerical performances of two methods for large-scale optimization: a limited memory quasi-Newton method (L-BFGS), and a discrete truncated-Newton method (TN). Various ways of classifying test problems âŠ
This paper examines the numerical performances of two methods for large-scale optimization: a limited memory quasi-Newton method (L-BFGS), and a discrete truncated-Newton method (TN). Various ways of classifying test problems are discussed in order to better understand the types of problems that each algorithm solves well. The L-BFGS and TN methods are also compared with the PolakâRibiĂšre conjugate gradient method.
The theory of the proximal point algorithm for maximal monotone operators is applied to three algorithms for solving convex programs, one of which has not previously been formulated. Rate-of-convergence results âŠ
The theory of the proximal point algorithm for maximal monotone operators is applied to three algorithms for solving convex programs, one of which has not previously been formulated. Rate-of-convergence results for the âmethod of multipliers,â of the strong sort already known, are derived in a generalized form relevant also to problems beyond the compass of the standard second-order conditions for oplimality. The new algorithm, the âproximal method of multipliers,â is shown to have much the same convergence properties, but with some potential advantages.
In this paper we discuss the use of truncated-Newton methods, a flexible class of iterative methods, in the solution of large-scale unconstrained minimization problems. At each major iteration, the Newton âŠ
In this paper we discuss the use of truncated-Newton methods, a flexible class of iterative methods, in the solution of large-scale unconstrained minimization problems. At each major iteration, the Newton equations are approximately solved by an inner iterative algorithm. The performance of the inner algorithm, and in addition the total method, can be greatly improved by the addition of preconditioning and scaling strategies. Preconditionings can be developed using either the outer nonlinear algorithm or using information computed during the inner iteration. Several preconditioning schemes are derived and tested. Numerical tests show that a carefully chosen truncated-Newton method can perform well in comparison with nonlinear conjugate-gradient-type algorithms. This is significant, since the two classes of methods have comparable storage and operation counts, and they are the only practical methods for solving many large-scale problems. In addition, with the Hessian matrix available, the truncated-Newton algorithm performs like Newton's method, usually considered the best general method for this problem.
This paper extends the known excellent global convergence properties of trust region algorithms for unconstrained optimization to the case where bounds on the variables are present. Weak conditions on the âŠ
This paper extends the known excellent global convergence properties of trust region algorithms for unconstrained optimization to the case where bounds on the variables are present. Weak conditions on the accuracy of the Hessian approximations are considered. It is also shown that, when the strict complementarily condition holds, the proposed algorithms reduce to an unconstrained calculation after finitely many iterations, allowing a fast asymptotic rate of convergence.
In many problems involving the solution of a system of nonlinear equations, it is necessary to keep an approximation to the Jacobian matrix which is updated at each iteration. Computational âŠ
In many problems involving the solution of a system of nonlinear equations, it is necessary to keep an approximation to the Jacobian matrix which is updated at each iteration. Computational experience indicates that the best updates are those that minimize some reasonable measure of the change to the current Jacobian approximation subject to the new approximation obeying a secant condition and perhaps some other approximation properties such as symmetry. In this paper we extend the affine case of a theorem of Cheney and Goldstein on proximity maps of convex sets to show that a generalization of the symmetrization technique of Powell always generates least change updates. This generalization has such broad applicability that we obtain an easy unified derivation of all the most successful updates. Furthermore, our techniques apply to interesting new cases such as when the secant condition might be inconsistent with some essential approximation property like sparsity. We also offer advice on how to choose the properties which are to be incorporated into the approximations and how to choose the measure of change to be minimized.
It is shown on a prototype of standard iterative method for solving convex optimization problems, that the variational convergence theory allows to explain some stability properties of such methods for âŠ
It is shown on a prototype of standard iterative method for solving convex optimization problems, that the variational convergence theory allows to explain some stability properties of such methods for a large class of perturbation.
The purpose of this article is to discuss the scope and functionality of a versatile environment for testing small- and large-scale nonlinear optimization algorithms. Although many of these facilities were âŠ
The purpose of this article is to discuss the scope and functionality of a versatile environment for testing small- and large-scale nonlinear optimization algorithms. Although many of these facilities were originally produced by the authors in conjunction with the software package LANCELOT, we believe that they will be useful in their own right and should be available to researchers for their development of optimization software. The tools can be obtained by anonymous ftp from a number of sources and may, in many cases, be installed automatically. The scope of a major collection of test problems written in the standard input format (SIF) used by the LANCELOT software package is described. Recognizing that most software was not written with the SIF in mind, we provide tools to assist in building an interface between this input format and other optimization packages. These tools provide a link between the SIF and a number of existing packages, including MINOS and OSL. Additionally, as each problem includes a specific classification that is designed to be useful in identifying particular classes of problems, facilities are provided to build and manage a database of this information. There is a Unix and C shell bias to many of the descriptions in the article, since, for the sake of simplicity, we do not illustrate everything in its fullest generality. We trust that the majority of potential users are sufficiently familiar with Unix that these examples will not lead to undue confusion.
The asymptotic convergence of the forward-backward splitting algorithm for solving equations of type 0 â T(z) is analyzed, where T is a multivalued maximal monotone operator in the n-dimensional Euclidean âŠ
The asymptotic convergence of the forward-backward splitting algorithm for solving equations of type 0 â T(z) is analyzed, where T is a multivalued maximal monotone operator in the n-dimensional Euclidean space. When the problem has a nonempty solution set, and T is split in the form T = â± + h with â± being maximal monotone and h being co-coercive with modulus greater than Âœ, convergence rates are shown, under mild conditions, to be linear, superlinear or sublinear depending on how rapidly â± â1 and h â1 grow in the neighborhoods of certain specific points. As a special case, when both â± and h are polyhedral functions, we get R-linear convergence and 2-step Q-linear convergence without any further assumptions on the strict monotonicity on T or on the uniqueness of the solution. As another special case when h = 0, the splitting algorithm reduces to the proximal point algorithm, and we get new results, which complement R. T. Rockafellar's and F. J. Luque's earlier results on the proximal point algorithm.
An algorithm for solving large nonlinear optimization problems with simple bounds is described. It is based on the gradient projection method and uses a limited memory BFGS matrix to approximate âŠ
An algorithm for solving large nonlinear optimization problems with simple bounds is described. It is based on the gradient projection method and uses a limited memory BFGS matrix to approximate the Hessian of the objective function. It is shown how to take advantage of the form of the limited memory approximation to implement the algorithm efficiently. The results of numerical tests on a set of large problems are reported.
Algorithms based on trust regions have been shown to be robust methods for unconstrained optimization problems. All existing methods, either based on the dogleg strategy or Hebden-More iterations, require solution âŠ
Algorithms based on trust regions have been shown to be robust methods for unconstrained optimization problems. All existing methods, either based on the dogleg strategy or Hebden-More iterations, require solution of system of linear equations. In large scale optimization this may be prohibitively expensive. It is shown in this paper that an approximate solution of the trust region problem may be found by the preconditioned conjugate gradient method. This may be regarded as a generalized dogleg technique where we asymptotically take the inexact quasi-Newton step. We also show that we have the same convergence properties as existing methods based on the dogleg strategy using an approximate Hessian.