Учебники

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

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

Шаг 1minf left(x right), где x inS и S – непустое выпуклое множество в  mathbbRn и f left(x right) – выпуклая функция.

Шаг 2minf left(x right),x in mathbbRn при условии

gi left(x right) geq0,1 leqm1 и gi left(x right) – выпуклая функция.

gi left(x right) leq0,m1+1 leqm2 и gi left(x right) – вогнутая функция.

gi left(x right)=0,m2+1 leqm и gi left(x right) – линейная функция.

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

Шаг 3maxf left(x right), где x inS и S – непустое выпуклое множество в  mathbbRn и f left(x\)справа) – вогнутая функция.

Шаг 4minf left(x right), где x in mathbbRn подчиняется

gi left(x right) geq0,1 leqm1 и gi left(x right) – выпуклая функция.

gi left(x right) leq0,m1+1 leqm2 и gi left(x right) – вогнутая функция.

gi left(x right)=0,m2+1 leqm и gi left(x right) – линейная функция.

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

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

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

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

Для данной функции f: mathbbRn Rightarrow mathbbR конус улучшения направления в  hatx обозначается через 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 inF называется улучшающим направлением или направлением спуска f в  hatx

теорема

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

Рассмотрим задачу minf left(x right), в которой x inS, где S – непустое множество в  mathbbRn. Предположим, что f дифференцируема в точке  hatx inS. Если  hatx является локальным оптимальным решением, то F0 capD= phi, где F_0 = \ left \ {d: \ bigtriangledown f \ left (\ hat {x} \ right) ^ T d <0 \ right \}, а D – конус возможного направления.

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

Если F0 capD= phi f является псевдовыпуклой функцией в  hatx и существует окрестность  hatx,N varepsilon left( hatx right), varepsilon>0 такое, что d=x hatx inD для любого x inS capN varepsilon left( hatx right), затем  hatx – локально оптимальное решение.

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

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

Пусть F0 capD neq phi, т. Е. Существует такое d inF0 capD, что d inF0 и d inD

Поскольку d inD, существует  delta1>0, для которого  hatx+ lambdad inS, lambda in left(0, delta1 right).

Так как d inF0, поэтому  bigtriangledownf left( hatx right)Td<0

Таким образом, существует  delta2>0 такое, что f left( hatx+ lambdad right)<f left( hatx right), forall lambda inf left(0, delta2 right)

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

Тогда  hatx+ lambdad inS,f left( hatx+ lambdad right)<f left( hatx right), forall lambda вf left(0, delta right)

Но  hatx является локальным оптимальным решением.

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

Таким образом, F0 capD= phi

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

Пусть F0 capD neq phi nd и f – псевдовыпуклая функция.

Пусть существует такая окрестность  hatx,N varepsilon left( hatx right), что d=x hatx, forallx inS колпачокN varepsilon left( hatx right)

Пусть  hatx не является локальным оптимальным решением.

Таким образом, существует  barx inS capN varepsilon left( hatx right), такой что f left( barx right)<f left( hatx right)

По предположению S capN varepsilon left( hatx right),d= left( barx hatx right) inD

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

f left( hatx right)>f left( barx right) Rightarrow bigtriangledownf left( hatx right)T left( barx hatx right)<0

 Rightarrow bigtriangledownf left( hatx right)Td<0

 Rightarrowd inF0

следовательно, F0 capD neq phi

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

Следовательно,  hatx является локальным оптимальным решением.

Рассмотрим следующую задачу: minf left(x right), где x inX такое, что gx left(x right) leq0,i=1,2,...,м

f:X rightarrow mathbbR,gi:X rightarrow mathbbRn, а X – открытое множество в  mathbbRn

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

Пусть  hatx inX, тогда 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 .