A new trust region method for unconstrained optimization

In this paper, we propose a new trust region method for unconstrained optimization problems. The new trust region method can automatically adjust the trust region radius of related subproblems at each iteration and has strong global convergence under some mild conditions. We also analyze the global linear convergence, local superlinear and quadratic convergence rate of the new method. Numerical results show that the new trust region method is available and efficient in practical computation.     

Combining nonmonotone conic trust region and line search techniques for unconstrained optimization

In this paper, we propose a trust region method for unconstrained optimization that can be regarded as a combination of conic model, nonmonotone and line search techniques. Unlike in traditional trust region methods, the subproblem of our algorithm is the conic minimization subproblem; moreover, our algorithm performs a nonmonotone line search to find the next iteration point when a trial step is not accepted, instead of resolving the subproblem. The global and superlinear convergence results for the algorithm are established under reasonable assumptions. Numerical results show that the new method is efficient for unconstrained optimization problems.     

A subspace implementation of quasi-Newton trust region methods for unconstrained optimization

This paper studies subspace properties of trust region methods for unconstrained optimization, assuming the approximate Hessian is updated by quasi- Newton formulae and the initial Hessian approximation is appropriately chosen. It is shown that the trial step obtained by solving the trust region subproblem is in the subspace spanned by all the gradient vectors computed. Thus, the trial step can be defined by minimizing the quasi-Newton quadratic model in the subspace. Based on this observation, some subspace trust region algorithms are proposed and numerical results are also reported.     

A new nonmonotone line search technique for unconstrained optimization

In this paper, we propose a new nonmonotone line search technique for unconstrained optimization problems. By using this new technique, we establish the global convergence under conditions weaker than those of the existed nonmonotone line search techniques.     

信赖域策略的内点投影既约Hessian方法解非线性约束优化

A interior point scaling projected reduced Hessian method with combination of nonmonotonic backtracking technique and trust region strategy for nonlinear equality constrained optimization with nonegative constraint on variables is proposed. In order to deal with large problems,a pair of trust region subproblems in horizontal and vertical subspaces is used to replace the general full trust region subproblem. The horizontal trust region subproblem in the algorithm is only a general trust region subproblem while the vertical trust region subproblem is defined by a parameter size of the vertical direction subject only to an ellipsoidal constraint. Both trust region strategy and line search technique at each iteration switch to obtaining a backtracking step generated by the two trust region subproblems. By adopting the l1 penalty function as the merit function, the global convergence and fast local convergence rate of the proposed algorithm are established under some reasonable conditions. A nonmonotonic criterion and the second order correction step are used to overcome Maratos effect and speed up the convergence progress in some ill-conditioned cases.     

Two modified HS type conjugate gradient methods for unconstrained optimization problems

Based on the modified secant equation, we propose two new HS type conjugate gradient formulas. Their forms are similar to the original HS conjugate gradient formula and inherit all nice properties of the HS method. By utilizing the technique of the three-term HS method in Zhang et al. (2007) [15], without the requirement of truncation and convexity of the objective function, we show that one with Wolfe line search and the other with Armijo line search are globally convergent. Moreover, under some mild conditions, the linear convergence rate of the two modified methods is established. The numerical results show that the proposed methods are efficient.     

A class of nonmonotone stabilization methods in unconstrained optimization

Summary This paper deals with the solution of smooth unconstrained minimization problems by Newton-type methods whose global convergence is enforced by means of a nonmonotone stabilization strategy. In particular, a stabilization scheme is analyzed, which includes different kinds of relaxation of the descent requirements. An extensive numerical experimentation is reported.     

Global convergence of the nonmonotone MBFGS method for nonconvex unconstrained minimization

In this paper, we propose a new nonmonotone Armijo type line search and prove that the MBFGS method proposed by Li and Fukushima with this new line search converges globally for nonconvex minimization. Some numerical experiments show that this nonmonotone MBFGS method is efficient for the given test problems.     

Interval method for bounding level sets: Revisited and tested with global optimization problems

An interval method for bounding level sets, modified to increase its efficiency and to get sharper bounding boxes, is presented. The new algorithm was tested with standard global optimization test problems. The test results show that, while the modified method gives a more valuable, guaranteed reliability result set, it is competitive with non-interval methods in terms of CPU time and number of function evaluations.This work was supported by Grant OTKA 1074/1987, and in part by DAAD Fellowship No. 314/108/004/8 during the author's stay at Düsseldorf University.     

On diagonally structured problems in unconstrained optimization using an inexact super Halley method

We consider solving the unconstrained minimization problem using an iterative method derived from the third order super Halley method. Each iteration of the super Halley method requires the solution of two linear systems of equations. We show a practical implementation using an iterative method to solve the linear systems. This paper introduces an array of arrays (jagged) data structure for storing the second and third derivative of a multivariate function and suitable termination criteria for the (inner) iterative method to achieve a cubic rate of convergence. Using a jagged compressed diagonal storage of the Hessian matrices and for the tensor, numerical results show that storing the diagonals are more efficient than the row or column oriented approach when we use an iterative method for solving the linear systems of equations.     

A multivariate spectral projected gradient method for bound constrained optimization

In this paper, we consider a multivariate spectral projected gradient (MSPG) method for bound constrained optimization. Combined with a quasi-Newton property, the multivariate spectral projected gradient method allows an individual adaptive step size along each coordinate direction. On the basis of nonmonotone line search, global convergence is established. A numerical comparison with the traditional SPG method shows that the method is promising.     

UOBYQA: unconstrained optimization by quadratic approximation

UOBYQA is a new algorithm for general unconstrained optimization calculations, that takes account of the curvature of the objective function, F say, by forming quadratic models by interpolation. Therefore, because no first derivatives are required, each model is defined by ?(n+1)(n+2) values of F, where n is the number of variables, and the interpolation points must have the property that no nonzero quadratic polynomial vanishes at all of them. A typical iteration of the algorithm generates a new vector of variables, _t say, either by minimizing the quadratic model subject to a trust region bound, or by a procedure that should improve the accuracy of the model. Then usually F( _t ) is obtained, and one of the interpolation points is replaced by _t . Therefore the paper addresses the initial positions of the interpolation points, the adjustment of trust region radii, the calculation of _t in the two cases that have been mentioned, and the selection of the point to be replaced. Further, UOBYQA works with the Lagrange functions of the interpolation equations explicitly, so their coefficients are updated when an interpolation point is moved. The Lagrange functions assist the procedure that improves the model, and also they provide an estimate of the error of the quadratic approximation to F, which allows the algorithm to achieve a fast rate of convergence. These features are discussed and a summary of the algorithm is given. Finally, a Fortran implementation of UOBYQA is applied to several choices of F, in order to investigate accuracy, robustness in the presence of rounding errors, the effects of first derivative discontinuities, and the amount of work. The numerical results are very promising for n≤20, but larger values are problematical, because the routine work of an iteration is of fourth order in the number of variables. Received: December 7, 2000 / Accepted: August 31, 2001?Published online April 12, 2002     

Accelerating method of global optimization for signomial geometric programming

Signomial geometric programming (SGP) has been an interesting problem for many authors recently. Many methods have been provided for finding locally optimal solutions of SGP, but little progress has been made for global optimization of SGP. In this paper we propose a new accelerating method for global optimization algorithm of SGP using a suitable deleting technique. This technique offers a possibility to cut away a large part of the currently investigated region in which the globally optimal solution of SGP does not exist, and can be seen as an accelerating device for global optimization algorithm of SGP problem. Compared with the method of Shen and Zhang [Global optimization of signomial geometric programming using linear relaxation, Appl. Math. Comput. 150 (2004) 99–114], numerical results show that the computational efficiency is improved obviously by using this new technique in the number of iterations, the required saving list length and the execution time of the algorithm.     

A self-adaptive trust region method with line search based on a simple subproblem model

In this paper, based on a simple model of the trust region subproblem, we propose a new self-adaptive trust region method with a line search technique for solving unconstrained optimization problems. By use of the simple subproblem model, the new method needs less memory capacitance and computational complexity. And the trust region radius is adjusted with a new self-adaptive adjustment strategy which makes full use of the information at the current point. When the trial step results in an increase in the objective function, the method does not resolve the subproblem, but it performs a line search technique from the failed point. Convergence properties of the method are proved under certain conditions. Numerical experiments show that the new method is effective and attractive for large-scale optimization problems.     

An algorithm for a class of nonlinear fractional problems using ranking of the vertices

In this note we consider an algorithm for quasiconcave nonlinear fractional programming problems, based on ranking the vertices of a linear fractional programming problem and techniques from global optimization.     

The convergence of subspace trust region methods

The trust region method is an effective approach for solving optimization problems due to its robustness and strong convergence. However, the subproblem in the trust region method is difficult or time-consuming to solve in practical computation, especially in large-scale problems. In this paper we consider a new class of trust region methods, specifically subspace trust region methods. The subproblem in these methods has an adequate initial trust region radius and can be solved in a simple subspace. It is easier to solve than the original subproblem because the dimension of the subproblem in the subspace is reduced substantially. We investigate the global convergence and convergence rate of these methods.     

A globally and superlinearly convergent trust region method for LC 1 optimization problems

Abstract. A new trust region algorithm for solving convex LC1 optimization problem is present-ed. It is proved that the algorithm is globally convergent and the rate of convergence is superlin-ear under some reasonable assumptions.     

A new adaptive trust region algorithm for optimization problems

It is well known that trust region methods are very effective for optimization problems. In this article, a new adaptive trust region method is presented for solving unconstrained optimization problems. The proposed method combines a modified secant equation with the BFGS updated formula and an adaptive trust region radius, where the new trust region radius makes use of not only the function information but also the gradient information. Under suitable conditions, global convergence is proved, and we demonstrate the local superlinear convergence of the proposed method. The numerical results indicate that the proposed method is very efficient.     

A method for generating a well-distributed Pareto set in nonlinear multiobjective optimization

A method is presented for generating a well-distributed Pareto set in nonlinear multiobjective optimization. The approach shares conceptual similarity with the Physical Programming-based method, the Normal-Boundary Intersection and the Normal Constraint methods, in its systematic approach investigating the objective space in order to obtain a well-distributed Pareto set. The proposed approach is based on the generalization of the class functions which allows the orientation of the search domain to be conducted in the objective space. It is shown that the proposed modification allows the method to generate an even representation of the entire Pareto surface. The generation is performed for both convex and nonconvex Pareto frontiers. A simple algorithm has been proposed to remove local Pareto solutions. The suggested approach has been verified by several test cases, including the generation of both convex and concave Pareto frontiers.     

Two descent hybrid conjugate gradient methods for optimization

In this paper, we propose two new hybrid nonlinear conjugate gradient methods, which produce sufficient descent search direction at every iteration. This property depends neither on the line search used nor on the convexity of the objective function. Under suitable conditions, we prove that the proposed methods converge globally for general nonconvex functions. The numerical results show that both hybrid methods are efficient for the given test problems from the CUTE library.