Powell’s algorithm

A key problem that arises in the implementation of Powell s algorithm is due to the linearization that produces a quadratic objective function and linear constraints, which often lead to infeasible solution vectors, X ]. This problem manifests itself in solu-... 

There are two basic types of unconstrained optimization algorithms (I) those reqmring function derivatives and (2) those that do not. The nonderivative methods are of interest in optimization applications because these methods can be readily adapted to the case in which experiments are carried out directly on the process. In such cases, an ac tual process measurement (such as yield) can be the objec tive function, and no mathematical model for the process is required. Methods that do not reqmre derivatives are called direc t methods and include sequential simplex (Nelder-Meade) and Powell s method. The sequential simplex method is quite satisfac tory for optimization with two or three independent variables, is simple to understand, and is fairly easy to execute. Powell s method is more efficient than the simplex method and is based on the concept of conjugate search directions. 

The Simplex algorithm and that of Powell s are examples of derivative-free methods (Edgar and Himmelblau, 1988 Seber and Wild, 1989, Powell, 1965). In this chapter only two algorithms will be presented (1) the LJ optimization procedure and (2) the simplex method. The well known golden section and Fibonacci methods for minimizing a function along a line will not be presented. Kowalik and Osborne (1968) and Press et al. (1992) among others discuss these methods in detail. 

Both difficulties are eliminated by replacing V L by a positive-definite quasi-Newton (QN) approximation B, which is updated using only values of L and V L (See Section 6.4 for a discussion of QN updates.) Most SQP algorithms use Powell s modification (see Nash and Sofer, 1996) of the BFGS update. Hence the QP subproblem becomes... 

One method to finding the minimum of a function is to search over all possible values of x and find the minimum based on the corresponding values of Y. These algorithms include region elimination methods, such as the Golden Search algorithm or point-estimation methods, such as Powell s method, neither of which require calculation of the derivatives. However, these types of methods often assume unimodality, and in some cases, continuity of the function. The reader is referred to Reklaitis Ravindran, and Ragsdell (1983) or Rao (1996) for details. 

An efficient and robust optimisation algorithm is primordial for this solution strategy. Rao Sawyer (1995) applied Powell s method to tackle the optimisation. Koyliioglu et al. (1995) defined a linear programming solution for this purpose. The input interval vector defines the number of constraints and, therefore, strongly influences the performance of the procedure. Also, because of the required execution of the deterministic FE analysis in each goal function evaluation, the optimisation approach is numerically expensive. Therefore, this approach is best suited for rather small FE models with a limited number of input uncertainties, unless approximate methods can be used that avoid the expensive iterative calculation of the entire FE system of equations. 

Vaughan M. Young S. Winker D. Powell K. Omar A. Liu Z. Hu Y. and Hostetler C. (2004). Fully automated analysis of space-based lidar data An overview of the CALIPSO retrieval algorithms and data products. Proc. SPIE, 5575, 16-30. 

---