WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     || 2 |
Государственный комитет Российской Федерации по высшему образованию Дальневосточный государственный университет Выпуклые функции и их свойства Учебно-методическое пособие по курсу "Методы Оптимизации" Владивосток 1996 2 УДК519.48 В методических указания приводятся необходимые сведения по теме "Выпуклые функции и их свойства", упражнения по исследованию функций на выпуклость и экстремум. Указания предназначены для студентов-математиков 3 и 4 курсов, слушающих курс "Методы оптимизации".

Методические указания подготовлены кафедрой процессов управления.

Печатается по решению учебно-методического совета ДВГУ.

Составитель Л.В.Горячев.

© Дальневосточный государственный университет 1986 3 Свойство выпуклости функции является фундаментальным в математике наряду с такими свойствами как монотонность, непрерывность, дифференцируемость и т.д. Особенно широко оно используется в теории экстремальных задач. Поэтому студент, прослушавший курс "Методы оптимизации", должен твердо усвоить его и уметь применить при решении практических задач оптимизации.

В учебниках и учебных пособиях по курсу "методы оптимизации"изучению темы "Выпуклые функции"отводится мало времени. По существу излагаются лишь определения и критерии выпуклости; алгебру выпуклых функций студент, по мнению авторов учебников, должен освоить самостоятельно в процессе решения примеров.

Однако по новой учебной программе практические занятия по методам оптимизации исключены из числа обязательных. Это обуславливает необходимость подготовки руководства, призванного более подробно познакомить студента со свойствами выпуклых функций и способствовать выработке у него практических навыков по анализу на выпуклость функций в практических задачах оптимизации.

Этим целям и служат настоящие методические указания.

Определение и практические свойства выпуклых функций Определение. Функция f(x), заданная на выпуклом множестве M Rn, называется выпуклой, если для любых x1, x2 и числа, 0 1 выполняется неравенство f(x1 +(1- )x2) f(x1) +(1- )f(x2) Если равенство достигается только при =0 и =1, то называется строго выпуклой.

Примерами строго выпуклой функции может служить функция:

1. y = lx 2. y = x3. y =sin x, x [, 2] 4. y =cos x, x [/2, 3/2] По определению f(x) является выпуклой, если значение ее от выпуклой комбинации значений аргумента x1 и x2 не больше, чем выпуклая комбинация значений f(x) при этих значениях аргумента.

Геометрически это означает, что хорда, соединяющая эти две точки (любые) графика функции, лежит над дугой, концами которой являются эти точки.

Противоположным по смыслу выпуклости функции является понятие вогнутой функции.

Определение. Функция f(x), заданная на выпуклом множестве, называется вогнутой (строго вогнутой), если g(x) =-f(x) является выпуклой (строго выпуклой) функцией.

При решении практической задачи оптимизации необходимо предварительно исследовать саму целевую функцию и функции, определяющие ограничения на выпуклость. От результатов этого исследования зависит выбор метода численного решения. Часто для этих целей достаточно определения. Рассмотрим ряд простых примеров.

1. Функция y = x является выпуклой. Действительно, для любых x1, x2 M имеем y(x1 +(1- )x2) = x1 +(1- )x x1 +(1- ) x2 = y(x1) +(1- )y(x2) 2. Квадратная форма y = xT Bx + bx + c является выпуклой функцией, где B — неотрицательноопределенная матрица. Действительно, для любых x1, x2 имеем y(x1 +(1- )x2) =(x1 +(1- )x2)T B((x1 +(1- )x2)+ +b(x1 +(1- )x2) +c =(x2 + (x1 - x2))T B(x2 + (x1 - x2))+ +b(x1 +(1- )x2) +c = xT Bx2 + 2(x1 - x2)T B(x1 - x2)+ +xT B(x1 - x2) +(x1 - x2)T Bx2 + bx1 +(1- )bx2 + c xT Bx2 + (x1 - x2)T B(x1 - x2) +xT B(x1 - x2) +(x1 - x2)T Bx2+ 2 +bx1 +(1- bx2 + c +(1- )c = xT Bx2 + xT B(x1 - x2)2 -xT B(x1 - x2) +xT B(x1 - x2) +(x1 - x2)T Bx2 + bx1 +(1- )bx2+ 2 +c +(1- )c = xT Bx2 - xT Bx2 + xT Bx1 - xT Bx2 + xT Bx2+ 2 2 1 1 +bx1 +(1- )bx2 + c +(1- )c = (xT Bx1 + bx1 + c)+ (1 - )(xT Bx2 + bx2 + c) =y(x1) +(1- )y(x2) 3. Пользуясь определением, можно установить выпуклость квадратного скалярного произведения y =(a, x)2. Действительно, y(x1 +(1- )x2) =(a, x1 +(1- )x2)2 =(a, x2 + (x1 - x2))2 = =[(a, x2) +(a, x1 - x2)]2 =(a, x2)2 +2(a, x2)(a, x1 - x2)+ +2(a, x1 - x2)2 (a, x2)2 +2(a, x2)(a, x1 - x2) +(a, x1 - x2)2 = =(a, x2)2 + [2(a, x2) - (a, x1 - x2)] (a, x1 - x2) =(a, x2)2 + [(a, x1)2-(a, x2)2] =(a, x1)2 +(1- )(a, x2)2 = y(x1) +(1- )y(x2) Однако часто одного определения выпуклой функции оказывается недостаточно для анализа функции и требуется применение более глубоких свойств, определяющих выпуклость.

Перечислим простые свойства выпуклых функций, наиболее часто используемые в теоретических и практических задачах. Знание этих свойств является обязательным для студента, прослушавшего курс "Методы оптимизации".

1. Выпуклые функции непрерывны во всех внутренних точках области определения.

2. Каждой выпуклой функции можно поставить в соответствие множество, называемое эпиграфом. Часто для выпуклой функции оно называется надграфиком, для вогнутой - подграфиком, и обозначается epi f(x). Если f(x) выпуклая, то epi f(x) ={(x, z) | x M, z f(x)}.

В практических случаях анализ на выпуклость некоторой функции можно заменить исследованием ее эпиграфа. Эпиграф часто используется при доказательстве различных свойств выпуклых функций.

3. Неравенство Иенсена: пусть f(x) — выпуклая функция x M Rn, тогда m f ixi if(xi), i =1, i 0, xi M i i i=Действительно, в этом случае epi будет выпуклым множеством и (xi, f(xi)) epi f, xi f(x) M, а значит i(xi, f(xi)) = ( ixi, if(xi)) epi f, откуда следует требуемое неравенство.



Часто условие выполнения неравенства Иенсена используется в качестве определения выпуклой функции.

4. Важнейшим свойством выпуклой функции, широко используемым в практике решения экстремальных задач, является следующее:

Если f(x) — выпуклая функция, то множество G = {x | f(x), = const} является выпуклым.

Доказательство его легко приводится по основе определения.

Для вогнутой функции g(x) множество G = {x | g(x), = const} также является выпуклым.

Таким образом, если целевая функция является выпуклой (вогнутой) и ограничения удовлетворяют указанным условиям, то мы относим задачу к задачам выпуклого (вогнутого) программирования и выбираем метод ее решения.

Исходя из этого, следует отметить, что указанным свойством обладают не только выпуклые функции, но и так называемые квазивыпуклые функции.

Определение. Функция f(x) называется квазивыпуклой, если для данных x1, x2 Rn и любого, 0 f(x1 +(1- )x2) min{f(x1), f(x, 2)}. Строгое неравенство для 0 <<1 определяет строго квазивыпуклую функцию.

Примерами квазивыпуклых функций могут служить функции, изображенные на рис 1 а, б, в.

Рис 1а Рис 1б Рис 1в Кквазивыпуклым также относятся функции 0 x

Определение. Квазивогнутой функцией называют функцию f(x) такую, что для любых x1, xM и, 0 1 верно f(x1 +(1- )x2) min{f(x1), f(x2)} Как и для выпуклых функций, если f(x) — квазивыпуклая функция, то -f(x) — квазивогнутая.

Теорема. Функция f(x) квазивогнутая тогда и только тогда, когда множество M = {x | f(x) j} выпукло для любой скалярной величины (см. упражнение 2).

Снова обратимся к свойствам выпуклой функции.

5. Весьма важным в практическом отношении является свойство функции "максимума": пусть fi(x), i =1, 2,..., m — выпуклые функции, тогда функция f(x) = max {fi(x), i =1, 2,..., m, x M} i Конечно, такая функция, как правило, недифференцируема.

В задачах на min i max рассматривается задача min f(x) = min max {fi(x), i =1, 2,..., m, x M} x x i Упражнение 1. Пусть (x) = maxy f(x, y), x M, y G, M — выпуклое множество, G — компакт, f(x, y) — выпуклая по x на M при каждом фиксированном y. Показать выпуклость.

Упражнение 2. Доказать теорему о квазивогнутости функции.

Замечание. Операция max сохраняет свойство выпуклости. В то же время операция min, вообще говоря, его не сохраняет. Для того, чтобы операция сохраняла свойство выпуклости, необходимо накладывать ряд довольно жестких условий. Например, справедливо утверждение: Функция = min f(x, y), x M, y G, M — выпуклое множество, G — выпуклый компакт, f(x, y) — выпуклая по совокупности переменных. При соблюдении этих условий функция (x) является выпуклой. Как видим, здесь требуется выпуклость G и выпуклость f(x, y) уже по совокупности переменных.

Большой интерес для теоретических и практических исследований имеет вопрос о математических операциях над выпуклыми функциями, которые не нарушают ее выпуклости.

Легко видеть, что операция взятия абсолютной величины выпуклой функции в общем случае нарушает условие выпуклости. Рис 2 а, б.

|f(x)| f(x) Рис 2а Рис 2б Очевидно, что выпуклость f(x) не нарушается, если f(x) 0.

Аналогично операция возведения в квадрат может нарушить свойство выпуклости функции.

Функция f2(x) остается выпуклой функцией, если f(x) — выпуклая неотрицательная функция.

Возведение в куб также может привести к нарушению выпуклости функции. Например, y = x — выпуклая функция, а y = x3 не является выпуклой, однако будет квазивыпуклой.

6. Выпуклые функции можно складывать с неотрицательными коэффициентами. Это свойство означает, что подмножество выпуклых функций в пространстве непрерывных на множестве M функций есть выпуклый конус, то есть множество замкнутое относительно операции сложения и умножения на неотрицательное число. Вершины конуса принадлежат подпространству линейных функций.

В общем случае произведение выпуклых функций не является выпуклой функцией. Например, y = x, y = l-x на [0, 2], тогда y = xl-x на отрезке [0, 2] является вогнутой функцией.

Студенту предлагается в качестве упражнения доказать следующее свойство 7. Пусть fi(x), i = 1, 2,..., m — выпуклые неотрицательные монотонно возрастающие на R функции, тогда функция f(x) = fi(x) обладает теми же свойствами.

Анализ на выпуклость функций представляет сложную задачу. При этом будут очень полезны следующие утверждения.

8. Пусть h(x) — выпуклая функция, P (y) — выпуклая и неубывающая. Тогда f(x) =P (h(x)) — выпуклая функция.

Действительно, для любых x1, x2 имеем f(x1 +(1- )x2) =P (h(x1 +(1- )x2)) P (h(x1) +(1- )h(x2)) P (h(x1)) + (1 - )P (h(x2)) f(x1) +(1- )f(x2) Таким образом, композиция выпуклых функций является выпуклой функцией. Это утверждение позволяет исследовать функцию, представляя ее как композицию функций, свойство выпуклости которых уже установлено.

Упражнение 3. Пользуясь этим утверждением студенту предлагается доказать, что если h(x) — вогнутая, то (h(x))p, 1/h(x) — выпуклые функции для h(x) > 0, P 1, P 1.

9. Пусть h(x, t) — выпуклая по x для каждого фиксированного t, тогда, если функция P (t) — неотрицательная, интеграл L(x) = h(x, t)P (t)dt P Действительно, для любых x1, x2 M L(x1 +(1- )x2) = h(x1 +(1- )x2, t)P (t)dt [h(x1) +(1- )h(x2)] P (t)dt = h(x1, t)P (t)dt +(1- ) h(x2, t)P (t)dt = h(x1) +(1- )h(x2) Этот результат полезен при исследовании экстремальных задач с неопределенностью. Если P (t) является плотностью распределения, то L(x) есть математическое ожидание функции h(x, t). В свою очередь может быть поставлена задача минимизации L(x).





Критерии выпуклости Прежде чем приступить к решению задачи на экстремум, необходимо провести тщательный анализ целевой функции и ограничений, определяющих множество допустимых планов. Желательным свойство рассматриваемых функций является их выпуклость. Обычно провести анализ, пользуясь лишь определением выпуклой функции, затруднительно. Для этой цели необходимо привлекать более тонкие свойства выпуклых функций.

Здесь следует отметить, что выпуклость функции по каждой переменной еще не позволяет сделать вывод о выпуклости по совокупности переменных. Для подтверждения сказанного можно привести следующий пример.

Пусть x R, (x, y) =x·y. Функция (x, y) является выпуклой по x при каждом фиксированном y ивыпуклойпоy при каждом фиксированном x. Положим, x = x1+(1-)x2, y = y1+(1-)y2, где 0 1. Для выпуклости (x, y) по совокупности переменных необходимо, чтобы для любых x1, x2, y1, y2 выполнялось неравенство (x, y) (x1, y1) +(1- )(x2, y2). Имеем F () (x, y) - (x1, y1) - (1 - )(x2, y2) =(x1 +(1- )x2)+ +(y1 +(1- )y2) - x1x2 - (1 - )x2y2 = (1 - )(y1 - y2)(x2 - x1) Очевидно, что при [0, 1], x1 = x2, y1 = y2, если sign(y1 - y2) = sign(x2 - x1), то F () > 0, а тогда условие выпуклости не выполняется, то есть не является выпуклой функцией по совокупности переменных.

Кнаибольшее широкоизвестным критериям выпуклости относится следующий.

Теорема. Пусть M — непустое открытое выпуклое множество в Rn, f(x) — недифференцируемая на M функция. Для того, чтобы функция f(x) была выпуклой, необходимо и достаточно, чтобы при любых x, x0 M выполнялось неравенство f(x) - f(x0) (f(x0), x - x0) Доказательство этой теоремы приводится в лекции. Очевиден геометрический смысл этой теоремы:

дифференцируемая функция является выпуклой тогда и только тогда, когда график ее целиком лежит выше касательной гиперплоскости, проведенной в любой точке поверхности. Можно сказать еще так: дифференцируемая функция является выпуклой тогда и только тогда, когда касательная гиперплоскость, проведенная в любой точке к поверхности y = f(x), является опорной гиперплоскостью к надграфику f(x).

Иногда рассматривается другая форма необходимого и достаточного условий выпуклости дифференцируемой функции.

Теорема. Пусть M — непустое открытое выпуклое множество в Rn, f(x) — дифференцируемая на M функция. Для того, чтобы функция f(x) была выпуклой, необходимо и достаточно, чтобы при любых x1, x2 M выполнялось неравенство [f(x2) -f(x1)]T (x2 - x1) Для строгой выпуклости f(x) необходимо и достаточно, чтобы неравенство было строгим.

Доказательство. Пусть f(x) выпукла и x1, x2 M, тогда по предыдущей лемме f(x1) f(x2) +f(x2)(x1 - x2) f(x2) f(x1) +f(x1)(x2 - x1) Складывая эти неравенства, получаем [f(x2) -f(x1)]T (x2 - x1) 0. Обратное для x1, x2 M.

По теореме о среднем значении () f(x2) - f(x1) =f(x)(x2 - x1), x = x1 +(1- )x2, [0, 1] Из предположения теоремы [f(x)-f(x1)]T (x-x1), то есть (1 - )[f(x)-f(x1)]T (x2 -x1) 0.

Отсюда fT (x)(x2 - x1) fT (x1)(x2 - x1). Тогда из () имеем, что f(x2) f(x1) +fT (x1)(x2 - x1) Тогда f(x) по предыдущей теореме выпукла.

Эти теоремы дают необходимы и достаточные условия выпуклости дифференцируемой функции. Однако с вычислительной точки зрения проверка этих условий сложна. Просто и легко проверяемое, по крайней мере для квадратичных функций, условие может быть получено дважды дифференцируемой функцией.

Теорема. Пусть M — непустое открытое выпуклое множество в Rn, f(x) — дважды дифференцируемая на M функция. Для того, чтобы функция f(x) была выпуклой, необходимо и достаточно, чтобы матрица Гессе была неотрицательно-определенной в каждой точке M.

Для вогнутости f(x) на M требуется неположительная определенность матрицы вторых производных. Эта теорема широко используется при проверке на выпуклость или вогнутость дважды дифференцируемых функций. В частности, если f(x) — квадратичная функция, то матрица Гессе не зависит от точки, в которой она вычисляется. Следовательно, проверка на выпуклость сводится к проверке неотрицательной определенности матрицы или, что то же самое, на неотрицательность ее собственных значений.

Пример. Пусть f(x1, x2) =2x1 +6x2 - 2x2 - 3x2 +4x1x2. Матрица Гессе равна 1 -4 H = 4 -Находим ее собственное значение, решая уравнение -4 - det(H - I) = = 2 +10 +8= 4 -6 - 1 = -5+ 17 < 0, 2 = -5 - 17 f(x) — вогнутая функция.

При использовании теоремы студенту необходимо вспомнить известные из алгебры критерии знакоопределенности и полуопределенности матриц. Пусть имеется знакосимметричная матрица a11 a12... a1n a21 a22... a2n A =.........

an1 an2... ann Критерий положительной определенности матрицы (критерий Сильвестра).

Для того, чтобы матрица была положительно определенной (то есть для любых x =0 выполня лось соотношение (Ax, x) > 0) необходимо и достаточно, чтобы все угловые миноры этой матрицы были строго положительны:

a11 a 1 = a11 > 0, 2 = > 0,..., n = det A> a21 aПоскольку любой главный минор (то есть минор, построенный на элементах, стоящих на пересечении строк и столбцов с одинаковыми номерами) матрицы A может при соответствующей перенумерации переменных помещен в левый верхний угол, то имеет место следствие.

Следствие. У положительно определенной матрицы не только угловые, но и все главные миноры строго положительны.

Pages:     || 2 |










© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.