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.     

Feasible generalized monotone line search SQP algorithm for nonlinear minimax problems with inequality constraints

In this paper, the nonlinear minimax problems with inequality constraints are discussed, and a sequential quadratic programming (SQP) algorithm with a generalized monotone line search is presented. At each iteration, a feasible direction of descent is obtained by solving a quadratic programming (QP). To avoid the Maratos effect, a high order correction direction is achieved by solving another QP. As a result, the proposed algorithm has global and superlinear convergence. Especially, the global convergence is obtained under a weak Mangasarian–Fromovitz constraint qualification (MFCQ) instead of the linearly independent constraint qualification (LICQ). At last, its numerical effectiveness is demonstrated with test examples.     

An exact penalty function algorithm for semi-infinite programmes

An algorithm for semi-inifinite programming using sequential quadratic programming techniques together with anL exact penalty function is presented, and global convergence is shown. An important feature of the convergence proof is that it does not require an implicit function theorem to be applicable to the semi-infinite constraints; a much weaker assumption concerning the finiteness of the number of global maximizers of each semi-infinite constraint is sufficient. In contrast to proofs based on an implicit function theorem, this result is also valid for a large class ofC ¹ 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.     

A sequential equality constrained quadratic programming algorithm for inequality constrained optimization

In this paper, the feasible type SQP method is improved. A new SQP algorithm is presented to solve the nonlinear inequality constrained optimization. As compared with the existing SQP methods, per single iteration, in order to obtain the search direction, it is only necessary to solve equality constrained quadratic programming subproblems and systems of linear equations. Under some suitable conditions, the global and superlinear convergence can be induced.     

A direct active set algorithm for large sparse quadratic programs with simple bounds

We show how a direct active set method for solving definite and indefinite quadratic programs with simple bounds can be efficiently implemented for large sparse problems. All of the necessary factorizations can be carried out in a static data structure that is set up before the numeric computation begins. The space required for these factorizations is no larger than that required for a single sparse Cholesky factorization of the Hessian of the quadratic. We propose several improvements to this basic algorithm: a new way to find a search direction in the indefinite case that allows us to free more than one variable at a time and a new heuristic method for finding a starting point. These ideas are motivated by the two-norm trust region problem. Additionally, we also show how projection techniques can be used to add several constraints to the active set at each iteration. Our experimental results show that an algorithm with these improvements runs much faster than the basic algorithm for positive definite problems and finds local minima with lower function values for indefinite problems.Research partially supported by the Applied Mathematical Sciences Research Program (KC-04-02) of the Office of Energy Research of the U.S. Department of Energy under grant DE-FG02-86ER25013.A000.     

Convergence of some algorithms for convex minimization

We present a simple and unified technique to establish convergence of various minimization methods. These contain the (conceptual) proximal point method, as well as implementable forms such as bundle algorithms, including the classical subgradient relaxation algorithm with divergent series.An important research work of Phil Wolfe's concerned convex minimization. This paper is dedicated to him, on the occasion of his 65th birthday, in appreciation of his creative and pioneering work.     

A superlinearly convergent strongly sub-feasible SSLE-type algorithm with working set for nonlinearly constrained optimization

In this paper, by means of a new efficient identification technique of active constraints and the method of strongly sub-feasible direction, we propose a new sequential system of linear equations (SSLE) algorithm for solving inequality constrained optimization problems, in which the initial point is arbitrary. At each iteration, we first yield the working set by a pivoting operation and a generalized projection; then, three or four reduced linear equations with a same coefficient are solved to obtain the search direction. After a finite number of iterations, the algorithm can produced a feasible iteration point, and it becomes the method of feasible directions. Moreover, after finitely many iterations, the working set becomes independent of the iterates and is essentially the same as the active set of the KKT point. Under some mild conditions, the proposed algorithm is proved to be globally, strongly and superlinearly convergent. Finally, some preliminary numerical experiments are reported to show that the algorithm is practicable and effective.     

An efficient algorithm for large scale global optimization of continuous functions

A fast descent algorithm, resorting to a “stretching” function technique and built on one hybrid method (GRSA) which combines simulated annealing (SA) algorithm and gradient based methods for large scale global optimizations, is proposed. Unlike the previously proposed method in which the original objective functions remain unchanged during the whole course of optimization, the new method firstly constructs an auxiliary function on one local minimizer obtained by gradient based methods and then SA is executed on this constructed auxiliary function instead of on the original objective function in order that we can improve the jumping ability of SA algorithm to escape from the currently discovered local minimum to a better one from which the gradient based methods restart a new local search. The above procedure is repeated until a global minimum is detected. In addition, corresponding to the adopted “stretching” technique, a new next trial point generating scheme is designed. It is verified by simulation especially on large scale problems that the convergence speed is greatly accelerated, which is its main difference from many other reported methods that mostly cope with functions with less than 50 variables and does not apply to large scale optimization problems. Furthermore, the new algorithm functions as a global optimization procedure with a high success probability and high solution precision.     

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.     

An ODE-based trust region method for unconstrained optimization problems

In this paper, a new trust region algorithm is proposed for solving unconstrained optimization problems. This method can be regarded as a combination of trust region technique, fixed step-length and ODE-based methods. A feature of this proposed method is that at each iteration, only a system of linear equations is solved to obtain a trial step. Another is that when a trial step is not accepted, the method generates an iterative point whose step-length is defined by a formula. Under some standard assumptions, it is proven that the algorithm is globally convergent and locally superlinear convergent. Preliminary numerical results are reported.     

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.     

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.     

Global convergence of a modified Fletcher–Reeves conjugate gradient method with Armijo-type line search

In this paper, we are concerned with the conjugate gradient methods for solving unconstrained optimization problems. It is well-known that the direction generated by a conjugate gradient method may not be a descent direction of the objective function. In this paper, we take a little modification to the Fletcher–Reeves (FR) method such that the direction generated by the modified method provides a descent direction for the objective function. This property depends neither on the line search used, nor on the convexity of the objective function. Moreover, the modified method reduces to the standard FR method if line search is exact. Under mild conditions, we prove that the modified method with Armijo-type line search is globally convergent even if the objective function is nonconvex. We also present some numerical results to show the efficiency of the proposed method.Supported by the 973 project (2004CB719402) and the NSF foundation (10471036) of China.     

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.     

Quadratic problems defined on a convex hull of points

In this paper we consider an algorithm for a class of quadratic problems defined on a polytope which is described as the convex hull of a set of points. The algorithm is based on simplex partitions using convex underestimating functions.     

A note on exploiting structure when using slack variables

We show how to exploit the structure inherent in the linear algebra for constrained nonlinear optimization problems when inequality constraints have been converted to equations by adding slack variables and the problem is solved using an augmented Lagrangian method.This research was supported in part by the Advanced Research Projects Agency of the Department of Defense and was monitored by the Air Force Office of Scientific Research under Contract No F49620-91-C-0079. The United States Goverment is authorized to reproduce and distribute reprints for governmental purposes notwithstanding any copyright notation hereon.Corresponding author.     

A variable metric algorithm for unconstrained minimization without evaluation of derivatives

Summary This paper presents a modification of the BFGS-method for unconstrained minimization that avoids computation of derivatives. The gradients are approximated by the aid of differences of function values. These approximations are calculated in such a way that a complete convergence proof can be given. The presented algorithm is implementable, no exact line search is required. It is shown that, if the objective function is convex and some usually required conditions hold, the algorithm converges to a solution. If the Hessian matrix of the objective function is positive definite and satisfies a Lipschitz-condition in a neighbourhood of the solution, then the rate of convergence is superlinear.     

A note on using alternative second-order models for the subproblems arising in barrier function methods for minimization

Summary. Inequality constrained minimization problems are often solved by considering a sequence of parameterized barrier functions. Each barrier function is approximately minimized and the relevant parameters subsequently adjusted. It is common for the estimated solution to one barrier function problem to be used as a starting estimate for the next. However, this has unfortunate repercussions for the standard Newton-like methods applied to the barrier subproblem. In this note, we consider a class of alternative Newton methods which attempt to avoid such difficulties. Such schemes have already proved of use in the Harwell Subroutine Library quadratic programming codes {\tt VE14} and {\tt VE19}. Received May 2, 1993/Revised form received February 12, 1994