볼록 해석학

3차원 볼록 다면체. 볼록 해석학은 유클리드 공간의 볼록 부분집합 연구뿐만 아니라 추상 공간의 볼록 함수 연구도 포함한다. **볼록 해석학**(convex analysis)은 수학의 한 분야로, 볼록 함수와 볼록 집합의 속성을 연구하는 학문이며, 종종 최적화 이론의 하위 영역인 볼록 최소화에 응용된다.
# 볼록 집합
볼록 집합 일부 벡터 공간 X의 부분집합 C \subseteq X는 다음 동등한 조건 중 하나를 만족하면 **볼록**이다. #만약 0 \leq r \leq 1이 실수이고 x, y \in C이면 r x + (1 - r) y \in C. #만약 0 -\infty인 경우 **유효**하다고 한다.pp=1-28 다르게 말하면, 이는 f의 정의역에 f(x) \in \mathbb{R}인 x가 존재하고, f가 결코 -\infty와 같지 않음을 의미한다. 즉, 함수가 **유효**하다는 것은 정의역이 비어 있지 않고, -\infty 값을 취하지 않으며, +\infty와 항등적으로 같지 않다는 것이다. 만약 f : \mathbb{R}^n \to [-\infty, \infty]가 유효 볼록 함수라면, b \in \mathbb{R}^n인 어떤 벡터와 r \in \mathbb{R}인 어떤 실수가 존재하여 :f(x) \geq x \cdot b - r 4모든 x에 대해 여기서 x \cdot b는 이들 벡터의 스칼라곱을 나타낸다.
# 볼록 켤레
볼록 켤레 함수 확장된 실수값을 가지는 함수 f : X \to [-\infty, \infty](반드시 볼록일 필요는 없음)의 **볼록 켤레**는 X의 (연속) 쌍대 공간 X^*에서 [-\infty, \infty]로 가는 함수 f^* : X^* \to [-\infty, \infty]이며,pp=75-79 :f^*\left(x^*\right) = \sup_{z \in X} \left\\{ \left\langle x^*, z \right\rangle - f(z) \right\\} 여기서 괄호 \left\langle \cdot, \cdot \right\rangle는 정준 쌍대성 \left\langle x^*, z \right\rangle := x^*(z)를 나타낸다. 만약 \operatorname{Func}(X; Y)가 X 위의 Y-값 함수의 집합을 나타낸다면, f \mapsto f^*로 정의되는 사상 \operatorname{Func}(X; [-\infty, \infty]) \to \operatorname{Func}\left( X^*; [-\infty, \infty] \right)는 **르장드르-펜첼 변환**이라고 불린다.
## 준미분 집합과 펜첼-영 부등식
만약 f : X \to [-\infty, \infty]이고 x \in X이면 **준미분 집합**은 : \begin{alignat}{4} \partial f(x) :&= \left\\{ x^* \in X^* ~:~ f(z) \geq f(x) + \left\langle x^*, z - x \right\rangle \text{ for all } z \in X \right\\} && (\text{“} z \in X \text{*} \text{ can be replaced with: } \text{“} z \in X \text{ such that } z \neq x \text{*}) \\\ &= \left\\{ x^* \in X^* ~:~ \left\langle x^*, x \right\rangle - f(x) \geq \left\langle x^*, z \right\rangle - f(z) \text{ for all } z \in X \right\\} && \\\ &= \left\\{ x^* \in X^* ~:~ \left\langle x^*, x \right\rangle - f(x) \geq \sup_{z \in X} \left\langle x^*, z \right\rangle - f(z) \right\\} && \text{ The right hand side is } f^*\left( x^* \right) \\\ &= \left\\{ x^* \in X^* ~:~ \left\langle x^*, x \right\rangle - f(x) = f^*\left( x^* \right) \right\\} && \text{ Taking } z := x \text{ in the } \sup{} \text{ gives the inequality } \leq. \\\ \end{alignat} 예를 들어, f = \| \cdot \|가 X의 노름인 중요한 특수 경우에,The conclusion is immediate if X = \\{ 0 \\} so assume otherwise. Fix x \in X. Replacing f with the norm gives \partial f(x) = \left\\{ x^* \in X^* ~:~ \left\langle x^*, x \right\rangle - \| x \| \geq \left\langle x^*, z \right\rangle - \| z \| \text{ for all } z \in X \right\\}. If x^* \in \partial f(x) and r \geq 0 is real then using z := r x gives \left\langle x^*, x \right\rangle - \| x \| \geq \left\langle x^*, r x \right\rangle - \| r x \| = r \left[ \left\langle x^*, x \right\rangle - \| x \| \right], where in particular, taking r := 2 gives x^*(x) \geq \| x \| while taking r := \frac1{2} gives x^*(x) \leq \| x \| and thus ; moreover, if in addition x \neq 0 then because x^*\left(\frac{x}{\|x\|}\right) = 1, it follows from the definition of the dual norm that \left\| x^* \right\| \geq 1. Because \partial f(x) \subseteq \left\\{ x^* \in X^* ~:~ x^*(x) = \| x \| \right\\}, which is equivalent to \partial f(x) = \partial f(x) \cap \left\\{ x^* \in X^* ~:~ x^*(x) = \| x \| \right\\}, it follows that \partial f(x) = \left\\{ x^* \in X^* ~:~ x^*(x) = \| x \| \text{ and } \| z \| \geq \left\langle x^*, z \right\rangle \text{ for all } z \in X \right\\}, which implies \left\| x^* \right\| \leq 1 for all x^* \in \partial f(x). From these facts, the conclusion can now be reached. ∎ 0 \neq x \in X이면 이 정의는 다음으로 축소된다는 것을 보일 수 있다. :\partial f (x) = \left\\{ x^* \in X^* ~:~ \left\langle x^*, x \right\rangle = \| x \| \text{ and } \left\| x^* \right\| = 1 \right\\} 4그리고4 \partial f(0) = \left\\{ x^* \in X^* ~:~ \left\| x^* \right\| \leq 1 \right\\}. 모든 x \in X와 x^* \in X^*에 대해, f(x) + f^*\left(x^*\right) \geq \left\langle x^*, x \right\rangle, 이는 펜첼-영 부등식이라고 불린다. 이 부등식은 x^* \in \partial f(x)인 경우에만 등식 (즉, f(x) + f^*\left(x^*\right) = \left\langle x^*, x \right\rangle)이 된다. 이런 방식으로 준미분 집합 \partial f (x)는 볼록 켤레 f^*\left( x^* \right)와 직접적으로 관련되어 있다.
## 이중 켤레
함수 f : X \to [-\infty, \infty]의 **이중 켤레**는 일반적으로 f^{**} : X \to [-\infty, \infty]로 표기되며, 켤레 함수의 켤레이다. 즉, 모든 x \in X에 대해 f^{**}(x) := \sup_{z^* \in X^*} \left\\{ \left\langle x, z^* \right\rangle - f^*\left( z^* \right) \right\\}이다. 이중 켤레는 강한 또는 약한 쌍대성이 언제 성립하는지 (섭동 함수를 통해) 보여주는 데 유용하다. 모든 x \in X에 대해 부등식 f^{**}(x) \leq f(x)는 펜첼-영 부등식에서 비롯된다. 유효 함수의 경우, 펜첼-모로 정리에 따라 f가 볼록이고 하반연속일 필요충분조건으로 f = f^{**}가 성립한다.pp=75-79
# 볼록 최소화
볼록 최적화 **볼록 최소화** (**원시**) **문제**는 볼록 함수 f : X \to [-\infty, \infty]와 볼록 부분집합 M \subseteq X가 주어졌을 때 다음 형태의 문제를 찾는 것이다. : \inf_{x \in M} f(x)를 찾아라.
## 쌍대 문제
쌍대성 (최적화) 최적화 이론에서 쌍대성 원리는 최적화 문제를 원시 문제 또는 쌍대 문제라는 두 가지 관점에서 볼 수 있다고 말한다. 일반적으로 두 쌍대 짝 분리된 국소 볼록 공간 \left(X, X^*\right)와 \left(Y, Y^*\right)가 주어졌다고 하자. 그러면 함수 f : X \to [-\infty, \infty]가 주어졌을 때, 원시 문제를 x를 찾아 다음을 만족하는 문제로 정의할 수 있다. :\inf_{x \in X} f(x). 제약 조건이 있다면, 이는 f = f + I_{\mathrm{constraints로 설정하여 함수 f에 포함시킬 수 있으며, 여기서 I는 지시 함수이다. 그리고 F(x, 0) = f(x)가 되는 섭동 함수 F : X \times Y \to [-\infty, \infty]를 정의한다. 선택된 섭동 함수에 대한 **쌍대 문제**는 다음으로 주어진다. :\sup_{y^* \in Y^*} -F^*\left(0, y^*\right) 여기서 F^*는 F의 두 변수에 대한 볼록 켤레이다. 쌍대성 간격은 다음 부등식의 우변과 좌변의 차이이다.pp=106-113 :\sup_{y^* \in Y^*} -F^*\left(0, y^*\right) \le \inf_{x \in X} F(x, 0). 이 원리는 약한 쌍대성과 동일하다. 만약 두 변이 서로 같다면, 이 문제는 강한 쌍대성을 만족한다고 한다. 강한 쌍대성이 성립하기 위한 많은 조건들이 있다. 예를 들면: * F = F^{**} 여기서 F는 원시 문제와 쌍대 문제를 연결하는 섭동 함수이고 F^{**}는 F의 이중 켤레이다. * 원시 문제가 선형 최적화 문제이다. * 볼록 최적화 문제에 대한 슬레이터 조건.
### 라그랑주 쌍대성
부등식 제약 조건이 있는 볼록 최소화 문제의 경우, :::\min {}_{x} f(x) 제약 조건 g_i(x) \leq 0 (i = 1, \ldots, m). 라그랑주 쌍대 문제는 다음과 같다. :::\sup {}_{u} \inf {}_{x} L(x, u) 제약 조건 u_i(x) \geq 0 (i = 1, \ldots, m). 여기서 목적 함수 L(x, u)는 다음과 같이 정의되는 라그랑주 쌍대 함수이다. :L(x, u) = f(x) + \sum_{j=1}^m u_j g_j(x)
# 내용주
isbn=978-0-691-01586-6 group=proof