Понятие о задаче оптимизации.

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

Функция одной действительной переменной f(x) достигает локального минимума в некоторой точке x₀, если существует такая d -окрестность этой точки, что для всех x из этой окрестности, т.е. таких, что | x - x₀ | < d, имеет место f(x) > f(x₀).

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

Матем. определение локального минимума функции в многомерном пространстве имеет тот же вид, если заменить точки x и x₀ на вектора, а вместо модуля использовать норму. Поиск минимума для функции многих переменных (многих факторов) является существенно более сложной задачей, чем для одной переменной. Это связано прежде всего с тем, что локальное направление уменьшения значения функции может не соответствовать направлению движения к точке минимума. Кроме того, с ростом размерности быстро возрастают затраты на вычисление функции.

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

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

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