Оглавление:
Методы внутренней точки для задачи математического программирования
Рассмотрим общую задачу математического программирования, не содержащую ограничений в виде равенств, т.е. минимизировать 
при ограничениях
Пусть вблизи локального минимума этой задачи 
существует окрестность, где есть такая точка 
в которой
и выполняются условия строгой дополняющей нежесткости:
если
Видоизменим достаточные условия локального минимума в точке , сформулированные в разд. 1.5. Предположим, что при малом 
в точке 
вблизи точки 
выполняются условия:
Из второго условия выразим 
и подставим это выражение в последнее равенство:
Непосредственной проверкой легко установить, что левая часть этого выражения — это градиент функции
обращающийся в нуль в точке 
, причем 
при 
. Функцию 
в таком виде называют логарифмической штрафной. Аналогично получаем другой вид штрафной функции 
полагая
При условии, что
имеем
и функция
примет вид
Задавая последовательность значений 
, стремящуюся к нулю, получаем последовательность 
, сходящуюся к 
. С помощью новых функций 
мы свели задачу определения условного экстремума (задачу математического программирования) к задаче поиска безусловного экстремума функции . Точнее, задачу математического программирования заменили семейством функций, зависящих от параметра r и обладающих следующими свойствами:
1) в окрестности оптимальной точки они близки к заданной минимизируемой функции;
2) каждая функция из построенного семейства достаточно быстро возрастает при приближении к границе допустимой области из «внутренней» части допустимой области.
К минимизируемой функции исходной задачи мы добавили ряд слагаемых, называемых штрафными (барьерными) функциями, зависящими от параметра r и функции одного из ограничений. При фиксированном значении параметра r второе слагаемое стремится к бесконечности при стремлении к нулю его аргумента. Каждую функцию семейства подвергают безусловной минимизации, и этот процесс не может вывести за пределы допустимой области. Подобные методы названы методами внутренней точки.
В задаче математического программирования при наличии ограничений-равенств допустимой области (в виде области) нет, и «метод внутренней точки» не применим.
Рассмотрим некоторые примеры перехода от задачи математического программирования к задаче безусловной минимизации «методом внутренней точки».
Пример:
Минимизировать
при ограничениях
Решение:
Построим логарифмическую штрафную функцию
Определим точки минимума аналитически, так как дифференцируема в рассматриваемой области. Для нахождения 
получим систему уравнений:
Отсюда найдем, что
(здесь оставим только знак «+», так как 
);
Заметим, что значения удовлетворяют условию положительной определенности матрицы 
. Возьмем последовательность значений r: 1,0; 0,5; 0,25; 0,1. Соответственно получим последовательности значений
сходящиеся при r->0 к точке (0, 0). Графическое решение данной задачи представлено на рис. 5.14.
В общем случае в задачах со многими локальными минимумами (при слабых условиях регулярности) существует последовательность безусловных локальных минимумов, сходящихся к каждому из условных локальных минимумов.
Рассмотрим второй пример: решение задачи линейного программирования методом внутренней точки.
Пример:
Минимизировать 
при условии
Решение:
Построим логарифмическую штрафную функцию
Необходимое условие существования минимума:
Отсюда находим, что
Из условия
следует, что для
безусловный минимум будет при
Эта теория взята со страницы лекций по предмету «математическое программирование»:
Предмет математическое программирование
Возможно эти страницы вам будут полезны:
