Множество AÌE называется выпуклым, если оно вместе с любыми двумя точками x1 и x2 содержит отрезок, соединяющий их, т.е. множества вида
[x1x2]={xÎEn| x=lx1+(1-l)x2, 0 £l £1}.
Рассмотренные выше полупространства являются выпуклыми множествами. Проверим, например, выпукло ли полупространство Н+ab{xÎEn| <a,x>³b}. Для этого рассмотрим две произвольные точки x1 и x2 этого полупространства. Для этих точек выполнены неравенства
<a,x1>³ b, <a,x2>³ b.
Сложим эти два неравенства, предварительно умножив первое на произвольное число lÎ[0,1], а второе на 1-l. В результате получим неравенство
l<a,x1> + (1-l) <a,x2> = <a,lx1 + (1-l)x2>³ b.
Поскольку l произвольно, весь отрезок, соединяющий выбранные точки, принадлежит данному полупространству. Следовательно, полупространство действительно является выпуклым множеством.
Рис.2.10.выпуклое(а), невыпуклое(б) множества.
Глава 3.Основные сведения о функциях.
3.1 Понятие функций.
Пусть X и Y два множества. Если указано правило, согласно которому каждому элементу множества X поставлен в соответствие определенный элемент множества Y, то говорят, что задана функция f, отображающая X в Y. Этот факт записывают в виде f: X®Y или y=f(x), где x ÎX, yÎY. Множество X называется областью данных или областью определения функции, а множество Y- множество значений. Функция f(x) представляет собой правило, которое позволяет каждому значению x поставить в соответствие единственное значение y=f(x). В этом случае x- независимая переменная, y- зависимая переменная. Функции y=f(x)=f(x1+x2,..,xn), т.е. функции с областью задания X Ì En и множеством значений Y Ì E называют числовыми функциями в отличие от векторных функций, для которых YÌ Em, m>1.
Множество вида
{(x,y)ÎEn+1 ½ y=f(x) при некоторых xÎX}
называют графиком функции y=f(x).
Ряд физических процессов можно описать с помощью непрерывных функций, т.е. функций, которые обладают свойством непрерывности в каждой точке x, принадлежащей областям их определения.
Функцию f называют непрерывной в точке x0ÎX, если для любого числа e>0 можно указать такое число de>0, что для всех xÎX Ç Ède ½x0½ выполняется неравенство ½f(x)-f(x0)½<e. Согласно данному определению функция f в изолированной точке всегда непрерывна. Напомним, что точка xÎX называется изолированной точкой множества X, если существует ее окрестность, которая не содержит никаких других точек из X, кроме самой точки x. Функцию, непрерывную в каждой точке множества X, называют непрерывной на множестве X (или просто непрерывной, если X=En).
В качестве примеров функций, непрерывных на En, приведем линейную функцию f1(x)=<c,x>+b=c1x1+c2x2+..+cnxn+b и квадратичную функцию f2(x)=1/2<Qx,x>+<c,x>+b,
где Q- числовая симметрическая матрица размера n*m, с- некоторый вектор из En и b- некоторое число, а Qx означает произведение матрицы на вектор по правилам перемножения матриц, принятых в линейной алгебре.
3.2 Классификация функций.
3.2.1 Разрывные и дискретные функции.
В инженерных приложениях нередки случаи, когда приходится использовать
разрывные функции. Например, затраты на сообщение некоторой системе количества
тепла при различных температурах системы получаем кусочно- непрерывную кривую (рис 3.1). возможны случаи, когда переменная принимает дискретные значения(рис 3.2).
В зависимости от того, является ли исследуемая функция непрерывной или разрывной следует использовать различные методы исследования. Необходимо отметить, что метод эффективный при анализе непрерывных функций, может оказаться неэффективным при исследовании разрывных функций, хотя обратное не исключается.
Функции можно также классифицировать в соответствии с их формой, определяющей топологические свойства функций в рассматриваемом интервале.
3.2.2 Монотонные функции.
Функция f(x) является монотонной (рис 3.3) как при возрастании , так и убывании), если для двух произвольных точек x1 и x2, таких, что x1<x2 выполняется одно из следующих неравенств: f(x1)£ f(x2) (монотонно возрастающая функция) f(x1)³ (x2) (монотонно убывающая функция)
Рис.3.3. К понятию монотонной функции.
На рис 3.4 изображен график функции, которая монотонно убывает при x£0 и монотонно возрастает при x³0. Функция достигает своего минимума в точке x=x* (начале координат0) и монотонна по обе стороны от точки минимума. Такие функции называются унимодальными. Заметим что унимодальная функция вовсе не должна быть гладкой (рис. 3.4, а) и даже непрерывной (рис.3.4,б), она может быть изломанной (недифференцируемой), разрывной (рис 3.4, в), дискретной (рис. 3.4 г) и даже может в некоторых интервалах не быть определенной (рис. 3.4, д.).
Итак функция f(x) называется унимодальной на отрезке [a;b], если она непрерывна на [a;b] и существуют числа a и b a£a£b£b, такие, что :
1) если a<a, то на отрезке [a;a] f(x) монотонно убывает;
2) если b<b то на отрезке[b;b] f(x) монотонно возрастает;
возможно вырождение в точку одного или двух из отрезков [a;a], [a;b], [b;b] (рис 3.5).
Рис.3.5. Варианты расположения и вырождения в точку отрезков монотонности и постоянства унимодальной функции.
множество функций, унимодальных на отрезке [a;b] будем обозначать Q[a;b]. Унимодальность функций является исключительно важным свойством, которое широко используется в оптимизационных исследованиях.
3.2.3 Выпуклые, псевдовыпуклые и квазивыпуклые функции.
Выпуклые функции и их обобщения (псевдовыпуклые и квазивыпуклые функции) играют важную роль в теории оптимизации. С помощью этих функций будут сформулированы достаточные условия оптимальности.
Числовую функцию f, определенную на выпуклом множестве X, XÌEn, называют выпуклой, если для любых двух точек x1,x2ÎX и произвольного числа lÎ[0,1] выполняется неравенство
f(lx1+(1-l)x2) £ lf(x1)+(1-l)f(x2). (3.1)
Неравенство противоположного смысла определяет вогнутую функцию, причем часто используются термины «выпуклая вниз (1)» «выпуклая вверх (2)» (рис3.6).
Геометрически выпуклость функции f означает, что любая точка произвольной хорды графика f располагается не ниже соответствующей точки самого графика (лежит ниже хорды, соединяющей две точки ее графика ),(рис 3.6., кривая 1 ).
Простейшими примерами выпуклых функций одной переменной служат парабола y=x2 и экспонента y=ex. Функции y=-x2 и y=-ex являются вогнутыми.
Если при всех x1, x2ÎX x1 ¹x2 и lÎ[0,1] неравенство (3.1) выполняется как строгое (<), то f называется строго выпуклой на X (рис 3.7,а). Функция называется (строго) выгнутой, если - f (строго) выпукла (рис. 3.7, б).
Рис.3.7. Строго выпуклая (а) и строго вогнутая функции, их производные (пунктир) и функция, имеющая линейный участок
Функция f(x), определенная на выпуклом множестве Х, называется сильно выпуклой с константой l > 0, если
(3.2)
Дадим геометрическую интерпретацию определения (3.2), рассмотрев функцию
y= f(x) одного переменного. Зафиксировав x1 и x2 из области определения функции и обозначив , будем изменять l от 0 до 1. Ясно, что тогда значение x(l), будет изменяться от x1 до х2 , а точка (х, f(x)) пройдет по графику функции y=f(x) от точки B= (x2, f(x2)) до точки А= (х1, f(x1)) (рис.3.8).
Рис.3.8. График сильно выпуклой функции.
Уравнения
в плоскости xOy описывают прямую L (секущую), соединяющую точки А и В, а уравнения
задают параболу Р вида , которая проходит через точки А и В. Неравенство (3.2) в этом случае означает, что график функции y = f(x) на плоскости хОу расположен ниже не только секущей, соединяющей точки А и В, но и параболы Р, прогиб которой определяется параметром l и его можно выбрать сколь угодно малым. Другими словами, в области, ограниченной секущей и графиком функции, можно построить параболу, соединяющую точки А и В.
· Теорема3.1 Непрерывно дифференцируемая на выпуклом множестве X функция f выпукла на этом множестве тогда и только тогда, когда для любых x1,x2Î X верно неравенство
f(x2) ³ f(x1) + <Ñf(x1,x2-x1)>, (3.3)
получаемое из разложения функции f(x) в ряд Тейлора в точке x1 путем исключения членов второго и более высокого порядка разложения
где h достаточно малое число, |h|<d. Известно, что если функция f дифференцируема в точке x1, то она в этой точке непрерывна и
Ñf(x1) = ( ¶f/¶x1, ¶f/¶x2,.., ¶f/¶xn)т,
т.е. представляет собой вектор частичных производных первого порядка, вычисленных в точке x1 и называется градиентом функции f в точке x1.
· Теорема 3.2 Пусть функция f дважды непрерывно дифференцируема на выпуклом множестве X, содержащем хотя бы одну внутреннюю точку, и Ñ2f(x)- ее гессиан. Тогда для выпуклости f на множестве X необходимо и достаточно, чтобы матрица Ñ2f(x) была неотрицательно определена при всех xÎX, т.е. чтобы неравенство
<Ñ2f(x)h, h>³0 (3.4)
выполнялось для всех точек xÎX, hÎEn. Здесь числовая матрица Ñ2f(x) называется гессианом (или матрицей Гессе). Если функция f имеет непрерывные частные производные второго порядка (дважды непрерывно дифференцируема ) в точке x1, то она дважды дифференцируема в x1 и обладает матрицей Гессе вида
причем эта матрица симметрична, т.е.
Аналогичные утверждения имеют место и для вогнутых функций. При этом в формулах (3.2) и (3.4) знак неравенства ³ следует заменить на £.
Проверка функции на выпуклость.
Функция f выпуклая, если ее матрица Гессе положительно определена (>0 ) или положительна полуопределена для всех значений x1,x2,..,xn.
Проверка функции на выгнутость.
Функция f выгнутая, если ее матрица Гессе отрицательно полуопределена (£0 ) для всех значений x1,x2,..,xn.
Строго выпуклая или вогнутая функция имеет единственный экстремум, являющийся соответственно глобальным минимумом или максимумом. Функция, имеющая линейный участок (рис 3.7, в), имеет бесконечное число экстремумов, равных по величине.
Для суждения об одноэкстремальности при наличии ограничений можно воспользоваться понятием выпуклости допустимого множества. Множество является выпуклым, если любой отрезок прямой, соединяющей две точки границ множества, целиком лежит внутри множества.
О выпуклости или вогнутости целевой функции можно судить также по характеру изменения ее частных производных ¶f/¶x. В случае строго выпуклой функции эта производная по мере увеличения аргумента возрастает (рис 3.7 а), а для строго выпуклой падает (рис 3.7 б). При наличии линейного участка целевой функции указанная производная на этом участке постоянна.
Выпуклое множество вида
X={xÎEn} | Ax£b}={xÎEn | <ai ,x>£bi, i=1,..,m}
где A- некоторая матрица размера m*n со строками a1,..,am, b=(b1,..,bm) Î En(m=1,2,..). Принято называть полиэдральными или просто полиэдрами. Таким образом, полиэдр - это множество решений некоторой системы конечного числа линейных неравенств, или, что то же самое, пересечение конечного числа полупространств (рис 3.9).
В инженерных приложениях нередки случаи, когда приходится использовать
(3.2)
, будем изменять l от 0 до 1. Ясно, что тогда значение x(l), будет изменяться от x1 до х2 , а точка (х, f(x)) пройдет по графику функции y=f(x) от точки B= (x2, f(x2)) до точки А= (х1, f(x1)) (рис.3.8).
, которая проходит через точки А и В. Неравенство (3.2) в этом случае означает, что график функции y = f(x) на плоскости хОу расположен ниже не только секущей, соединяющей точки А и В, но и параболы Р, прогиб которой определяется параметром l и его можно выбрать сколь угодно малым. Другими словами, в области, ограниченной секущей и графиком функции, можно построить параболу, соединяющую точки А и В.
