Выпуклая оптимизация — полярный конус

Пусть S — непустое множество в $\ mathbb {R} ^ n$. Тогда полярный конус S, обозначаемый $S ^ *$, задается через $S ^ * = \ left \ {p \ in \ mathbb {R } ^ n, p ^ Tx \ leq 0 \: \ forall x \ in S \ right \}$.

замечание

• Полярный конус всегда выпуклый, даже если S не выпуклый.

• Если S пустое множество, $S ^ * = \ mathbb {R} ^ n$.

• Полярность можно рассматривать как обобщение ортогональности.

Полярный конус всегда выпуклый, даже если S не выпуклый.

Если S пустое множество, $S ^ * = \ mathbb {R} ^ n$.

Полярность можно рассматривать как обобщение ортогональности.

Пусть $C \ subseteq \ mathbb {R} ^ n$, то ортогональное пространство C, обозначаемое $C ^ \ perp = \ left \ {y \ in \ mathbb {R} ^ n: \ left \ langle x, y \ right \ rangle = 0 \ forall x \ in C \ right \}$.

лемма

Пусть $S, S_1$ и $S_2$ — непустые множества в $\ mathbb {R} ^ n$, тогда следующие утверждения верны:

• $S ^ *$ — замкнутый выпуклый конус.

• $S \ subseteq S ^ {**}$ где $S ^ {**}$ — полярный конус $S ^ *$.

• $S_1 \ subseteq S_2 \ Rightarrow S_ {2} ^ {*} \ subseteq S_ {1} ^ {*}$.

$S ^ *$ — замкнутый выпуклый конус.

$S \ subseteq S ^ {**}$ где $S ^ {**}$ — полярный конус $S ^ *$.

$S_1 \ subseteq S_2 \ Rightarrow S_ {2} ^ {*} \ subseteq S_ {1} ^ {*}$.

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

Шаг 1 — $S ^ * = \ left \ {p \ in \ mathbb {R} ^ n, p ^ Tx \ leq 0 \: \ forall \: x \ in S \ right \}$

• Пусть $x_1, x_2 \ in S ^ * \ Rightarrow x_ {1} ^ {T} x \ leq 0$ и $x_ {2} ^ {T} x \ leq 0, \ forall x \ in S$

  Для $\ lambda \ in \ left (0, 1 \ right), \ left [\ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ right] ^ Tx = \ left [\ left (\ lambda x_1 \ right) ) ^ T + \ left \ {\ left (1- \ lambda \ right) x_ {2} \ right \} ^ {T} \ right] x, \ forall x \ in S$

  $= \ left [\ lambda x_ {1} ^ {T} + \ left (1- \ lambda \ right) x_ {2} ^ {T} \ right] x = \ lambda x_ {1} ^ {T} x + \ left (1- \ lambda \ right) x_ {2} ^ {T} \ leq 0$

  Таким образом, $\ lambda x_1 + \ left (1- \ lambda \ right) x_ {2} \ in S ^ *$

  Следовательно, $S ^ *$ — выпуклое множество.

• Для  lambda geq0,pTx leq0, forallx inS$\ lambda \ geq 0, p ^ {T} x \ leq 0, \ forall \: x \ in S$

  Следовательно, $\ lambda p ^ T x \ leq 0,$

  $\ Rightarrow \ left (\ lambda p \ right) ^ T x \ leq 0$

  $\ Rightarrow \ lambda p \ in S ^ *$

  Таким образом, $S ^ *$ является конусом.

• Показывать, что $S ^ *$ замкнуто, т. Е. Показывать, что если $p_n \ rightarrow p$ как $n \ rightarrow \ infty$, то $p \ in S ^ *$

  $\ forall x \ in S, p_ {n} ^ {T} xp ^ T x = \ left (p_n-p \ right) ^ T x$

  As $p_n \ rightarrow p$ as $n \ rightarrow \ infty \ Rightarrow \ left (p_n \ rightarrow p \ right) \ rightarrow 0$

  Следовательно, $p_ {n} ^ {T} x \ rightarrow p ^ {T} x$. Но pTnx leq0, forallx inS$p_ {n} ^ {T} x \ leq 0, \: \ forall x \ in S$

  Таким образом, $p ^ Tx \ leq 0, \ forall x \ in S$

  $\ Rightarrow p \ in S ^ *$

  Следовательно, $S ^ *$ замкнуто.

Пусть $x_1, x_2 \ in S ^ * \ Rightarrow x_ {1} ^ {T} x \ leq 0$ и $x_ {2} ^ {T} x \ leq 0, \ forall x \ in S$

Для $\ lambda \ in \ left (0, 1 \ right), \ left [\ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ right] ^ Tx = \ left [\ left (\ lambda x_1 \ right) ) ^ T + \ left \ {\ left (1- \ lambda \ right) x_ {2} \ right \} ^ {T} \ right] x, \ forall x \ in S$

$= \ left [\ lambda x_ {1} ^ {T} + \ left (1- \ lambda \ right) x_ {2} ^ {T} \ right] x = \ lambda x_ {1} ^ {T} x + \ left (1- \ lambda \ right) x_ {2} ^ {T} \ leq 0$

Таким образом, $\ lambda x_1 + \ left (1- \ lambda \ right) x_ {2} \ in S ^ *$

Следовательно, $S ^ *$ — выпуклое множество.

Для  lambda geq0,pTx leq0, forallx inS$\ lambda \ geq 0, p ^ {T} x \ leq 0, \ forall \: x \ in S$

Следовательно, $\ lambda p ^ T x \ leq 0,$

$\ Rightarrow \ left (\ lambda p \ right) ^ T x \ leq 0$

$\ Rightarrow \ lambda p \ in S ^ *$

Таким образом, $S ^ *$ является конусом.

Показывать, что $S ^ *$ замкнуто, т. Е. Показывать, что если $p_n \ rightarrow p$ как $n \ rightarrow \ infty$, то $p \ in S ^ *$

$\ forall x \ in S, p_ {n} ^ {T} xp ^ T x = \ left (p_n-p \ right) ^ T x$

As $p_n \ rightarrow p$ as $n \ rightarrow \ infty \ Rightarrow \ left (p_n \ rightarrow p \ right) \ rightarrow 0$

Следовательно, $p_ {n} ^ {T} x \ rightarrow p ^ {T} x$. Но pTnx leq0, forallx inS$p_ {n} ^ {T} x \ leq 0, \: \ forall x \ in S$

Таким образом, $p ^ Tx \ leq 0, \ forall x \ in S$

$\ Rightarrow p \ in S ^ *$

Следовательно, $S ^ *$ замкнуто.

Шаг 2 — $S ^ {**} = \ left \ {q \ in \ mathbb {R} ^ n: q ^ T p \ leq 0, \ forall p \ in S ^ * \ right \}$

Пусть $x \ in S$, затем $\ forall p \ in S ^ *, p ^ T x \ leq 0 \ Rightarrow x ^ Tp \ leq 0 \ Rightarrow x \ in S ^ {**}$

Таким образом, $S \ subseteq S ^ {**}$

Шаг 3 — $S_2 ^ * = \ left \ {p \ in \ mathbb {R} ^ n: p ^ Tx \ leq 0, \ forall x \ in S_2 \ right \}$

Так как $S_1 \ subseteq S_2 \ Rightarrow \ forall x \ in S_2 \ Rightarrow \ forall x \ in S_1$

Следовательно, если $\ hat {p} \ in S_2 ^ *,$, то $\ hat {p} ^ Tx \ leq 0, \ forall x \ in S_2$

$\ Rightarrow \ hat {p} ^ Tx \ leq 0, \ forall x \ in S_1$

$\ Rightarrow \ hat {p} ^ T \ in S_1 ^ *$

$\ Rightarrow S_2 ^ * \ subseteq S_1 ^ *$

теорема

Пусть C — непустой замкнутый выпуклый конус, тогда $C = C ^ **$

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

$C = C ^ {**}$ по предыдущей лемме.

Для доказательства: $x \ in C ^ {**} \ subseteq C$

Пусть $x \ in C ^ {**}$ и пусть $x \ notin C$

Тогда по фундаментальной теореме разделения существует вектор $p \ neq 0$ и скалярный $\ alpha$ такой, что $p ^ Ty \ leq \ alpha, \ forall y \ in C$

Следовательно, $p ^ Tx> \ alpha$

Но, поскольку $\ left (y = 0 \ right) \ in C$ и $p ^ Ty \ leq \ alpha, \ forall y \ in C \ Rightarrow \ alpha \ geq 0$ и $p ^ Tx> 0$

Если $p \ notin C ^ *$, то существует некоторый $\ bar {y} \ in C$ такой, что $p ^ T \ bar {y}> 0$ и $p ^ T \ left (\ lambda \ bar {y} \ right)$ можно сделать сколь угодно большим, если взять $\ lambda$ достаточно большим.

Это противоречит тому факту, что $p ^ Ty \ leq \ alpha, \ forall y \ in C$

Следовательно, $p \ in C ^ *$

Поскольку $x \ in C ^ * = \ left \ {q: q ^ Tp \ leq 0, \ forall p \ in C ^ * \ right \}$

Следовательно, $x ^ Tp \ leq 0 \ Rightarrow p ^ Tx \ leq 0$

Но $p ^ Tx> \ alpha$

Такова контракция.

Таким образом, $x \ in C$

Следовательно, $C = C ^ {**}$.