Successive linear programming

Successive Linear Programming (SLP), also known as Sequential Linear Programming, is an optimization technique for approximately solving nonlinear optimization problems.^[1] It is related to, but distinct from, quasi-Newton methods.

Starting at some estimate of the optimal solution, the method is based on solving a sequence of first-order approximations (i.e. linearizations) of the model. The linearizations are linear programming problems, which can be solved efficiently. As the linearizations need not be bounded, trust regions or similar techniques are needed to ensure convergence in theory. ^[2]

SLP has been used widely in the petrochemical industry since the 1970s.^[3] Since then, however, they have been superseded by sequential quadratic programming methods. While solving a QP subproblem takes more time than solving an LP one, the overall decrease in the number of iterations, due to improved convergence, results in significantly lower running times and fewer function evaluations."

See also

• Sequential quadratic programming
• Sequential linear-quadratic programming
• Augmented Lagrangian method

References

Sources

• Nocedal, Jorge; Wright, Stephen J. (2006). Numerical Optimization (2nd ed.). Berlin, New York: Springer-Verlag. ISBN 978-0-387-30303-1.
• Bazaraa, Mokhtar S.; Sherali, Hanif D.; Shetty, C.M. (1993). Nonlinear Programming, Theory and Applications (2nd ed.). John Wiley & Sons. ISBN 0-471-55793-5.
• Palacios-Gomez, F.; Lasdon, L.; Enquist, M. (October 1982). "Nonlinear Optimization by Successive Linear Programming". Management Science. 28 (10): 1106–1120. doi:10.1287/mnsc.28.10.1106.

• v
• t
• e

Optimization: Algorithms, methods, and heuristics

Unconstrained nonlinear

Functions Golden-section search Interpolation methods Line search Nelder–Mead method Successive parabolic interpolation Gradients Convergence Trust region Wolfe conditions Quasi–Newton Berndt–Hall–Hall–Hausman Broyden–Fletcher–Goldfarb–Shanno and L-BFGS Davidon–Fletcher–Powell Symmetric rank-one (SR1) Other methods Conjugate gradient Gauss–Newton Gradient Mirror Levenberg–Marquardt Powell's dog leg method Truncated Newton Hessians Newton's method

Constrained nonlinear
General Barrier methods Penalty methods Differentiable Augmented Lagrangian methods Sequential quadratic programming Successive linear programming

Convex optimization
Convex minimization Cutting-plane method Reduced gradient (Frank–Wolfe) Subgradient method Linear and quadratic Interior point Affine scaling Ellipsoid algorithm of Khachiyan Projective algorithm of Karmarkar Basis-exchange Simplex algorithm of Dantzig Revised simplex algorithm Criss-cross algorithm Principal pivoting algorithm of Lemke

Combinatorial
Paradigms Approximation algorithm Dynamic programming Greedy algorithm Integer programming Branch and bound/cut Graph algorithms Minimum spanning tree Borůvka Prim Kruskal Shortest path Bellman–Ford SPFA Dijkstra Floyd–Warshall Network flows Dinic Edmonds–Karp Ford–Fulkerson Push–relabel maximum flow

Metaheuristics
Evolutionary algorithm Hill climbing Local search Parallel metaheuristics Simulated annealing Spiral optimization algorithm Tabu search

• Software

This algorithms or data structures-related article is a stub. You can help Wikipedia by expanding it.

• v
• t
• e