Методы решения задач условной оптимизации (1006297), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

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

Теорема Куна-Такера. Необходимое условие минимума функции f(X) при ограничениях имеет вид:

Необходимое условие максимума функции f(X) при имеет вид: первые два уравнения из предыдущей системы и:

Решая систему уравнений и неравенств, получаем стационарные точки, среди которых могут быть локальные минимумы (максимумы).

3. Метод штрафных функций

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

- штрафная функция, имеющая вид:

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

Геометрическая интерпретации метода штрафных функций при n=1 и m=1 приведена на рисунке. Минимум q(x), а значит и f(x) при , достигается в точке х*.

4. Методы случайного поиска

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

1. Метод с возвратом на неудачном шаге

Алгоритм нахождения и Х^(к+1) на каждой итерации к состоит в следующем.

1. Генерируем случайное направление в n-мерном пространстве, т.е. случайный вектор , где - случайная величина с известным законом распределения (для простоты как правило используют равномерное распределение на отрезке [-1;1].

2. Примем и вычислим

3. Определяем . Если выполнено условие ,т.е. , переходим к п.4, иначе полученное Х отбрасывается и переходим к п.1.

4. Если в случае поиска минимума f(X) (или при максимуме), то переходим к п.1, иначе Х^(к+1) =Х

5. Конец алгоритма.

2. Метод наилучшей пробы

Алгоритм нахождения и Х^(к+1) на каждой итерации к состоит в следующем.

1. Генерируем s случайных направлений находим соответствующие им s значений векторов и s значений f(X_v) функции f(X) в этих точках X_v.

2. В случае поиска минимума функции f(X) выберем то , которое соответствует минимальному значению среди значений f(X_v), т.е. при примем и ; В случае поиска максимума функции f(X) при примем и .

3. Определяем . Если выполнено условие ,т.е. , переходим к п.4, иначе полученное Х отбрасывается и переходим к п.1.

4. Если при поиске минимума f(X) (или при максимуме), то переходим к п.1, иначе Х^(к+1) =Х.

5. Конец алгоритма.

3. Метод с обучением

В отличие от первых двух методов без обучения в данном методе учитывается опыт выбора удачного направления поиска экстремума на двух предыдущих итерациях.

Алгоритм нахождения и Х^(к+1) на каждой итерации к состоит в следующем:

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

с использованием знака «+» при в случае поиска максимума функции f(X) и «-» при минимуме f(X);

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

1. Находим .

2. Определяем . Если выполнено условие ,т.е. , переходим к п.4, иначе полученное Х отбрасывается и переходим к п.1.

3. Если в случае поиска минимума f(X) (или при максимуме), то переходим к п.1, иначе Х^(к+1) =Х

4. Конец алгоритма.

Задачи выпуклого программирования и их решение

В частном случае, когда задача нелинейного программирования является задачей выпуклого программирования, ее любой локальный экстремум одновременно будет и глобальным, а зачастую и единственным. Задача выпуклого программирования представляет собой задачу нахождения min f(X) или max f(X) ( )при условии, что f(X) выпуклая функция при поиске ее минимума и вогнутая функция при максимуме, а допустимое множество XD является замкнутым и выпуклым. Множество XD называется выпуклым, если вместе с любыми принадлежащими ему двумя точками, этому множеству принадлежит и соединяющий их.

Функция называется выпуклой на выпуклом множестве XD, если для любых двух точек и этого множества и для любого числа выполнялось соотношение

Функция строго выпукла, если данное неравенство строгое при . Функция f(X) вогнутая, если функция - f(X)- выпуклая. Пример строго выпуклой функции f(X) при n=1 и при любом х на рисунке (а), строго вогнутой на (б), выпуклой для и строго выпуклой для на рисунке (в).

Выпуклая функция на замкнутом и выпуклом множестве XD обладает следующим свойством: ее любой локальный минимум одновременно является и ее глобальным минимумом, а для строго выпуклой функции – и единственным. Любой локальный максимум вогнутой функции на замкнутом и выпуклом множестве XD является одновременно и ее глобальным максимумом, а для строго вогнутой функции – и единственным.

Справедлива теорема. Для того, чтобы непустое множество было выпукло, достаточно, чтобы все были выпуклыми функциями. Учитывая данную теорему и задачи выпуклого программирования, получаем два вида задачи:

1) , при условии, что f(X) и все - выпуклые функции;

2) , при условии, что f(X)- вогнутая а все - выпуклые функции.

Функция строго вогнута, если выполняется условие отрицательной определенности ее матрицы Гессе, и строго выпукла при положительной определенности.

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

10

Характеристики

Список файлов ответов (шпаргалок)