Навигация
Выпуклая оптимизация. Условие выпуклости
23385
знаков
0
таблиц
0
изображений
4 Выпуклая оптимизация. Условие выпуклости
Основная задача выпуклого программирования
Пусть задано выпуклое и замкнутое множество 
. Рассмотрим множество
={
}, 
=(
,…,
), 
Î
.
где 
(
) — вогнутые (выпуклые вверх) непрерывные на скалярные функции. В теории математического программирования каждый элемент 
Î принято называть допустимым планом, а само множество — множеством допустимых планов.
Формальная постановка задачи выпуклого программирования
Задачу
,
где 
выпукла, а определяется вышеприведенными условиями, называется основной задачей выпуклого программирования.
0 означает, что ставится задача:
Если существует минимальное значение функции на множестве , то среди всех допустимых планов найти оптимальный план 
, для которого
=
=
при этом число называют значением задачи.
Если оптимального плана не существует, то требуется
· либо найти значение задачи как точную нижнюю грань значений функции на множестве :
=
· либо убедиться, что неограничена снизу на множестве ;
· либо убедиться в том, что множество допустимых планов пусто.
Для решения предложенной оптимизационной задачи следует выполнить следующие действия:
· Определить множество .
· Определить вектор-функцию =(,…,) и вектор Î.
· Определить множество допустимых планов ={}.
· Привести задачу к стандартной форме основной задачи выпуклого программирования и определить оптимизируемую функцию .
· Проверить, является ли полученная оптимизационная задача ЗВП, для этого
· проверить на выпуклость множество ;
· проверить на выпуклость функцию .
В случае успеха п.
· Построить функцию Лагранжа полученной ЗВП.
· С помощью дифференциальных условий Куна-Таккера найти седловые точки построенной функции Лагранжа.
В случае неудачи п. попытаться найти другие методы решения задачи.
Методы субградиентной оптимизации. Эти итеративные процедуры формируют последовательность векторов {lk}.
Фундаментальный теоретический результат заключается в том, что
.
Размер шага на практике обычно выбирают, следуя ,
где q k — скаляр, 0 < q k
2 и z* — верхняя граница для n(D). Обычно z* получают эвристикой для P. В методе ветвей и границ z* — текущий рекорд. Последовательность q k, как правило, начинается с q 0=2 и затем q k делится пополам, через фиксированное число итераций, зависящее от размерности задачи.
Похожие работы
... несколько уравнений, а в каждом уравнении - несколько переменных. Задача оценивания параметров такой разветвленной модели решается с помощью сложных и причудливых методов. Однако все они имеют одну и ту же теоретическую основу. Поэтому для получения начального представления о содержании эконометрических методов мы ограничимся в последующих параграфах рассмотрением простой линейной регрессии. ...
... во многих экономических задачах, приводит к линейной функции с линейными ограничениями, наложенными на неизвестные. 2. Области применения и ограничения использования линейного программирования для решения экономических задач Особенно широкое применение методы и модели линейного программирования получили при решении задач экономии ресурсов (выбор ресурсосберегающих технологий, составление ...
... управления, прочие системы. Целью данной курсовой работы является рассмотрение, освещение и оценка возможностей пакета прикладных программ MS OFFICE с точки зрения информационных технологий и методов их использования при решении экономических задач. 2. Использование пакета прикладных программ MS OFFICE при решении экономических задач 2.1 Обзор возможностей Microsoft Office Пакет ...
... (нынешняя) стоимость или общая сумма, которая на настоящий равноценна серии будущих выплат; Тип - 0 или 1, Если 0 – оплата производится в конце периода, если 1, то в начале. В данной задаче функции приобретают вид ЧПС(0;D2;E2;F2) и БС(I2;B2;;-C2). 4. С помощью функции Подбор параметра определена ставка, при которой выгоднее деньги вложить в инвестиционный проект 8,5%. 1. Внесены исходные ...
0 комментариев