볼록 최적화-프로그래밍 문제
볼록 프로그래밍 문제에는 네 가지 유형이 있습니다.
Step 1 − $ min \ : f \ left (x \ right) $, 여기서 $ x \ in S $ 및 S는 $ \ mathbb {R} ^ n $ 및 $ f \ left (x \ right ) $는 볼록 함수입니다.
Step 2 − $ 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) $는 볼록 함수입니다.
Step 3 − $ max \ : f \ left (x \ right) $ 여기서 $ x \ in S $ 및 S는 $ \ mathbb {R} ^ n $ 및 $ f \ left (x \ right)에있는 비어 있지 않은 볼록 집합입니다. $는 오목 함수입니다.
Step 4 − $ 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 $에 비어 있지 않은 세트로하고 $ \ hat {x} \ in \ : Closure \ left (S \ right) $, $에서 S의 실현 가능한 방향의 원뿔이되도록합니다. D로 표시되는 \ hat {x} $은 $ D = \ left \ {d : d \ neq 0, \ hat {x} + \ lambda d \ in S, \ lambda \ in \ left (0, \ delta \ right), \ delta> 0 \ right \} $
0이 아닌 각 벡터 $ 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 $는 $ \ hat {x} $에서 f의 개선 방향 또는 하강 방향이라고합니다.
정리
Necessary Condition
$ x \ in S $가되는 $ min f \ left (x \ right) $ 문제를 생각해보십시오. 여기서 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는 가능한 방향의 원뿔입니다.
Sufficient Condition
$ F_0 \ cap D = \ phi $ f가 $ \ hat {x} $에서 의사 볼록 함수이고 $ \ hat {x}, N_ \ varepsilon \ left (\ hat {x} \ right) 근처에있는 경우 , \ varepsilon> 0 $ : $ x \ in S \ cap N_ \ varepsilon \ left (\ hat {x} \ right) $, $ \에 대해 $ d = x- \ hat {x} \ in D $ hat {x} $는 지역 최적 솔루션입니다.
증명
Necessary Condition
$ F_0 \ cap D \ neq \ phi $, 즉 $ d \ in F_0 \ cap D $가 존재하므로 $ d \ in F_0 $ 및 $ d \ in D $
$ d \ in D $이므로 $ \ hat {x} + \ lambda d \ in S, \ lambda \ in \ left (0, \ delta_1 \ right)와 같은 $ \ delta_1> 0 $이 있습니다.
$ d \ in F_0 $이므로 $ \ bigtriangledown f \ left (\ hat {x} \ right) ^ T d <0 $
따라서 $ f \ left (\ hat {x} + \ lambda d \ right) <f \ left (\ hat {x} \ right), \ forall \ lambda \ in f와 같은 $ \ delta_2> 0 $가 있습니다. \ 왼쪽 (0, \ delta_2 \ 오른쪽) $
$ \ 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 $
Sufficient Condition
$ F_0 \ cap D \ neq \ phi $ nd f를 pseudoconvex 함수로 둡니다.
$ \ 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} \ 오른쪽) $
$ S \ cap N_ \ varepsilon \ left (\ hat {x} \ right), d = \ left (\ bar {x}-\ hat {x} \ right) \ in D $에서 가정
f의 pseudoconvex에 의해,
$$ f \ left (\ hat {x} \ right)> f \ left (\ bar {x} \ right) \ Rightarrow \ bigtriangledown f \ left (\ hat {x} \ right) ^ T \ left (\ bar {x}-\ 모자 {x} \ 오른쪽) <0 $$
$ \ Rightarrow \ bigtriangledown f \ left (\ hat {x} \ right) ^ T d <0 $
$ \ 오른쪽 화살표 d \ in F_0 $
따라서 $ F_0 \ cap D \ neq \ phi $
그것은 모순입니다.
따라서 $ \ hat {x} $는 로컬 최적 솔루션입니다.
다음 문제를 고려하십시오 : $ min \ : f \ left (x \ right) $ 여기서 $ x \ in X $는 $ g_x \ left (x \ right) \ leq 0, i = 1,2, ..., m $
$ 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 \} $ 여기서 $ \ 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는 오픈 세트이므로 $ \ hat {x} + \ lambda d \ in X $ for $ \ lambda \ in \과 같은 $ \ delta_1> 0 $이 있습니다. 왼쪽 (0, \ delta_1 \ 오른쪽) $
또한 $ 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 $, for $ \ 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 $
$ \ 오른쪽 화살표 d \ in D $
$ \ 오른쪽 화살표 G_0 \ subseteq D $
따라서 입증되었습니다.
정리
Necessary Condition
$ 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 $입니다.
Sufficient Condition
$ 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) $ that that $ 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 \ 왼쪽 (x \ 오른쪽) \ 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 $입니다.