볼록 최적화

이 글에는 여러 가지 문제가 있다. 이 문제를 개선하거나 대화 페이지에서 토의하십시오. (이러한 템플릿 메시지를 제거하는 방법 및 시기 알아보기) 이 글은 대부분의 독자들이 이해하기에는 너무 기술적인 것일 수도 있다. 기술 세부 정보를 삭제하지 않고 비전문가가 이해할 수 있도록 개선하십시오. (2013년 6월) (이 템플릿 메시지를 제거하는 방법과 시기 알아보기) 이 글은 일반적인 참고문헌 목록을 포함하고 있지만, 그에 상응하는 인라인 인용구가 충분하지 않기 때문에 대체로 검증되지 않은 상태로 남아 있다. 보다 정확한 인용구를 도입하여 이 기사를 개선할 수 있도록 도와주십시오. (2012년 2월) (이 템플릿 메시지를 제거하는 방법과 시기 알아보기) (이 템플릿 메시지를 제거하는 방법 및 시기 알아보기)

볼록 최적화는 볼록 집합에 걸쳐 볼록함수를 최소화하는 문제를 연구하는 수학적 최적화의 하위 분야다. 수학적 최적화는 일반적으로 NP-hard인 반면,^[1] 많은 종류의 볼록 최적화 문제는 다항식 시간 알고리즘을 인정한다.^[2][3][4]

볼록 최적화 자동 제어 시스템, 평가, 신호 처리, 통신과 네트워크, 전자 회로 design,[5]자료 분석과 모델링, 금융, 통계(최적 실험 설계)[6]고 근사 개념을 증명했다 구조 최적화, 같은 분야로 넓은 범위의 적용시킬 수 있습니다.되려고 능률적인^[7][8] 최근 컴퓨팅과 최적화 알고리즘의 발달로 볼록 프로그래밍은 선형 프로그래밍만큼이나 간단하다.^[9]

정의

볼록 최적화 문제는 객관적 기능이 볼록함수이고 실현 가능한 집합이 볼록 집합인 최적화 문제다. A function ${\displaystyle f}$ mapping some subset of ${\displaystyle \mathbb {R} ^{n}}$into ${\displaystyle \mathbb {R} \cup \{\pm \infty \}}$ is convex if its domain is convex and for all ${\displaystyle \theta \in [0,1]}$ and all ${\displaystyle x,y}$ in its domain, the following condition holds: ${\displaystyle f(\theta x+(1-\theta )y)\leq \theta f(x)+(1-\theta )f(y)}$. A set S is convex if for all members ${\displaystyle x,y\in S}$ and all ${\displaystyle \theta \in [0,1]}$, we have that ${\displaystyle \theta x+(1-\theta )y\in S}$$S}$에서 \$displaystyle \theta x+(1-$\theta $)y$

구체적으로 볼록 최적화 문제는 일부 $x{\displaystyle {\mathbf{}}^{}}$x ${\displaystyle C}$ ${\displaystyle \mathbf$ {$x^{\ast$ }}$\in$ C$}$에 도달하는 문제를 찾는 것이다.

${\displaystyle inf}${ ${\displaystyle f}$( ${\displaystyle x\mathbf{}}$)${\displaystyle }$: ${\displaystyle x\mathbf{}}$ ${\displaystyle \in }$ ${\displaystyle C}$ ${\displaystyle \}}$ ${\displaystyle \inf\{f(\mathbf {x}):\mathbf {x} \in$ C$\backslash \},$

where the objective function ${\displaystyle f:{\mathcal {D}}\subseteq \mathbb {R} ^{n}\to \mathbb {R} }$ is convex, as is the feasible set ${\displaystyle C}$.^{[10] [11]} If such a point exists, it is referred to as an optimal point or solution; the set of all optimal points is called the optimal set. $F{\displaystyle }$ ${\displaystyle f}$이(가) $C{\displaystyle }$ ${\displaystyle$ C$}$에 대해 아래에 바인딩되지 않았거나$$ 최소값에 도달하지 못한 경우 최적화 문제는 바인딩되지 않은 것으로 간주된다. 그렇지 않으면 $C{\displaystyle }$ ${\displaystyle C}$이(가) 빈 세트라면, 그 문제는 실현 불가능하다고 한다.^[12]

표준형식

볼록 최적화 문제는 다음과 같이 기록될 경우 표준 형식이다.

${\displaystyle {\begin{aligned}&{\underset {\mathbf {x} }{\operatorname {minimize} }}&&f(\mathbf {x} )\\&\operatorname {subject\ to} &&g_{i}(\mathbf {x} )\leq 0,\quad i=1,\dots ,m\\&&&h_{i}(\mathbf {x} )=0,\quad i=1,\dots ,p,\end{aligned}}}$

where ${\displaystyle \mathbf {x} \in \mathbb {R} ^{n}}$ is the optimization variable, the function ${\displaystyle f:{\mathcal {D}}\subseteq \mathbb {R} ^{n}\to \mathbb {R} }$ is convex, ${\displaystyle g_{i}:\mathbb {R} ^{n}\to \mathbb {R} }$, ${\displaystyle i=1,\dots ,}$${\displaystyle m}$ ${\displaystyle i=1,\ldots$,$m$$}$은$($는) 볼록이고, ${\displaystyle h_{}}$ :${\displaystyle {}_{}{}^{}}$n → ${\displaystyle R\mathbb{}}${\$displaystyle h_{i}:\mathb {R} ^{n}\to \mathb {R$${\displaystyle }i{\displaystyle }$ =${\displaystyle 1}$, ${\displaystyle p}$ = p$,\displaystysty$i=1$,\dots.$^[12] This notation describes the problem of finding ${\displaystyle \mathbf {x} \in \mathbb {R} ^{n}}$ that minimizes ${\displaystyle f(\mathbf {x} )}$ among all ${\displaystyle \mathbf {x} }$ satisfying ${\displaystyle g_{i}(\mathbf {x} )\leq 0}$, ${\displayst$$yle i=1,\ldots ,m}$ and ${\displaystyle h_{i}(\mathbf {x} )=0}$, ${\displaystyle i=1,\ldots ,p}$. The function ${\displaystyle f}$ is the objective function of the problem, and the functions ${\displaystyle g_{i}}$ and ${\displaystyle h_{i}}$ are the constraint funct이온

최적화 문제의 실현$$ 가능한 세트 $C{\displaystyle }$ ${\displaystyle C}$은(는) 제약 조건을 만족하는$$ 모든 포인트 $x{\displaystyle \mathbf{}}$ ${\displaystyle \in }$ D ${\$로 구성된다. $이{\displaystyle \mathcal{}}$ 세트는 D ${\$이(가) 볼록하고, 볼록함수의 하위 집합이 볼록하고, 아핀 집합이 볼록하며, 볼록 집합의 교차점이 볼록하기 때문에 볼록하다.^[13]

A solution to a convex optimization problem is any point ${\displaystyle \mathbf {x} \in C}$ attaining ${\displaystyle \inf\{f(\mathbf {x} ):\mathbf {x} \in C\}}$. In general, a convex optimization problem may have zero, one, or many solutions.^{[citation needed]}

많은 최적화 문제는 이 표준 형식에서 동등하게 공식화될 수 있다. 예를 들어 오목함수 $f{\displaystyle }$ ${\displaystyle$ f$}$을(를)^{[citation needed]} 최대화하는 문제는 볼록함수를 최소화하는 문제로서${\displaystyle }$동등하게 다시 형성될 수 있다$$$($${\displaystyle f}$ ${\displaystyle -f}).$ 볼록 집합에 걸쳐 오목함수를 최대화하는 문제를 흔히 볼록 최적화 문제라고 한다.

특성.

다음은 볼록 최적화 문제의 유용한 특성이다.^[14][12]

• 모든 국소 최소값은 글로벌 최소값이다.
• 최적 세트는 볼록함.
• 객관적 함수가 엄격히 볼록한 경우, 문제는 최대 하나의 최적점을 가진다.

이러한 결과는 힐버트 투영 정리, 분리 하이퍼플레인 정리, 파르카스의 보조정리 등 기능분석(힐버트 공간 내)으로부터의 기하학적 개념과 함께 볼록 최소화 이론에 의해 사용된다.^{[citation needed]}

적용들

벤하인과 엘리사코프^[15](1990), 엘리사코프 외 연구진(1994)은 불확도 모델에 볼록 분석을 적용했다.^[16]

다음의 문제 등급은 모두 볼록 최적화 문제 또는 간단한 변환을 통해 볼록 최적화 문제로 축소될 수 있다.^[12][17]

• 최소 제곱
• 선형 프로그래밍
• 선형 제약 조건을 갖는 볼록 2차 최소화
• 볼록 2차 구속조건에 따른 2차 최소화
• 원뿔 최적화
• 기하 프로그래밍
• 2차 콘 프로그래밍
• 세미데피나이트 프로그래밍
• 적절한 제약 조건을 갖춘 엔트로피 최대화

볼록스 최적화는 다음을 위한 실용적인 적용이 있다.

• 포트폴리오 최적화^[18]
• 최악의 경우 위험 분석^[18]
• 최적 광고^[18]
• 통계 회귀 분석의 변동(정규화 및 정량화 회귀 분석 포함)^[18]
• 모델 피팅^[18](멀티클라스 분류^[19])
• 발전 최적화^[19]
• 조합 최적화^[19]

라그랑주 승수

이 절은 출처를 인용하지 않는다. 신뢰할 수 있는 출처에 인용문을 추가하여 이 섹션을 개선할 수 있도록 도와주십시오. 비소싱 소재에 이의를 제기하여 제거할 수 있음(2021년 4월) (이 템플릿 메시지 제거 방법 및 시기 학습)

${\displaystyle \mathrm{비용}}함수{\displaystyle \mathrm{}}$ $f{\displaystyle }$( ${\displaystyle x}$) ${\displaystyle f(x)}$ 및$$ 불평등 제약 조건 $g{\displaystyle {}_{}}$ ${\displaystyle i{}_{}}$( x${\displaystyle }$) ${\displaystyle \le }$ 0 $(\$$displaystyle$ $g_{i}(x)\$$leq 0}$에 의해 표준 형식으로 주어진 볼록 최소화 문제를 고려한다$.$ 그러면 도메인 $X{\displaystyle \mathcal{}}$ ${\$은(는) 다음과$$ 같다.

${\displaystyle {\mathcal{X}=\왼쪽\{x\in X\vert g_{1}(x),\ldots, g_{m}(x)\leq 0\right\}.}$

문제의 라그랑지안 함수는

${\displaystyle L(x,\lambda _{0},\lambda _{1}f(x)+\lambda _{1}g(x)+\lambda _{m}(x)=\lambda _{m}.}$

For each point ${\displaystyle x}$ in ${\displaystyle X}$ that minimizes ${\displaystyle f}$ over ${\displaystyle X}$, there exist real numbers ${\displaystyle \lambda _{0},\lambda _{1},\ldots ,\lambda _{m},}$ called Lagrange multipliers, that satisfy these conditions simultaneously:

1. ${\displaystyle x}$ ${\displaystyle x$${\displaystyle {}_{}}$는 ${\displaystyle {모든}_{}}$ $y{\displaystyle }$ ${\displaystyle \in }$ ${\displaystyle X}$, ${\displaystyle y\in$ X$,}$에 걸쳐 $(y,\lambda _{0},\lambda _{1$},\$lambda$ $_$${m})$을 최소화한다.
2. ${\displaystyle {\lambda }_{}}$ ${\displaystyle {0\mathrm{}}_{}}$ ,${\displaystyle {}_{}{\lambda \mathrm{}}_{}}$ 1${\displaystyle {}_{}}$,${\displaystyle }$… ,${\displaystyle m_{}}$ m${\displaystyle {}_{}0}$0 ,$${\$displaystyle \dada _{0},\ldots,\ldots,\m}\geq 0,$ 적어도$$ > ${\displaysty \lambda _{k},},}}}$
3. ${\displaystyle {\lambda }_{}}$ ${\displaystyle {1\mathrm{}}_{}}$ ${\displaystyle g}$ 1${\displaystyle {}_{}}$( x${\displaystyle }$)${\displaystyle }$= ${\displaystyle \cdots }$= ${\displaystyle {\lambda }_{}}$ m ${\displaystyle g_{}}$ ${\displaystyle m{}_{}}$( x${\displaystyle }$)${\displaystyle }$= ${\displaystyle 0}$ ${\displaystyle \lambda _{1}g_{1$}g_{$1}(x)=\cdots =\m}g_{m}(x)=0}($완전 느슨함).

"엄격한 실행 가능한 점", 즉, 만족하는$$ 점 $z{\displaystyle }$ ${\displaystyle z}$이(가) 있는 경우

${\displaystyle g_{1}(z),\ldots ,g_{m}(z)<0,}$

그러면 위의 문구를 강화하여 ${\displaystyle \mathrm{\lambda }}$ 0${\displaystyle {}_{}}$= 1 ${\displaystyle$\ \$da _{0}=1}$을(를) 요구할 수 있다$.$

Conversely, if some ${\displaystyle x}$ in ${\displaystyle X}$ satisfies (1)–(3) for scalars ${\displaystyle \lambda _{0},\ldots ,\lambda _{m}}$ with ${\displaystyle \lambda _{0}=1}$ then ${\displaystyle x}$ is certain to minimize ${\displaystyle f}$ over ${\displa$$ystyle X}$.

알고리즘

구속되지 않는 볼록 최적화는 적절한 스텝 크기를 위한 선 검색과 결합하여 구배 강하(가장 가파른 강하의 특별한 경우) 또는 뉴턴의 방법으로 쉽게 해결할 수 있다. 이것들은 수학적으로 빠르게 수렴될 수 있으며, 특히 후자의 방법이 그렇다.^[20] 선형평등 제약조건을 가진 볼록스 최적화도 목표함수가 2차 함수(초기점이 제약을 충족하지 못하더라도 작용하는 뉴턴의 방법의 변형으로 일반화)인 경우 KKT 매트릭스 기법을 사용하여 해결할 수 있지만, 일반적으로 동등 c를 제거함으로써 해결할 수도 있다.선형 대수학 또는 이중 문제 해결로 인한 ^[20]기질 결국, 두 사람 선형 평등 제약과 볼록 불평등 제약 조건들과 볼록 최적화 목적 함수와 로그 장벽 조건 구속 받지 않는 볼록 최적화 기술을 적용하여 해결될 수 있다.[20](제약 조건을 만족시키기-이'특별한 단계에 의해 선행되고 있을 때 출발점은 실현 가능하지 않다-그것이다.나는 실현 가능한 지점을 찾거나 존재하지 않는다는 것을 보여주는 방법을 사용한다. 1단계 방법은 일반적으로 문제의 검색을 또 다른 볼록 최적화 문제로 축소하는 것으로 구성된다.)^[20]

볼록스 최적화 문제는 다음과 같은 현대적 방법으로도 해결할 수 있다.^[21]

• 번들 방법(Wolfe, Lemaréchal, Kiwiel) 및
• 하위 단계 투영 방법(Polyak),
• 내부 포인트 방법 ^[1]- 자기 모순 장벽 기능과 자기 규칙적인 장벽 기능을 사용한다.^[23]
• 절단면 방법
• 타원체법
• 소분법
• 이중하위 및 드리프트 플러스 벌칙법

하위 단계 방법은 단순하게 구현될 수 있으므로 널리 사용된다.^{[24][citation needed]} 이중 저급 방법은 이중 문제에 적용되는 하위급 방법이다. 표류-플러스-페널티 방법은 이중하위법과 유사하지만 원시 변수의 시간 평균이 소요된다.^{[citation needed]}

구현

볼록스 최적화 및 관련 알고리즘은 다음과 같은 소프트웨어 프로그램에서 구현되었다.

프로그램	언어	설명	FOSS?	참조
CVX	매트랩	SeDuMi 및 SDPT3 해결사와의 인터페이스. 볼록 최적화 문제만 표현하도록 설계.	네	[25]
CVXMOD	파이톤	CVXOPT 해결사와의 인터페이스.	네	[25]
CVXPY	파이톤			[26]
CVXR	R		네	[27]
얄미프	매트랩	CPLE, GROBI, MOSEK, SDPT3, SEDUMI, CSDP, SDPA, PENNON 솔버와의 인터페이스. 또한 정수 및 비선형 최적화 및 일부 비콘벡스 최적화를 지원한다. LP/SOCP/SDP 제약 조건의 불확실성과 함께 강력한 최적화 수행 가능	네	[25]
LMI 연구소	매트랩	준우량 프로그래밍 문제("선형 행렬 불평등"이라 함)를 표현하고 해결	아니요.	[25]
LMI랩 번역기		LMI 실험실 문제를 SDP 문제로 변환	네	[25]
xLMI	매트랩	LMI 연구소와 유사하지만 SeDuMi 해결사를 사용한다.	네	[25]
AIMMS		선형 프로그래밍과 혼합 정수 선형 프로그래밍에서 강력한 최적화를 수행할 수 있다. LP + SDP 및 강력한 버전을 위한 모델링 패키지.	아니요.	[25]
로마		강력한 최적화를 위한 모델링 시스템. 분포적으로 강력한 최적화 및 불확실성 세트 지원	네	[25]
글로프티폴리 3	MATLAB, 옥타브	다항식 최적화를 위한 모델링 시스템.	네	[25]
소스툴스		다항식 최적화를 위한 모델링 시스템. SDPT3 및 SeDuMi 사용. 심볼 연산 도구 상자 필요.	네	[25]
스파스POP		다항식 최적화를 위한 모델링 시스템. SDPA 또는 SeDuMi 해결기 사용	네	[25]
CDPLEX		LP + SOCP에 대한 원시 이중 방식 지원 LP, QP, SOCP, 혼합 정수 선형 프로그래밍 문제를 해결할 수 있다.	아니요.	[25]
CSDP	C	LP + SDP에 대한 원시 이중 방식 지원 MATLAB, R 및 Python에 사용할 수 있는 인터페이스. 병렬 버전 사용 가능. SDP 해결사.	네	[25]
CVXOPT	파이톤	LP + SOCP + SDP에 대한 원시 이중 방식 지원 네스테로프-토드 스케일링 사용 MOSEK 및 DSDP에 대한 인터페이스.	네	[25]
모섹		LP + SOCP에 대한 원시 이중 방식 지원	아니요.	[25]
세두미	MATLAB, MEX	LP + SOCP + SDP 해결 LP + SOCP + SDP에 대한 원시 이중 방식 지원	네	[25]
SDPA	C++	LP + SDP 해결 LP + SDP에 대한 원시 이중 방식 지원 병렬 및 확장 정밀 버전을 사용할 수 있다.	네	[25]
SDPT3	MATLAB, MEX	LP + SOCP + SDP 해결 LP + SOCP + SDP에 대한 원시 이중 방식 지원	네	[25]
코닉번들		LP + SOCP + SDP에 대한 범용 코드 지원 번들 방법을 사용한다. SDP 및 SOCP 제약에 대한 특별 지원.	네	[25]
DSDP		LP + SDP에 대한 범용 코드 지원 이중 내부 포인트 방법을 사용한다.	네	[25]
로코		비선형 프로그래밍 문제로 취급하는 SOCP에 대해 범용 코드를 지원한다.	아니요.	[25]
펜논		범용 코드 지원. 특히 SDP 제약조건의 문제에 대해서는 증강된 라그랑지안 방법을 사용한다.	아니요.	[25]
SDPLR		범용 코드 지원. 증강된 라그랑지식 방법으로 낮은 순위 인자화를 사용한다.	네	[25]
GAMS		선형, 비선형, 혼합 정수 선형/비선형 및 2차 원뿔 프로그래밍 문제를 위한 모델링 시스템.	아니요.	[25]
최적화 서비스		최적화 문제 및 솔루션을 인코딩하기 위한 XML 표준.		[25]

확장

볼록 최적화의 확장에는 비콘벡스, 사이비콘벡스, 퀘이콘벡스 함수의 최적화가 포함된다. 비콘벡스 최소화 문제를 대략적으로 해결하기 위한 볼록 분석 이론과 반복적 방법의 확장은 추상 볼록 분석이라고도 하는 일반화된 볼록성 분야에서 발생한다.^{[citation needed]}

참고 항목

• 이중성
• 카루시-쿤-터커 조건
• 최적화 문제
• 근위부 그라데이션법

메모들

참조

• Bertsekas, Dimitri P.; Nedic, Angelia; Ozdaglar, Asuman (2003). Convex Analysis and Optimization. Belmont, MA.: Athena Scientific. ISBN 978-1-886529-45-8.
• Bertsekas, Dimitri P. (2009). Convex Optimization Theory. Belmont, MA.: Athena Scientific. ISBN 978-1-886529-31-1.
• Bertsekas, Dimitri P. (2015). Convex Optimization Algorithms. Belmont, MA.: Athena Scientific. ISBN 978-1-886529-28-1.
• Borwein, Jonathan; Lewis, Adrian (2000). Convex Analysis and Nonlinear Optimization: Theory and Examples, Second Edition (PDF). Springer. Retrieved 12 Apr 2021.{{cite book}}: CS1 maint : url-status (링크)
• Christensen, Peter W.; Anders Klarbring (2008). An introduction to structural optimization. Vol. 153. Springer Science & Business Media. ISBN 9781402086663.

• 히리아트우루티, 장바티스트, 르마레찰, 클로드. (2004). 볼록 분석의 기초. 베를린: 스프링거.
• Hiriart-Urruty, Jean-Baptiste; Lemaréchal, Claude (1993). Convex analysis and minimization algorithms, Volume I: Fundamentals. Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]. Vol. 305. Berlin: Springer-Verlag. pp. xviii+417. ISBN 978-3-540-56850-6. MR 1261420.
• Hiriart-Urruty, Jean-Baptiste; Lemaréchal, Claude (1993). Convex analysis and minimization algorithms, Volume II: Advanced theory and bundle methods. Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]. Vol. 306. Berlin: Springer-Verlag. pp. xviii+346. ISBN 978-3-540-56852-0. MR 1295240.
• Kiwiel, Krzysztof C. (1985). Methods of Descent for Nondifferentiable Optimization. Lecture Notes in Mathematics. New York: Springer-Verlag. ISBN 978-3-540-15642-0.
• Lemaréchal, Claude (2001). "Lagrangian relaxation". In Michael Jünger and Denis Naddef (ed.). Computational combinatorial optimization: Papers from the Spring School held in Schloß Dagstuhl, May 15–19, 2000. Lecture Notes in Computer Science. Vol. 2241. Berlin: Springer-Verlag. pp. 112–156. doi:10.1007/3-540-45586-8_4. ISBN 978-3-540-42877-0. MR 1900016. S2CID 9048698.
• Nesterov, Yurii; Nemirovskii, Arkadii (1994). Interior Point Polynomial Methods in Convex Programming. SIAM.
• 네스테로프, 유리. (2004). Kluwer 학술출판사 볼록스 최적화 입문강좌
• Rockafellar, R. T. (1970). Convex analysis. Princeton: Princeton University Press.

• Ruszczyński, Andrzej (2006). Nonlinear Optimization. Princeton University Press.
• 쉬밋, LA; 플뢰리, C. 1980: 근사 개념과 이중 방법을 결합한 구조 합성. J. 아머. 인스트. 항공. 우주인 18, 1252-1260

외부 링크

위키미디어 커먼스는 볼록스 최적화 관련 매체를 보유하고 있다.

• EE364a: 볼록스 최적화 I 및 EE364b: 볼록스 최적화 II, 스탠포드 과정 홈페이지
• 6.253: 볼록 분석 및 최적화, MIT OCW 과정 홈페이지
• Brian Borchers, 볼록 최적화 소프트웨어 개요