Programowanie stożka drugiego rzędu

Program stożkowy drugiego rzędu ( SOCP ) jest wypukłym problemem optymalizacji formy

fa $} x \ }$

z zastrzeżeniem

${\ Displaystyle \ lVert A_ { ja} x + b_ {i} \ rVert _ {2} \ równoważnik c_ {i} ^ {T} x + d_ {i}, \ quad i = 1, \ kropki, m} fa x =$

$Fx =g\ }$

gdzie parametrami problemu są ${\ Displaystyle f \ w \ mathbb {R} ^ {n}, \ A_ {i} \ w \ mathbb {R} ^ {{n_ {i}} \ razy n}, \ b_ {i} \ w \ mathbb {R} ^{n_{i}},\ c_{i}\in \mathbb {R} ^{n},\ d_{i}\in \mathbb {R} ,\ F\in \mathbb {R} ^ {p \ razy n}}$ i ${\ Displaystyle g \ in \ mathbb {R} ^ {p}}$ . ${\ displaystyle x \ in \ mathbb {R} ^ {n}}$ jest zmienną optymalizacyjną. ${\ Displaystyle \ l Vert x \ r Vert _ {2}}$ jest normą euklidesową i ${\ Displaystyle ^ {T}}$ oznacza transpozycję . „Stożek drugiego rzędu” w SOCP wynika z ograniczeń, które są równoważne wymaganiu funkcji afinicznej ${\ Displaystyle (Ax + b, c ^ {T} x + d )}$ leżeć w stożku drugiego rzędu w R $\ Displaystyle \ mathbb {R} ^ {n_ {i} + 1}}$ .

SOCP można rozwiązywać metodami punktów wewnętrznych i ogólnie można je rozwiązywać wydajniej niż problemy z programowaniem półokreślonym (SDP). Niektóre zastosowania inżynieryjne SOCP obejmują projektowanie filtrów, projektowanie masy anten, projektowanie kratownic i optymalizację siły chwytania w robotyce. Zastosowania w finansach ilościowych obejmują optymalizację portfela ; niektóre wpływu na rynek , ponieważ nie są liniowe, nie mogą być rozwiązane za pomocą programowania kwadratowego , ale można je sformułować jako problemy SOCP.

Stożek drugiego rzędu

Standardowy lub jednostkowy stożek drugiego rzędu o wymiarze jest zdefiniowany jako ${\ displaystyle n + 1}$

${\ Displaystyle {\ mathcal {C}} _ ​​{n + 1} = \ lewo \ {{\ początek {bmatrix} x \\ t \ koniec {bmatrix}} {\ Bigg |} x \ w \ mathbb {R} ^{n},t\in \mathbb {R} ,||x||_{2}\równ.t\prawo\}}$ .

Stożek drugiego rzędu jest również znany jako stożek kwadratowy , stożek lodowy lub stożek Lorentza . Stożek drugiego rzędu w ${\ Displaystyle \ mathbb {R} ^ {3}}$ to ${\ Displaystyle \ lewo \ {(x, y, z) {\ duży |} {\ sqrt {x ^ {2} + y ^ {2}}} \ równoważnik z \ prawo \ }}$ .

Zbiór punktów spełniających ograniczenie stożka drugiego rzędu jest odwrotnym obrazem jednostkowego stożka drugiego rzędu w odwzorowaniu afinicznym:

${\ Displaystyle \ l Vert A_ {i} x + b_ {i} \ r Vert _ {2} \ równoważnik c_ {i} ^ {T} x + d_ {i} \ Leftrightarrow {\ rozpocząć {bmatrix} A_ {i} \ \c_{i}^{T}\end{bmatrix}}x+{\begin{bmatrix}b_{i}\\d_{i}\end{bmatrix}}\in {\mathcal {C}}_{n_ {i}+1}}$

a więc jest wypukła.

Od tego czasu stożek drugiego rzędu można osadzić w stożku dodatnich półokreślonych macierzy

${\ Displaystyle || x | | \ równoważnik t \ strzałka w prawo {\ początek {bmatrix} tI & x \\ x ^ {T} i t \ koniec {bmatrix}} \ succcurlyeq 0 ,}$

$jest$ równoważne liniowej nierówności macierzy (tutaj oznacza , $)$ ​​jest to macierz półokreślona Podobnie mamy też,

${\ Displaystyle \ l Vert A_ {i} x + b_ {i} \ r Vert _ {2} \ równoważnik c_ {i} ^ {T} x + d_ {i} \ Leftrightarrow {\ rozpocząć {bmatrix} (c_ {i} ^{T}x+d_{i})I&A_{i}x+b_{i}\\(A_{i}x+b_{i})^{T}&c_{i}^{T}x+d_ {i}\end{bmatrix}}\succcurlyeq 0}$ .

Związek z innymi problemami optymalizacyjnymi

Hierarchia problemów optymalizacji wypukłej. (LP: program liniowy, QP: program kwadratowy, program stożkowy drugiego rzędu SOCP, SDP: program półokreślony, CP: program stożkowy.)

Kiedy dla $Displaystyle$$}$ , SOCP redukuje się do programu liniowego . Kiedy do $\ Displaystyle c_ {i} = 0}$ dla ${\ Displaystyle i = 1, \ kropki, m}$ , SOCP jest równoważne wypukłemu kwadratowo ograniczonemu programowi liniowemu.

wypukłymi ograniczeniami kwadratowymi można również formułować jako SOCP poprzez przeformułowanie funkcji celu jako ograniczenia. Programowanie półokreślone obejmuje SOCP, ponieważ ograniczenia SOCP można zapisać jako liniowe nierówności macierzowe (LMI) i można je przeformułować jako przykład programu półokreślonego. Odwrotność jednak nie jest ważna: istnieją dodatnie półokreślone stożki, które nie dopuszczają żadnej reprezentacji stożka drugiego rzędu. W rzeczywistości, podczas gdy dowolny domknięty zbiór półalgebraiczny wypukły na płaszczyźnie można zapisać jako możliwy region SOCP, wiadomo, że istnieją wypukłe zbiory semialgebraiczne, które nie są reprezentowalne przez SDP, to znaczy istnieją wypukłe zbiory semialgebraiczne, których nie można zapisać jako możliwy region SDP .

Przykłady

Ograniczenie kwadratowe

Rozważ wypukłe ograniczenie kwadratowe formy

${\ Displaystyle x ^ {T} Ax + b ^ {T} x + c \ równoważnik 0.}$

Jest to równoważne z ograniczeniem SOCP

${\ Displaystyle \ lVert A ^ {1/2} x + {\ Frac {1} {2}}A^{-1/2}b\rVert \leq \left({\frac {1}{4}}b^{T}A^{-1}bc\right)^{\frac { 1}{2}}}$

Stochastyczne programowanie liniowe

Rozważ stochastyczny program liniowy w postaci nierówności

zminimalizować do ${T} x \ }$

z zastrzeżeniem

${\ Displaystyle \ mathbb {P} (a_ {i }^{T}x\leq b_{i})\geq p,\quad i=1,\kropki ,m}$

$i$ parametry $są$ niezależnymi wektorami losowymi Gaussa ze kowariancją ${ ja} \ }$ i ${\ Displaystyle p \ geq 0,5}$ . Ten problem można wyrazić jako SOCP

zminimalizować do $^ {T} x \ }$

z zastrzeżeniem

${\ Displaystyle {\ bar {a}} _ {i} ^ {T} x + \ Phi ^ {-1} (p) \ l Vert \ Sigma _ {i} ^ {1/2} x \ r Vert _ {2} \leq b_{i},\quad i=1,\kropki ,m}$

gdzie $_$ . _ _

Stochastyczne programowanie stożkowe drugiego rzędu

Programy stożkowe drugiego rzędu nazywamy deterministycznymi programami stożkowymi drugiego rzędu, ponieważ definiujące je dane są deterministyczne. Stochastyczne programy stożkowe drugiego rzędu to klasa problemów optymalizacyjnych, które są zdefiniowane w celu obsługi niepewności danych definiujących deterministyczne programy stożkowe drugiego rzędu.

Solvery i języki skryptowe (programowania).

Nazwa	Licencja	Krótka informacja
AMPL	handlowy	Algebraiczny język modelowania z obsługą SOCP
Artelys Knitro	handlowy
CPLEX	handlowy
FICO Xpress	handlowy
Gurobi	handlowy
MATLAB	handlowy	Funkcja coneprog rozwiązuje problemy SOCP przy użyciu algorytmu punktu wewnętrznego
MOSEK	handlowy	równoległy algorytm punktu wewnętrznego
Biblioteka numeryczna NAG	handlowy	Biblioteka numeryczna ogólnego przeznaczenia z solverem SOCP