Учебнометодическое пособие по курсу "Методы Оптимизации" Владивосток 1996 2 удк519. 48
 Скачать 102.37 Kb.
|
|
Государственный комитет Российской Федерации по высшему образованию Дальневосточный государственный университет Выпуклые функции и их свойства Учебно-методическое пособие по курсу "Методы Оптимизации" Владивосток 1996 2 УДК519.48 В методических указания приводятся необходимые сведения по теме "Выпуклые функции и их свойства", упражнения по исследованию функций на выпуклость и экстремум. Указания предна- значены для студентов-математиков 3 и 4 курсов, слушающих курс "Методы оптимизации". Методические указания подготовлены кафедрой процессов управления. Печатается по решению учебно-методического совета ДВГУ. Составитель Л.В.Горячев. c Дальневосточный государственный университет 1986 3 Свойство выпуклости функции является фундаментальным в математике наряду с такими свой- ствами как монотонность, непрерывность, дифференцируемость и т.д. Особенно широко оно исполь- зуется в теории экстремальных задач. Поэтому студент, прослушавший курс "Методы оптимиза- ции", должен твердо усвоить его и уметь применить при решении практических задач оптимизации. В учебниках и учебных пособиях по курсу "методы оптимизации"изучению темы "Выпуклые функции"отводится мало времени. По существу излагаются лишь определения и критерии выпук- лости; алгебру выпуклых функций студент, по мнению авторов учебников, должен освоить само- стоятельно в процессе решения примеров. Однако по новой учебной программе практические занятия по методам оптимизации исключены из числа обязательных. Это обуславливает необходимость подготовки руководства, призванного бо- лее подробно познакомить студента со свойствами выпуклых функций и способствовать выработке у него практических навыков по анализу на выпуклость функций в практических задачах оптими- зации. Этим целям и служат настоящие методические указания. Определение и практические свойства выпуклых функций Определение. Функция f(x), заданная на выпуклом множестве M ⊂ R n , называется выпуклой, если для любых x 1 , x 2 и числа α, 0 ≤ α ≤ 1 выполняется неравенство f (αx 1 + (1 − α)x 2 ) ≤ αf(x 1 ) + (1 − α)f(x 2 ) Если равенство достигается только при α = 0 и α = 1, то называется строго выпуклой. Примерами строго выпуклой функции может служить функция: 1. y = l x 2. y = x 2 3. y = sin x, x ∈ [π, 2π] 4. y = cos x, x ∈ [π/2, 3π/2] По определению f(x) является выпуклой, если значение ее от выпуклой комбинации значений аргу- мента x 1 и x 2 не больше, чем выпуклая комбинация значений f(x) при этих значениях аргумента. Геометрически это означает, что хорда, соединяющая эти две точки (любые) графика функции, лежит над дугой, концами которой являются эти точки. Противоположным по смыслу выпуклости функции является понятие вогнутой функции. Определение. Функция f(x), заданная на выпуклом множестве, называется вогнутой (строго вогнутой), если g(x) = −f(x) является выпуклой (строго выпуклой) функцией. При решении практической задачи оптимизации необходимо предварительно исследовать саму целевую функцию и функции, определяющие ограничения на выпуклость. От результатов этого исследования зависит выбор метода численного решения. Часто для этих целей достаточно опре- деления. Рассмотрим ряд простых примеров. 1. Функция y = x является выпуклой. Действительно, для любых x 1 , x 2 ⊂ M имеем y(λx 1 + (1 − λ)x 2 ) = λx 1 + (1 − λ)x 2 ≤ ≤ λx 1 + (1 − λ)x 2 = λy(x 1 ) + (1 − λ)y(x 2 ) 2. Квадратная форма y = x T Bx + bx + c является выпуклой функцией, где B — неотрицательно- определенная матрица. Действительно, для любых x 1 , x 2 имеем y(λx 1 + (1 − λ)x 2 ) = (λx 1 + (1 − λ)x 2 ) T B((λx 1 + (1 − λ)x 2 )+ +b(λx 1 + (1 − λ)x 2 ) + c = (x 2 + λ(x 1 − x 2 )) T B(x 2 + λ(x 1 − x 2 ))+ +b(λx 1 + (1 − λ)x 2 ) + c = x T 2 Bx 2 + λ 2 (x 1 − x 2 ) T B(x 1 − x 2 )+ +λx T 2 B(x 1 − x 2 ) + λ(x 1 − x 2 ) T Bx 2 + λbx 1 + (1 − λ)bx 2 + c ≤ ≤ x T 2 Bx 2 + λ(x 1 − x 2 ) T B(x 1 − x 2 ) + λx T 2 B(x 1 − x 2 ) + λ(x 1 − x 2 ) T Bx 2 + 4 +λbx 1 + (1 − λbx 2 + λc + (1 − λ)c = x T 2 Bx 2 + λx T 1 B(x 1 − x 2 ) − −λx T 2 B(x 1 − x 2 ) + λx T 2 B(x 1 − x 2 ) + λ(x 1 − x 2 ) T Bx 2 + λbx 1 + (1 − λ)bx 2 + +λc + (1 − λ)c = x T 2 Bx 2 − λx T 2 Bx 2 + λx T 1 Bx 1 − λx T 1 Bx 2 + λx T 1 Bx 2 + +λbx 1 + (1 − λ)bx 2 + λc + (1 − λ)c = λ(x T 1 Bx 1 + bx 1 + c)+ (1 − λ)(x T 2 Bx 2 + bx 2 + c) = λy(x 1 ) + (1 − λ)y(x 2 ) 3. Пользуясь определением, можно установить выпуклость квадратного скалярного произведе- ния y = (a, x) 2 . Действительно, y(λx 1 + (1 − λ)x 2 ) = (a, λx 1 + (1 − λ)x 2 ) 2 = (a, x 2 + λ(x 1 − x 2 )) 2 = = [(a, x 2 ) + λ(a, x 1 − x 2 )] 2 = (a, x 2 ) 2 + 2λ(a, x 2 )(a, x 1 − x 2 )+ +λ 2 (a, x 1 − x 2 ) 2 ≤ (a, x 2 ) 2 + 2λ(a, x 2 )(a, x 1 − x 2 ) + λ(a, x 1 − x 2 ) 2 = = (a, x 2 ) 2 + λ [2(a, x 2 ) − (a, x 1 − x 2 )] (a, x 1 − x 2 ) = (a, x 2 ) 2 + λ[(a, x 1 ) 2 − −(a, x 2 ) 2 ] = λ(a, x 1 ) 2 + (1 − λ)(a, x 2 ) 2 = λy(x 1 ) + (1 − λ)y(x 2 ) Однако часто одного определения выпуклой функции оказывается недостаточно для анализа функ- ции и требуется применение более глубоких свойств, определяющих выпуклость. Перечислим простые свойства выпуклых функций, наиболее часто используемые в теоретиче- ских и практических задачах. Знание этих свойств является обязательным для студента, прослу- шавшего курс "Методы оптимизации". 1. Выпуклые функции непрерывны во всех внутренних точках области определения. 2. Каждой выпуклой функции можно поставить в соответствие множество, называемое эпигра- фом. Часто для выпуклой функции оно называется надграфиком, для вогнутой - подгра- фиком, и обозначается epi f(x). Если f(x) выпуклая, то epi f(x) = {(x, z) | x ∈ M, z ≥ f(x)}. В практических случаях анализ на выпуклость некоторой функции можно заменить иссле- дованием ее эпиграфа. Эпиграф часто используется при доказательстве различных свойств выпуклых функций. 3. Неравенство Иенсена: пусть f(x) — выпуклая функция x ∈ M ⊂ R n , тогда f i α i x i ≤ i α i f (x i ), m i=1 α i = 1, α i ≥ 0, x i ∈ M Действительно, в этом случае epi f(x) будет выпуклым множеством и (x i , f (x i )) ∈ epi f, x i ∈ M , а значит α i (x i , f (x i )) = ( α i x i , α i f (x i )) ∈ epi f, откуда следует требуемое неравен- ство. Часто условие выполнения неравенства Иенсена используется в качестве определения выпук- лой функции. 4. Важнейшим свойством выпуклой функции, широко используемым в практике решения экс- тремальных задач, является следующее: Если f(x) — выпуклая функция, то множество G = {x | f(x) ≤ γ, γ = const} является выпуклым. Доказательство его легко приводится по основе определения. Для вогнутой функции g(x) множество G = {x | g(x) ≥ γ, γ = const} также является выпуклым. 5 Таким образом, если целевая функция является выпуклой (вогнутой) и ограничения удовлетво- ряют указанным условиям, то мы относим задачу к задачам выпуклого (вогнутого) программиро- вания и выбираем метод ее решения. Исходя из этого, следует отметить, что указанным свойством обладают не только выпуклые функции, но и так называемые квазивыпуклые функции. Определение. Функция f(x) называется квазивыпуклой, если для данных x 1 , x 2 ∈ R n и любого α , 0 ≤ α ≤ 1 f (αx 1 + (1 − α)x 2 ) ≤ min{f(x 1 ), f (x, 2) } . Строгое неравенство для 0 < α < 1 определяет строго квазивыпуклую функцию. Примерами квазивыпуклых функций могут служить функции, изображенные на рис 1 а, б, в. Рис 1а Рис 1б Рис 1в Кквазивыпуклым также относятся функции f (x) = 0 x < 0 −x n x ≥ 0, n ≥ 2 натуральное Эта функция является вогнутой и квазивыпуклой. Квазивыпуклая функция может иметь разрыв первого рода. Определение. Квазивогнутой функцией называют функцию f(x) такую, что для любых x 1 , x 2 ∈ M и Θ, 0 ≤ Θ ≤ 1 верно f (Θx 1 + (1 − Θ)x 2 ) ≥ min{f(x 1 ), f (x 2 ) } Как и для выпуклых функций, если f(x) — квазивыпуклая функция, то −f(x) — квазивогнутая. Теорема. Функция f(x) квазивогнутая тогда и только тогда, когда множество M = {x | f(x) ≥ j} выпукло для любой скалярной величины (см. упражнение 2). Снова обратимся к свойствам выпуклой функции. 5. Весьма важным в практическом отношении является свойство функции "максимума": пусть f i (x), i = 1, 2, . . . , m — выпуклые функции, тогда функция f (x) = max i {f i (x), i = 1, 2, . . . , m, x ∈ M} Конечно, такая функция, как правило, недифференцируема. В задачах на min i max рассматривается задача min x f (x) = min x max i {f i (x), i = 1, 2, . . . , m, x ∈ M} Упражнение 1. Пусть ϕ(x) = max y 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) уже по совокупности переменных. 6 Большой интерес для теоретических и практических исследований имеет вопрос о математиче- ских операциях над выпуклыми функциями, которые не нарушают ее выпуклости. Легко видеть, что операция взятия абсолютной величины выпуклой функции в общем случае нарушает условие выпуклости. Рис 2 а, б. f(x) | | f(x) Рис 2а Рис 2б Очевидно, что выпуклость f(x) не нарушается, если f(x) ≥ 0. Аналогично операция возведения в квадрат может нарушить свойство выпуклости функции. Функция f 2 (x) остается выпуклой функцией, если f(x) — выпуклая неотрицательная функция. Возведение в куб также может привести к нарушению выпуклости функции. Например, y = x — выпуклая функция, а y = x 3 не является выпуклой, однако будет квазивыпуклой. 6. Выпуклые функции можно складывать с неотрицательными коэффициентами. Это свойство означает, что подмножество выпуклых функций в пространстве непрерывных на множестве M функций есть выпуклый конус, то есть множество замкнутое относительно операции сложе- ния и умножения на неотрицательное число. Вершины конуса принадлежат подпространству линейных функций. В общем случае произведение выпуклых функций не является выпуклой функцией. Например, y = x, y = l −x на [0, 2], тогда y = xl −x на отрезке [0, 2] является вогнутой функцией. Студенту предлагается в качестве упражнения доказать следующее свойство 7. Пусть f i (x), i = 1, 2, . . . , m — выпуклые неотрицательные монотонно возрастающие на R 1 функции, тогда функция f(x) = f i (x) обладает теми же свойствами. Анализ на выпуклость функций представляет сложную задачу. При этом будут очень полезны следующие утверждения. 8. Пусть h(x) — выпуклая функция, P (y) — выпуклая и неубывающая. Тогда f(x) = P (h(x)) — выпуклая функция. Действительно, для любых x 1 , x 2 имеем f (λx 1 + (1 − λ)x 2 ) = P (h(λx 1 + (1 − λ)x 2 )) ≤ P (λh(x 1 ) + (1 − λ)h(x 2 )) ≤ ≤ λP (h(x 1 )) + (1 − λ)P (h(x 2 )) ≤ λf(x 1 ) + (1 − λ)f(x 2 ) Таким образом, композиция выпуклых функций является выпуклой функцией. Это утверждение позволяет исследовать функцию, представляя ее как композицию функций, свойство выпуклости которых уже установлено. Упражнение 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) = P h(x, t)P (t)dt Действительно, для любых x 1 , x 2 ∈ M L(αx 1 + (1 − α)x 2 ) = h(αx 1 + (1 − α)x 2 , t)P (t)dt ≤ [αh(x 1 ) + (1 − α)h(x 2 )] 7 P (t)dt = α h(x 1 , t)P (t)dt + (1 − α) h(x 2 , t)P (t)dt = αh(x 1 ) + (1 − α)h(x 2 ) Этот результат полезен при исследовании экстремальных задач с неопределенностью. Если P (t) является плотностью распределения, то L(x) есть математическое ожидание функции h(x, t). В свою очередь может быть поставлена задача минимизации L(x). Критерии выпуклости Прежде чем приступить к решению задачи на экстремум, необходимо провести тщательный ана- лиз целевой функции и ограничений, определяющих множество допустимых планов. Желательным свойство рассматриваемых функций является их выпуклость. Обычно провести анализ, пользуясь лишь определением выпуклой функции, затруднительно. Для этой цели необходимо привлекать более тонкие свойства выпуклых функций. Здесь следует отметить, что выпуклость функции по каждой переменной еще не позволяет сде- лать вывод о выпуклости по совокупности переменных. Для подтверждения сказанного можно привести следующий пример. Пусть x ∈ R, ϕ(x, y) = x·y. Функция ϕ(x, y) является выпуклой по x при каждом фиксированном y и выпуклой по y при каждом фиксированном x. Положим, x α = αx 1 +(1 −α)x 2 , y α = αy 1 +(1 −α)y 2 , где 0 ≤ α ≤ 1. Для выпуклости ϕ(x, y) по совокупности переменных необходимо, чтобы для любых x 1 , x 2 , y 1 , y 2 выполнялось неравенство ϕ(x α , y α ) ≤ αϕ(x 1 , y 1 ) + (1 − α)ϕ(x 2 , y 2 ) . Имеем F (α) ≡ ϕ(x α , y α ) − αϕ(x 1 , y 1 ) − (1 − α)ϕ(x 2 , y 2 ) = (αx 1 + (1 − α)x 2 )+ +(αy 1 + (1 − α)y 2 ) − αx 1 x 2 − (1 − α)x 2 y 2 = α(1 − α)(y 1 − y 2 )(x 2 − x 1 ) Очевидно, что при α ∈ [0, 1], x 1 = x 2 , y 1 = y 2 , если sign(y 1 − y 2 ) = sign(x 2 − x 1 ) , то F (α) > 0, а тогда условие выпуклости не выполняется, то есть не является выпуклой функцией по совокупности переменных. Кнаибольшее широкоизвестным критериям выпуклости относится следующий. Теорема. Пусть M — непустое открытое выпуклое множество в R n , f(x) — недифференцируемая на M функция. Для того, чтобы функция f(x) была выпуклой, необходимо и достаточно, чтобы при любых x, x 0 ∈ M выполнялось неравенство f (x) − f(x 0 ) ≥ (∇f(x 0 ), x − x 0 ) Доказательство этой теоремы приводится в лекции. Очевиден геометрический смысл этой теоремы: дифференцируемая функция является выпуклой тогда и только тогда, когда график ее целиком лежит выше касательной гиперплоскости, проведенной в любой точке поверхности. Можно сказать еще так: дифференцируемая функция является выпуклой тогда и только тогда, когда касательная гиперплоскость, проведенная в любой точке к поверхности y = f(x), является опорной гиперплос- костью к надграфику f(x). Иногда рассматривается другая форма необходимого и достаточного условий выпуклости диф- ференцируемой функции. Теорема. Пусть M — непустое открытое выпуклое множество в R n , f(x) — дифференцируемая на M функция. Для того, чтобы функция f(x) была выпуклой, необходимо и достаточно, чтобы при любых x 1 , x 2 ∈ M выполнялось неравенство [ ∇f(x 2 ) − ∇f(x 1 )] T (x 2 − x 1 ) ≥ 0 Для строгой выпуклости f(x) необходимо и достаточно, чтобы неравенство было строгим. Доказательство. Пусть f(x) выпукла и x 1 , x 2 ∈ M, тогда по предыдущей лемме f (x 1 ) ≥ f(x 2 ) + ∇f(x 2 )(x 1 − x 2 ) f (x 2 ) ≥ f(x 1 ) + ∇f(x 1 )(x 2 − x 1 ) Складывая эти неравенства, получаем [∇f(x 2 ) − ∇f(x 1 )] T (x 2 − x 1 ) ≥ 0. Обратное для x 1 , x 2 ∈ M. По теореме о среднем значении ( ∗) f (x 2 ) − f(x 1 ) = ∇f(x)(x 2 − x 1 ), x = λx 1 + (1 − λ)x 2 , λ ∈ [0, 1] 8 Из предположения теоремы [∇f(x)−∇f(x 1 )] T (x −x 1 ) , то есть (1 − λ)[∇f(x)−∇f(x 1 )] T (x 2 −x 1 ) ≥ 0. Отсюда ∇f T (x)(x 2 − x 1 ) ≥ ∇f T (x 1 )(x 2 − x 1 ) . Тогда из (∗) имеем, что f (x 2 ) ≥ f(x 1 ) + ∇f T (x 1 )(x 2 − x 1 ) Тогда f(x) по предыдущей теореме выпукла. Эти теоремы дают необходимы и достаточные условия выпуклости дифференцируемой функ- ции. Однако с вычислительной точки зрения проверка этих условий сложна. Просто и легко про- веряемое, по крайней мере для квадратичных функций, условие может быть получено дважды дифференцируемой функцией. Теорема. Пусть M — непустое открытое выпуклое множество в R n , f(x) — дважды дифферен- цируемая на M функция. Для того, чтобы функция f(x) была выпуклой, необходимо и достаточно, чтобы матрица Гессе была неотрицательно-определенной в каждой точке M. Для вогнутости f(x) на M требуется неположительная определенность матрицы вторых про- изводных. Эта теорема широко используется при проверке на выпуклость или вогнутость дважды дифференцируемых функций. В частности, если f(x) — квадратичная функция, то матрица Гессе не зависит от точки, в которой она вычисляется. Следовательно, проверка на выпуклость сводится к проверке неотрицательной определенности матрицы или, что то же самое, на неотрицательность ее собственных значений. Пример. Пусть f(x 1 , x 2 ) = 2x 1 + 6x 2 − 2x 2 1 − 3x 2 2 + 4x 1 x 2 . Матрица Гессе равна H = −4 4 4 −6 Находим ее собственное значение, решая уравнение det(H − λI) = −4 − λ 4 4 −6 − λ = λ 2 + 10λ + 8 = 0 λ 1 = −5 + √ 17 < 0, λ 2 = −5 − √ 17 ≤ 0 f (x) — вогнутая функция. При использовании теоремы студенту необходимо вспомнить известные из алгебры критерии знакоопределенности и полуопределенности матриц. Пусть имеется знакосимметричная матрица A = a 11 a 12 . . . a 1n a 21 a 22 . . . a 2n . . . . . . . . . a n1 a n2 . . . a nn Критерий положительной определенности матрицы (критерий Сильвестра). Для того, чтобы матрица была положительно определенной (то есть для любых x = 0 выполня- лось соотношение (Ax, x) > 0) необходимо и достаточно, чтобы все угловые миноры этой матрицы были строго положительны: 1 = a 11 > 0, 2 = a 11 a 12 a 21 a 22 > 0, ..., n = det A > 0 Поскольку любой главный минор (то есть минор, построенный на элементах, стоящих на пересече- нии строк и столбцов с одинаковыми номерами) матрицы A может при соответствующей перену- мерации переменных помещен в левый верхний угол, то имеет место следствие. Следствие. У положительно определенной матрицы не только угловые, но и все главные миноры строго положительны. Критерий неотрицательной определенной матрицы: Для того, чтобы матрица A была неотрицательно-определена (то есть для любых x ∈ R n выполнялось соотношение (Ax, x) ≥ 0) необходимо и достаточно, чтобы все ее главные миноры были неотрицательны. 9 Замечание. Неотрицательность одних угловых миноров недостаточна для неотрицательности определенности матрицы. Так, например, знакомеременная форма f = −x 2 2 + 2x 1 x 3 имеет матрицу вторых производных A = 0 0 2 0 −2 0 2 0 0 у которой все угловые миноры неотрицательны. Критерий отрицательной определенности матрицы. Для того, чтобы матрица была отрицательно-определенной, необходимо и достаточно, чтобы угловые миноры матрицы чередо- вались по знаку, причем ∆ 1 < 0 Пример. Выясним, при каких значениях параметра функция является выпуклой f(x) = α 1 x 2 1 x 2 2 + (x 2 1 +x 2 2 ) 2 . Очевидно, что для этого надо составить матрицу вторых производных этой функции и из условий ее неотрицательной определенности получить ограничения на параметр. Действительно, f x 1 x 1 = 6x 2 1 + (2 + α)x 2 2 , f x 2 x 2 = 6x 2 2 + (2 + α)x 2 1 , f x 1 x 2 = f x 2 x 1 = 2(2 + α)x 1 x 2 Наша функция будет выпуклой, если 6x 2 1 + (2 + α)x 2 2 ≥ 0 6x 2 2 + (2 + α)x 2 1 ≥ 0 [6x 2 1 + (2 + α)x 2 2 ][6x 2 2 + (2 + α)x 2 1 ] ≥ 0 Очевидно из первых двух неравенств, что α ≥ −2 Следующее неравенство дает, положив 2 + α = t 6tx 4 1 + 6tx 2 2 − 3t 2 x 2 1 x 2 2 + 36x 2 1 x 2 2 ≥ 0, ∀x 1 , x 2 Это неравенство выполнимо для любых x 1 , x 2 при (t 2 − 12)/2t ≤ 2. Отсюда сразу получаем, что 0 < t ≤ 6. Но случай t = 0, как это легко увидеть, удовлетворяет нас. Следовательно, −2 ≤ α ≤ 4. Упражнение 1. Найти плоскость параметров (α, β) области, где функция f(x 1 , x 2 ) = x α 1 x β 2 , (x 1 ≥ 0, x 2 ≥ 0) является выпуклой (строго выпуклой) и вогнутой (строго вогнутой). Упражнение 2. Найти на плоскости (x 1 , x 2 ) области, в которых является выпуклой и область, в которой является вогнутой функция. Максимумы и минимумы выпуклых функций В этом разделе приводятся свойства выпуклых (вогнутых) функций, имеющих фундаментальное значение для практической оптимизации. 1. Для того, чтобы выпуклая функция f(x) имела в точке x ∗ безусловный минимум, необходимо и достаточно, чтобы ∇f(x ∗ ) = 0 . Это свойство говорит о том, что для выпуклой функции нет необходимости исследовать точку, как это делается в случае произвольной дифференцируемой функции. 2. Для того, чтобы выпуклая функция f(x) имела в точке x ∗ безусловный минимум, необходимо и достаточно, чтобы производные по любому направлению были неотрицательными, то есть ∂f ∂S (x ∗ i ) ≥ 0, ∀S. Этот признак оптимальности может быть сформулирован в более конструк- тивной форме. 3. Для того, чтобы выпуклая функция f(x) имела в точке x ∗ безусловный минимум, необходимо и достаточно, чтобы 0 ∈ ∂f(x ∗ ) , где ∂f(x ∗ ) — субдифференциал f(x) в точке x ∗ 4. Если функция f(x) выпукла на выпуклом множестве, то она не имеет локальных минимумов, а каждый ее минимум является глобальным. Причем множество экстремальных точек выпукло. Это свойство особо следует иметь в виду при решении практических задач, так как это поз- воляет нам определить одноэкстремальная или многоэкстремальная задача. Последнее имеет место в случае произвольной функции. Однако, экстремальных и в случае выпуклой функции может быть множество. 10 5. Если f(x) — строго выпуклая функция, определенная на выпуклом множестве M, то множе- ство точек, на котором f(x) достигает минимума, состоит из единственной точки. Это свойство делает понятным, почему необходим анализ функции на строгую выпуклость. 6. Выпуклая функция f(x), определенная на R n , либо является константой, либо неограничена сверху. Это свойство констатирует очевидный факт, что выпуклая функция не ограничена сверху. 7. Выпуклая функция f(x) непрерывная и ограниченная сверху на многограннике, достигает своего глобального максимума в одной из крайних точек. Известно, что задача максимилизации выпуклой функции на ограниченном множестве в об- щем случае многоэкстремальна, для отыскания ее глобального максимума достаточно срав- нить значения функции в крайних точках. Обобщение этого свойства на случай произвольного ограниченного множества дается в следующем утверждении. 8. Если f(x) — непрерывная функция на ограниченном выпуклом множестве M, то она достигает своего глобального максимума в крайней точке. Это утверждение опирается в свою очередь на свойство выпуклого компакта иметь, по крайней мере, одну крайнюю точку. Эту теорему можно распространить и на неограниченное выпуклое множество, не имеющее внутреннего подпространства. 9. Выпуклая функция f(x), определенная на выпуклом множестве G, достигает минимума в точке x ∗ ∈ G тогда и только тогда, когда ( ∇f(x ∗ ), x − x ∗ ) ≥ 0, ∀x ∈ G Это свойство дает критерии оптимальности функции в точке x ∗ . Если f(x) — произвольная функция, то x ∗ — точка лишь локального минимума. Если f(x) — вогнутая функция, то имеем противоположное неравенство. Упражнение 1. Найти максимумы и минимумы функций. 1. f(x) = 2x 3 − 5x 2 + 14x + 6 2x 2 2. f(x, y) = x 4 + y 4 − 2x 2 + 4xy − 2y 2 3. f(x, y, z) = x 2 + y 2 + z 2 − xy + x − 2z 4. f(x, y) = (1 + l y ) cos x + l y |