Опуклі множини та їх властивості - студопедія

Безліч - опукле, якщо разом з будь-якими двома точками безлічі належать всі крапки відрізка, що з'єднує в просторі точку з точкою. Зауважимо, що відрізок, що складається з точок. можна параметризрвані наступним чином: Тоді при виходитиме точка. при - точка. а при - проміжні точки відрізка, так що позначення точок відрізка як будуть узгоджені з позначеннями його кінців.

На наступному малюнку зображено два безлічі на площині. одне опукле, а інше немає.

Опуклими в просторі є, наприклад, такі множини: весь простір. його позитивний октант і невід'ємних октант. будь-яку кулю, як відкритий. так і замкнутий. будь-яка гіперплоскость (задана деяким рівнянням виду. а також відкрите і замкнутий півпростору, задані, відповідно, умовами і.

Теорема 1.Якщо все безлічі деякого сімейства опуклі, то опукло і їх перетин

Доведення. Нехай точки і належать; тоді обидві вони належать кожному з множин. Значить, якщо - довільна точка відрізка, що з'єднує і. то вона належить. оскільки опукло. Але так як для всіх. то. що й потрібно було довести.

З цієї теореми випливає, наприклад, що пряма в вимірному просторі (її можна задати як векторних рівнянням:. Де - фіксовані вектори, а - параметр, так і у вигляді перетину гіперплоскостей) є опуклим безліччю. Дійсно, кожна гіперплоскость - опукле безліч.

Означення: Функція. задана на відрізку. називається опуклою (або опуклою донизу) на цьому відрізку, якщо для всіх і виконується нерівність

і увігнутою (або опуклою догори), якщо виконується нерівність

(Тобто функція увігнута в тому і тільки тому випадку, якщо функція опукла.)

У лівій частині цієї нерівності варто значення функції в похідною точці

відрізка між і (будемо для простоти вважати, що), а в правій частині нерівності - значення лінійної функції. такий що і

Якщо і . то нерівність, що означає опуклість функції. перетворюється в таке:

Дамо тепер визначення опуклої функції багатьох змінних.

Определеніе1 Нехай - опукла множина, на якому задана функція. Функція називається опуклою (або опуклою донизу) на множині. якщо для будь-яких двох точок функція. служить обмеженням функції на відрізок, що з'єднує точки і. є опуклою (донизу) функцією одного змінного (тут, як і вище,).

Функція називається увігнутою (або опуклою догори) в. якщо функція увігнута.

Таким чином, функція увігнута в тому і тільки тому випадку, коли функція опукла.

Опуклість функції в означає, що для будь-якого відрізка з кінцями і параметризація цього відрізка у вигляді задає композицію. що є опуклою функцією параметра. З огляду на опуклості області. будь-які точки і відрізка лежать в. і їх знову можна взяти в якості кінців відрізка. Тому для опуклості функції в області необхідно і достатньо, щоб нерівність

виконувалося при всіх і.

Якщо при цьому при всіх і виконується суворе нерівність

то функцію будемо називати строго опуклою в.

Нарешті, функція називається строго ввігнутої. якщо функція строго опукла; це означає виконання строгої нерівності

Геометрично (в разі) сувора опуклість означає, що для будь-якої хорди графіка точки дуги графіка з тими ж кінцями, що у хорди, що лежать в вертикальному перерізі, що проходить через цю хорду, розташовуються нижче точок хорди. Сувора увігнутість означає, що в будь-якому вертикальному перетині графік проходить вище будь-якого відрізка, що з'єднує дві точки графіка.

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

Дамо тепер таке алгебраїчне визначення.

Визначення: Нехай дана квадратна матриця розміру. Вона називається невід'ємне певної. якщо для будь-якого вектора-стовпця (точкою позначено скалярний твір в). Матриця називається позитивно певної. якщо для всіх.

Зауважимо, що вираз можна записати у вигляді. де - це матриця-рядок, що дорівнює транспоновану колонки. Взагалі, верхній лівий індекс ми будемо застосовувати для позначення транспонованою матриці.

Визначення Квадратна матриця називається симетричною. якщо при всіх має місце рівність. тобто якщо.

У симетричній матриці дорівнюють один одному елементи, розташовані симетрично один одному щодо головної діагоналі матриці.

Теорема: Нехай - симетрична неотрицательно певна матриця розміру. Тоді квадратична функція (вона ж називається квадратичною формою. Заданою матрицею)

є опуклою функцією (у всьому просторі, тобто при).

Якщо ж симетрична матриця - позитивно певна, то задана нею квадратична форма є строго опуклою.

Доведення. Нехай і - дві довільні точки і. де. - точка відрізка, що з'єднує с.

Припустимо, що матриця неотрицательно визначена. Елементарні перетворення дозволяють записати у вигляді