Определение подходящего направления
Для описания алгоритма выбора наилучшего направления поиска очередной точки минимизирующей последовательности введём ряд важных понятий.
Определение 13.3. Ограничение ( ) называется
активным в фиксированной точке , если
( ).
Введём в рассмотрение множества индексов активных ограничений
в фиксированной точке : - индексное множество активных нелинейных ограничений; - индексное множество активных линейных ограничений;
; .
Введем в рассмотрение множество n-мерных векторов в точке и построим множество
Множество представляет собой конус возможных направлений в точке . Если - внутренняя точка множества R, то множество пусто, т.е. в этой точке нет активных ограничений, и на выбор вектора S не накладывается никаких ограничений.
Введем искусственную переменную и определим множество (n+1)-мерных векторов следующим образом:
.
Задачу выбора подходящего направления сформулируем как задачу линейного программирования:
. (13.7)
Очевидно, что при множества и совпадают. Если , то из ограничения следует, что и направление будет подходящим. В этом случае , т.е. не направлено по касательной к нелинейным границам. При этом, чем больше , тем больше отличается от нуля , т.е. тем больший угол образуется между и внешней нормалью . Если , то точка оказывается точкой минимума функции .
Присутствие в задаче (13.7) ограничения объясняется следующим образом. Когда речь идёт о выборе направления, нас интересует именно направление, которое задаётся некоторым вектором произвольной длины. Но при решении ЗЛП (13.7) величина может оказаться неограниченной. Чтобы этого избежать следует наложить на длину S некоторые ограничения. Поэтому в постановке задачи (13.7) должно присутствовать так называемое условие нормализации. Таким условием может быть одно из следующих ограничений:
№1. .
№2.
№3. если или если
№4.
Признак оптимальности в задаче выбора наилучшего подходящего направления устанавливается следующей теоремой.
Теорема 13.2. Точка является точкой минимума на , регулярном по Слейтеру тогда и только тогда, когда для всех , удовлетворяющих неравенству .
Д о к а з а т е л ь с т в о.Если в решении задачи выбора направления (13.7) окажется, что , то соответствующее направление будет подходящим, и точка не может быть точкой минимума функции .
Пусть теперь для всех , удовлетворяющих условиям
(13.8) | ||
(13.9) | ||
(13.10) |
Будем считать для сокращения записей, что в (13.10) содержатся также и прямые ограничения на переменные задачи .
Введя в рассмотрение - мерные вектора , неравенство можно записать в виде
В силу теоремы Фаркаша, устанавливающей равносильность условий
,
найдется такой вектор , , что имеют место равенства
(13.11) | |
(13.12) |
Если , т.е. , то из (13.11)
, (13.13)
Умножая скалярно равенство (13.13) на некоторый произвольный вектор , принадлежащий множеству получим
.
Но в множестве выполняются условия и для любого . Следовательно, для любого , а значит в точке нет подходящего направления и она является точкой минимума функции на .
Если , то из условия и равенства (13.12) следует существование по крайней мере одного , . Тогда умножая (13.11) на
(13.14)
Но из регулярности по Слейеру следует существование точки такой, что для всех . Тогда, полагая , в силу теоремы 12.5 имеем
т.к. , а . Таким образом, хотя бы одно из слагаемых в (13.14) строго меньше нуля а все остальные неположительны. Поэтому левая часть равенства (13.14) не может быть равна нулю, т.е. случай невозможен. Теорема доказана.
Контрольные вопросы
1. В чем заключается основная идея метода возможных направлений?
2. Какое направление называется возможным в допустимой точке?
3. Поясните понятие подходящего направления в допустимой точке.
4. Какие ограничения называются активными в фиксированной точке?
5. Какой метод решения задачи выпуклого программирования называется методом возможных направлений?
6. Приведите алгоритм построения начального приближения в методе возможных направлений.
7. Опишите процедуру построения очередной точки минимизирующей последовательности в методе возможных направлений.
8. Дайте определениеконуса возможных направлений в точке.
9. Опишите постановку вспомогательной задачи для выбора наилучшего подходящего направления в допустимой точке.
10. Сформулируйте признак оптимальности в задаче выбора наилучшего подходящего направления в допустимой точке.
Дата добавления: 2015-08-14; просмотров: 639;