Лекція №4 тема 2

Завдання опуклого програмування

2.1.1. Поняття опуклого безлічі

Визначення. МножествоS

En називається опуклим, якщо для будь-яких двох точок і маємо

при будь-якому

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

Приклади опуклих множин

2. Порожня множина.

3. Безліч, що складається з однієї точки

,

,

де

, a ≠ 0, иb - число. Пріn = 3 це безліч збігається зі звичайною площиною, а пріn = 2 - з прямою.

,

де

, a ≠ 0, иb - число.

,

а y (k) - задані вектори

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

7. Опукла комбінація (оболонка) кінцевого числа точок

.

Таке безліч геометрично являє собою n -мірний опуклий багатогранник.

8. Перетин кінцевого числа напівпросторів

,

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

9. Куля радіуса r ≥0 з центром в

.

Як приклади неопуклих множин можна назвати безліч цілих чисел або безліч раціональних чисел.

2.1.2. Властивості опуклих множин

Перетин будь-якого числа опуклих множин є опуклим безліччю.

Об'єднання двох опуклих множин не обов'язково опукло.

Приклад: об'єднання двох точок не є опукле безліч.

геометрична сума

. двох опуклих множин і. обумовлена ​​як

,

також є опуклим безліччю.

Твір опуклого безлічі

на чіслоα. визначається як

також є опуклим безліччю.

Ці твердження випливають з визначення опуклого безлічі. Доведемо, наприклад, перше твердження для перетину двох множин

і. Нехай. Розглянемо

.

З опуклості A і b отримуємо, що

і при всіх . Звідси. Затвердження доведено.

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

Як приклад наведемо опуклий багатогранник. Його крайніми точками є його вершини.

Визначення. МножествоS

En називаетсястрого опуклим. якщо воно опукло і все його граничні точки є крайніми.

Прикладом строго опуклого безлічі є замкнутий куля.

2.1.3. опорна гіперплоскость

Розглянемо найважливіше поняття опорної гіперплощини. Насамперед зазначимо, що будь-яка гіперплоскость. де

, a ≠ 0, визначає в просторі два замкнутих півпростору

Гіперплоскость є перетином цих напівпросторів і одночасно кордоном кожного з них.

Нехай є деяка опукле безліч S і його гранична точкаy.

Визначення. ГіперплоскостьH. що проходить через точкуy і містить всі точки множествоS в одному з визначених нею замкнутих напівпросторів, називається гиперплоскостью, опорної до множествуS в точкеy.

Можна показати, що опорну гіперплоскость можна провести через будь-яку граничну точку опуклого безлічі. Ілюстрація опорної гіперплощини приведена на рис. 3.1.

Мал. 3.1. Опорна гіперплоскость H до опуклого безлічі S в точці y.

Відзначимо, що опорна гіперплоскость може бути не єдина (див. Рис. 3.2).

Мал. 3.2. Дві опорних гіперплощини H1 і H2 до опуклого безлічі S в точці y.

Нехай тепер задано два непустих безлічі A і b. ГіперплоскостьH називаетсяразделяющей гиперплоскостью, якщо всі крапки множестваA лежать в одному з замкнутих напівпросторів, що визначаються гіперплоскостьюH. а всі крапки множестваB лежать в іншому з визначених нею замкнутих напівпросторів. Можна довести кілька теорем про які поділяють гіперплоскостей. Розглянемо найпростішу з них. нехай

- сукупність внутрішніх точок множестваA.

Теорема 3.1. ПустьA иb - два непустих опуклих безлічі, прічемØ. Тоді існує гіперплоскостьH. розділяє множестваA іB.1

Приклади поділяють гіперплоскостей наведені на рис. 3.3 і 3.4.

Мал. 3.3. Гіперплоскость H розділяє безлічі S1 і S2. не мають спільну точку

Мал. 3.4. Гіперплоскость H розділяє безлічі S1 і S2. мають спільну точку

Опуклі і увігнуті функції