Все Лекции по Оптимизации (g8)

Посмотреть архив целиком

66



  1. Задачи условной оптимизации.

    1. Выпуклые функции.

Определение.

Пусть , где - непустое выпуклое множество в .Функция выпукла на множестве , если для и :

( 8.1.0)

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

Функция называется вогнутой ( строго вогнутой ) , если функция выпукла ( строго выпукла ) на .


Что означает соотношение ( 8.1 .0):

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


Примеры выпуклых функций:

;

;


    1. Задачи оптимизации с ограничениями в форме равенств и неравенств. Штрафные и барьерные функции.

Суть используемых здесь методов заключается в замене исходной задачи эквивалентной задачей безусловной оптимизации или последовательностью задач безусловной оптимизации.

Рассматриваются два альтернативных подхода:


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


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

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

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

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

Если ограничения имеют форму:


то целесообразно использовать штрафную функцию следующего вида:


( 8.2.0)

где - непрерывные функции , удовлетворяющие условиям:

, если и , если .

, если и , если .


Типичными являются следующие формы функций :

,


где - целые положительные числа.

Часто выбирают .


Таким образом, штрафная функция, с учетом ( 8.2 .0), имеет вид:

Функцию называют вспомогательной.


Пример1.


Рассмотрим задачу



Решение .


Положим

,

тогда


Минимум достигается в точке . При последовательность таких точек стремиться к точке , являющейся точкой минимума исходной задачи.


График.




Пример2.



Оптимум достигается в точке и равен .


Задача со штрафом при достаточно большом :


, - координаты вектора .

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

то есть частные производные

.

Решая эту систему из двух уравнений, получаем:


при .

        1. Алгоритм метода штрафных функций.


- точность вычисления;

- некое число, ;

- начальная точка;

- штрафной параметр, ;

- параметр цикла;

- оптимальное решение задачи безусловной оптимизации(на каждой итерации свое);

- оптимальное решение исходной задачи.

      1. Метод барьерных функций.

Иначе метод барьеров или метод внутренних штрафных функций.

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

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

Исходная задача

преобразуется в задачу безусловной оптимизации:

,

где - барьерная функция, которая в общем виде записывается как:

,

где - функция одной переменной, удовлетворяющая условиям:

, если .

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

Типичная барьерная функция имеет вид: («минус», так как задача на min и ).

Функцию называют вспомогательной конструкцией.

        1. Алгоритм метода барьеров.

- точность вычисления;

- некое число, ;

- начальная точка;

- штрафной параметр, ;

- параметр цикла;

- оптимальное решение задачи безусловной оптимизации(на каждой итерации свое);

- оптимальное решение исходной задачи.




Случайные файлы

Файл
4252.rtf
158904.rtf
82801.rtf
3683-1.rtf
183297.doc