Оглавление:
Методы внутренней точки для задачи математического программирования
Рассмотрим общую задачу математического программирования, не содержащую ограничений в виде равенств, т.е. минимизировать при ограничениях
![Методы внутренней точки для задачи математического программирования](https://lfirmal.com/wp-content/uploads/2020/04/image-1538.png)
Пусть вблизи локального минимума этой задачи существует окрестность, где есть такая точка
в которой
![Методы внутренней точки для задачи математического программирования](https://lfirmal.com/wp-content/uploads/2020/04/image-1541.png)
и выполняются условия строгой дополняющей нежесткости:
![Методы внутренней точки для задачи математического программирования](https://lfirmal.com/wp-content/uploads/2020/04/image-1543.png)
если
![Методы внутренней точки для задачи математического программирования](https://lfirmal.com/wp-content/uploads/2020/04/image-1544.png)
Видоизменим достаточные условия локального минимума в точке , сформулированные в разд. 1.5. Предположим, что при малом
в точке
вблизи точки
выполняются условия:
![Методы внутренней точки для задачи математического программирования](https://lfirmal.com/wp-content/uploads/2020/04/image-1553.png)
Из второго условия выразим и подставим это выражение в последнее равенство:
![Методы внутренней точки для задачи математического программирования](https://lfirmal.com/wp-content/uploads/2020/04/image-1556.png)
Непосредственной проверкой легко установить, что левая часть этого выражения — это градиент функции
![Методы внутренней точки для задачи математического программирования](https://lfirmal.com/wp-content/uploads/2020/04/image-1557.png)
обращающийся в нуль в точке , причем
при
. Функцию
в таком виде называют логарифмической штрафной. Аналогично получаем другой вид штрафной функции
полагая
![Методы внутренней точки для задачи математического программирования](https://lfirmal.com/wp-content/uploads/2020/04/image-1566.png)
При условии, что
![Методы внутренней точки для задачи математического программирования](https://lfirmal.com/wp-content/uploads/2020/04/image-1567.png)
имеем
![Методы внутренней точки для задачи математического программирования](https://lfirmal.com/wp-content/uploads/2020/04/image-1568.png)
и функция
![Методы внутренней точки для задачи математического программирования](https://lfirmal.com/wp-content/uploads/2020/04/image-1569.png)
примет вид
![Методы внутренней точки для задачи математического программирования](https://lfirmal.com/wp-content/uploads/2020/04/image-1570.png)
Задавая последовательность значений , стремящуюся к нулю, получаем последовательность
, сходящуюся к
. С помощью новых функций
мы свели задачу определения условного экстремума (задачу математического программирования) к задаче поиска безусловного экстремума функции
. Точнее, задачу математического программирования заменили семейством функций, зависящих от параметра r и обладающих следующими свойствами:
1) в окрестности оптимальной точки они близки к заданной минимизируемой функции;
2) каждая функция из построенного семейства достаточно быстро возрастает при приближении к границе допустимой области из «внутренней» части допустимой области.
К минимизируемой функции исходной задачи мы добавили ряд слагаемых, называемых штрафными (барьерными) функциями, зависящими от параметра r и функции одного из ограничений. При фиксированном значении параметра r второе слагаемое стремится к бесконечности при стремлении к нулю его аргумента. Каждую функцию семейства подвергают безусловной минимизации, и этот процесс не может вывести за пределы допустимой области. Подобные методы названы методами внутренней точки.
В задаче математического программирования при наличии ограничений-равенств допустимой области (в виде области) нет, и «метод внутренней точки» не применим.
Рассмотрим некоторые примеры перехода от задачи математического программирования к задаче безусловной минимизации «методом внутренней точки».
Пример:
Минимизировать
![Методы внутренней точки для задачи математического программирования](https://lfirmal.com/wp-content/uploads/2020/04/image-1580.png)
при ограничениях
![Методы внутренней точки для задачи математического программирования](https://lfirmal.com/wp-content/uploads/2020/04/image-1582.png)
Решение:
Построим логарифмическую штрафную функцию
![Методы внутренней точки для задачи математического программирования](https://lfirmal.com/wp-content/uploads/2020/04/image-1584.png)
Определим точки минимума аналитически, так как
дифференцируема в рассматриваемой области. Для нахождения
получим систему уравнений:
![Методы внутренней точки для задачи математического программирования](https://lfirmal.com/wp-content/uploads/2020/04/image-1587.png)
Отсюда найдем, что
![Методы внутренней точки для задачи математического программирования](https://lfirmal.com/wp-content/uploads/2020/04/image-1588.png)
(здесь оставим только знак «+», так как );
![Методы внутренней точки для задачи математического программирования](https://lfirmal.com/wp-content/uploads/2020/04/image-1592.png)
Заметим, что значения удовлетворяют условию положительной определенности матрицы
. Возьмем последовательность значений r: 1,0; 0,5; 0,25; 0,1. Соответственно получим последовательности значений
![Методы внутренней точки для задачи математического программирования](https://lfirmal.com/wp-content/uploads/2020/04/image-1595.png)
сходящиеся при r->0 к точке (0, 0). Графическое решение данной задачи представлено на рис. 5.14.
![Методы внутренней точки для задачи математического программирования](https://lfirmal.com/wp-content/uploads/2020/04/image-1597.png)
В общем случае в задачах со многими локальными минимумами (при слабых условиях регулярности) существует последовательность безусловных локальных минимумов, сходящихся к каждому из условных локальных минимумов.
Рассмотрим второй пример: решение задачи линейного программирования методом внутренней точки.
Пример:
Минимизировать при условии
![Методы внутренней точки для задачи математического программирования](https://lfirmal.com/wp-content/uploads/2020/04/image-1602.png)
Решение:
Построим логарифмическую штрафную функцию
![Методы внутренней точки для задачи математического программирования](https://lfirmal.com/wp-content/uploads/2020/04/image-1605.png)
Необходимое условие существования минимума:
![Методы внутренней точки для задачи математического программирования](https://lfirmal.com/wp-content/uploads/2020/04/image-1606.png)
Отсюда находим, что
![Методы внутренней точки для задачи математического программирования](https://lfirmal.com/wp-content/uploads/2020/04/image-1607.png)
Из условия
![Методы внутренней точки для задачи математического программирования](https://lfirmal.com/wp-content/uploads/2020/04/image-1608.png)
следует, что для
![Методы внутренней точки для задачи математического программирования](https://lfirmal.com/wp-content/uploads/2020/04/image-1609.png)
безусловный минимум будет при
![Методы внутренней точки для задачи математического программирования](https://lfirmal.com/wp-content/uploads/2020/04/image-1611.png)
Эта теория взята со страницы лекций по предмету «математическое программирование»:
Предмет математическое программирование
Возможно эти страницы вам будут полезны: