ЭКОНОМИКА И МАТЕМАТИЧЕСКИЕ МЕТОДЫ, 2004, том 40, № 2, с. 116-118
ЗАМЕТКИ И ПИСЬМА
КОНЦЕВЫЕ ФУНКЦИИ
© 2004 г. Т. М. Гатауллин
(Москва)
1. Концевые функции. Введем новый, полезный для задач оптимизации класс функций.
Определение. Назовем функцию максконцевой, если ее область определения - выпуклое множество, максимум этой функции на любом отрезке, лежащем в области определения, достигается на одном из концов этого отрезка.
Аналогично определяются миниконцевые функции. Миниконцевые и максконцевые функции объединяются в класс концевых.
Область определения функции - это подмножество некоторого конечного арифметического линейного пространства (т.е. в Я" рассматриваются только конечномерные пространства и их подмножества). Отрезок в таком множестве определяется по формуле
Ух, у е Я"[х, у] = [Хх + (1-X)у: 0 <Х< 1}.
Пусть на этом отрезке задано естественное линейное упорядочение.
2. Концевые функции и угловые точки. Точка некоторого подмножества линейного пространства называется угловой для этого подмножества, если она не является внутренней точкой никакого отрезка, лежащего в этом множестве. Основное свойство концевых функций выражено в следующем предложении. (Аналогично формулируются свойства для миниконцевых функций.)
Предложение 1. Пусть/- максконцевая функция, определенная на компактном выпуклом множестве, тогда для любой точки г найдется угловая точка х этого множества, такая что /(г) < /(х).
Следствие 1. Если максимум максконцевой функции на компактном выпуклом множестве достигается, то он достигается в некоторой угловой точке.
Следствие 2. Если множество угловых точек компактного выпуклого множества конечно, то максконцевая функция на этом множестве достигает максимума (очевидно, в некоторой угловой точке).
Следствие 3. Если максконцевая функция не ограничена на компактном выпуклом подмножестве некоторого Я", то она не ограничена на множестве его угловых точек.
Доказательство предложения 1. По теореме Крейна-Мильмана (Рудин, 1975) компактное выпуклое подмножество К с Я есть выпуклая оболочка множества его угловых точек. Пусть г - произвольная точка множества К,
тогда г = Хх +...+ Хтхт для некоторых угловых точек х1, ..., хт и Х1, ..., Хт > 0 и 1 X; = 1, т.е. г = (Х^) + (Хх + ... +
+ Хтхт). Следовательно, г - (внутренняя) точка отрезка [х1,у], где у = 2 ( Х;/(1 - Х^)х;. Так как / максконцевая
функция, то она достигает максимума в точке х1 или в точке у. Если имеет место случай 1, то доказательство окончено, так как х1 - угловая точка и /(г) < /(х ). В случае 2 точка у является линейной комбинацией т-1 угловой точки и /(г) < /(у). Далее действуем по индукции. В
Предложение 2. Пусть К - компактное выпуклое подмножество и О - множество его угловых точек. Пусть / на О положительно, а в остальных точках множества К равно 0, тогда / - максконцевая функция.
Доказательство. Пусть I - отрезок из К. Если он лежит в К\О , то / принимает максимум в одном из концов, поскольку на I функция равна 0; если один из концов лежит в О, то тем более максимум/принимает в одном из концов. Итак, / - максконцевая функция.
Предложение 2 показывает, что свойства концевых функций могут сильно отличаться от свойств непрерывных, линейных и других хорошо изученных функций.
3. Характеризация концевых функций одной переменной. Для максконцевых функций одной переменной следствие 1 верно и без оговорки о достижении максимума, так как любое компактное выпуклое подмножество Я1 является отрезком. Среди функций одной переменной монотонные функции являются концевыми в обоих смыслах.
Следующее предложение характеризует максконцевые функции одной переменной.
Предложение 3. Функция одной переменной является концевой, если и только если ее область определения есть объединение двух промежутков монотонности: максконцевая функция на левом промежутке убывает, на правом возрастает, для миниконцевой - наоборот.
Доказательство. Так как область определения концевой функции - это выпуклое подмножество действительной прямой, то некоторый промежуток может быть или конечным, или бесконечным. Докажем, что максконцевая функция / характеризуется указанным образом. Предположим, что минимум / достигается в какой-то точке, принадлежащей области определения. Пусть х < у < с, тогда максимум функции/ на отрезке [х, с] достигается в точке х, так что/(х) </(у), т.е. левее точки с функция/убывает. Аналогично, пусть с < х < у, тогда максимум функции/на отрезке [с, у] достигается в точке у, так что/(х) </(у), т.е. правее точки с функция/возрастает.
Рассмотрим теперь случай, когда минимум/не достигается. Сначала пусть М/ = г. Существует последовательность {х;}, на которой этот инфимум реализуется. Возможны два случая: существует ограниченная подпоследовательность,
КОНЦЕВЫЕ ФУНКЦИИ
117
на которой достигается инфимум, и случай, когда такой подпоследовательности не существует. В обоих случаях можно считать, что сама последовательность {x} такова.
1. Пусть c = lim{xj} и на рассматриваемой последовательности функция убывает. Тогда /(c) > r. Предположим, что вся последовательность {xj} лежит слева от с.
Пусть г < у < с . Найдется Xj такое, что у < Xj и fxj) < /у), тог- Рисунок.
да максимум / на отрезке [г, Xj] достигается в точке г, следовательно, /(г) >/(у) , так что левее точки с функция/убывает.
Пусть с < г < у. Найдется xk такое, что /(xk) </(с). Тогда максимум/на отрезке [x^, у] достигается в точке у. Следовательно, /(г) >/(у) и правее точки с функция/возрастает.
Предположим теперь, что вся последовательность {xj} лежит справа от с. Пусть с < у < г . Найдется xj такое, что xj < у и /(xj) < /(у), тогда максимум/ на отрезке [г, xj] достигается в точке г. Следовательно, /(г) > /(у) и правее точки с функция / возрастает.
Пусть г < у < с. Найдется xk такое, что /(xk) < /(у), тогда максимум/ на отрезке [г, x^] достигается в точке г. Следовательно, /(г) >/(у) и левее точки с функция/убывает.
2. Рассмотрим случай, когда инфимум реализуется на бесконечности. Пусть предел последовательности {xj} стремится к +
Пусть г < у. Найдется xj такое, что xj > у и /(у) > /(xj). Тогда на отрезке [г-xj] максимум / может быть только в г. Следовательно, /(г) >/(у) и/убывает на всей области определения.
Если же предел последовательности {xj} стремится к - то доказывается, что/возрастает на всей области определения. В
Предложение 4. Среди функций одной переменной только монотонные функции являются одновременно и мак-сконцевыми, и миниконцевыми.
Доказательство. Ранее было показано, что монотонная функция является и максконцевой, и миниконцевой. Нам осталось доказать, что функция одной переменной, которая является одновременно максконцевой и миниконцевой, будет и монотонной.
Рассмотрим такую функцию /. Если это константа, то нам не надо ничего доказывать. Поэтому пусть найдутся точки a < b: /(a) Ф/(b) и, например,/(a) </(b). Пусть b < с. Тогда/(b) </(с), так как/максконцевая. Пусть с < d, тогда по той же причине /(с) < /(d). Следовательно, правее точки b функция / возрастает. Так как / миниконцевая, то левее точки a функция/убывает. Пусть теперь a <p < q < b. Так как/(а) </(b) и/- максконцевая, то/(q) </(b). По той же причине /(p) < /(q), а так как она одновременно и миниконцевая, то /(a) < g(p). Тем самым доказано, что/- возрастающая функция. В
4. Концевые функции многих переменных. Следующее предложение дает важные примеры концевых функций многих переменных. Напомним, что функция / называется выпуклой, если ее область определения - выпуклое подмножество (некоторого линейного пространства) и/(Xx + (1 - Х)у) < X/(x) + (1 - У/у) для любых x, у из области определения и любого X е [0, 1].
Предложение 5. Выпуклая функция является максконцевой.
Доказательство. Пусть функция / выпукла и отрезок [x, у] лежит в области определения. Тогда /(Xx + (1 - Х)у) < < X/(x) + (1 - Х)/(у) < (X + (1 - X))g = g, где g - максимальное из чисел/(x),/(у). Тем самым доказано, что/- максконцевая функция. В
Следствие 4. Линейная функция является одновременно и максконцевой, и миниконцевой.
Замечание. Выпуклые функции не покрывают весь объем класса максконцевых функций, даже для функций одной переменной. Так, на рисунке представлен график максконцевой функции (по предложению 3), не являющейся выпуклой.
Это замечание вместе с предложением 5 позволяет привести простые примеры максконцевых и не миниконцевых функций. Например, таковой будет выпуклая функция, не являющаяся возрастающей, скажем, квадратичная с положительным старшим коэффициентом.
Предложение 6. Пусть u(%1,., xm), i = 1, ..., m - линейные функции, а /(U1, ..., um) - концевая функция переменных «1, ..., um. Тогда суперпозиция этих функций, т.е. функция F(x1, ..., xn) = /(u^x^ ..., xn), ..., um(x1, ..., xn)) - концевая функция переменных x1,..., xn (того же типа, что и/, т.е. максконцевая/миниконцевая).
Доказательство. Перейдем к векторным обозначениям. Пусть X - вектор из области определения D(U) вектор-функции U(X). Надо доказать, что функция F(X) = /(U(X)) - концевая. Пусть I = {A + (1 - Х)В} - отрезок в D(U), тогда вектор-функцией U он переводится в отрезок U(I) = {U(A) + (1- X)U(B)}, причем концы отрезка I переходят в концы отрезка U(I) (если U(A) = U(B), то отрезок U(I) вырождается в точку) и, следовательно, на отрезке I нужный экстремум достигается в одном из концов. В
Концевые функции представляют значительное обобщение многих известных функций. Скажем, в задачах линейного программирования (ЛП) целевая функция может считаться всего лишь концевой. Действительно, при такой замене первая основная теорема ЛП остается справедливой. В самом деле, данная теорема гласит, что задача ЛП имеет оптимальное решение, если допустимое множество непусто (необходимое условие) и целевая функция задачи ограничена на допустимом множестве в направлении экстремума. Но, как известно, в задаче ЛП угловых точек в допустимом множестве конечное число, следовательно, целевая (любая!) функция ограничена на множестве G угловых точек. Таким образом, можно сформулировать следующее предложение.
Предложение 7. Пусть дана задача максимизации максконцевой фу
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.