Умова Слейтера

Умова Слейтера — це достатня умова для сильної двоїстості в задачі опуклої оптимізації. Умову названо ім'ям Мортона Л. СлейтераШаблон:Sfn. Неформально, умова Слейтера стверджує, що допустима область повинна мати внутрішню точку (див. подробиці нижче).

Умова Слейтера є прикладом умов регулярностіШаблон:Sfn . Зокрема, якщо умова Слейтера виконується для прямої задачі, то розрив двоїстості дорівнює 0 і якщо значення двоїстої задачі скінченне, воно досягаєтьсяШаблон:Sfn.

Формулювання

Розглянемо задачу оптимізації: Мінімізувати $f_0(x)$

За обмежень

$f_i(x)⩽0,i=1,\dots ,m$

$Ax=b$ ,

де $f_0,\dots ,f_m$ — опуклі функції. Це випадок задачі опуклого програмування.

Іншими словами, умова Слейтера для опуклого програмування стверджує, що сильна двоїстість виконується, якщо є точка $x^{*}$, така, що $x^{*}$ лежить строго всередині області допустимих розв'язків (тобто всі обмеження виконуються, а нелінійні обмеження виконуються як строгі нерівності).

Математично умова Слейтера стверджує, що сильна двоїстість виконується, якщо існує точка $x^{*}\in \mathrm{relint}(D)$ (де relint позначає відносну внутрішність опуклої множини $D:=\underset{i=0}{\overset{m}{\cap }}\mathrm{dom}(f_i)$), така, що

$f_i(x^{*})<0,i=1,\dots ,m,$ (опуклі нелінійні обмеження)

$A{x}^{*}=b$Шаблон:Sfn.

Узагальнені нерівності

Нехай дано задачу: Мінімізувати $f_0(x)$

За обмежень

$f_i(x){⩽}_{K_i}0,i=1,\dots ,m$

$Ax=b$ ,

де функція $f_0$ опукла, а $f_i$$K_i$ — опукла для будь-якого $i$. Тоді умова Слейтера каже, що у випадку, коли існує $x^{*}\in \mathrm{relint}(D)$, таке, що

$f_i(x^{*}){<}_{K_i}0,i=1,\dots ,m$ і

$A{x}^{*}=b,$

то має місце сильна двоїстістьШаблон:Sfn.

Література

• Шаблон:Стаття Передруковано в
  • Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга