Powell's method

Powell's method, strictly Powell's conjugate direction method, is an algorithm proposed by Michael J. D. Powell for finding a local minimum of a function.The function need not be differentiable, and no derivatives are taken.The function must be a real-valued function of a fixed number of real-valued inputs.The caller passes in the initial point.The caller also passes in a set of initial search vectors.Typically N search vectors (say) are passed in which are simply the normals aligned to each axis.[1] The method minimises the function by a bi-directional search along each search vector, in turn.The bi-directional line search along each search vector can be done by Golden-section search or Brent's method.Let the minima found during each bi-directional line search beis the initial starting point andis the scalar determined during bi-directional search along) can then be expressed as a linear combination of the search vectors i.e.) becomes a new search vector, and is added to the end of the search vector list.Meanwhile, the search vector which contributed most to the new direction, i.e. the one which was most successful (), is deleted from the search vector list.The new set of N search vectors isThe algorithm iterates an arbitrary number of times until no significant improvement is made.[1] The method is useful for calculating the local minimum of a continuous but complex function, especially one without an underlying mathematical definition, because it is not necessary to take derivatives.The basic algorithm is simple; the complexity is in the linear searches along the search vectors, which can be achieved via Brent's method.
Graph of a strictly concave quadratic function with unique maximum.
Optimization computes maxima and minima.
algorithmMichael J. D. Powelllocal minimumGolden-section searchBrent's methodOptimizationAlgorithmsmethodsheuristicsUnconstrained nonlinearFunctionsLine searchNelder–Mead methodSuccessive parabolic interpolationGradientsConvergenceTrust regionWolfe conditionsQuasi–NewtonBerndt–Hall–Hall–HausmanBroyden–Fletcher–Goldfarb–ShannoL-BFGSDavidon–Fletcher–PowellSymmetric rank-one (SR1)Other methodsConjugate gradientGauss–NewtonGradientMirrorLevenberg–MarquardtPowell's dog leg methodTruncated NewtonHessiansNewton's methodConstrained nonlinearBarrier methodsPenalty methodsAugmented Lagrangian methodsSequential quadratic programmingSuccessive linear programmingConvex optimizationConvex minimizationCutting-plane methodReduced gradient (Frank–Wolfe)Subgradient methodLinearquadraticAffine scalingEllipsoid algorithm of KhachiyanProjective algorithm of KarmarkarBasis-exchangeSimplex algorithm of DantzigRevised simplex algorithmCriss-cross algorithmPrincipal pivoting algorithm of LemkeActive-set methodCombinatorialApproximation algorithmDynamic programmingGreedy algorithmInteger programmingBranch and boundGraph algorithmsMinimum spanning treeBorůvkaKruskalShortest pathBellman–FordDijkstraFloyd–WarshallNetwork flowsEdmonds–KarpFord–FulkersonPush–relabel maximum flowMetaheuristicsEvolutionary algorithmHill climbingLocal searchParallel metaheuristicsSimulated annealingSpiral optimization algorithmTabu searchSoftware