볼록 최적화

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 정의
3. 이론
4. 종류
5. 라그랑주 승수
6. 방법
- 6.1. 제약 없는 문제와 등식 제약 문제
7. 소프트웨어
8. 응용
9. 확장
참조

1. 개요

볼록 최적화는 볼록 함수를 목적 함수로 하고 볼록 집합을 실현 가능한 집합으로 하는 최적화 문제이다. 이 문제는 지역 최소점이 전역 최소점인 등의 유용한 속성을 가지며, 최소제곱법, 선형 계획법 등 다양한 종류가 있다. 표준 형태는 목적 함수, 부등식 제약, 등식 제약으로 구성되며, 원뿔 형태로도 표현될 수 있다. 라그랑주 승수를 사용하여 문제를 분석할 수 있으며, 내점법, 서브구배 방법 등 다양한 방법으로 해결할 수 있다. 볼록 최적화는 제어 시스템, 신호 처리, 금융 등 다양한 분야에 응용되며, 소프트웨어 도구를 통해 모델링하고 해결할 수 있다.

더 읽어볼만한 페이지

볼록 최적화 - 선형 계획법
선형 계획법은 선형 제약 조건 아래에서 선형 목적 함수의 최적화를 추구하는 기법으로, 자원 배분 문제 해결에서 시작하여 경영 과학, 경제학, 공학 등 여러 분야에서 활용되며, 네트워크 흐름 및 정수 계획법 문제 해결에 중요한 도구로 사용된다.
볼록 최적화 - 확률적 경사 하강법
확률적 경사 하강법은 기계 학습에서 목적 함수를 최소화하는 반복적 최적화 알고리즘으로, 대규모 데이터 세트에서 일부 데이터만 사용하여 경사를 추정하여 계산 비용을 줄이고, 서포트 벡터 머신, 로지스틱 회귀, 심층 신경망 등 다양한 모델 훈련에 활용되며, Adam과 같은 파생 최적화기가 널리 사용된다.
볼록 해석 - 옌센 부등식
옌센 부등식은 볼록 함수 f에 대해 f의 기댓값은 f의 인수의 기댓값에 적용된 함수 값보다 크거나 같다는 부등식으로, 산술-기하 평균 부등식을 포함한 여러 부등식 유도에 사용되며 다양한 분야에 응용된다.
볼록 해석 - 볼록 함수
볼록 함수는 실수 벡터 공간의 볼록 집합에서 정의되고 그래프 상의 두 점을 연결한 선분이 항상 그래프 위에 있거나 접하는 특징을 가지며 다양한 수학적 성질과 여러 분야에 응용되는 함수이다.
수학적 최적화 - 제약된 최적화
제약된 최적화는 제약 조건을 만족하는 해 중에서 목적 함수를 최적화하는 해를 찾는 문제로, 자원 할당, 스케줄링 등에 활용되며, 다양한 제약 조건과 해법을 통해 해결될 수 있습니다.
수학적 최적화 - 모서리해
모서리 해는 경제학에서 소비자가 예산 제약 하에 효용을 극대화할 때, 두 상품 중 하나만 소비하는 경우를 의미하며, 이는 소비자의 극단적인 선택이나 완전 대체재 관계에서 가격이 낮은 상품만 구매하는 경우 등에 나타나는 현상입니다.

볼록 최적화
개요
분야	수학, 컴퓨터 과학, 경제학, 경영 과학
하위 분야	선형 계획법, 정수 계획법, 비선형 계획법, 볼록 프로그래밍, 제약 조건 만족, 혼합 정수 계획법
정의
유형	최적화 문제
설명	제약 조건 집합을 만족하면서 목표 함수를 최소화(또는 최대화)하는 문제
특징
볼록 함수	볼록 집합 위에서 정의된 볼록 함수
응용 분야	기계 학습, 신호 처리, 제어 이론, 통계학, 금융 공학
관련 항목
관련 항목	최적화, 선형 계획법, 비선형 계획법, 볼록 분석

2. 정의

볼록 최적화 문제는 다음 두 가지 요소로 정의된다.^[5]^[6]

목적 함수: n개의 변수를 가지며 실수 값을 갖는 볼록 함수 $f :\mathcal D \subseteq \mathbb{R}^n \to \mathbb{R}$ 이다.
실현 가능한 집합: 볼록 부분 집합 $C\subseteq \mathbb{R}^n$ 이다.

문제의 목표는

\inf \{ f(\mathbf{x}) : \mathbf{x} \in C \}

를 달성하는

\mathbf{x^\ast} \in C

를 찾는 것이다.

최적화 문제의 실행 가능 집합

C

는 부등식 및 등식 제약을 만족하는 모든 점

\mathbf{x} \in \mathcal{D}

로 구성된다. 이 집합은

\mathcal{D}

가 볼록하고, 볼록 함수의 준위 집합이 볼록하며, 아핀 변환 집합이 볼록하고, 볼록 집합의 교집합이 볼록하기 때문에 볼록하다.^[7]

오목 함수

f

를 최대화하는 문제는 볼록 함수

-f

를 최소화하는 문제와 같으므로, 볼록 집합에서 오목 함수를 최대화하는 문제도 일반적으로 볼록 최적화 문제라고 한다.^[8]

2. 1. 추상적 형태

볼록 최적화 문제는 다음 두 가지 요소로 정의된다.^[5]^[6]

'''목적 함수''': ''n''개 변수의 볼록 함수 $f :\mathcal D \subseteq \mathbb{R}^n \to \mathbb{R}$ 이며, 실수 값을 가진다.
'''실현 가능한 집합''': 볼록 부분 집합 $C\subseteq \mathbb{R}^n$ 이다.

문제의 목표는

\inf \{ f(\mathbf{x}) : \mathbf{x} \in C \}

를 만족하는

\mathbf{x^\ast} \in C

를 찾는 것이다.

일반적으로 해의 존재에 관해 다음 세 가지 경우가 있다.^[7]

그러한 점 ''x''*가 존재하면, 이를 ''최적점'' 또는 ''해''라고 하며, 모든 최적점의 집합을 ''최적 집합''이라고 하고, 문제는 ''해결 가능''하다고 한다.
$f$ 가 $C$ 에서 아래로 무한정하거나, 하한이 달성되지 않으면, 최적화 문제는 ''무한정''이라고 한다.
그렇지 않고, $C$ 가 공집합이면, 문제는 ''실현 불가능''이라고 한다.

\mathcal{X}

상의

x^\ast

를 찾는 최적화 문제는 다음과 같다.

:

f(x^\ast) = \min \{f(x):x \in \mathcal{X}\},

여기서

\mathcal{X} \subset \mathbb{R}^n

은 실현 가능한 집합이며,

f(x):\mathbb{R}^n \rightarrow \mathbb{R}

는 목적 함수이다.

\mathcal{X}

가 닫힌 볼록 집합이고,

\mathbb{R}^n

상에서

f(x)

가 볼록 함수이면 이를 볼록 최적화 문제라고 한다.

이는 수학적으로 일반화된 정의이지만, 이 문제가 실제로 제시되는 상황에서

\mathcal{X}\subseteq\mathbb{R^2}

는 구체적인 형태로 표현되는 경우가 많다. 흔한 예로, 주어진 볼록 함수

g_i(x):i = 1,\dots,m

을 사용하여 다음과 같이 연립 부등식을 만족하는 집합으로 정의된다.

\mathcal{X}:=\{x\in\mathbb{R^n}:g_i(x)\leq0,i = 1,\dots,m\}

이러한 점을 고려하여 다음과 같은 정의가 주어지기도 한다.

:

\begin{align}&\operatorname{minimize}& & f(x) \\&\operatorname{subject\;to}& &g_i(x) \leq 0, \quad i = 1,\dots,m\end{align}

여기서, 함수

f, g_1 \ldots g_m : \mathbb{R}^n \rightarrow \mathbb{R}

는 볼록하다.

2. 2. 표준 형태

볼록 최적화 문제는 다음의 형태로 작성될 때 표준 형식을 갖는다.^[7]

:

\begin{align}&\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{align}

여기서:^[7]

$\mathbf{x} \in \mathbb{R}^n$ 는 최적화 변수의 벡터이다.
목적 함수 $f: \mathcal D \subseteq \mathbb{R}^n \to \mathbb{R}$ 는 볼록 함수이다.
부등식 제약 함수 $g_i : \mathbb{R}^n \to \mathbb{R}$ , $i=1, \ldots, m$ 은 볼록 함수이다.
등식 제약 함수 $h_i : \mathbb{R}^n \to \mathbb{R}$ , $i=1, \ldots, p$ 는 아핀 변환이며, $h_i(\mathbf{x}) = \mathbf{a_i}\cdot \mathbf{x} - b_i$ 의 형태를 갖는다. 여기서 $\mathbf{a_i}$ 는 벡터이고 $b_i$ 는 스칼라이다.

표준형은 볼록 최소화 문제를 직관적인 형식으로 표현하며, 다음 세 부분으로 구성된다.

목적 함수: 최소화할 볼록 함수 $f(x): \mathbb{R}^n \to \mathbb{R}$
부등식 제약: $g_i(x) \leq 0$ 형태의 제약 조건. 여기서 $g_i$ 는 볼록 함수이다.
등식 제약: $h_j(x) = 0$ 형태의 제약 조건. 여기서 $h_j$ 는 아핀 변환 함수이다.

일반성을 잃지 않고 목적 함수 f를 선형 함수로 가정할 수 있다. 이는 일반적인 목적 함수를 가진 문제를, 변수 t와 제약 조건

f(\mathbf{x}) - t \leq 0

을 추가하여 선형 목적 함수를 가진 문제로 변환할 수 있기 때문이다.^[9]

등식 제약

h(x) = 0

은 두 개의 부등식 제약

h(x)\leq 0

과

-h(x)\leq 0

으로 대체할 수 있다. 따라서 등식 제약은 이론적으로는 중복되지만, 실제적인 이점 때문에 사용된다.

2. 3. 원뿔 형태

모든 볼록 계획법은 ''원뿔 형태''로 표현될 수 있으며, 이는 아핀 평면과 볼록 원뿔의 교차점에서 선형 목적 함수를 최소화하는 것을 의미한다.^[9]

:

\begin{align}&\underset{\mathbf{x}}{\operatorname{minimize}}& & c^T x \\&\operatorname{subject\ to}& &x \in (b+L)\cap K\end{align}

여기서 K는 닫힌 뾰족한 볼록 원뿔, L은 Rⁿ의 선형 부분 공간, b는 Rⁿ의 벡터이다. 표준 형태의 선형 계획법은 K가 Rⁿ의 음이 아닌 직교좌표계일 때의 특수한 경우이다.

2. 4. 등식 제약 조건 제거

표준 형식의 볼록 최적화 문제는 등식 제약 조건이 없는 볼록 최적화 문제로 변환할 수 있다.^[7] 등식 제약 조건 ''h_i''(''x'')=0을 ''Ax''=''b''로 표시한다. 여기서 ''A''는 ''n''개의 열을 갖는다. 만약 ''Ax''=''b''가 실행 불가능하다면, 당연히 원래의 문제도 실행 불가능하다. 그렇지 않다면, 어떤 해 ''x''₀를 가지며, 모든 해의 집합은 ''Fz''+''x''₀와 같이 나타낼 수 있다. 여기서 ''z''는 ''R^k''에 속하고, ''k''=''n''-rank(''A''), ''F''는 ''n'' x ''k'' 행렬이다. 원래 문제에 ''x'' = ''Fz''+''x''₀를 대입하면 다음과 같다.

minimize|미니마이즈^영어 ''f''('''Fz'''+'''x'''₀)

subject to|서브젝트 투^영어 ''g_i''('''Fz'''+'''x'''₀) ≤ 0, ''i'' = 1, ..., ''m''

여기서 변수는 '''z'''이다. 변수의 개수가 rank(''A'')만큼 줄어든다는 것에 주목해야 한다. 이것은 원칙적으로 등식 제약 조건이 없는 볼록 최적화 문제에 집중할 수 있다는 것을 의미한다. 그러나 실제로는 등식 제약 조건을 유지하는 것이 선호될 수 있는데, 이는 몇몇 알고리즘을 더 효율적으로 만들 수 있고, 또한 문제를 더 쉽게 이해하고 분석할 수 있게 하기 때문이다.

3. 이론

볼록 최적화 문제에는 다음과 같은 유용한 속성이 있다:^[11]^[7]

모든 지역 최소점은 전역 최소점이다.
최적 집합은 볼록하다.
만약 목적 함수가 '엄격하게' 볼록하다면, 문제는 최대 하나의 최적점을 갖는다.

이러한 결과는 힐베르트 공간에서 힐베르트 투영 정리, 분리 초평면 정리, Farkas의 보조정리와 같은 함수 해석학의 기하학적 개념과 함께 볼록 최소화 이론에 사용된다.

볼록 최적화 문제에서 다음 명제는 참이다.

극소값이 존재하면 대역적 최소값이다.
모든 (대역적) 최소값의 집합은 볼록하다.
강볼록 함수이며 함수가 최소값을 가지면, 유일하게 결정된다.

힐베르트 투영 정리, 분리 초평면 정리, Farkas의 보조정리 등의 함수해석학(힐베르트 공간 상의)과도 관련이 있다.

4. 종류

다음 문제 유형은 모두 볼록 최적화 문제이거나 간단한 변환을 통해 볼록 최적화 문제로 축소될 수 있다.^[7]^[10]

볼록 최적화 문제의 계층 구조. (LP: 선형 계획법, QP: 이차 계획법, SOCP 이차원뿔 계획법, SDP: 반정부호 계획법, CP: 원뿔 최적화.)

선형 계획법 문제는 가장 간단한 볼록 프로그램이다. 목적 함수와 제약 조건 함수는 모두 선형이다.
이차 계획법은 그 다음으로 간단하다. 제약 조건은 모두 선형이지만, 목적 함수는 볼록 이차 함수일 수 있다.
이차원뿔 계획법은 더 일반적이다.
반정부호 계획법은 더 일반적이다.
원뿔 최적화는 훨씬 더 일반적이다. (오른쪽 그림 참조)

기타 특수한 사례는 다음과 같다.

최소 제곱법
볼록 이차 제약 조건이 있는 이차 최소화
기하 계획법
적절한 제약 조건이 있는 엔트로피 최대화.

다음은 모두 볼록 최소화 문제이거나, 변수 변환을 통해 볼록 최소화 문제로 만들 수 있는 문제의 예시이다.

문제 유형
최소제곱법
선형 계획법
선형 제약 조건이 있는 볼록 이차 계획법
이차 제약 조건이 있는 이차 계획법 문제
원뿔 선형 계획법
기하 계획법
이차 원뿔 계획법
반정부호 계획법
엔트로피 최대화

5. 라그랑주 승수

표준 형식으로 주어진 볼록 최소화 문제는 비용 함수 $f(x)$ 와 $1 \leq i \leq m$ 에 대한 부등식 제약 조건 $g_i(x)\leq 0$ 으로 구성된다. 이때 정의역 $\mathcal{X}$ 는 다음과 같이 정의된다.

: $\mathcal{X} = \left\{x\in X \vert g_1(x), \ldots, g_m(x)\leq 0\right\}.$

이 문제에 대한 라그랑주 함수는 다음과 같다.^[16]

: $L(x,\lambda_{0},\lambda_1, \ldots ,\lambda_{m})=\lambda_{0} f(x) + \lambda_{1} g_{1} (x)+\cdots + \lambda_{m} g_{m} (x).$

$X$ 에서 $f$ 를 최소화하는 $X$ 의 각 점 $x$ 에 대해, 다음 조건을 동시에 만족하는 라그랑주 승수라고 불리는 실수 $\lambda_{0},\lambda_1, \ldots, \lambda_{m}$ 이 존재한다.

# $x$ 는 모든 $y \in X$ 에 대해 $L(y,\lambda_{0},\lambda_{1},\ldots ,\lambda_{m})$ 을 최소화한다.

# $\lambda_{0},\lambda_{1},\ldots ,\lambda_{m} \geq 0,$ 적어도 하나는 $\lambda_{k} > 0$ 이다.

# $\lambda_{1}g_{1}(x)=\cdots = \lambda_{m}g_{m}(x) = 0$ (상보적 완화 조건).

만약 "엄격한 실행 가능 점", 즉

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

를 만족하는 점 $z$ 가 존재하면, 위의 명제는 $\lambda_{0}=1$ 을 요구하도록 강화될 수 있다.

반대로, $\lambda_{0}=1$ 인 스칼라 $\lambda_{0},\ldots,\lambda_{m}$ 에 대해 $X$ 의 일부 $x$ 가 위 조건 (1) – (3)을 만족하면, $x$ 는 $X$ 에서 $f$ 를 최소화하는 것이 확실하다.

6. 방법

볼록 최적화 문제를 해결하는 현대적인 방법은 다음과 같다:^[12]

내점법: 자기 일치 함수 장벽 함수^[13] 및 자기 정규 장벽 함수를 사용한다.^[14]
번들 방법 (Wolfe, Lemaréchal, Kiwiel)
서브그래디언트 투영 방법 (Polyak)
절단면 방법
타원체 방법
서브그래디언트 방법
Dual subgradients and the drift-plus-penalty method

서브그래디언트 방법은 간단하게 구현할 수 있어 널리 사용된다.^[15] 이중 서브그래디언트 방법은 쌍대 문제에 적용된 서브그래디언트 방법이다. drift-plus-penalty 방법은 이중 서브그래디언트 방법과 유사하지만 원시 변수의 시간 평균을 사용한다.

부등식 제약 조건이 있는 문제를 해결하는 일반적인 방법은 장벽 함수를 목적 함수에 추가하여 부등식 제약 조건을 적용, 제약이 없는 문제로 줄이는 것이다. 이러한 방법을 내점법이라고 한다.^[7]

일부 볼록 최적화 문제에서는 갱신 방법의 효율성이 좋지 않은 경우가 있다. 실용적인 효율성을 얻기 위해서는 문제에 추가적인 제약을 가할 필요가 있다. 장벽 함수법에는 자기 조화 장벽 함수와 자기 정규 장벽 함수, 두 가지 방법이 있다.

6. 1. 제약 없는 문제와 등식 제약 문제

볼록 최적화 문제 중 가장 풀기 쉬운 문제는 ''제약이 없는'' 문제 또는 등식 제약만 있는 문제이다. 등식 제약은 모두 선형이므로 선형대수를 사용하여 제거하고 목적 함수에 통합하여 등식 제약 문제를 제약 없는 문제로 변환할 수 있다.

제약이 없는(또는 등식 제약이 있는) 문제 중에서 가장 간단한 문제는 목적 함수가 이차 함수인 문제이다. 이러한 문제의 경우 KKT 조건(최적성에 필요)은 모두 선형이므로 해석적으로 풀 수 있다.^[7]

두 번 미분 가능한 일반 볼록 목적 함수를 갖는 제약 없는(또는 등식 제약이 있는) 문제의 경우 뉴턴 방법을 사용할 수 있다. 이는 일반적인 제약 없는 볼록 문제를 일련의 이차 문제로 줄이는 것으로 볼 수 있다.^[7] 뉴턴 방법은 적절한 스텝 크기를 위한 선형 탐색과 결합될 수 있으며, 빠르게 수렴한다는 것이 수학적으로 증명될 수 있다.

제약 없는 최소화를 위한 다른 효율적인 알고리즘은 경사 하강법(최급강하법의 특수한 경우)이다.

7. 소프트웨어

볼록 최적화 문제를 해결하기 위한 다양한 소프트웨어 도구들이 존재한다. 이러한 도구는 크게 솔버와 모델링 도구(또는 인터페이스) 두 가지로 분류할 수 있다.

솔버는 최적화 알고리즘을 직접 구현하며, 보통 C와 같은 프로그래밍 언어로 작성된다. 솔버를 사용하려면 사용자가 특정 형식에 맞춰 최적화 문제를 정의해야 하는데, 이는 모델링 관점에서 다소 번거로울 수 있다.

반면, 모델링 도구는 사용자가 좀 더 직관적이고 높은 수준의 언어로 최적화 문제를 정의할 수 있게 해주는 별도의 소프트웨어이다. 모델링 도구는 사용자가 정의한 모델과 솔버의 입/출력 형식 사이의 변환을 자동으로 처리해 준다.

다음은 볼록 최적화 문제 해결에 사용되는 주요 소프트웨어 도구들을 정리한 표이다. 이 표에는 CVXPY, Convex.jl과 같은 모델링 도구와 CVXOPT, MOSEK와 같은 솔버가 함께 포함되어 있으며, 모든 도구를 망라한 것은 아니다.


프로그램	언어	설명	참고
CVX	MATLAB	SeDuMi 및 SDPT3 솔버와 인터페이스를 제공하며, 볼록 최적화 문제만 표현하도록 설계되었다.	^[17]
CVXMOD	파이썬	[https://cvxopt.org/ CVXOPT] 솔버와 인터페이스를 제공한다.	^[17]
CVXPY	파이썬		^[18]
Convex.jl	줄리아	규율 기반 볼록 프로그래밍으로, 여러 솔버를 지원한다.	^[19]
CVXR	R		^[20]
YALMIP	MATLAB, Octave	CPLEX, GUROBI, MOSEK, SDPT3, SEDUMI, CSDP, SDPA, PENNON 솔버와 인터페이스를 제공하며, 정수 및 비선형 최적화, 일부 비볼록 최적화도 지원한다. LP/SOCP/SDP 제약 조건의 불확실성을 포함한 강건 최적화를 수행할 수 있다.	^[17]
LMI lab	MATLAB	반정부호 계획 문제를 표현하고 해결한다("선형 행렬 부등식"이라고 불림).	^[17]
LMIlab 변환기		LMI lab 문제를 SDP 문제로 변환한다.	^[17]
xLMI	MATLAB	LMI lab과 유사하지만 SeDuMi 솔버를 사용한다.	^[17]
AIMMS		선형 계획법에 대한 강건 최적화(2차원 콘 프로그래밍을 해결하기 위해 MOSEK 사용) 및 혼합 정수 선형 계획법을 수행할 수 있다. LP + SDP 및 강건 버전의 모델링 패키지이다.	^[17]
ROME		강건 최적화를 위한 모델링 시스템이다. 분포 강건 최적화와 불확실성 집합을 지원한다.	^[17]
GloptiPoly 3	MATLAB, Octave	다항식 최적화를 위한 모델링 시스템이다.	^[17]
SOSTOOLS		다항식 최적화를 위한 모델링 시스템이다. SDPT3 및 SeDuMi를 사용한다. 기호 계산 툴박스가 필요하다.	^[17]
SparsePOP		다항식 최적화를 위한 모델링 시스템이다. SDPA 또는 SeDuMi 솔버를 사용한다.	^[17]
CPLEX		LP + SOCP를 위한 프라이멀-듀얼 방법을 지원한다. LP, QP, SOCP 및 혼합 정수 선형 계획법 문제를 해결할 수 있다.	^[17]
CSDP	C	LP + SDP를 위한 프라이멀-듀얼 방법을 지원한다. MATLAB, R, 파이썬에 대한 인터페이스가 제공된다. 병렬 버전이 제공된다. SDP 솔버이다.	^[17]
[https://cvxopt.org/ CVXOPT]	파이썬	LP + SOCP + SDP를 위한 프라이멀-듀얼 방법을 지원한다. Nesterov-Todd 스케일링을 사용한다. MOSEK 및 DSDP에 대한 인터페이스가 제공된다.	^[17]
MOSEK		LP + SOCP를 위한 프라이멀-듀얼 방법을 지원한다.	^[17]
SeDuMi	MATLAB, Octave, MEX	LP + SOCP + SDP를 해결한다. LP + SOCP + SDP를 위한 프라이멀-듀얼 방법을 지원한다.	^[17]
SDPA	C++	LP + SDP를 해결한다. LP + SDP를 위한 프라이멀-듀얼 방법을 지원한다. 병렬화되고 확장된 정밀도 버전이 제공된다.	^[17]
SDPT3	MATLAB, Octave, MEX	LP + SOCP + SDP를 해결한다. LP + SOCP + SDP를 위한 프라이멀-듀얼 방법을 지원한다.	^[17]
ConicBundle		LP + SOCP + SDP를 위한 범용 코드를 지원한다. 번들 방법을 사용한다. SDP 및 SOCP 제약 조건에 대한 특수 지원을 제공한다.	^[17]
DSDP		LP + SDP를 위한 범용 코드를 지원한다. 듀얼 내부점 방법을 사용한다.	^[17]
LOQO		SOCP에 대한 범용 코드를 지원하며, 이를 비선형 계획법 문제로 취급한다.	^[17]
PENNON		범용 코드를 지원한다. 증강 라그랑지안 방법을 사용하며, 특히 SDP 제약 조건이 있는 문제에 사용된다.	^[17]
SDPLR		범용 코드를 지원한다. 증강 라그랑지안 방법을 사용하여 낮은 랭크 팩터리제이션을 사용한다.	^[17]
GAMS		선형, 비선형, 혼합 정수 선형/비선형 및 2차원 콘 프로그래밍 문제를 위한 모델링 시스템이다.	^[17]
최적화 서비스		최적화 문제 및 솔루션을 인코딩하기 위한 XML 표준이다.	^[17]

8. 응용

볼록 최적화는 다음과 같은 광범위한 분야의 문제를 모델링하는 데 사용될 수 있다.

자동 제어 시스템
추정 및 신호 처리
통신 및 네트워크
전자 회로 설계^[7]
데이터 분석 및 모델링
금융
통계 (최적 실험 설계)^[21]
구조 최적화
포트폴리오 최적화^[23]
최악의 경우의 위험 분석^[23]
최적의 광고^[23]
회귀 분석 (정규화 및 분위수 회귀 포함)^[23]
모델 적합^[23] (특히 다중 클래스 분류^[24])
전기 생산 최적화^[24]
조합 최적화^[24]
불확실성의 비확률적 모델링^[25]
무선 신호를 사용한 위치 파악^[26]

다음은 모두 볼록 최소화 문제이거나, 변수 변환을 통해 볼록 최소화 문제로 만들 수 있는 문제의 예시이다.

최소제곱법
선형 계획법
선형 제약 조건이 있는 볼록 이차 계획법
이차 제약 조건이 있는 이차 계획법 문제
원뿔 선형 계획법
기하 계획법
이차 원뿔 계획법
반정부호 계획법
엔트로피 최대화

9. 확장

쌍볼록 최적화, 의사볼록 함수, 준볼록 함수의 최적화를 포함하는 볼록 최적화의 확장이 있다. 볼록 해석 이론의 확장과 비볼록 최소화 문제를 근사적으로 해결하기 위한 반복적인 방법은 일반화 볼록성 분야에서 발생하며, 이는 추상 볼록 해석이라고도 한다.

유리 네스테로프(Yuri Nesterov)는 준볼록 최소화 문제를 효율적으로 풀 수 있음을 증명했다. 이 결과는 키위엘(Kiwiel)에 의해 확장되었다.

볼록에 가깝지만 비볼록인 함수의 문제는 계산하기 어렵다. 이바노프(Ivanov)의 결과에 따르면 함수가 매끄럽더라도 단봉 함수를 최소화하는 것은 어렵다. 볼록 함수는 양의 무한대를 포함하도록 확장될 수 있다.

볼록 함수의 확장에는 유사볼록 함수와 준볼록 함수가 포함된다. 볼록 해석과 갱신 방법의 부분적인 확장은 비볼록 최소화 문제에 대한 근사해법으로 일반화된 볼록성 안에서 고려되고 있다.

참조

_[1] harvnb
_[2] journal Some NP-complete problems in quadratic and nonlinear programming
_[3] 문서 "Computationally related problems," in SIAM Journal on Computing, 3, 262--279
_[4] journal Quadratic programming with one negative eigenvalue is NP-hard https://link.springe[...] 1991
_[5] book Convex analysis and minimization algorithms: Fundamentals https://books.google[...] Springer
_[6] book Lectures on modern convex optimization: analysis, algorithms, and engineering applications https://books.google[...]
_[7] 웹사이트 Convex Optimization https://web.stanford[...] Cambridge University Press 2021-04-12
_[8] 웹사이트 Optimization Problem Types - Convex Optimization https://www.solver.c[...] 2011-01-09
_[9] book Interior point polynomial-time methods in convex programming https://citeseerx.is[...]
_[10] journal A rewriting system for convex optimization problems https://web.stanford[...]
_[11] journal Lagrange multipliers and optimality http://web.williams.[...]
_[12] 문서
_[13] book Interior-Point Polynomial Algorithms in Convex Programming Society for Industrial and Applied Mathematics
_[14] journal Self-regular functions and new search directions for linear and semidefinite optimization
_[15] journal Numerical Optimization https://link.springe[...] 2006
_[16] book Optimization and Stability Theory for Economic Analysis Cambridge University Press
_[17] 웹사이트 An Overview Of Software For Convex Optimization http://infohost.nmt.[...] 2021-04-12
_[18] 웹사이트 Welcome to CVXPY 1.1 — CVXPY 1.1.11 documentation https://www.cvxpy.or[...] 2021-04-12
_[19] arXiv Convex Optimization in Julia 2014-10-17
_[20] 웹사이트 Disciplined Convex Optimiation - CVXR https://www.cvxgrp.o[...] 2021-06-17
_[21] 문서
_[22] 문서
_[23] 웹사이트 Convex Optimization Applications https://web.stanford[...] 2021-04-12
_[24] 웹사이트 Convex optimization: applications, formulations, relaxations https://www-ljk.imag[...] 2021-04-12
_[25] 문서
_[26] 문서

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com