Выпуклая оптимизация — проблема программирования

Существует четыре типа задач выпуклого программирования:

Шаг 1 — minf left(x right)$min \: f \ left (x \ right)$, где $x \ in S$ и S — непустое выпуклое множество в $\ mathbb {R} ^ n$ и $f \ left (x \ right)$ — выпуклая функция.

Шаг 2 — minf left(x right),x in mathbbRn$min \: f \ left (x \ right), x \ in \ mathbb {R} ^ n$ при условии

$g_i \ left (x \ right) \ geq 0, 1 \ leq m_1$ и $g_i \ left (x \ right)$ — выпуклая функция.

$g_i \ left (x \ right) \ leq 0, m_1 + 1 \ leq m_2$ и $g_i \ left (x \ right)$ — вогнутая функция.

$g_i \ left (x \ right) = 0, m_2 + 1 \ leq m$ и $g_i \ left (x \ right)$ — линейная функция.

где $f \ left (x \ right)$ — выпуклая функция.

Шаг 3 — maxf left(x right)$max \: f \ left (x \ right)$, где $x \ in S$ и S — непустое выпуклое множество в $\ mathbb {R} ^ n$ и $f \ left (x \) справа)$ — вогнутая функция.

Шаг 4 — minf left(x right)$min \: f \ left (x \ right)$, где $x \ in \ mathbb {R} ^ n$ подчиняется

$g_i \ left (x \ right) \ geq 0, 1 \ leq m_1$ и $g_i \ left (x \ right)$ — выпуклая функция.

$g_i \ left (x \ right) \ leq 0, m_1 + 1 \ leq m_2$ и $g_i \ left (x \ right)$ — вогнутая функция.

$g_i \ left (x \ right) = 0, m_2 + 1 \ leq m$ и $g_i \ left (x \ right)$ — линейная функция.

где $f \ left (x \ right)$ — вогнутая функция.

Конус возможного направления

Пусть S — непустое множество в $\ mathbb {R} ^ n$, и пусть  hatx inClosure left(S right)$\ hat {x} \ in \: Closure \ left (S \ right)$, тогда конус допустимого направления S в $\ hat {x}$, обозначаемый D, определяется как $D = \ left \ {d: d \ neq 0, \ hat {x} + \ lambda d \ in S, \ lambda \ in \ left (0, \ delta \ right), \ delta> 0 \ right \}$

Каждый ненулевой вектор $d \ in D$ называется допустимым направлением.

Для данной функции $f: \ mathbb {R} ^ n \ Rightarrow \ mathbb {R}$ конус улучшения направления в $\ hat {x}$ обозначается через F и определяется как

$$F = \ left \ {d: f \ left (\ hat {x} + \ lambda d \ right) \ leq f \ left (\ hat {x} \ right), \ forall \ lambda \ in \ left ( 0, \ delta \ right), \ delta> 0 \ right \}$$

Каждое направление $d \ in F$ называется улучшающим направлением или направлением спуска f в $\ hat {x}$

теорема

Необходимое условие

Рассмотрим задачу $min f \ left (x \ right)$, в которой $x \ in S$, где S — непустое множество в $\ mathbb {R} ^ n$. Предположим, что f дифференцируема в точке $\ hat {x} \ in S$. Если $\ hat {x}$ является локальным оптимальным решением, то $F_0 \ cap D = \ phi$, где $F_0 = \ left \ {d: \ bigtriangledown f \ left (\ hat {x} \ right) ^ T d <0 \ right \}$, а D — конус возможного направления.

Достаточное условие

Если $F_0 \ cap D = \ phi$ f является псевдовыпуклой функцией в $\ hat {x}$ и существует окрестность $\ hat {x}, N_ \ varepsilon \ left (\ hat {x} \ right) , \ varepsilon> 0$ такое, что $d = x- \ hat {x} \ in D$ для любого $x \ in S \ cap N_ \ varepsilon \ left (\ hat {x} \ right)$, затем $\ hat {x}$ — локально оптимальное решение.

доказательство

Необходимое условие

Пусть $F_0 \ cap D \ neq \ phi$, т. Е. Существует такое $d \ in F_0 \ cap D$, что $d \ in F_0$ и $d \ in D$

Поскольку $d \ in D$, существует $\ delta_1> 0$, для которого $\ hat {x} + \ lambda d \ in S, \ lambda \ in \ left (0, \ delta_1 \ right).$

Так как $d \ in F_0$, поэтому $\ bigtriangledown f \ left (\ hat {x} \ right) ^ T d <0$

Таким образом, существует $\ delta_2> 0$ такое, что $f \ left (\ hat {x} + \ lambda d \ right) <f \ left (\ hat {x} \ right), \ forall \ lambda \ in f \ left (0, \ delta_2 \ right)$

Пусть $\ delta = min \ left \ {\ delta_1, \ delta_2 \ right \}$

Тогда $\ hat {x} + \ lambda d \ in S, f \ left (\ hat {x} + \ lambda d \ right) <f \ left (\ hat {x} \ right), \ forall \ lambda \ в f \ left (0, \ delta \ right)$

Но $\ hat {x}$ является локальным оптимальным решением.

Отсюда и противоречие.

Таким образом, $F_0 \ cap D = \ phi$

Достаточное условие

Пусть $F_0 \ cap D \ neq \ phi$ nd и f — псевдовыпуклая функция.

Пусть существует такая окрестность $\ hat {x}, N _ {\ varepsilon} \ left (\ hat {x} \ right)$, что $d = x- \ hat {x}, \ forall x \ in S \ колпачок N_ \ varepsilon \ left (\ hat {x} \ right)$

Пусть $\ hat {x}$ не является локальным оптимальным решением.

Таким образом, существует $\ bar {x} \ in S \ cap N_ \ varepsilon \ left (\ hat {x} \ right)$, такой что $f \ left (\ bar {x} \ right) <f \ left ( \ hat {x} \ right)$

По предположению $S \ cap N_ \ varepsilon \ left (\ hat {x} \ right), d = \ left (\ bar {x} - \ hat {x} \ right) \ in D$

По псевдовыпуклости f,

$$f \ left (\ hat {x} \ right)> f \ left (\ bar {x} \ right) \ Rightarrow \ bigtriangledown f \ left (\ hat {x} \ right) ^ T \ left (\ bar {x} - \ hat {x} \ right) <0$$

$\ Rightarrow \ bigtriangledown f \ left (\ hat {x} \ right) ^ T d <0$

$\ Rightarrow d \ in F_0$

следовательно, $F_0 \ cap D \ neq \ phi$

что противоречие.

Следовательно, $\ hat {x}$ является локальным оптимальным решением.

Рассмотрим следующую задачу: minf left(x right)$min \: f \ left (x \ right)$, где $x \ in X$ такое, что $g_x \ left (x \ right) \ leq 0, i = 1,2, ..., м$

$f: X \ rightarrow \ mathbb {R}, g_i: X \ rightarrow \ mathbb {R} ^ n$, а X — открытое множество в $\ mathbb {R} ^ n$

Пусть $S = \ left \ {x: g_i \ left (x \ right) \ leq 0, \ forall i \ right \}$

Пусть $\ hat {x} \ in X$, тогда $M = \ left \ {1,2, ..., m \ right \}$

Пусть $I = \ left \ {i: g_i \ left (\ hat {x} \ right) = 0, i \ in M ​​\ right \}$, где I называется набором индексов для всех активных ограничений в $\ hat {x }$

Пусть $J = \ left \ {i: g_i \ left (\ hat {x} \ right) <0, i \ in M ​​\ right \}$, где J называется набором индексов для всех активных ограничений в $\ hat {x }$.

Пусть $F_0 = \ left \ {d \ in \ mathbb {R} ^ m: \ bigtriangledown f \ left (\ hat {x} \ right) ^ T d <0 \ right \}$

Пусть $G_0 = \ left \ {d \ in \ mathbb {R} ^ m: \ bigtriangledown gI \ left (\ hat {x} \ right) ^ T d <0 \ right \}$

или $G_0 = \ left \ {d \ in \ mathbb {R} ^ m: \ bigtriangledown gi \ left (\ hat {x} \ right) ^ T d <0, \ forall i \ in I \ right \}$

лемма

Если $S = \ left \ {x \ in X: g_i \ left (x \ right) \ leq 0, \ forall i \ in I \ right \}$ и X — непустое открытое множество в $\ mathbb {R } ^ N$. Пусть $\ hat {x} \ in S$ и $g_i$ различны в $\ hat {x}, i \ in I$, и пусть $g_i$, где $i \ in J$ непрерывны в $\ hat {x }$, затем $G_0 \ subseteq D$.

доказательство

Пусть $d \ in G_0$

Поскольку $\ hat {x} \ in X$ и X — открытое множество, таким образом, существует $\ delta_1> 0$ такое, что $\ hat {x} + \ lambda d \ in X$ для $\ lambda \ in \ влево (0, \ delta_1 \ right)$

Также, так как $g_ \ hat {x} <0$ и $g_i$ непрерывны в $\ hat {x}, \ forall i \ in J$, существует $\ delta_2> 0$, $g_i \ left (\ hat {x} + \ lambda d \ right) <0, \ lambda \ in \ left (0, \ delta_2 \ right)$

Так как $d \ in G_0$, следовательно, $\ bigtriangledown g_i \ left (\ hat {x} \ right) ^ T d <0, \ forall i \ in I$, таким образом, существует $\ delta_3> 0, g_i \ left (\ hat {x} + \ lambda d \ right) <g_i \ left (\ hat {x} \ right) = 0$, для $\ lambda \ in \ left (0, \ delta_3 \ right) i \ in J$

Пусть $\ delta = min \ left \ {\ delta_1, \ delta_2, \ delta_3 \ right \}$

следовательно, $\ hat {x} + \ lambda d \ in X, g_i \ left (\ hat {x} + \ lambda d \ right) <0, i \ in M ​​$

$\ Rightarrow \ hat {x} + \ lambda d \ in S$

$\ Rightarrow d \ in D$

$\ Rightarrow G_0 \ subseteq D$

Отсюда доказано.

теорема

Необходимое условие

Пусть $f$ и $g_i, i \ in I$, различны в $\ hat {x} \ in S,$ и $g_j$ непрерывны в $\ hat {x} \ in S$. Если $\ hat {x}$ является локальным минимумом $S$, то $F_0 \ cap G_0 = \ phi$.

Достаточное условие

Если $F_0 \ cap G_0 = \ phi$ и f — псевдовыпуклая функция в $\ left (\ hat {x}, g_i 9x \ right), i \ in I$ — строго псевдовыпуклые функции над некоторой $\ varepsilon$ — окрестностью $\ hat {x}, \ hat {x}$ — локальное оптимальное решение.

Пусть $\ hat {x}$ — допустимая точка, такая, что $\ bigtriangledown f \ left (\ hat {x} \ right) = 0$, тогда $F_0 = \ phi$. Таким образом, $F_0 \ cap G_0 = \ phi$, но $\ hat {x}$ не является оптимальным решением

Но если $\ bigtriangledown g \ left (\ hat {x} \ right) = 0$, то $G_0 = \ phi$, то есть $F_0 \ cap G_0 = \ phi$

Рассмотрим задачу: min $f \ left (x \ right)$ такое, что $g \ left (x \ right) = 0$.

Так как $g \ left (x \ right) = 0$, то $g_1 \ left (x \ right) = g \ left (x \ right) <0$ и $g_2 \ left (x \ right) = - g \ left (x \ right) \ leq 0$.

Пусть $\ hat {x} \ in S$, тогда $g_1 \ left (\ hat {x} \ right) = 0$ и $g_2 \ left (\ hat {x} \ right) = 0$.

Но $\ bigtriangledown g_1 \ left (\ hat {x} \ right) = - \ bigtriangledown g_2 \ left (\ hat {x} \ right)$

Таким образом, $G_0 = \ phi$ и $F_0 \ cap G_0 = \ phi$.