Метод эллипсоидов, предложенный советским математиком Леонидом Хачияном в 1979 году, стал исторической вехой в математическом программировании. Этот алгоритм впервые строго доказал, что задачи линейного программирования могут быть решены за полиномиальное время. В отличие от классического симплекс-метода, который в худших сценариях (например, на кубе Клее-Минти) требует экспоненциального количества шагов, метод эллипсоидов гарантирует нахождение оптимума с оценкой сложности, зависящей только от размера входных данных, что навсегда изменило теоретический ландшафт теории алгоритмов и вычислительной сложности.

Когда целевая функция имеет сложный, мультимодальный ландшафт с множеством локальных минимумов, градиентные методы оказываются бесполезными. В таких случаях на помощь приходят методы глобальной оптимизации, основанные на случайном поиске. Они не гарантируют нахождение глобального минимума за конечное время, но обладают высокой вероятностью попадания в "бассейн притяжения" глобального оптимума.

Метод последовательных приближений охватывает широкий класс итерационных алгоритмов, в которых решение задачи находится как предел последовательности, сходящейся к оптимальному значению. К ним относятся методы простой итерации, методы Ньютона, градиентные методы. Основная задача — обеспечить сходимость алгоритма и оценить скорость достижения заданной точности.