원뿔 최적화

이 글은 일반적인 참고문헌 목록을 포함하고 있지만, 그에 상응하는 인라인 인용구가 충분하지 않다. 보다 정확한 인용구를 도입하여 이 기사를 개선할 수 있도록 도와주십시오.(2011년 10월) (이 템플릿 메시지를 제거하는 방법과 시기 알아보기)

원뿔 최적화는 아핀 서브공간과 볼록콘의 교차점에 걸쳐 볼록함수를 최소화하는 것으로 구성되는 문제를 연구하는 볼록 최적화의 하위 분야다.

원뿔 최적화 문제의 등급은 가장 잘 알려진 볼록 최적화 문제의 일부 등급, 즉 선형 및 세미데드파인 프로그래밍을 포함한다.

정의

실제 벡터 공간 X, 볼록한 실제 값 함수

${\displaystyle f:C\to \mathb {R} }$

defined on a convex cone ${\displaystyle C\subset X}$, and an affine subspace ${\displaystyle {\mathcal {H}}}$ defined by a set of affine constraints ${\displaystyle h_{i}(x)=0\ }$, a conic optimization problem is to find the point ${\displaystyle x}$ in ${\displaystyle C\cap$숫자$$ $f{\displaystyle (x}$) ${\displaystyle f(x)}$이(가) 가장 작은$$ ${\mathcal{H}}.$

Examples of ${\displaystyle C}$ include the positive orthant ${\displaystyle \mathbb {R} _{+}^{n}=\left\{x\in \mathbb {R} ^{n}:\,x\geq \mathbf {0} \right\}}$, positive semidefinite matrices ${\displaystyle \mathbb {S} _{+}^{n}}$, and the second-order cone ${\displaystyle \{(x}$${\displaystyle \left\{(x,t)\in \mathbb {R} ^{n}\times \mathbb {R} :\lVert x\rVert \leq t\right\}}$. Often ${\displaystyle f\ }$ is a linear function, in which case the conic optimization problem reduces to a linear program, a semidefinite program, and a second order cone program, respectively.

이중성

원뿔 최적화 문제의 특별한 경우에는 이중 문제에 대한 폐쇄형 표현이 눈에 띈다.

코닉 LP

원뿔 선형 프로그램의 이중

${\displaystyle {}^{}}$ C x ${\$ c$^{$$T}x\ }$

$A{\displaystyle }$ ${\displaystyle x}$= ${\displaystyle b,}$ ${\displaystyle x}$ ${\displaystyle \in }$ ${\displaystyle C}$ ${\$ C$\}$의 적용을 받는다.

이다

${\displaystyle {}^{}}$ T ${\displaystyle y^{}}$ ${\$ b$^{$$T}y\ }$

$A{\displaystyle {}^{}}$ ${\displaystyle T^{}}$ ${\displaystyle {}^{}}$+ ${\displaystyle s}$= ${\displaystyle c}$, ${\displaystyle {}^{}}$ ${\displaystyle \in }$ C ${\displaystyle {\ast }^{}}$ $displaystyle$ A$^{$$T}y+s=c,s\in C^{*}\ }$

여기서 $∗{\$는 $C{\displaystyle }$ ${\$ C$\}$의 이중 원뿔을 나타낸다$$$.$

약한 이중성이 원뿔 선형 프로그래밍을 유지하지만, 강한 이중성이 반드시 유지되는 것은 아니다.^[1]

세미데피나이트 프로그램

불평등 형태의 반물질 프로그램의 이중화

${\displaystyle {}^{}}$ C x ${\$ c$^{$$T}x\ }$

${\displaystyle \mathrm{x}}$ ${\displaystyle {1\mathrm{}}_{}}$ ${\displaystyle {}_{}{}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$+ ${\displaystyle \cdots }$+ ${\displaystyle {}_{}}$ ${\displaystyle n_{}}$ F ${\displaystyle n_{}}$+ ${\displaystyle G}$ ${\displaystyle \le }$ 0 ${\displaystyle x_{1$의 적용 대상$}}F_{1}+\cdots +x_{n}$$F_{n}+G\leq 0}$

에 의해 주어지다

$t{\displaystyle \mathrm{}}$ ${\displaystyle \mathrm{r}}$ (${\displaystyle G}$ Z${\displaystyle }$) ${\$

$t{\displaystyle \mathrm{}}$ ${\displaystyle \mathrm{r}}$(${\displaystyle {}_{}}$ Z${\displaystyle }$)${\displaystyle }$+ ${\displaystyle c_{}}$ i${\displaystyle {}_{}}$= ${\displaystyle 0,}$ ${\displaystyle i}$= ${\displaystyle 1}$,${\displaystyle n,}$ n ${\displaystyle \mathrm {tr} \ (F_{i}Z)+c_{i}=0,\quad i=1,\dots,n}$의 적용을 받는다.

$Z\geq 0}Z\geq 0}$

참조

외부 링크

• Boyd, Stephen P.; Vandenberghe, Lieven (2004). Convex Optimization (pdf). Cambridge University Press. ISBN 978-0-521-83378-3. Retrieved October 15, 2011.
• 원뿔 최적화 문제를 해결할 수 있는 MOSEK 소프트웨어.