g8 (Акчурин)
Описание файла
Файл "g8" внутри архива находится в папке "Акчурин". Документ из архива "Акчурин", который расположен в категории "". Всё это находится в предмете "базы данных" из 7 семестр, которые можно найти в файловом архиве НИУ «МЭИ» . Не смотря на прямую связь этого архива с НИУ «МЭИ» , его также можно найти и в других разделах. Архив можно найти в разделе "книги и методические указания", в предмете "базы данных" в общих файлах.
Онлайн просмотр документа "g8"
Текст из документа "g8"
66
8.Задачи условной оптимизации.
8.1Выпуклые функции.
Определение.
Пусть , где - непустое выпуклое множество в .Функция выпукла на множестве , если для и :
( 8.1.0)
Функция строго выпукла на множестве , если для и :
Функция называется вогнутой ( строго вогнутой ) , если функция выпукла ( строго выпукла ) на .
Что означает соотношение ( 8.1 .0):
для выпуклой функции значение в точках отрезка, соединяющего , не превосходит средневзвешенного ( с тем же ) значения величин .
Примеры выпуклых функций:
;
8.2Задачи оптимизации с ограничениями в форме равенств и неравенств. Штрафные и барьерные функции.
Суть используемых здесь методов заключается в замене исходной задачи эквивалентной задачей безусловной оптимизации или последовательностью задач безусловной оптимизации.
Рассматриваются два альтернативных подхода:
-
первый называется методом штрафных функций и заключается в следующем: к целевой функции исходной задачи добавляется функция, интерпретируемая как штраф за нарушение каждого из ограничений. Метод генерирует последовательность недопустимых точек, которая сходится к оптимальному решению исходной задачи.
-
второй подход называется методом барьеров. В этом методе к целевой функции исходной задачи добавляется барьерный член, который не позволяет генерируемым точкам выходить за пределы допустимой области, и эта последовательность точек сходится к оптимальному решению исходной задачи. Этот метод (барьер) может использоваться только в задачах с ограничениями в виде неравенств.
8.2.1Метод штрафных функций.
В этом методе с помощью функций, задающих ограничения, строится так называемый штраф, который добавляется к целевой функции исходной задачи так, что нарушение какого либо из ограничений становится невыгодным с точки зрения полученной задачи безусловной оптимизации.
Обычно подходящая штрафная функция должна определять положительный штраф в недопустимых точках и не штрафовать допустимые точки.
Если ограничения имеют форму:
то целесообразно использовать штрафную функцию следующего вида:
где - непрерывные функции , удовлетворяющие условиям:
Типичными являются следующие формы функций :
где - целые положительные числа.
Таким образом, штрафная функция, с учетом ( 8.2 .0), имеет вид:
Функцию называют вспомогательной.
Пример1.
Рассмотрим задачу
Положим
тогда
Минимум достигается в точке . При последовательность таких точек стремиться к точке , являющейся точкой минимума исходной задачи.
График.
Пример2.
Оптимум достигается в точке и равен .
Задача со штрафом при достаточно большом :
, - координаты вектора .
При целевая функция этой задачи выпуклая. Необходимым и достаточным условием оптимальности является равенство нулю градиента функции
то есть частные производные
.
Решая эту систему из двух уравнений, получаем:
при .
8.2.1.1Алгоритм метода штрафных функций.
- точность вычисления;
- начальная точка;
- штрафной параметр, ;
- параметр цикла;
- оптимальное решение задачи безусловной оптимизации(на каждой итерации свое);
- оптимальное решение исходной задачи.
8.2.2Метод барьерных функций.
Иначе метод барьеров или метод внутренних штрафных функций.
В этом методе к целевой функции исходной задачи добавляется барьерная функция, которая не позволяет генерируемым точкам выходить за пределы допустимой области. Эта последовательность точек сходится к оптимальному решению исходной задачи.
Барьерные функции используются, также как и штрафные, для преобразования задачи с ограничениями в задачу безусловной оптимизации или в последовательность таких задач. Барьерные функции как бы препятствуют выходу из допустимой области. Ограничения должны быть только в форме неравенств .
Исходная задача
преобразуется в задачу безусловной оптимизации:
,
где - барьерная функция, которая в общем виде записывается как:
,
где - функция одной переменной, удовлетворяющая условиям:
, если .
конструируется таким образом, чтобы она была неотрицательна и непрерывна в области и стремилась к бесконечности при приближении из внутренней точки к границе области.
Типичная барьерная функция имеет вид: («минус», так как задача на min и ).
Функцию называют вспомогательной конструкцией.
8.2.2.1Алгоритм метода барьеров.
- точность вычисления;
- начальная точка;
- штрафной параметр, ;
- параметр цикла;
- оптимальное решение задачи безусловной оптимизации(на каждой итерации свое);
- оптимальное решение исходной задачи.