Численные методы нелинейного программирования (многомерные безусловные оптимизации)

F(x)=f(x1,x2,x3…xn)->min(max)

В зависимости от выбора шага поиска экстремума(/\ h), различают методы без градиентные, градиентные и случайного поиска.

Без градиентные методы

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

Метод сканирования. Поиска на сетки переменной.

Состоит в последовательном просмотре или вычислений значений критерия f(x) в ряде точек из множества допустимых решений, точность вычислений определяется густотой сетки. Вычислений по каждой следующей переменной начинается после того, как закончено вычислений по предыдущей.

Достоинтства простота, ищется глобальный экстремум, недостаток, большое количество вычислений.

Метод можно использовать для грубого поиска глобального экстремума выбрав в начале большой шаг /\ 0х, после провиденной оценки, значение шага уменьшается.

Иногда после прикидочного расчета для точного поиска используют градиентные методы. Наличие ограничений лишь сокращает объем вычислений.

Поочередное изменение направление поиска (метод Гаусса)

Идея изменяются последовательно. Последовательно изменяются все независимые переменные (n-переменных) так чтобы по каждой из них целевая функция f(x) достигала минимума. очередность изменения переменных, произвольная.

Которая не меняется во время вычислений в процессе поиска.

Поиск вдоль по конкретной переменной ищется любым из известным поиском (например, метод сканирования). При n=2 метод совпадает с методом релаксации.

Достоинства и простота:

Зависит от ориентации осей, математической записи. Метод застревает на границах в любой точке. Метод застревает в оврагах.

Симплексный метод, метод квантования симплекса.

Симплекс это многогранник в n-мерном пространстве содержащий ровно n+1 вершиину.

Симплексы бывают правильные и неправильные.

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

Метод прост движение к экстремуму эффективное и не важен вид функции.

Много зависит от начальных условий

Градиентные методы

Здесь в процессе поиска вычисляются частные производные и градиент функции в отдельных точках.

Метод градиента

Шаги осуществляются по направлению наибольшего убывания функции в каждой точке поиска.

Поиск происходит в два этапа:

1)находятся производная по всем переменным xi и выбирается из них наибольшая по модулю, которая показывает направление в котором функция меняется наиболее сильно. Если она положительна то переменную xj надо уменьшать, а если отрицательное, то увеличивать.

2)делается шаг в направление обратном градиенту функции при этом сразу изменяются все переменные функции, по алгоритму.

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

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

Нелинейное программирование

F(x)=f(x1,x2…xn) э Rⁿ

Нулевой порядок первого порядка второго порядка

Без градиентного метода