ЧИСЛЕННЫЕ МЕТОДЫ ОПТИМИЗАЦИИ.

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

Центральным вопросом численной оптимизации является вопрос выбора подходящего вычислительного алгоритма и анализа его сходимости.

Алгоритм поиска оптимального решения сходится, если он непосредственно вычисляет значение  и соответственно  за конечное число шагов, либо представляет его в виде ее предельного значения   последовательности точек  ,  ,  ,…

Во втором случае о сходимости можно говорить только в смысле существования =  ,т.к. достичь ее за конечное число шагов невозможно.

Рассмотрим некоторые, наиболее использующиеся методы численной оптимизации.

Методы возможных направлений.

Идея метода возможных направлений проста: из начальной, допустимой по условиям задачи точки  осуществляется переход к новой допустимой точке  ,в которой значение целевой функции z лучше, чем в предыдущей. И так до тех пор, пока есть возможность улучшения z. Каждый шаг основан на выборе подходящего направления движения из очередной точки   и оценке требуемой «длины шага» таким образом, что позволяет в итоге найти . Выбор очередного (k+1) – го значения производится по формуле:

 =   + ,

где, -величина k-ого шага ; -единичный вектор ,определяющий направление перемещения.

Приведенное выражение является общим. Разница между методами заключается в способе задания  и .

Метод крутого восхождения (наискорейшего спуска).

В основе метода крутого восхождения лежат следующие правила:

1. В качестве вектора возможных направлений выбирается вектор градиента целевой функции , т.е.

=

2.Величина шага  определяется

- либо из условия  ,

- либо задается фиксировано;

-  либо изменяется по определенному правилу (увеличивается, либо уменьшается)

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

Если целевая функция невыпуклая, то существует несколько точек экстремума функции и метод из разных начальных точек может сходиться к разным локальным экстремальным точкам.

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