볼록 최적화-퀵 가이드

이 과정은 다양한 엔지니어링 및 과학 응용 프로그램에서 발생하는 비선형 최적화 문제를 해결하려는 학생들에게 유용합니다. 이 과정은 선형 계획법의 기본 이론으로 시작하여 볼록 세트 및 함수의 개념과 관련 용어를 소개하여 비선형 계획법 문제를 해결하는 데 필요한 다양한 정리를 설명합니다. 이 과정에서는 이러한 문제를 해결하는 데 사용되는 다양한 알고리즘을 소개합니다. 이러한 유형의 문제는 기계 학습, 전기 공학의 최적화 문제 등 다양한 응용 프로그램에서 발생합니다. 학생들은 고등학교 수학 개념과 미적분에 대한 사전 지식이 있어야합니다.

이 과정에서 학생들은 다음과 같은 최적화 문제를 해결하는 방법을 배웁니다. $min f\left ( x \right )$ 일부 제약이 있습니다.

이러한 문제는 다음과 같은 경우 쉽게 해결할 수 있습니다. $f\left ( x \right )$선형 함수이고 제약 조건이 선형 인 경우. 그런 다음 선형 계획법 문제 (LPP)라고합니다. 그러나 제약 조건이 비선형이면 위의 문제를 해결하기가 어렵습니다. 그래프에 함수를 그릴 수 없다면 최적화 분석을 시도하는 것은 한 가지 방법이 될 수 있지만 3 차원을 초과하는 경우 함수를 그릴 수 없습니다. 따라서 이러한 문제를 해결하기 위해 비선형 프로그래밍 또는 볼록 프로그래밍 기술이 제공됩니다. 이 튜토리얼에서는 이러한 기술을 배우는 데 중점을두고 결국에는 이러한 문제를 해결하기위한 몇 가지 알고리즘에 대해 알아 봅니다. 먼저 우리는 볼록 프로그래밍 문제의 기초가되는 볼록 집합의 개념을 가져올 것입니다. 그런 다음 볼록 함수를 도입하여 이러한 문제를 해결하기위한 몇 가지 중요한 정리와 이러한 정리를 기반으로하는 일부 알고리즘을 사용합니다.

용어

  • 우주 $\mathbb{R}^n$ − 다음과 같이 정의 된 실수를 가진 n 차원 벡터입니다 − $\mathbb{R}^n=\left \{ \left ( x_1,x_2,...,x_n \right )^{\tau }:x_1,x_2,....,x_n \in \mathbb{R} \right \}$

  • 우주 $\mathbb{R}^{mXn}$ − 모든 실수 값 행렬의 집합입니다. $mXn$.

방법론

선형 최적화라고도하는 선형 계획법은 관계가 본질적으로 선형 인 수학적 문제를 해결하는 데 사용되는 기술입니다. 선형 계획법의 기본 특성은objective function 일부에 따라 constraints. 목적 함수는 문제의 수학적 모델에서 얻은 선형 함수입니다. 제약 조건은 모델에 부과되는 조건이며 또한 선형입니다.

  • 주어진 질문에서 목적 함수를 찾으십시오.
  • 제약을 찾으십시오.
  • 그래프에 제약 조건을 그립니다.
  • 모든 제약의 교차로 형성되는 실행 가능 영역을 찾으십시오.
  • 가능한 영역의 꼭지점을 찾으십시오.
  • 이 꼭지점에서 목적 함수의 값을 찾으십시오.
  • (질문에 따라) 목적 함수를 최대화하거나 최소화하는 정점이 정답입니다.

Step 1 − 최대화 $5x+3y$ 대상

$x+y\leq 2$,

$3x+y\leq 3$,

$x\geq 0 \:and \:y\geq 0$

Solution

첫 번째 단계는 그래프에서 실행 가능한 영역을 찾는 것입니다.

그래프에서 분명히 알 수 있듯이 실행 가능 영역의 꼭지점은 다음과 같습니다.

$\left ( 0, 0 \right )\left ( 0, 2 \right )\left ( 1, 0 \right )\left ( \frac{1}{2}, \frac{3}{2} \right )$

허락하다 $f\left ( x, y \right )=5x+3y$

이 값을 목적 함수에 넣으면 다음과 같이됩니다.

$f\left ( 0, 0 \right )$= 0

$f\left ( 0, 2 \right )$= 6

$f\left ( 1, 0 \right )$= 5

$f\left ( \frac{1}{2}, \frac{3}{2} \right )$= 7

따라서 함수는 $\left ( \frac{1}{2}, \frac{3}{2} \right )$

Step 2− 한 시계 회사에서 디지털 및 기계식 시계를 생산합니다. 장기적인 예측은 매일 최소 100 개의 디지털 시계와 80 개의 기계식 시계에 대한 예상 수요를 나타냅니다. 생산 능력의 한계로 인해 매일 200 개 이상의 디지털 시계와 170 개의 기계식 시계를 만들 수 없습니다. 배송 계약을 충족하기 위해 매일 총 200 개 이상의 시계가 배송됩니다.

판매 된 각 디지털 시계가 $\$2$ loss, but each mechanical watch produces a $\$5$ 순이익을 극대화하려면 각 유형에서 매일 몇 개를 만들어야합니까?

Solution

허락하다 $x$ 생산 된 디지털 시계의 수

$y$ 생산 된 기계식 시계의 수

질문에 따르면 매일 최소 100 개의 디지털 시계를 만들고 최대 200 개의 디지털 시계를 만들 수 있습니다.

$\Rightarrow 100 \leq \:x\leq 200$

마찬가지로 매일 최소 80 개의 기계식 시계가 만들어지고 최대 170 개의 기계식 시계가 만들어 질 수 있습니다.

$\Rightarrow 80 \leq \:y\leq 170$

매일 최소 200 개의 시계가 생산되기 때문입니다.

$\Rightarrow x +y\leq 200$

판매 된 각 디지털 시계는 $\$2$ loss, but each mechanical watch produces a $\$5$ 이익,

총 이익은 다음과 같이 계산할 수 있습니다.

$Profit =-2x + 5y$

그리고 우리는 이익을 극대화해야합니다. 따라서 질문은 다음과 같이 공식화 될 수 있습니다.

최대화 $-2x + 5y$ 대상

$100 \:\leq x\:\leq 200$

$80 \:\leq y\:\leq 170$

$x+y\:\leq 200$

위의 방정식을 그래프로 그리면,

실행 가능 영역의 정점은 다음과 같습니다.

$\left ( 100, 170\right )\left ( 200, 170\right )\left ( 200, 180\right )\left ( 120, 80\right ) and \left ( 100, 100\right )$

목적 함수의 최대 값은 $\left ( 100, 170\right )$ 따라서 순이익을 극대화하기 위해서는 디지털 시계 100 대와 기계식 시계 170 대를 생산해야한다.

노름은 벡터 또는 변수에 엄격하게 양의 값을 제공하는 함수입니다.

규범은 함수 다 $f:\mathbb{R}^n\rightarrow \mathbb{R}$

규범의 기본 특성은 다음과 같습니다.

허락하다 $X$ 다음과 같은 벡터 $X\in \mathbb{R}^n$

  • $\left \| x \right \|\geq 0$

  • $\left \| x \right \|= 0 \Leftrightarrow x= 0\forall x \in X$

  • $\left \|\alpha x \right \|=\left | \alpha \right |\left \| x \right \|\forall \:x \in X and \:\alpha \:is \:a \:scalar$

  • $\left \| x+y \right \|\leq \left \| x \right \|+\left \| y \right \| \forall x,y \in X$

  • $\left \| x-y \right \|\geq \left \| \left \| x \right \|-\left \| y \right \| \right \|$

정의에 따라 규범은 다음과 같이 계산됩니다.

  • $\left \| x \right \|_1=\displaystyle\sum\limits_{i=1}^n\left | x_i \right |$

  • $\left \| x \right \|_2=\left ( \displaystyle\sum\limits_{i=1}^n\left | x_i \right |^2 \right )^{\frac{1}{2}}$

  • $\left \| x \right \|_p=\left ( \displaystyle\sum\limits_{i=1}^n\left | x_i \right |^p \right )^{\frac{1}{p}},1 \leq p \leq \infty$

규범은 연속 함수입니다.

증명

정의에 따라 $x_n\rightarrow x$ 에 $X\Rightarrow f\left ( x_n \right )\rightarrow f\left ( x \right ) $ 그때 $f\left ( x \right )$ 상수 함수입니다.

허락하다 $f\left ( x \right )=\left \| x \right \|$

따라서, $\left | f\left ( x_n \right )-f\left ( x \right ) \right |=\left | \left \| x_n \right \| -\left \| x \right \|\right |\leq \left | \left | x_n-x \right | \:\right |$

이후 $x_n \rightarrow x$ 그러므로, $\left \| x_n-x \right \|\rightarrow 0$

따라서 $\left | f\left ( x_n \right )-f\left ( x \right ) \right |\leq 0\Rightarrow \left | f\left ( x_n \right )-f\left ( x \right ) \right |=0\Rightarrow f\left ( x_n \right )\rightarrow f\left ( x \right )$

따라서 규범은 연속 함수입니다.

내적은 벡터 쌍에 스칼라를 제공하는 함수입니다.

내부 제품 − $f:\mathbb{R}^n \times \mathbb{R}^n\rightarrow \kappa$ 어디 $\kappa$ 스칼라입니다.

내부 제품의 기본 특성은 다음과 같습니다.

허락하다 $X \in \mathbb{R}^n$

  • $\left \langle x,x \right \rangle\geq 0, \forall x \in X$

  • $\left \langle x,x \right \rangle=0\Leftrightarrow x=0, \forall x \in X$

  • $\left \langle \alpha x,y \right \rangle=\alpha \left \langle x,y \right \rangle,\forall \alpha \in \kappa \: and\: \forall x,y \in X$

  • $\left \langle x+y,z \right \rangle =\left \langle x,z \right \rangle +\left \langle y,z \right \rangle, \forall x,y,z \in X$

  • $\left \langle \overline{y,x} \right \rangle=\left ( x,y \right ), \forall x, y \in X$

Note

  • 규범과 내적 사이의 관계 : $\left \| x \right \|=\sqrt{\left ( x,x \right )}$

  • $\forall x,y \in \mathbb{R}^n,\left \langle x,y \right \rangle=x_1y_1+x_2y_2+...+x_ny_n$

1. 내적 찾기 $x=\left ( 1,2,1 \right )\: and \: y=\left ( 3,-1,3 \right )$

해결책

$\left \langle x,y \right \rangle =x_1y_1+x_2y_2+x_3y_3$

$\left \langle x,y \right \rangle=\left ( 1\times3 \right )+\left ( 2\times-1 \right )+\left ( 1\times3 \right )$

$\left \langle x,y \right \rangle=3+\left ( -2 \right )+3$

$\left \langle x,y \right \rangle=4$

2. 만약 $x=\left ( 4,9,1 \right ),y=\left ( -3,5,1 \right )$ 과 $z=\left ( 2,4,1 \right )$, 찾기 $\left ( x+y,z \right )$

해결책

아시다시피 $\left \langle x+y,z \right \rangle=\left \langle x,z \right \rangle+\left \langle y,z \right \rangle$

$\left \langle x+y,z \right \rangle=\left ( x_1z_1+x_2z_2+x_3z_3 \right )+\left ( y_1z_1+y_2z_2+y_3z_3 \right )$

$\left \langle x+y,z \right \rangle=\left \{ \left ( 4\times 2 \right )+\left ( 9\times 4 \right )+\left ( 1\times1 \right ) \right \}+$

$\left \{ \left ( -3\times2 \right )+\left ( 5\times4 \right )+\left ( 1\times 1\right ) \right \}$

$\left \langle x+y,z \right \rangle=\left ( 8+36+1 \right )+\left ( -6+20+1 \right )$

$\left \langle x+y,z \right \rangle=45+15$

$\left \langle x+y,z \right \rangle=60$

로컬 최소화 또는 최소화

$\bar{x}\in \:S$ 함수의 국소 최솟값이라고합니다. $f$ 만약 $f\left ( \bar{x} \right )\leq f\left ( x \right ),\forall x \in N_\varepsilon \left ( \bar{x} \right )$ 어디 $N_\varepsilon \left ( \bar{x} \right )$ 이웃을 의미 $\bar{x}$즉, $N_\varepsilon \left ( \bar{x} \right )$$ \ left \ | x- \ bar {x} \ 오른쪽 \ | <\ varepsilon $

로컬 Maxima 또는 Maximizer

$\bar{x}\in \:S$ 함수의 극댓값이라고합니다. $f$ 만약 $f\left ( \bar{x} \right )\geq f\left ( x \right ), \forall x \in N_\varepsilon \left ( \bar{x} \right )$ 어디 $N_\varepsilon \left ( \bar{x} \right )$ 이웃을 의미 $\bar{x}$즉, $N_\varepsilon \left ( \bar{x} \right )$$ \ left \ | x- \ bar {x} \ 오른쪽 \ | <\ varepsilon $

글로벌 최소값

$\bar{x}\in \:S$ 함수의 글로벌 최소값이라고합니다. $f$ 만약 $f\left ( \bar{x} \right )\leq f\left ( x \right ), \forall x \in S$

글로벌 최대 값

$\bar{x}\in \:S$ 함수의 글로벌 최댓값이라고합니다. $f$ 만약 $f\left ( \bar{x} \right )\geq f\left ( x \right ), \forall x \in S$

Step 1 − 로컬 최소값과 최대 값 찾기 $f\left ( \bar{x} \right )=\left | x^2-4 \right |$

Solution

위 함수의 그래프에서 국소 최솟값이 $x= \pm 2$ 및 로컬 최대 값 $x = 0$

Step 2 − 함수에서 전역 최소값 찾기 $f\left (x \right )=\left | 4x^3-3x^2+7 \right |$

Solution

위 함수의 그래프에서 전역 최소값이 $x=-1$.

허락하다 $S\subseteq \mathbb{R}^n$ 세트 S의 두 점을 연결하는 선분이 S에도 속한다면 S 세트는 볼록하다고합니다. $x_1,x_2 \in S$, 다음 $\lambda x_1+\left ( 1-\lambda \right )x_2 \in S$ 어디 $\lambda \in\left ( 0,1 \right )$.

Note

  • 두 볼록 세트의 결합은 볼록 일 수도 있고 아닐 수도 있습니다.
  • 두 볼록 세트의 교차점은 항상 볼록합니다.

Proof

허락하다 $S_1$ 과 $S_2$ 두 개의 볼록한 세트입니다.

허락하다 $S_3=S_1 \cap S_2$

허락하다 $x_1,x_2 \in S_3$

이후 $S_3=S_1 \cap S_2$ 그러므로 $x_1,x_2 \in S_1$과 $x_1,x_2 \in S_2$

이후 $S_i$ 볼록 세트입니다. $\forall$ $i \in 1,2,$

그러므로 $\lambda x_1+\left ( 1-\lambda \right )x_2 \in S_i$ 어디 $\lambda \in \left ( 0,1 \right )$

그러므로 $\lambda x_1+\left ( 1-\lambda \right )x_2 \in S_1\cap S_2$

$\Rightarrow \lambda x_1+\left ( 1-\lambda \right )x_2 \in S_3$

그 후, $S_3$ 볼록 세트입니다.

  • 양식의 가중 평균 $\displaystyle\sum\limits_{i=1}^k \lambda_ix_i$,어디 $\displaystyle\sum\limits_{i=1}^k \lambda_i=1$ 과 $\lambda_i\geq 0,\forall i \in \left [ 1,k \right ]$ 원추형 조합이라고합니다. $x_1,x_2,....x_k.$

  • 양식의 가중 평균 $\displaystyle\sum\limits_{i=1}^k \lambda_ix_i$, 어디 $\displaystyle\sum\limits_{i=1}^k \lambda_i=1$ 아핀 조합이라고합니다. $x_1,x_2,....x_k.$

  • 양식의 가중 평균 $\displaystyle\sum\limits_{i=1}^k \lambda_ix_i$ 선형 조합이라고합니다. $x_1,x_2,....x_k.$

Step 1 − 세트가 $S=\left \{ x \in \mathbb{R}^n:Cx\leq \alpha \right \}$ 볼록 세트입니다.

해결책

허락하다 $x_1$ 과 $x_2 \in S$

$\Rightarrow Cx_1\leq \alpha$ 과 $\:and \:Cx_2\leq \alpha$

표시하려면 :$\:\:y=\left ( \lambda x_1+\left ( 1-\lambda \right )x_2 \right )\in S \:\forall \:\lambda \in\left ( 0,1 \right )$

$Cy=C\left ( \lambda x_1+\left ( 1-\lambda \right )x_2 \right )=\lambda Cx_1+\left ( 1-\lambda \right )Cx_2$

$\Rightarrow Cy\leq \lambda \alpha+\left ( 1-\lambda \right )\alpha$

$\Rightarrow Cy\leq \alpha$

$\Rightarrow y\in S$

따라서, $S$ 볼록 세트입니다.

Step 2 − 세트가 $S=\left \{ \left ( x_1,x_2 \right )\in \mathbb{R}^2:x_{1}^{2}\leq 8x_2 \right \}$ 볼록 세트입니다.

해결책

허락하다 $x,y \in S$

허락하다 $x=\left ( x_1,x_2 \right )$ 과 $y=\left ( y_1,y_2 \right )$

$\Rightarrow x_{1}^{2}\leq 8x_2$ 과 $y_{1}^{2}\leq 8y_2$

보여주기 위해- $\lambda x+\left ( 1-\lambda \right )y\in S\Rightarrow \lambda \left ( x_1,x_2 \right )+\left (1-\lambda \right )\left ( y_1,y_2 \right ) \in S\Rightarrow \left [ \lambda x_1+\left ( 1- \lambda)y_2] \in S\right ) \right ]$

$Now, \left [\lambda x_1+\left ( 1-\lambda \right )y_1 \right ]^{2}=\lambda ^2x_{1}^{2}+\left ( 1-\lambda \right )^2y_{1}^{2}+2 \lambda\left ( 1-\lambda \right )x_1y_1$

그러나 $2x_1y_1\leq x_{1}^{2}+y_{1}^{2}$

따라서,

$\left [ \lambda x_1 +\left ( 1-\lambda \right )y_1\right ]^{2}\leq \lambda ^2x_{1}^{2}+\left ( 1- \lambda \right )^2y_{1}^{2}+2 \lambda\left ( 1- \lambda \right )\left ( x_{1}^{2}+y_{1}^{2} \right )$

$\Rightarrow \left [ \lambda x_1+\left ( 1-\lambda \right )y_1 \right ]^{2}\leq \lambda x_{1}^{2}+\left ( 1- \lambda \right )y_{1}^{2}$

$\Rightarrow \left [ \lambda x_1+\left ( 1-\lambda \right )y_1 \right ]^{2}\leq 8\lambda x_2+8\left ( 1- \lambda \right )y_2$

$\Rightarrow \left [ \lambda x_1+\left ( 1-\lambda \right )y_1 \right ]^{2}\leq 8\left [\lambda x_2+\left ( 1- \lambda \right )y_2 \right ]$

$\Rightarrow \lambda x+\left ( 1- \lambda \right )y \in S$

Step 3 − 세트 표시 $S \in \mathbb{R}^n$ 각 정수 k에 대해 볼록한 경우에만 k 점의 모든 볼록 조합 $S$ 에 $S$.

해결책

허락하다 $S$볼록한 집합이어야합니다. 그런 다음 보여주기 위해;

$c_1x_1+c_2x_2+.....+c_kx_k \in S, \displaystyle\sum\limits_{1}^k c_i=1,c_i\geq 0, \forall i \in 1,2,....,k$

귀납법에 의한 증명

에 대한 $k=1,x_1 \in S, c_1=1 \Rightarrow c_1x_1 \in S$

에 대한 $k=2,x_1,x_2 \in S, c_1+c_2=1$ S는 볼록 세트이므로

$\Rightarrow c_1x_1+c_2x_2 \in S.$

S의 m 점의 볼록한 조합이 S에 있다고합시다.

$c_1x_1+c_2x_2+...+c_mx_m \in S,\displaystyle\sum\limits_{1}^m c_i=1 ,c_i \geq 0, \forall i \in 1,2,...,m$

자,하자 $x_1,x_2....,x_m,x_{m+1} \in S$

허락하다 $x=\mu_1x_1+\mu_2x_2+...+\mu_mx_m+\mu_{m+1}x_{m+1}$

허락하다 $x=\left ( \mu_1+\mu_2+...+\mu_m \right )\frac{\mu_1x_1+\mu_2x_2+\mu_mx_m}{\mu_1+\mu_2+.........+\mu_m}+\mu_{m+1}x_{m+1}$

허락하다 $y=\frac{\mu_1x_1+\mu_2x_2+...+\mu_mx_m}{\mu_1+\mu_2+.........+\mu_m}$

$\Rightarrow x=\left ( \mu_1+\mu_2+...+\mu_m \right )y+\mu_{m+1}x_{m+1}$

지금 $y \in S$ 계수의 합이 1이기 때문입니다.

$\Rightarrow x \in S$ S는 볼록 세트이고 $y,x_{m+1} \in S$

따라서 귀납법으로 증명되었습니다.

세트 $A$ 두 개의 다른 점에 대해이 점을 통과하는 선이 세트에있는 경우 아핀 세트라고합니다. $A$.

Note

  • $S$ 포인트의 모든 아핀 조합을 포함하는 경우에만 아핀 집합입니다.

  • 빈 세트와 싱글 톤 세트는 모두 아핀 및 볼록 세트입니다.

    예를 들어 선형 방정식의 해는 아핀 집합입니다.

증명

S를 선형 방정식의해라 고합시다.

정의상 $S=\left \{ x \in \mathbb{R}^n:Ax=b \right \}$

허락하다 $x_1,x_2 \in S\Rightarrow Ax_1=b$ 과 $Ax_2=b$

를 입증하기 위해 : $A\left [ \theta x_1+\left ( 1-\theta \right )x_2 \right ]=b, \forall \theta \in\left ( 0,1 \right )$

$A\left [ \theta x_1+\left ( 1-\theta \right )x_2 \right ]=\theta Ax_1+\left ( 1-\theta \right )Ax_2=\theta b+\left ( 1-\theta \right )b=b$

따라서 S는 아핀 집합입니다.

정리

만약 $C$ 아핀 세트이고 $x_0 \in C$, 다음 세트 $V= C-x_0=\left \{ x-x_0:x \in C \right \}$ C의 부분 공간입니다.

증명

허락하다 $x_1,x_2 \in V$

표시하려면 : $\alpha x_1+\beta x_2 \in V$ 일부 $\alpha,\beta$

지금, $x_1+x_0 \in C$ 과 $x_2+x_0 \in C$ V의 정의

지금, $\alpha x_1+\beta x_2+x_0=\alpha \left ( x_1+x_0 \right )+\beta \left ( x_2+x_0 \right )+\left ( 1-\alpha -\beta \right )x_0$

그러나 $\alpha \left ( x_1+x_0 \right )+\beta \left ( x_2+x_0 \right )+\left ( 1-\alpha -\beta \right )x_0 \in C$ C는 아핀 집합이기 때문입니다.

따라서, $\alpha x_1+\beta x_2 \in V$

따라서 증명되었습니다.

S에있는 점 집합의 볼록 껍질은 내부 또는 경계에있는 S의 모든 점을 포함하는 가장 작은 볼록 영역의 경계입니다.

또는

허락하다 $S\subseteq \mathbb{R}^n$ 표시되는 S의 볼록 껍질 $Co\left ( S \right )$ by는 S의 모든 볼록한 조합의 모음입니다. $x \in Co\left ( S \right )$ 경우에만 $x \in \displaystyle\sum\limits_{i=1}^n \lambda_ix_i$, 어디 $\displaystyle\sum\limits_{1}^n \lambda_i=1$ 과 $\lambda_i \geq 0 \forall x_i \in S$

Remark − 평면에서 S 지점 집합의 Conves 헐은 볼록 다각형을 정의하고 다각형 경계에있는 S 지점은 다각형의 꼭지점을 정의합니다.

Theorem $Co\left ( S \right )= \left \{ x:x=\displaystyle\sum\limits_{i=1}^n \lambda_ix_i,x_i \in S, \displaystyle\sum\limits_{i=1}^n \lambda_i=1,\lambda_i \geq 0 \right \}$ 볼록 껍질이 볼록 집합임을 보여줍니다.

증명

허락하다 $x_1,x_2 \in Co\left ( S \right )$, 다음 $x_1=\displaystyle\sum\limits_{i=1}^n \lambda_ix_i$ 과 $x_2=\displaystyle\sum\limits_{i=1}^n \lambda_\gamma x_i$ 어디 $\displaystyle\sum\limits_{i=1}^n \lambda_i=1, \lambda_i\geq 0$ 과 $\displaystyle\sum\limits_{i=1}^n \gamma_i=1,\gamma_i\geq0$

에 대한 $\theta \in \left ( 0,1 \right ),\theta x_1+\left ( 1-\theta \right )x_2=\theta \displaystyle\sum\limits_{i=1}^n \lambda_ix_i+\left ( 1-\theta \right )\displaystyle\sum\limits_{i=1}^n \gamma_ix_i$

$\theta x_1+\left ( 1-\theta \right )x_2=\displaystyle\sum\limits_{i=1}^n \lambda_i \theta x_i+\displaystyle\sum\limits_{i=1}^n \gamma_i\left ( 1-\theta \right )x_i$

$\theta x_1+\left ( 1-\theta \right )x_2=\displaystyle\sum\limits_{i=1}^n\left [ \lambda_i\theta +\gamma_i\left ( 1-\theta \right ) \right ]x_i$

계수를 고려하면,

$\displaystyle\sum\limits_{i=1}^n\left [ \lambda_i\theta +\gamma_i\left ( 1-\theta \right ) \right ]=\theta \displaystyle\sum\limits_{i=1}^n \lambda_i+\left ( 1-\theta \right )\displaystyle\sum\limits_{i=1}^n\gamma_i=\theta +\left ( 1-\theta \right )=1$

그 후, $\theta x_1+\left ( 1-\theta \right )x_2 \in Co\left ( S \right )$

따라서 볼록 껍질은 볼록 집합입니다.

S를 임의의 집합으로하자 $\mathbb{R}^n$.만약 $x \in Co\left ( S \right )$, 다음 $x \in Co\left ( x_1,x_2,....,x_n,x_{n+1} \right )$.

증명

이후 $x \in Co\left ( S\right )$, 다음 $x$ S에서 유한 한 수의 점의 볼록한 조합으로 표시됩니다. 즉,

$x=\displaystyle\sum\limits_{j=1}^k \lambda_jx_j,\displaystyle\sum\limits_{j=1}^k \lambda_j=1, \lambda_j \geq 0$ 과 $x_j \in S, \forall j \in \left ( 1,k \right )$

만약 $k \leq n+1$, 얻은 결과는 분명히 사실입니다.

만약 $k \geq n+1$, 다음 $\left ( x_2-x_1 \right )\left ( x_3-x_1 \right ),....., \left ( x_k-x_1 \right )$ 선형 의존적입니다.

$\Rightarrow \exists \mu _j \in \mathbb{R}, 2\leq j\leq k$ (모두 0이 아님) $\displaystyle\sum\limits_{j=2}^k \mu _j\left ( x_j-x_1 \right )=0$

밝히다 $\mu_1=-\displaystyle\sum\limits_{j=2}^k \mu _j$, 다음 $\displaystyle\sum\limits_{j=1}^k \mu_j x_j=0, \displaystyle\sum\limits_{j=1}^k \mu_j=0$

모두가 아닌 $\mu_j's$0과 같습니다. 이후$\displaystyle\sum\limits_{j=1}^k \mu_j=0$, 다음 중 하나 이상 $\mu_j > 0,1 \leq j \leq k$

그때, $x=\displaystyle\sum\limits_{1}^k \lambda_j x_j+0$

$x=\displaystyle\sum\limits_{1}^k \lambda_j x_j- \alpha \displaystyle\sum\limits_{1}^k \mu_j x_j$

$x=\displaystyle\sum\limits_{1}^k\left ( \lambda_j- \alpha\mu_j \right )x_j $

고르다 $\alpha$ 그런 $\alpha=min\left \{ \frac{\lambda_j}{\mu_j}, \mu_j\geq 0 \right \}=\frac{\lambda_j}{\mu _j},$ 일부 $i=1,2,...,k$

만약 $\mu_j\leq 0, \lambda_j-\alpha \mu_j\geq 0$

만약 $\mu_j> 0, then \:\frac{\lambda _j}{\mu_j}\geq \frac{\lambda_i}{\mu _i}=\alpha \Rightarrow \lambda_j-\alpha \mu_j\geq 0, j=1,2,...k$

특히, $\lambda_i-\alpha \mu_i=0$, 정의에 따라 $\alpha$

$x=\displaystyle\sum\limits_{j=1}^k \left ( \lambda_j- \alpha\mu_j\right )x_j$,어디

$\lambda_j- \alpha\mu_j\geq0$ 과 $\displaystyle\sum\limits_{j=1}^k\left ( \lambda_j- \alpha\mu_j\right )=1$ 과 $\lambda_i- \alpha\mu_i=0$

따라서 x는 최대 (k-1) 점의 볼록한 조합으로 나타낼 수 있습니다.

x가 (n + 1) 요소의 볼록한 조합으로 표시 될 때까지이 감소 과정을 반복 할 수 있습니다.

S를 비어 있지 않고 닫히고 경계가 지정된 집합 (간단한 집합이라고도 함)이라고합니다. $\mathbb{R}^n$ 그리고하자 $f:S\rightarrow \mathbb{R} $ S에 대한 연속 함수이면 문제 min $\left \{ f\left ( x \right ):x \in S \right \}$ 최소에 도달합니다.

증명

S는 비어 있지 않고 경계가 있으므로 하한이 있습니다.

$\alpha =Inf\left \{ f\left ( x \right ):x \in S \right \}$

이제 $S_j=\left \{ x \in S:\alpha \leq f\left ( x \right ) \leq \alpha +\delta ^j\right \} \forall j=1,2,...$ 과 $\delta \in \left ( 0,1 \right )$

infimium의 정의에 따르면 $S_j$ 비어 있지 않습니다. $j$.

일부 선택 $x_j \in S_j$ 시퀀스를 얻으려면 $\left \{ x_j \right \}$ ...에 대한 $j=1,2,...$

S가 경계이므로 시퀀스도 경계가 지정되고 수렴 하위 시퀀스가 ​​있습니다. $\left \{ y_j \right \}$, 수렴 $\hat{x}$. 그 후$\hat{x}$ 한계점이고 S는 닫혀 있으므로 $\hat{x} \in S$. f는 연속적이므로$f\left ( y_i \right )\rightarrow f\left ( \hat{x} \right )$.

이후 $\alpha \leq f\left ( y_i \right )\leq \alpha+\delta^k, \alpha=\displaystyle\lim_{k\rightarrow \infty}f\left ( y_i \right )=f\left ( \hat{x} \right )$

그러므로, $\hat{x}$ 최소화 솔루션입니다.

비고

Weierstrass 정리에 필요한 두 가지 중요한 조건이 있습니다. 이들은 다음과 같습니다-

  • Step 1 − 집합 S는 경계 집합이어야합니다.

    f \ left (x \ right) = x $ 함수를 고려하십시오.

    무제한 세트이며 도메인의 어느 지점에서나 최소값이 있습니다.

    따라서 최소값을 얻으려면 S를 제한해야합니다.

  • Step 2 − 세트 S를 닫아야합니다.

    \ left (0,1 \ right) 도메인의 $ f \ left (x \ right) = \ frac {1} {x} $ 함수를 고려하십시오.

    이 함수는 주어진 도메인에서 닫히지 않으며 최소값도 존재하지 않습니다.

    따라서 최소값을 얻으려면 S를 닫아야합니다.

S를 $ \ mathbb {R} ^ n에있는 비어 있지 않은 닫힌 볼록 집합이라고합니다.$ and let $y \ notin S$, then $\ 존재$ a point $\ bar {x} \ in S$ with minimum distance from y, i.e.,$\ 왼쪽 \ | y- \ bar {x} \ 오른쪽 \ | \ leq \ 왼쪽 \ | yx \ 오른쪽 \ | \ forall x \ in S. $

또한 $ \ bar {x}$ is a minimizing point if and only if $\ 왼쪽 (y- \ 모자 {x} \ 오른쪽) ^ {T} \ 왼쪽 (x- \ 모자 {x} \ 오른쪽) \ leq 0$ or $\ left (y- \ hat {x}, x- \ hat {x} \ right) \ leq 0 $

증명

가장 가까운 지점의 존재

$ S \ ne \ phi, \ 존재 이후$ a point $\ hat {x} \ in S$ such that the minimum distance of S from y is less than or equal to $\ 왼쪽 \ | y- \ hat {x} \ 오른쪽 \ | $.

$ \ hat {S} = S \ cap \ left \ {x : \ left \ | 정의 yx \ 오른쪽 \ | \ leq \ 왼쪽 \ | y- \ hat {x} \ 오른쪽 \ | \ 오른쪽 \} $

$ \ hat {S} 이후$ is closed and bounded, and since norm is a continuous function, then by Weierstrass theorem, there exists a minimum point $\ hat {x} \ in S$ such that $\ 왼쪽 \ | y- \ hat {x} \ right \ | = Inf \ left \ {\ left \ | yx \ 오른쪽 \ |, x \ in S \ 오른쪽 \} $

고유성

$ \ bar {x} \ in S라고 가정합니다.$ such that $\ 왼쪽 \ | y- \ hat {x} \ 오른쪽 \ | = \ 왼쪽 \ | y- \ hat {x} \ 오른쪽 \ | = \ alpha $

S는 볼록하므로 $ \ frac {\ hat {x} + \ bar {x}} {2} \ in S $

하지만 $ \ left \ | y- \ frac {\ hat {x}-\ bar {x}} {2} \ right \ | \ leq \ frac {1} {2} \ left \ | y- \ hat {x} \ 오른쪽 \ | + \ frac {1} {2} \ 왼쪽 \ | y- \ bar {x} \ 오른쪽 \ | = \ alpha $

$ \ hat {x} $가 y에 가장 가깝기 때문에 완전 부등식 일 수 없습니다.

따라서 $ \ left \ | y- \ hat {x} \ 오른쪽 \ | = \ mu \ 왼쪽 \ | y- \ hat {x} \ 오른쪽 \ |$, for some $\ mu $

이제 $ \ left \ | \ mu \ 오른쪽 \ | = 1.$ If $\ mu = -1$, then $\ left (y- \ hat {x} \ right) =-\ left (y- \ hat {x} \ right) \ Rightarrow y = \ frac {\ hat {x} + \ bar {x}} {2} \ in S $

하지만 $ y \ in S$. Hence contradiction. Thus $\ mu = 1 \ Rightarrow \ hat {x} = \ bar {x} $

따라서 최소화 포인트는 고유합니다.

증명의 두 번째 부분에서 $ \ left (y- \ hat {x} \ right) ^ {\ tau} \ left (x- \ bar {x} \ right) \ leq 0$ for all $x \ in S $

지금,

$ \ 왼쪽 \ | yx \ 오른쪽 \ | ^ {2} = \ 왼쪽 \ | y- \ hat {x} + \ hat {x} -x \ 오른쪽 \ | ^ {2} = \ 왼쪽 \ | y- \ hat {x} \ 오른쪽 \ | ^ {2} + \ 왼쪽 \ | \ hat {x} -x \ 오른쪽 \ | ^ {2} +2 \ 왼쪽 (\ hat {x} -x \ right) ^ {\ tau} \ left (y- \ hat {x} \ right) $

$ \ Rightarrow \ 왼쪽 \ | yx \ 오른쪽 \ | ^ {2} \ geq \ 왼쪽 \ | y- \ hat {x} \ 오른쪽 \ | ^ {2}$ because $\ 왼쪽 \ | \ hat {x} -x \ right \ | ^ {2} \ geq 0$ and $\ left (\ hat {x}-x \ right) ^ {T} \ left (y- \ hat {x} \ right) \ geq 0 $

따라서 $ \ hat {x} $는 포인트를 최소화합니다.

반대로 $ \ hat {x} $가 minimizimg 포인트라고 가정합니다.

$ \ Rightarrow \ 왼쪽 \ | yx \ 오른쪽 \ | ^ {2} \ geq \ 왼쪽 \ | y- \ hat {x} \ 오른쪽 \ | ^ 2 \ forall x \ in S $

S는 볼록 세트이기 때문에.

$ \ Rightarrow \ lambda x + \ left (1- \ lambda \ right) \ hat {x} = \ hat {x} + \ lambda \ left (x- \ hat {x} \ right) \ in S$ for $x \ in S$ and $\ lambda \ in \ left (0,1 \ right) $

이제 $ \ left \ | y- \ hat {x}-\ lambda \ left (x- \ hat {x} \ right) \ right \ | ^ {2} \ geq \ left \ | y- \ hat {x} \ 오른쪽 \ | ^ 2 $

$ \ 왼쪽 \ | y- \ hat {x}-\ lambda \ left (x- \ hat {x} \ right) \ right \ | ^ {2} = \ left \ | y- \ hat {x} \ 오른쪽 \ | ^ {2} + \ lambda ^ 2 \ 왼쪽 \ | x- \ hat {x} \ 오른쪽 \ | ^ {2} -2 \ lambda \ left (y- \ hat {x} \ right) ^ {T} \ left (x- \ hat {x} \ right) $

$ \ Rightarrow \ 왼쪽 \ | y- \ hat {x} \ 오른쪽 \ | ^ {2} + \ lambda ^ {2} \ 왼쪽 \ | x- \ hat {x} \ 오른쪽 \ | -2 \ lambda \ left (y- \ hat {x} \ right) ^ {T} \ left (x- \ hat {x} \ right) \ geq \ left \ | y- \ hat {x} \ 오른쪽 \ | ^ {2} $

$ \ Rightarrow 2 \ lambda \ left (y- \ hat {x} \ right) ^ {T} \ left (x- \ hat {x} \ right) \ leq \ lambda ^ 2 \ left \ | x- \ hat {x} \ 오른쪽 \ | ^ 2 $

$ \ Rightarrow \ left (y- \ hat {x} \ right) ^ {T} \ left (x- \ hat {x} \ right) \ leq 0 $

따라서 입증되었습니다.

S를 $ \ mathbb {R} ^ n에 설정된 비어 있지 않은 닫힌 볼록이라고합시다.$ and $y \ notin S$. Then, there exists a non zero vector $피$ and scalar $\베타$ such that $p ^ T y> \ beta$ and $p ^ T x <\ beta$ for each $x \ in S $

증명

S는 비어 있지 않은 닫힌 볼록 세트이고 $ y \ notin S이기 때문에$ thus by closest point theorem, there exists a unique minimizing point $\ hat {x} \ in S $에서

$ \ left (x- \ hat {x} \ right) ^ T \ left (y- \ hat {x} \ right) \ leq 0 \ forall x \ in S $

$ p = \ left (y- \ hat {x} \ right) \ neq 0$ and $\ beta = \ hat {x} ^ T \ left (y- \ hat {x} \ right) = p ^ T \ hat {x} $.

그런 다음 $ \ left (x- \ hat {x} \ right) ^ T \ left (y- \ hat {x} \ right) \ leq 0 $

$ \ Rightarrow \ left (y- \ hat {x} \ right) ^ T \ left (x- \ hat {x} \ right) \ leq 0 $

$ \ Rightarrow \ left (y- \ hat {x} \ right) ^ Tx \ leq \ left (y- \ hat {x} \ right) ^ T \ hat {x} = \ hat {x} ^ T \ left (y- \ hat {x} \ 오른쪽)$ i,e., $p ^ Tx \ leq \ beta $

또한 $ p ^ Ty- \ beta = \ left (y- \ hat {x} \ right) ^ Ty- \ hat {x} ^ T \ left (y- \ hat {x} \ right) $

$ = \ left (y- \ hat {x} \ right) ^ T \ left (yx \ right) = \ left \ | y- \ hat {x} \ 오른쪽 \ | ^ {2}> 0 $

$ \ Rightarrow p ^ Ty> \ beta $

이 정리는 초평면을 분리합니다. 위의 정리에 기반한 초평면은 다음과 같이 정의 할 수 있습니다.

$ S_1하자$ and $S_2$ are be non-empty subsets of $\ mathbb {R}$ and $H = \ left \ {X : A ^ TX = b \ right \} $는 초평면입니다.

  • 초평면 H는 $ S_1을 분리한다고합니다.$ and $S_2$ if $A ^ TX \ leq b \ forall X \ in S_1$ and $A_TX \ geq b \ forall X \ in S_2 $

  • 초평면 H는 $ S_1을 엄격하게 분리한다고합니다.$ and $S_2$ if $A ^ TX <b \ forall X \ in S_1$ and $A_TX> b \ forall X \ in S_2 $

  • 초평면 H는 $ S_1을 강력하게 분리한다고합니다.$ and $S_2$ if $A ^ TX \ leq b \ forall X \ in S_1$ and $A_TX \ geq b + \ varepsilon \ forall X \ in S_2$, where $\ varepsilon $은 양의 스칼라입니다.

$ \ mathbb {R} ^ n의 비어 있지 않은 집합 C$ is said to be cone with vertex 0 if $x \ in C \ Rightarrow \ lambda x \ in C \ forall \ lambda \ geq 0 $.

세트 C는 원뿔과 마찬가지로 볼록한 경우 볼록 원뿔입니다.

예를 들어, $ y = \ left | x \ right | $는 볼록하지 않기 때문에 볼록한 원뿔이 아닙니다.

하지만 $ y \ geq \ left | x \ right | $는 볼록하고 원뿔이기 때문에 볼록 원뿔입니다.

Note − 원뿔 C는 $ x, y \ in C, x + y \ in C $ 인 경우에만 볼록합니다.

증명

C는 원뿔이므로 $ x, y \ in C \ Rightarrow \ lambda x \ in C$ and $\ mu y \ in C \ : \ forall \ : \ lambda, \ mu \ geq 0 $

$ \ lambda x + \ left (1- \ lambda \ right) y \ in C \ : \ forall \ : \ lambda \ in \ left (0, 1 \ right) $이면 C는 볼록입니다.

C는 원뿔이므로 $ \ lambda x \ in C$ and $\ left (1- \ lambda \ right) y \ in C \ Leftrightarrow x, y \ in C $

따라서 C는 $ x + y \ in C $이면 볼록합니다.

일반적으로 $ x_1, x_2 \ in C$, then, $\ lambda_1x_1 + \ lambda_2x_2 \ in C, \ forall \ lambda_1, \ lambda_2 \ geq 0 $

  • $ \ mathbb {R} ^ n $에있는 무한 벡터 집합의 원뿔 조합은 볼록 원뿔입니다.

  • 빈 세트는 볼록 원뿔입니다.

  • 모든 선형 함수는 볼록 원뿔입니다.

  • 초평면은 선형이므로 볼록한 원뿔이기도합니다.

  • 닫힌 절반 공간도 볼록한 원뿔입니다.

Note − 두 볼록 원뿔의 교차점은 볼록 원뿔이지만 그 결합은 볼록 원뿔 일 수도 있고 아닐 수도 있습니다.

$ \ mathbb {R} ^ n에서 S를 비어 있지 않은 집합으로 지정합니다.$ Then, the polar cone of S denoted by $S ^ *$ is given by $S ^ * = \ left \ {p \ in \ mathbb {R} ^ n, p ^ Tx \ leq 0 \ : \ forall x \ in S \ right \} $.

  • S가 볼록하지 않더라도 폴라 콘은 항상 볼록합니다.

  • S가 빈 집합이면 $ S ^ * = \ mathbb {R} ^ n $.

  • 극성은 직교성의 일반화로 볼 수 있습니다.

$ C \ subseteq \ mathbb {R} ^ n$ then the orthogonal space of C, denoted by $C ^ \ perp = \ left \ {y \ in \ mathbb {R} ^ n : \ left \ langle x, y \ right \ rangle = 0 \ forall x \ in C \ right \} $.

정리

$ S, S_1하자$ and $S_2$ be non empty sets in $\ mathbb {R} ^ n $ 다음 문장이 참입니다-

  • $ S ^ * $는 닫힌 볼록 원뿔입니다.

  • $ S \ subseteq S ^ {**}$ where $S ^ {**}$ is a polar cone of $S ^ * $.

  • $ S_1 \ subseteq S_2 \ Rightarrow S_ {2} ^ {*} \ subseteq S_ {1} ^ {*} $.

증명

Step 1 − $ S ^ * = \ left \ {p \ in \ mathbb {R} ^ n, p ^ Tx \ leq 0 \ : \ forall \ : x \ in S \ right \} $

  • $ x_1, x_2 \ in S ^ * \ Rightarrow x_ {1} ^ {T} x \ leq 0 $ and $x_ {2} ^ {T} x \ leq 0, \ forall x \ in S $

    $ \ lambda \ in \ left (0, 1 \ right), \ left [\ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ right] ^ Tx = \ left [\ left (\ lambda x_1 \ right ) ^ T + \ left \ {\ left (1- \ lambda \ right) x_ {2} \ right \} ^ {T} \ right] x, \ forall x \ in S $

    $ = \ left [\ lambda x_ {1} ^ {T} + \ left (1- \ lambda \ right) x_ {2} ^ {T} \ right] x = \ lambda x_ {1} ^ {T} x + \ left (1- \ lambda \ right) x_ {2} ^ {T} \ leq 0 $

    따라서 $ \ lambda x_1 + \ left (1- \ lambda \ right) x_ {2} \ in S ^ * $

    따라서 $ S ^ * $는 볼록한 집합입니다.

  • $ \ lambda \ geq 0, p ^ {T} x \ leq 0, \ forall \ : x \ in S $

    따라서 $ \ lambda p ^ T x \ leq 0, $

    $ \ Rightarrow \ left (\ lambda p \ right) ^ T x \ leq 0 $

    $ \ Rightarrow \ lambda p \ in S ^ * $

    따라서 $ S ^ * $는 원뿔입니다.

  • $ S ^ * 표시$ is closed, i.e., to show if $p_n \ rightarrow p$ as $n \ rightarrow \ infty$, then $p \ in S ^ * $

    $ \ forall x \ in S, p_ {n} ^ {T} xp ^ T x = \ left (p_n-p \ right) ^ T x $

    $ p_n \ rightarrow p로$ as $n \ rightarrow \ infty \ Rightarrow \ left (p_n \ rightarrow p \ right) \ rightarrow 0 $

    따라서 $ p_ {n} ^ {T} x \ rightarrow p ^ {T} x$. But $p_ {n} ^ {T} x \ leq 0, \ : \ forall x \ in S $

    따라서 $ p ^ Tx \ leq 0, \ forall x \ in S $

    $ \ Rightarrow p \ in S ^ * $

    따라서 $ S ^ * $가 닫힙니다.

Step 2 − $ S ^ {**} = \ left \ {q \ in \ mathbb {R} ^ n : q ^ T p \ leq 0, \ forall p \ in S ^ * \ right \} $

$ x \ in S$, then $ \ forall p \ in S ^ *, p ^ T x \ leq 0 \ Rightarrow x ^ Tp \ leq 0 \ Rightarrow x \ in S ^ {**} $

따라서 $ S \ subseteq S ^ {**} $

Step 3 − $ S_2 ^ * = \ left \ {p \ in \ mathbb {R} ^ n : p ^ Tx \ leq 0, \ forall x \ in S_2 \ right \} $

$ S_1 \ subseteq S_2 \ Rightarrow \ forall x \ in S_2 \ Rightarrow \ forall x \ in S_1 $부터

따라서 $ \ hat {p} \ in S_2 ^ *, $then $\ hat {p} ^ Tx \ leq 0, \ forall x \ in S_2 $

$ \ Rightarrow \ hat {p} ^ Tx \ leq 0, \ forall x \ in S_1 $

$ \ Rightarrow \ hat {p} ^ T \ in S_1 ^ * $

$ \ Rightarrow S_2 ^ * \ subseteq S_1 ^ * $

정리

C를 비어 있지 않은 닫힌 볼록 원뿔로하고 $ C = C ^ ** $

증명

$ C = C ^ {**} $ by 이전 기본형.

증명하려면 : $ x \ in C ^ {**} \ subseteq C $

$ x \ in C ^ {**}$ and let $x \ notin C $

그런 다음 기본 분리 정리에 의해 벡터 $ p \ neq 0이 있습니다.$ and a scalar $\ alpha$ such that $p ^ Ty \ leq \ alpha, \ forall y \ in C $

따라서 $ p ^ Tx> \ alpha $

하지만 $ \ left (y = 0 \ right) \ in C$ and $p ^ Ty \ leq \ alpha, \ forall y \ in C \ Rightarrow \ alpha \ geq 0$ and $p ^ Tx> 0 $

$ p \ notin C ^ *$, then there exists some $\ bar {y} \ in C$ such that $p ^ T \ bar {y}> 0$ and $p ^ T \ left (\ lambda \ bar {y} \ right)$ can be made arbitrarily large by taking $\ lambda $ 충분히 큽니다.

이것은 $ p ^ Ty \ leq \ alpha, \ forall y \ in C $라는 사실과 모순됩니다.

따라서 $ p \ in C ^ * $

$ x \ in C ^ * = \ left \ {q : q ^ Tp \ leq 0, \ forall p \ in C ^ * \ right \} $ 이후

따라서 $ x ^ Tp \ leq 0 \ Rightarrow p ^ Tx \ leq 0 $

하지만 $ p ^ Tx> \ alpha $

따라서 모순입니다.

따라서 $ x \ in C $

따라서 $ C = C ^ {**} $.

$ \ alpha_1x_1 + \ alpha_2x_2 + .... + \ alpha_nx_n 형식의 포인트$ with $\ alpha_1, \ alpha_2, ..., \ alpha_n \ geq 0$ is called conic combination of $x_1, x_2, ..., x_n. $

  • $ x_i 인 경우$ are in convex cone C, then every conic combination of $x_i $도 C에 있습니다.

  • 집합 C는 요소의 모든 원추 조합을 포함하는 경우 볼록 원뿔입니다.

원추형 선체

원추형 선체는 주어진 세트 S의 모든 원추형 조합의 세트로 정의되며 coni (S)로 표시됩니다.

따라서 $ coni \ left (S \ right) = \ left \ {\ displaystyle \ sum \ limits_ {i = 1} ^ k \ lambda_ix_i : x_i \ in S, \ lambda_i \ in \ mathbb {R}, \ lambda_i \ geq 0, i = 1,2, ... \ 오른쪽 \} $

  • 원추형 선체는 볼록한 집합입니다.
  • 원점은 항상 원추형 선체에 속합니다.

$ \ mathbb {R} ^ n $에있는 집합은 제한된 수의 닫힌 반 공간의 교차점 인 경우 다면체라고합니다.

$ S = \ left \ {x \ in \ mathbb {R} ^ n : p_ {i} ^ {T} x \ leq \ alpha_i, i = 1,2, ...., n \ right \} $

예를 들면

  • $ \ 왼쪽 \ {x \ in \ mathbb {R} ^ n : AX = b \ 오른쪽 \} $

  • $ \ 왼쪽 \ {x \ in \ mathbb {R} ^ n : AX \ leq b \ 오른쪽 \} $

  • $ \ 왼쪽 \ {x \ in \ mathbb {R} ^ n : AX \ geq b \ 오른쪽 \} $

다면체 원뿔

$ \ mathbb {R} ^ n의 집합$ is said to be polyhedral cone if it is the intersection of a finite number of half spaces that contain the origin, i.e., $S = \ left \ {x \ in \ mathbb {R} ^ n : p_ {i} ^ {T} x \ leq 0, i = 1, 2, ... \ right \} $

폴리 토프

다면체는 경계가있는 다면체 집합입니다.

비고

  • 폴리 토프는 유한 한 점 집합의 볼록 껍질입니다.
  • 다면체 원뿔은 유한 벡터 집합에 의해 생성됩니다.
  • 다면체 집합은 닫힌 집합입니다.
  • 다면체 집합은 볼록 집합입니다.

S를 $ \ mathbb {R} ^ n에있는 볼록 집합이라고합시다.$. A vector $x \ in S$ is said to be a extreme point of S if $x = \ lambda x_1 + \ left (1- \ lambda \ right) x_2$ with $x_1, x_2 \ in S$ and $\ lambda \ in \ left (0, 1 \ right) \ Rightarrow x = x_1 = x_2 $.

Step 1 − $ S = \ left \ {\ left (x_1, x_2 \ right) \ in \ mathbb {R} ^ 2 : x_ {1} ^ {2} + x_ {2} ^ {2} \ leq 1 \ right \ } $

극단 점, $ E = \ left \ {\ left (x_1, x_2 \ right) \ in \ mathbb {R} ^ 2 : x_ {1} ^ {2} + x_ {2} ^ {2} = 1 \ right \} $

Step 2 − $ S = \ left \ {\ left (x_1, x_2 \ right) \ in \ mathbb {R} ^ 2 : x_1 + x_2 <2, -x_1 + 2x_2 \ leq 2, x_1, x_2 \ geq 0 \ right \ } $

극단 점, $ E = \ left \ {\ left (0, 0 \ right), \ left (2, 0 \ right), \ left (0, 1 \ right), \ left (\ frac {2} {3 }, \ frac {4} {3} \ right) \ right \} $

Step 3 − S는 점 $ \ left \ {\ left (0,0 \ right), \ left (1,1 \ right), \ left (1,3 \ right), \ left (-2, 4 \ 오른쪽), \ 왼쪽 (0,2 \ 오른쪽) \ 오른쪽 \} $

극단 점, $ E = \ left \ {\ left (0,0 \ right), \ left (1,1 \ right), \ left (1,3 \ right), \ left (-2,4 \ right) \ 오른쪽 \} $

비고

  • 볼록 세트 S의 모든 지점은 극단 지점의 볼록 조합으로 나타낼 수 있습니다.

  • $ \ mathbb {R} ^ n $의 폐쇄 및 경계 세트에만 해당됩니다.

  • 무제한 세트의 경우에는 해당되지 않을 수 있습니다.

k 극점

볼록 집합의 한 점은 S 내에있는 k 차원 볼록 집합의 내부 점이고 S 내에있는 (k + 1) 차원 볼록 집합의 내부 점이 아닌 경우에만 k 극단이라고합니다. 기본적으로 볼록 세트 S의 경우 k 개의 극점은 k 차원의 열린면을 만듭니다.

S를 $ \ mathbb {R} ^ n에있는 닫힌 볼록 집합이라고합니다.$. A non zero vector $d \ in \ mathbb {R} ^ n$ is called a direction of S if for each $x \ in S, x + \ lambda d \ in S, \ forall \ lambda \ geq 0. $

  • 양방향 $ d_1$ and $d_2$ of S are called distinct if $d \ neq \ alpha d_2$ for $ \ alpha> 0 $.

  • 방향 $ d$ of $에스$ is said to be extreme direction if it cannot be written as a positive linear combination of two distinct directions, i.e., if $d = \ lambda _1d_1 + \ lambda _2d_2$ for $\ lambda _1, \ lambda _2> 0$, then $d_1 = \ alpha d_2$ for some $\ alpha $.

  • 다른 방향은 극단 방향의 양의 조합으로 표현할 수 있습니다.

  • 볼록 세트 $ S의 경우$, the direction d such that $x + \ lambda d \ in S$ for some $x \ in S$ and all $\ lambda \ geq0 $이 호출됩니다. recessive $ S $.

  • E를 특정 함수 $ f : S \ rightarrow$ over a non-empty convex set S in $\ mathbb {R} ^ n$ attains its maximum, then $이자형$ is called exposed face of $S $. 노출 된면의 방향을 노출 된 방향이라고합니다.

  • 방향이 극단 인 광선을 극단 광선이라고합니다.

$ f \ left (x \ right) = y = \ left | x \ right |$, where $x \ in \ mathbb {R} ^ n$. Let d be unit vector in $\ mathbb {R} ^ n $

그러면 d는 모든 $ \ lambda \ geq 0, x + \ lambda d \ in f \ left (x \ right) $에 대해 함수 f의 방향입니다.

$ f : S \ rightarrow \ mathbb {R}$, where S is non empty convex set in $\ mathbb {R} ^ n$, then $f \ 왼쪽 (x \ 오른쪽)$ is said to be convex on S if $f \ left (\ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ right) \ leq \ lambda f \ left (x_1 \ right) + \ left (1- \ lambda \ right) f \ left (x_2 \ 오른쪽), \ forall \ lambda \ in \ left (0,1 \ right) $.

반면에 $ f : S \ rightarrow \ mathbb {R}$, where S is non empty convex set in $\ mathbb {R} ^ n$, then $f \ 왼쪽 (x \ 오른쪽)$ is said to be concave on S if $f \ left (\ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ right) \ geq \ lambda f \ left (x_1 \ right) + \ left (1- \ lambda \ right) f \ left (x_2 \ 오른쪽), \ forall \ lambda \ in \ left (0, 1 \ right) $.

$ f : S \ rightarrow \ mathbb {R}$ where S is non empty convex set in $\ mathbb {R} ^ n$, then $f \ 왼쪽 (x \ 오른쪽)$ is said to be strictly convex on S if $f \ left (\ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ right) <\ lambda f \ left (x_1 \ right) + \ left (1- \ lambda \ right) f \ left (x_2 \ right ), \ forall \ lambda \ in \ left (0, 1 \ right) $.

$ f : S \ rightarrow \ mathbb {R}$ where S is non empty convex set in $\ mathbb {R} ^ n$, then $f \ 왼쪽 (x \ 오른쪽)$ is said to be strictly concave on S if $f \ left (\ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ right)> \ lambda f \ left (x_1 \ right) + \ left (1- \ lambda \ right) f \ left (x_2 \ right ), \ forall \ lambda \ in \ left (0, 1 \ right) $.

  • 선형 함수는 볼록하고 오목합니다.

  • $ f \ 왼쪽 (x \ 오른쪽) = \ 왼쪽 | x \ right | $는 볼록 함수입니다.

  • $ f \ left (x \ right) = \ frac {1} {x} $는 볼록 함수입니다.

정리

$ f_1, f_2, ..., f_k : \ mathbb {R} ^ n \ rightarrow \ mathbb {R}$ be convex functions. Consider the function $f \ left (x \ right) = \ displaystyle \ sum \ limits_ {j = 1} ^ k \ alpha_jf_j \ left (x \ right)$ where $\ alpha_j> 0, j = 1, 2, ... k,$ then $f \ left (x \ right) $는 볼록 함수입니다.

증명

$ f_1, f_2, ... f_k $는 볼록 함수이므로

따라서 $ f_i \ left (\ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ right) \ leq \ lambda f_i \ left (x_1 \ right) + \ left (1- \ lambda \ right) f_i \ left (x_2 \ right), \ forall \ lambda \ in \ left (0, 1 \ right)$ and $i = 1, 2, ...., k $

$ f \ left (x \ right) $ 함수를 고려하십시오.

따라서,

$ f \ 왼쪽 (\ lambda x_1 + \ 왼쪽 (1- \ lambda \ 오른쪽) x_2 \ 오른쪽) $

$ = \ displaystyle \ sum \ limits_ {j = 1} ^ k \ alpha_jf_j \ left (\ lambda x_1 + 1- \ lambda \ right) x_2 \ leq \ displaystyle \ sum \ limits_ {j = 1} ^ k \ alpha_j \ 람다 f_j \ left (x_1 \ right) + \ left (1- \ lambda \ right) f_j \ left (x_2 \ right) $

$ \ Rightarrow f \ left (\ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ right) \ leq \ lambda \ left (\ displaystyle \ sum \ limits_ {j = 1} ^ k \ alpha _jf_j \ left ( x_1 \ right) \ right) + \ left (\ displaystyle \ sum \ limits_ {j = 1} ^ k \ alpha _jf_j \ left (x_2 \ right) \ right) $

$ \ 오른쪽 화살표 f \ left (\ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ right) \ leq \ lambda f \ left (x_2 \ right) \ leq \ left (1- \ lambda \ right) f \ 왼쪽 (x_2 \ 오른쪽) $

따라서 $ f \ left (x \ right) $는 볼록 함수입니다.

정리

$ f \ left (x \ right)하자$ be a convex function on a convex set $S \ subset \ mathbb {R} ^ n$ then a local minima of $S의 f \ left (x \ right) $는 전역 최소값입니다.

증명

$ \ hat {x}하자$ be a local minima for $f \ 왼쪽 (x \ 오른쪽)$ and $\ hat {x} $은 전역 최소값이 아닙니다.

따라서 $ \ exists \ hat {x} \ in S$ such that $f \ 왼쪽 (\ bar {x} \ 오른쪽) <f \ 왼쪽 (\ hat {x} \ 오른쪽) $

$ \ hat {x} 이후$ is a local minima, there exists neighbourhood $N_ \ varepsilon \ left (\ hat {x} \ right)$ such that $f \ left (\ hat {x} \ right) \ leq f \ left (x \ right), \ forall x \ in N_ \ varepsilon \ left (\ hat {x} \ right) \ cap S $

But $f\left ( x \right )$ is a convex function on S, therefore for $\lambda \in \left ( 0, 1 \right )$

we have $\lambda \hat{x}+\left ( 1-\lambda \right )\bar{x}\leq \lambda f\left ( \hat{x} \right )+\left ( 1-\lambda \right )f\left ( \bar{x} \right )$

$\Rightarrow \lambda \hat{x}+\left ( 1-\lambda \right )\bar{x}< \lambda f\left ( \hat{x} \right )+\left ( 1-\lambda \right )f\left (\hat{x} \right )$

$\Rightarrow \lambda \hat{x}+\left ( 1-\lambda \right )\bar{x}< f\left (\hat{x} \right ), \forall \lambda \in \left ( 0,1 \right )$

But for some $\lambda<1$ but close to 1, we have

$\lambda \hat{x}+\left ( 1-\lambda \right )\bar{x} \in N_\varepsilon \left ( \hat{x} \right )\cap S$ and $f\left ( \lambda \hat{x}+\left ( 1-\lambda \right )\bar{x} \right )< f\left ( \bar{x} \right )$

which is a contradiction.

Hence, $\bar{x}$ is a global minima.

Epigraph

let S be a non-empty subset in $\mathbb{R}^n$ and let $f:S \rightarrow \mathbb{R}$ then the epigraph of f denoted by epi(f) or $E_f$ is a subset of $\mathbb{R}^n+1$ defined by $E_f=\left \{ \left ( x,\alpha \right ):x \in \mathbb{R}^n, \alpha \in \mathbb{R}, f\left ( x \right )\leq \alpha \right \}$

Hypograph

let S be a non-empty subset in $\mathbb{R}^n$ and let $f:S \rightarrow \mathbb{R}$, then the hypograph of f denoted by hyp(f) or $H_f=\left \{ \left ( x, \alpha \right ):x \in \mathbb{R}^n, \alpha \in \mathbb{R}^n, \alpha \in \mathbb{R}, f\left ( x \right )\geq \alpha \right \}$

Theorem

Let S be a non-empty convex set in $\mathbb{R}^n$ and let $f:S \rightarrow \mathbb{R}^n$, then f is convex if and only if its epigraph $E_f$ is a convex set.

Proof

Let f is a convex function.

To show $E_f$ is a convex set.

Let $\left ( x_1, \alpha_1 \right ),\left ( x_2, \alpha_2 \right ) \in E_f,\lambda \in\left ( 0, 1 \right )$

To show $\lambda \left ( x_1,\alpha_1 \right )+\left ( 1-\lambda \right )\left ( x_2, \alpha_2 \right ) \in E_f$

$\Rightarrow \left [ \lambda x_1+\left ( 1-\lambda \right )x_2, \lambda \alpha_1+\left ( 1-\lambda \right )\alpha_2 \right ]\in E_f$

$f\left ( x_1 \right )\leq \alpha _1, f\left ( x_2\right )\leq \alpha _2$

Therefore, $f\left (\lambda x_1+\left ( 1-\lambda \right )x_2 \right )\leq \lambda f\left ( x_1 \right )+\left ( 1-\lambda \right )f \left ( x_2 \right )$

$\Rightarrow f\left ( \lambda x_1+\left ( 1-\lambda \right )x_2 \right )\leq \lambda \alpha_1+\left ( 1-\lambda \right )\alpha_2$

Converse

Let $E_f$ is a convex set.

To show f is convex.

i.e., to show if $x_1, x_2 \in S,\lambda \left ( 0, 1\right )$

$f\left ( \lambda x_1+\left ( 1-\lambda \right )x_2 \right )\leq \lambda f\left ( x_1 \right )+\left ( 1-\lambda \right )f\left ( x_2 \right )$

Let $x_1,x_2 \in S, \lambda \in \left ( 0, 1 \right ),f\left ( x_1 \right ), f\left ( x_2 \right ) \in \mathbb{R}$

Since $E_f$ is a convex set, $\left ( \lambda x_1+\left ( 1-\lambda \right )x_2, \lambda f\left ( x_1 \right )+\left ( 1-\lambda \right )\right )f\left ( x_2 \right )\in E_f$

Therefore, $f\left ( \lambda x_1+\left ( 1-\lambda \right )x_2 \right )\leq \lambda f\left ( x_1 \right )+\left ( 1-\lambda \right )f\left ( x_2 \right )$

Let S be a non-empty convex set in $\mathbb{R}^n$ and $f:S \rightarrow \mathbb{R}^n$. Then f is convex if and only if for each integer $k>0$

$x_1,x_2,...x_k \in S, \displaystyle\sum\limits_{i=1}^k \lambda_i=1, \lambda_i\geq 0, \forall i=1,2,s,k$, we have $f\left ( \displaystyle\sum\limits_{i=1}^k \lambda_ix_i \right )\leq \displaystyle\sum\limits_{i=1}^k \lambda _if\left ( x \right )$

Proof

By induction on k.

$k=1:x_1 \in S$ Therefore $f\left ( \lambda_1 x_1\right ) \leq \lambda_i f\left (x_1\right )$ because $\lambda_i=1$.

$k=2:\lambda_1+\lambda_2=1$ and $x_1, x_2 \in S$

Therefore, $\lambda_1x_1+\lambda_2x_2 \in S$

Hence by definition, $f\left ( \lambda_1 x_1 +\lambda_2 x_2 \right )\leq \lambda _1f\left ( x_1 \right )+\lambda _2f\left ( x_2 \right )$

Let the statement is true for $n < k$

Therefore,

$f\left ( \lambda_1 x_1+ \lambda_2 x_2+....+\lambda_k x_k\right )\leq \lambda_1 f\left (x_1 \right )+\lambda_2 f\left (x_2 \right )+...+\lambda_k f\left (x_k \right )$

$k=n+1:$ Let $x_1, x_2,....x_n,x_{n+1} \in S$ and $\displaystyle\sum\limits_{i=1}^{n+1}=1$

Therefore $\mu_1x_1+\mu_2x_2+.......+\mu_nx_n+\mu_{n+1} x_{n+1} \in S$

thus,$f\left (\mu_1x_1+\mu_2x_2+...+\mu_nx_n+\mu_{n+1} x_{n+1} \right )$

$=f\left ( \left ( \mu_1+\mu_2+...+\mu_n \right)\frac{\mu_1x_1+\mu_2x_2+...+\mu_nx_n}{\mu_1+\mu_2+\mu_3}+\mu_{n+1}x_{n+1} \right)$

$=f\left ( \mu_y+\mu_{n+1}x_{n+1} \right )$ where $\mu=\mu_1+\mu_2+...+\mu_n$ and

$y=\frac{\mu_1x_1+\mu_2x_2+...+\mu_nx_n}{\mu_1+\mu_2+...+\mu_n}$ and also $\mu_1+\mu_{n+1}=1,y \in S$

$\Rightarrow f\left ( \mu_1x_1+\mu_2x_2+...+\mu_nx_n+\mu_{n+1}x_{n+1}\right ) \leq \mu f\left ( y \right )+\mu_{n+1} f\left ( x_{n+1} \right )$

$\Rightarrow f\left ( \mu_1x_1+\mu_2x_2+...+\mu_nx_n+\mu_{n+1}x_{n+1}\right ) \leq$

$\left ( \mu_1+\mu_2+...+\mu_n \right )f\left ( \frac{\mu_1x_1+\mu_2x_2+...+\mu_nx_n}{\mu_1+\mu_2+...+\mu_n} \right )+\mu_{n+1}f\left ( x_{n+1} \right )$

$\Rightarrow f\left ( \mu_1x_1+\mu_2x_2+...+\mu_nx_n +\mu_{n+1}x_{n+1}\right )\leq \left ( \mu_1+ \mu_2+ ...+\mu_n \right )$

$\left [ \frac{\mu_1}{\mu_1+ \mu_2+ ...+\mu_n}f\left ( x_1 \right )+...+\frac{\mu_n}{\mu_1+ \mu_2+ ...+\mu_n}f\left ( x_n \right ) \right ]+\mu_{n+1}f\left ( x_{n+1} \right )$

$\Rightarrow f\left ( \mu_1x_1+\mu_2x_2+...+\mu_nx_n+\mu_{n+1}x_{n+1}\right )\leq \mu_1f\left ( x_1 \right )+\mu_2f\left ( x_2 \right )+....$

Hence Proved.

Let S be a non-empty open set in $\mathbb{R}^n$,then $f:S\rightarrow \mathbb{R}$ is said to be differentiable at $\hat{x} \in S$ if there exist a vector $\bigtriangledown f\left ( \hat{x} \right )$ called gradient vector and a function $\alpha :\mathbb{R}^n\rightarrow \mathbb{R}$ such that

$f\left ( x \right )=f\left ( \hat{x} \right )+\bigtriangledown f\left ( \hat{x} \right )^T\left ( x-\hat{x} \right )+\left \| x=\hat{x} \right \|\alpha \left ( \hat{x}, x-\hat{x} \right ), \forall x \in S$ where

$\alpha \left (\hat{x}, x-\hat{x} \right )\rightarrow 0 \bigtriangledown f\left ( \hat{x} \right )=\left [ \frac{\partial f}{\partial x_1}\frac{\partial f}{\partial x_2}...\frac{\partial f}{\partial x_n} \right ]_{x=\hat{x}}^{T}$

Theorem

let S be a non-empty, open convexset in $\mathbb{R}^n$ and let $f:S\rightarrow \mathbb{R}$ be differentiable on S. Then, f is convex if and only if for $x_1,x_2 \in S, \bigtriangledown f\left ( x_2 \right )^T \left ( x_1-x_2 \right ) \leq f\left ( x_1 \right )-f\left ( x_2 \right )$

Proof

Let f be a convex function. i.e., for $x_1,x_2 \in S, \lambda \in \left ( 0, 1 \right )$

$f\left [ \lambda x_1+\left ( 1-\lambda \right )x_2 \right ]\leq \lambda f\left ( x_1 \right )+\left ( 1-\lambda \right )f\left ( x_2 \right )$

$ \Rightarrow f\left [ \lambda x_1+\left ( 1-\lambda \right )x_2 \right ]\leq \lambda \left ( f\left ( x_1 \right )-f\left ( x_2 \right ) \right )+f\left ( x_2 \right )$

$ \Rightarrow\lambda \left ( f\left ( x_1 \right )-f\left ( x_2 \right ) \right )\geq f\left ( x_2+\lambda \left ( x_1-x_2 \right ) \right )-f\left ( x_2 \right )$

$\Rightarrow \lambda \left ( f\left ( x_1 \right )-f\left ( x_2 \right ) \right )\geq f\left ( x_2 \right )+\bigtriangledown f\left ( x_2 \right )^T\left ( x_1-x_2 \right )\lambda +$

$\left \| \lambda \left ( x_1-x_2 \right ) \right \|\alpha \left ( x_2,\lambda\left (x_1 - x_2 \right )-f\left ( x_2 \right ) \right )$

where $\alpha\left ( x_2, \lambda\left (x_1 - x_2 \right ) \right )\rightarrow 0$ as$\lambda \rightarrow 0$

Dividing by $\lambda$ on both sides, we get −

$f\left ( x_1 \right )-f\left ( x_2 \right ) \geq \bigtriangledown f\left ( x_2 \right )^T \left ( x_1-x_2 \right )$

Converse

Let for $x_1,x_2 \in S, \bigtriangledown f\left ( x_2 \right )^T \left ( x_1-x_2 \right ) \leq f\left ( x_1 \right )-f \left ( x_2 \right )$

To show that f is convex.

Since S is convex, $x_3=\lambda x_1+\left (1-\lambda \right )x_2 \in S, \lambda \in \left ( 0, 1 \right )$

Since $x_1, x_3 \in S$, therefore

$f\left ( x_1 \right )-f \left ( x_3 \right ) \geq \bigtriangledown f\left ( x_3 \right )^T \left ( x_1 -x_3\right )$

$ \Rightarrow f\left ( x_1 \right )-f \left ( x_3 \right )\geq \bigtriangledown f\left ( x_3 \right )^T \left ( x_1 - \lambda x_1-\left (1-\lambda \right )x_2\right )$

$ \Rightarrow f\left ( x_1 \right )-f \left ( x_3 \right )\geq \left ( 1- \lambda\right )\bigtriangledown f\left ( x_3 \right )^T \left ( x_1 - x_2\right )$

Since, $x_2, x_3 \in S$ therefore

$f\left ( x_2 \right )-f\left ( x_3 \right )\geq \bigtriangledown f\left ( x_3 \right )^T\left ( x_2-x_3 \right )$

$\Rightarrow f\left ( x_2 \right )-f\left ( x_3 \right )\geq \bigtriangledown f\left ( x_3 \right )^T\left ( x_2-\lambda x_1-\left ( 1-\lambda \right )x_2 \right )$

$\Rightarrow f\left ( x_2 \right )-f\left ( x_3 \right )\geq \left ( -\lambda \right )\bigtriangledown f\left ( x_3 \right )^T\left ( x_1-x_2 \right )$

Thus, combining the above equations, we get −

$\lambda \left ( f\left ( x_1 \right )-f\left ( x_3 \right ) \right )+\left ( 1- \lambda \right )\left ( f\left ( x_2 \right )-f\left ( x_3 \right ) \right )\geq 0$

$\Rightarrow f\left ( x_3\right )\leq \lambda f\left ( x_1 \right )+\left ( 1-\lambda \right )f\left ( x_2 \right )$

Theorem

let S be a non-empty open convex set in $\mathbb{R}^n$ and let $f:S \rightarrow \mathbb{R}$ be differentiable on S, then f is convex on S if and only if for any $x_1,x_2 \in S,\left ( \bigtriangledown f \left ( x_2 \right )-\bigtriangledown f \left ( x_1 \right ) \right )^T \left ( x_2-x_1 \right ) \geq 0$

Proof

let f be a convex function, then using the previous theorem −

$\bigtriangledown f\left ( x_2 \right )^T\left ( x_1-x_2 \right )\leq f\left ( x_1 \right )-f\left ( x_2 \right )$ and

$\bigtriangledown f\left ( x_1 \right )^T\left ( x_2-x_1 \right )\leq f\left ( x_2 \right )-f\left ( x_1 \right )$

Adding the above two equations, we get −

$\bigtriangledown f\left ( x_2 \right )^T\left ( x_1-x_2 \right )+\bigtriangledown f\left ( x_1 \right )^T\left ( x_2-x_1 \right )\leq 0$

$\Rightarrow \left ( \bigtriangledown f\left ( x_2 \right )-\bigtriangledown f\left ( x_1 \right ) \right )^T\left ( x_1-x_2 \right )\leq 0$

$\Rightarrow \left ( \bigtriangledown f\left ( x_2 \right )-\bigtriangledown f\left ( x_1 \right ) \right )^T\left ( x_2-x_1 \right )\geq 0$

Converse

Let for any $x_1,x_2 \in S,\left (\bigtriangledown f \left ( x_2\right )- \bigtriangledown f \left ( x_1\right )\right )^T \left ( x_2-x_1\right )\geq 0$

To show that f is convex.

Let $x_1,x_2 \in S$, thus by mean value theorem, $\frac{f\left ( x_1\right )-f\left ( x_2\right )}{x_1-x_2}=\bigtriangledown f\left ( x\right ),x \in \left ( x_1-x_2\right ) \Rightarrow x= \lambda x_1+\left ( 1-\lambda\right )x_2$ because S is a convex set.

$\Rightarrow f\left ( x_1 \right )- f\left ( x_2 \right )=\left ( \bigtriangledown f\left ( x \right )^T \right )\left ( x_1-x_2 \right )$

for $x,x_1$, we know −

$\left ( \bigtriangledown f\left ( x \right )-\bigtriangledown f\left ( x_1 \right ) \right )^T\left ( x-x_1 \right )\geq 0$

$\Rightarrow \left ( \bigtriangledown f\left ( x \right )-\bigtriangledown f\left ( x_1 \right ) \right )^T\left ( \lambda x_1+\left ( 1-\lambda \right )x_2-x_1 \right )\geq 0$

$\Rightarrow \left ( \bigtriangledown f\left ( x \right )- \bigtriangledown f\left ( x_1 \right )\right )^T\left ( 1- \lambda \right )\left ( x_2-x_1 \right )\geq 0$

$\Rightarrow \bigtriangledown f\left ( x \right )^T\left ( x_2-x_1 \right )\geq \bigtriangledown f\left ( x_1 \right )^T\left ( x_2-x_1 \right )$

Combining the above equations, we get −

$\Rightarrow \bigtriangledown f\left ( x_1 \right )^T\left ( x_2-x_1 \right )\leq f\left ( x_2 \right )-f\left ( x_1 \right )$

Hence using the last theorem, f is a convex function.

Twice Differentiable function

Let S be a non-empty subset of $\mathbb{R}^n$ and let $f:S\rightarrow \mathbb{R}$ then f is said to be twice differentiable at $\bar{x} \in S$ if there exists a vector $\bigtriangledown f\left (\bar{x}\right ), a \:nXn$ matrix $H\left (x\right )$(called Hessian matrix) and a function $\alpha:\mathbb{R}^n \rightarrow \mathbb{R}$ such that $f\left ( x \right )=f\left ( \bar{x}+x-\bar{x} \right )=f\left ( \bar{x} \right )+\bigtriangledown f\left ( \bar{x} \right )^T\left ( x-\bar{x} \right )+\frac{1}{2}\left ( x-\bar{x} \right )H\left ( \bar{x} \right )\left ( x-\bar{x} \right )$

where $ \alpha \left ( \bar{x}, x-\bar{x} \right )\rightarrow Oasx\rightarrow \bar{x}$

Theorem

Let f be twice differentiable function. If $\bar{x}$ is a local minima, then $\bigtriangledown f\left ( \bar{x} \right )=0$ and the Hessian matrix $H\left ( \bar{x} \right )$ is a positive semidefinite.

Proof

Let $d \in \mathbb{R}^n$. Since f is twice differentiable at $\bar{x}$.

Therefore,

$f\left ( \bar{x} +\lambda d\right )=f\left ( \bar{x} \right )+\lambda \bigtriangledown f\left ( \bar{x} \right )^T d+\lambda^2d^TH\left ( \bar{x} \right )d+\lambda^2d^TH\left ( \bar{x} \right )d+$

$\lambda^2\left \| d \right \|^2\beta \left ( \bar{x}, \lambda d \right )$

But $\bigtriangledown f\left ( \bar{x} \right )=0$ and $\beta\left ( \bar{x}, \lambda d \right )\rightarrow 0$ as $\lambda \rightarrow 0$

$\Rightarrow f\left ( \bar{x} +\lambda d \right )-f\left ( \bar{x} \right )=\lambda ^2d^TH\left ( \bar{x} \right )d$

Since $\bar{x }$ is a local minima, there exists a $\delta > 0$ such that $f\left ( x \right )\leq f\left ( \bar{x}+\lambda d \right ), \forall \lambda \in \left ( 0,\delta \right )$

Theorem

Let $f:S \rightarrow \mathbb{R}^n$ where $S \subset \mathbb{R}^n$ be twice differentiable over S. If $\bigtriangledown f\left ( x\right )=0$ and $H\left ( \bar{x} \right )$ is positive semi-definite, for all $x \in S$, then $\bar{x}$ is a global optimal solution.

Proof

Since $H\left ( \bar{x} \right )$ is positive semi-definite, f is convex function over S. Since f is differentiable and convex at $\bar{x}$

$\bigtriangledown f\left ( \bar{x} \right )^T \left ( x-\bar{x} \right ) \leq f\left (x\right )-f\left (\bar{x}\right ),\forall x \in S$

Since $\bigtriangledown f\left ( \bar{x} \right )=0, f\left ( x \right )\geq f\left ( \bar{x} \right )$

Hence, $\bar{x}$ is a global optima.

Theorem

Suppose $\bar{x} \in S$ is a local optimal solution to the problem $f:S \rightarrow \mathbb{R}$ where S is a non-empty subset of $\mathbb{R}^n$ and S is convex. $min \:f\left ( x \right )$ where $x \in S$.

Then:

  • $\bar{x}$ is a global optimal solution.

  • If either $\bar{x}$ is strictly local minima or f is strictly convex function, then $\bar{x}$ is the unique global optimal solution and is also strong local minima.

Proof

Let $\bar{x}$ be another global optimal solution to the problem such that $x \neq \bar{x}$ and $f\left ( \bar{x} \right )=f\left ( \hat{x} \right )$

Since $\hat{x},\bar{x} \in S$ and S is convex, then $\frac{\hat{x}+\bar{x}}{2} \in S$ and f is strictly convex.

$\Rightarrow f\left ( \frac{\hat{x}+\bar{x}}{2} \right )< \frac{1}{2} f\left (\bar{x}\right )+\frac{1}{2} f\left (\hat{x}\right )=f\left (\hat{x}\right )$

This is contradiction.

Hence, $\hat{x}$ is a unique global optimal solution.

Corollary

Let $f:S \subset \mathbb{R}^n \rightarrow \mathbb{R}$ be a differentiable convex function where $\phi \neq S\subset \mathbb{R}^n$ is a convex set. Consider the problem $min f\left (x\right ),x \in S$,then $\bar{x}$ is an optimal solution if $\bigtriangledown f\left (\bar{x}\right )^T\left (x-\bar{x}\right ) \geq 0,\forall x \in S.$

Proof

Let $\bar{x}$ is an optimal solution, i.e, $f\left (\bar{x}\right )\leq f\left (x\right ),\forall x \in S$

$\Rightarrow f\left (x\right )=f\left (\bar{x}\right )\geq 0$

$f\left (x\right )=f\left (\bar{x}\right )+\bigtriangledown f\left (\bar{x}\right )^T\left (x-\bar{x}\right )+\left \| x-\bar{x} \right \|\alpha \left ( \bar{x},x-\bar{x} \right )$

where $\alpha \left ( \bar{x},x-\bar{x} \right )\rightarrow 0$ as $x \rightarrow \bar{x}$

$\Rightarrow f\left (x\right )-f\left (\bar{x}\right )=\bigtriangledown f\left (\bar{x}\right )^T\left (x-\bar{x}\right )\geq 0$

Corollary

Let f be a differentiable convex function at $\bar{x}$,then $\bar{x}$ is global minimum iff $\bigtriangledown f\left (\bar{x}\right )=0$

Examples

  • $f\left (x\right )=\left (x^2-1\right )^{3}, x \in \mathbb{R}$.

    $\bigtriangledown f\left (x\right )=0 \Rightarrow x= -1,0,1$.

    $\bigtriangledown^2f\left (\pm 1 \right )=0, \bigtriangledown^2 f\left (0 \right )=6>0$.

    $f\left (\pm 1 \right )=0,f\left (0 \right )=-1$

    Hence, $f\left (x \right ) \geq -1=f\left (0 \right )\Rightarrow f\left (0 \right ) \leq f \left (x \right)\forall x \in \mathbb{R}$

  • $f\left (x \right )=x\log x$ defined on $S=\left \{ x \in \mathbb{R}, x> 0 \right \}$.

    ${f}'x=1+\log x$

    ${f}''x=\frac{1}{x}>0$

    Thus, this function is strictly convex.

  • $f \left (x \right )=e^{x},x \in \mathbb{R}$ is strictly convex.

Let $f:S \rightarrow \mathbb{R}$ where $S \subset \mathbb{R}^n$ is a non-empty convex set. The function f is said to be quasiconvex if for each $x_1,x_2 \in S$, we have $f\left ( \lambda x_1+\left ( 1-\lambda \right )x_2 \right )\leq max\left \{ f\left ( x_1 \right ),f\left ( x_2 \right ) \right \},\lambda \in \left ( 0, 1 \right )$

For example, $f\left ( x \right )=x^{3}$

Let $f:S\rightarrow R $ where $S\subset \mathbb{R}^n$ is a non-empty convex set. The function f is said to be quasiconvex if for each $x_1, x_2 \in S$, we have $f\left ( \lambda x_1+\left ( 1-\lambda \right )x_2 \right )\geq min\left \{ f\left ( x_1 \right ),f\left ( x_2 \right ) \right \}, \lambda \in \left ( 0, 1 \right )$

Remarks

  • Every convex function is quasiconvex but the converse is not true.
  • A function which is both quasiconvex and quasiconcave is called quasimonotone.

Theorem

Let $f:S\rightarrow \mathbb{R}$ and S is a non empty convex set in $\mathbb{R}^n$. The function f is quasiconvex if and only if $S_{\alpha} =\left ( x \in S:f\left ( x \right )\leq \alpha \right \}$ is convex for each real number \alpha$

Proof

Let f is quasiconvex on S.

Let $x_1,x_2 \in S_{\alpha}$ therefore $x_1,x_2 \in S$ and $max \left \{ f\left ( x_1 \right ),f\left ( x_2 \right ) \right \}\leq \alpha$

Let $\lambda \in \left (0, 1 \right )$ and let $x=\lambda x_1+\left ( 1-\lambda \right )x_2\leq max \left \{ f\left ( x_1 \right ),f\left ( x_2 \right ) \right \}\Rightarrow x \in S$

Thus, $f\left ( \lambda x_1+\left ( 1-\lambda \right )x_2 \right )\leq max\left \{ f\left ( x_1 \right ), f\left ( x_2 \right ) \right \}\leq \alpha$

Therefore, $S_{\alpha}$ is convex.

Converse

Let $S_{\alpha}$ is convex for each $\alpha$

$x_1,x_2 \in S, \lambda \in \left ( 0,1\right )$

$x=\lambda x_1+\left ( 1-\lambda \right )x_2$

Let $x=\lambda x_1+\left ( 1-\lambda \right )x_2$

For $x_1, x_2 \in S_{\alpha}, \alpha= max \left \{ f\left ( x_1 \right ), f\left ( x_2 \right ) \right \}$

$\Rightarrow \lambda x_1+\left (1-\lambda \right )x_2 \in S_{\alpha}$

$\Rightarrow f \left (\lambda x_1+\left (1-\lambda \right )x_2 \right )\leq \alpha$

Hence proved.

Theorem

Let $f:S\rightarrow \mathbb{R}$ and S is a non empty convex set in $\mathbb{R}^n$. The function f is quasiconcave if and only if $S_{\alpha} =\left \{ x \in S:f\left ( x \right )\geq \alpha \right \}$ is convex for each real number $\alpha$.

Theorem

Let $f:S\rightarrow \mathbb{R}$ and S is a non empty convex set in $\mathbb{R}^n$. The function f is quasimonotone if and only if $S_{\alpha} =\left \{ x \in S:f\left ( x \right )= \alpha \right \}$ is convex for each real number $\alpha$.

Theorem

Let S be a non empty convex set in $\mathbb{R}^n$ and $f:S \rightarrow \mathbb{R}$ be differentiable on S, then f is quasiconvex if and only if for any $x_1,x_2 \in S$ and $f\left ( x_1 \right )\leq f\left ( x_2 \right )$, we have $\bigtriangledown f\left ( x_2 \right )^T\left ( x_2-x_1 \right )\leq 0$

Proof

Let f be a quasiconvex function.

Let $x_1,x_2 \in S$ such that $f\left ( x_1 \right ) \leq f\left ( x_2 \right )$

By differentiability of f at $x_2, \lambda \in \left ( 0, 1 \right )$

$f\left ( \lambda x_1+\left ( 1-\lambda \right )x_2 \right )=f\left ( x_2+\lambda \left (x_1-x_2 \right ) \right )=f\left ( x_2 \right )+\bigtriangledown f\left ( x_2 \right )^T\left ( x_1-x_2 \right )$

$+\lambda \left \| x_1-x_2 \right \|\alpha \left ( x_2,\lambda \left ( x_1-x_2 \right ) \right )$

$\Rightarrow f\left ( \lambda x_1+\left ( 1-\lambda \right )x_2 \right )-f\left ( x_2 \right )-f\left ( x_2 \right )=\bigtriangledown f\left ( x_2 \right )^T\left ( x_1-x_2 \right )$

$+\lambda \left \| x_1-x_2 \right \|\alpha \left ( x2, \lambda\left ( x_1-x_2 \right )\right )$

But since f is quasiconvex, $f \left ( \lambda x_1+ \left ( 1- \lambda \right )x_2 \right )\leq f \left (x_2 \right )$

$\bigtriangledown f\left ( x_2 \right )^T\left ( x_1-x_2 \right )+\lambda \left \| x_1-x_2 \right \|\alpha \left ( x_2,\lambda \left ( x_1,x_2 \right ) \right )\leq 0$

But $\alpha \left ( x_2,\lambda \left ( x_1,x_2 \right )\right )\rightarrow 0$ as $\lambda \rightarrow 0$

Therefore, $\bigtriangledown f\left ( x_2 \right )^T\left ( x_1-x_2 \right ) \leq 0$

Converse

let for $x_1,x_2 \in S$ and $f\left ( x_1 \right )\leq f\left ( x_2 \right )$, $\bigtriangledown f\left ( x_2 \right )^T \left ( x_1,x_2 \right ) \leq 0$

To show that f is quasiconvex,ie, $f\left ( \lambda x_1+\left ( 1-\lambda \right )x_2 \right )\leq f\left ( x_2 \right )$

Proof by contradiction

Suppose there exists an $x_3= \lambda x_1+\left ( 1-\lambda \right )x_2$ such that $f\left ( x_2 \right )< f \left ( x_3 \right )$ for some $ \lambda \in \left ( 0, 1 \right )$

For $x_2$ and $x_3,\bigtriangledown f\left ( x_3 \right )^T \left ( x_2-x_3 \right ) \leq 0$

$\Rightarrow -\lambda \bigtriangledown f\left ( x_3 \right )^T\left ( x_2-x_3 \right )\leq 0$

$\Rightarrow \bigtriangledown f\left ( x_3 \right )^T \left ( x_1-x_2 \right )\geq 0$

For $x_1$ and $x_3,\bigtriangledown f\left ( x_3 \right )^T \left ( x_1-x_3 \right ) \leq 0$

$\Rightarrow \left ( 1- \lambda \right )\bigtriangledown f\left ( x_3 \right )^T\left ( x_1-x_2 \right )\leq 0$

$\Rightarrow \bigtriangledown f\left ( x_3 \right )^T \left ( x_1-x_2 \right )\leq 0$

thus, from the above equations, $\bigtriangledown f\left ( x_3 \right )^T \left ( x_1-x_2 \right )=0$

Define $U=\left \{ x:f\left ( x \right )\leq f\left ( x_2 \right ),x=\mu x_2+\left ( 1-\mu \right )x_3, \mu \in \left ( 0,1 \right ) \right \}$

Thus we can find $x_0 \in U$ such that $x_0 = \mu_0 x_2= \mu x_2+\left ( 1- \mu \right )x_3$ for some $\mu _0 \in \left ( 0,1 \right )$ which is nearest to $x_3$ and $\hat{x} \in \left ( x_0,x_1 \right )$ such that by mean value theorem,

$$\frac{f\left ( x_3\right )-f\left ( x_0\right )}{x_3-x_0}= \bigtriangledown f\left ( \hat{x}\right )$$

$$\Rightarrow f\left ( x_3 \right )=f\left ( x_0 \right )+\bigtriangledown f\left ( \hat{x} \right )^T\left ( x_3-x_0 \right )$$

$$\Rightarrow f\left ( x_3 \right )=f\left ( x_0 \right )+\mu_0 \lambda f\left ( \hat{x}\right )^T \left ( x_1-x_2 \right )$$

Since $x_0$ is a combination of $x_1$ and $x_2$ and $f\left (x_2 \right )< f\left ( \hat{x}\right )$

By repeating the starting procedure, $\bigtriangledown f \left ( \hat{x}\right )^T \left ( x_1-x_2\right )=0$

Thus, combining the above equations, we get:

$$f\left ( x_3\right )=f\left ( x_0 \right ) \leq f\left ( x_2\right )$$

$$\Rightarrow f\left ( x_3\right )\leq f\left ( x_2\right )$$

Hence, it is contradiction.

Examples

Step 1 − $f\left ( x\right )=X^3$

$Let f \left ( x_1\right )\leq f\left ( x_2\right )$

$\Rightarrow x_{1}^{3}\leq x_{2}^{3}\Rightarrow x_1\leq x_2$

$\bigtriangledown f\left ( x_2 \right )\left ( x_1-x_2 \right )=3x_{2}^{2}\left ( x_1-x_2 \right )\leq 0$

Thus, $f\left ( x\right )$ is quasiconvex.

Step 2 − $f\left ( x\right )=x_{1}^{3}+x_{2}^{3}$

Let $\hat{x_1}=\left ( 2, -2\right )$ and $\hat{x_2}=\left ( 1, 0\right )$

thus, $f\left ( \hat{x_1}\right )=0,f\left ( \hat{x_2}\right )=1 \Rightarrow f\left ( \hat{x_1}\right )\setminus < f \left ( \hat{x_2}\right )$

Thus, $\bigtriangledown f \left ( \hat{x_2}\right )^T \left ( \hat{x_1}- \hat{x_2}\right )= \left ( 3, 0\right )^T \left ( 1, -2\right )=3 >0$

Hence $f\left ( x\right )$ is not quasiconvex.

Let $f:S\rightarrow \mathbb{R}^n$ and S be a non-empty convex set in $\mathbb{R}^n$ then f is said to be strictly quasicovex function if for each $x_1,x_2 \in S$ with $f\left ( x_1 \right ) \neq f\left ( x_2 \right )$, we have $f\left ( \lambda x_1+\left ( 1-\lambda \right )x_2 \right )< max \:\left \{ f\left ( x_1 \right ),f\left ( x_2 \right ) \right \}$

Remarks

  • Every strictly quasiconvex function is strictly convex.
  • Strictly quasiconvex function does not imply quasiconvexity.
  • Strictly quasiconvex function may not be strongly quasiconvex.
  • Pseudoconvex function is a strictly quasiconvex function.

Theorem

Let $f:S\rightarrow \mathbb{R}^n$ be strictly quasiconvex function and S be a non-empty convex set in $\mathbb{R}^n$.Consider the problem: $min \:f\left ( x \right ), x \in S$. If $\hat{x}$ is local optimal solution, then $\bar{x}$ is global optimal solution.

Proof

Let there exists $ \bar{x} \in S$ such that $f\left ( \bar{x}\right )\leq f \left ( \hat{x}\right )$

Since $\bar{x},\hat{x} \in S$ and S is convex set, therefore,

$$\lambda \bar{x}+\left ( 1-\lambda \right )\hat{x}\in S, \forall \lambda \in \left ( 0,1 \right )$$

Since $\hat{x}$ is local minima, $f\left ( \hat{x} \right ) \leq f\left ( \lambda \bar{x}+\left ( 1-\lambda \right )\hat{x} \right ), \forall \lambda \in \left ( 0,\delta \right )$

Since f is strictly quasiconvex.

$$f\left ( \lambda \bar{x}+\left ( 1-\lambda \right )\hat{x} \right )< max \left \{ f\left ( \hat{x} \right ),f\left ( \bar{x} \right ) \right \}=f\left ( \hat{x} \right )$$

Hence, it is contradiction.

Strictly quasiconcave function

Let $f:S\rightarrow \mathbb{R}^n$ and S be a non-empty convex set in $\mathbb{R}^n$, then f is saud to be strictly quasicovex function if for each $x_1,x_2 \in S$ with $f\left (x_1\right )\neq f\left (x_2\right )$, we have

$$f\left (\lambda x_1+\left (1-\lambda\right )x_2\right )> min \left \{ f \left (x_1\right ),f\left (x_2\right )\right \}$$.

Examples

  • $f\left (x\right )=x^2-2$

    It is a strictly quasiconvex function because if we take any two points $x_1,x_2$ in the domain that satisfy the constraints in the definition $f\left (\lambda x_1+\left (1- \lambda\right )x_2\right )< max \left \{ f \left (x_1\right ),f\left (x_2\right )\right \}$ As the function is decreasing in the negative x-axis and it is increasing in the positive x-axis (since it is a parabola).

  • $f\left (x\right )=-x^2$

    It is not a strictly quasiconvex function because if we take take $x_1=1$ and $x_2=-1$ and $\lambda=0.5$, then $f\left (x_1\right )=-1=f\left (x_2\right )$ but $f\left (\lambda x_1+\left (1- \lambda\right )x_2\right )=0$ Therefore it does not satisfy the conditions stated in the definition. But it is a quasiconcave function because if we take any two points in the domain that satisfy the constraints in the definition $f\left ( \lambda x_1+\left (1-\lambda\right )x_2\right )> min \left \{ f \left (x_1\right ),f\left (x_2\right )\right \}$. As the function is increasing in the negative x-axis and it is decreasing in the positive x-axis.

Let $f:S\rightarrow \mathbb{R}^n$ and S be a non-empty convex set in $\mathbb{R}^n$ then f is strongly quasiconvex function if for any $x_1,x_2 \in S$ with $\left ( x_1 \right ) \neq \left ( x_2 \right )$, we have $f\left ( \lambda x_1+\left ( 1-\lambda \right )x_2 \right )< max \:\left \{ f\left ( x_1 \right ),f\left ( x_2 \right ) \right \},\forall \lambda \in \left ( 0,1\right )$

Theorem

A quasiconvex function $f:S\rightarrow \mathbb{R}^n$ on a non-empty convex set S in $\mathbb{R}^n$ is strongly quasiconvex function if it is not constant on a line segment joining any points of S.

Proof

Let f is quasiconvex function and it is not constant on a line segment joining any points of S.

Suppose f is not strongly quasiconvex function.

There exist $x_1,x_2 \in S$ with $x_1 \neq x_2$ such that

$$f\left ( z \right )\geq max\left \{ f\left ( x_1 \right ), f\left ( x_2 \right ) \right \}, \forall z= \lambda x_1+\left ( 1-\lambda \right )x_2, \lambda \in \left ( 0,1 \right )$$

$\Rightarrow f\left ( x_1 \right )\leq f\left ( z \right )$ and $f\left ( x_2 \right )\leq f\left ( z \right )$

Since f is not constant in $\left [ x_1,z \right ]$ and $\left [z,x_2 \right ] $

So there exists $u \in \left [ x_1,z \right ]$ and $v=\left [ z,x_2 \right ]$

$$\Rightarrow u= \mu_1x_1+\left ( 1-\mu_1\right )z,v=\mu_2z+\left ( 1- \mu_2\right )x_2$$

Since f is quasiconvex,

$$\Rightarrow f\left ( u \right )\leq max\left \{ f\left ( x_1 \right ),f \left ( z \right ) \right \}=f\left ( z \right )\:\: and \:\:f \left ( v \right ) \leq max \left \{ f\left ( z \right ),f\left ( x_2 \right ) \right \}$$

$$\Rightarrow f\left ( u \right )\leq f\left ( z \right ) \:\: and \:\: f\left ( v \right )\leq f\left ( z \right )$$

$$\Rightarrow max \left \{ f\left ( u \right ),f\left ( v \right ) \right \} \leq f\left ( z \right )$$

But z is any point between u and v, if any of them are equal, then f is constant.

Therefore, $max \left \{ f\left ( u \right ),f\left ( v \right ) \right \} \leq f\left ( z \right )$

which contradicts the quasiconvexity of f as $z \in \left [ u,v \right ]$.

Hence f is strongly quasiconvex function.

Theorem

Let $f:S\rightarrow \mathbb{R}^n$ and S be a non-empty convex set in $\mathbb{R}^n$. If $\hat{x}$ is local optimal solution, then $\hat{x}$ is unique global optimal solution.

Proof

Since a strong quasiconvex function is also strictly quasiconvex function, thus a local optimal solution is global optimal solution.

Uniqueness − Let f attains global optimal solution at two points $u,v \in S$

$$\Rightarrow f\left ( u \right ) \leq f\left ( x \right ).\forall x \in S\:\: and \:\:f\left ( v \right ) \leq f\left ( x \right ).\forall x \in S$$

If u is global optimal solution, $f\left ( u \right )\leq f\left ( v \right )$ and $f\left ( v \right )\leq f\left ( u\right )\Rightarrow f\left ( u \right )=f\left ( v\right )$

$$f\left ( \lambda u+\left ( 1-\lambda\right )v\right )< max \left \{f\left ( u \right ),f\left ( v \right ) \right \}=f\left ( u \right )$$

which is a contradiction.

Hence there exists only one global optimal solution.

Remarks

  • A strongly quasiconvex function is also strictly quasiconvex fucntion.
  • A strictly convex function may or may not be strongly quasiconvex.
  • A differentiable strictly convex is strongly quasiconvex.

Let $f:S\rightarrow \mathbb{R}$ be a differentiable function and S be a non-empty convex set in $\mathbb{R}^n$, then f is said to be pseudoconvex if for each $x_1,x_2 \in S$ with $\bigtriangledown f\left ( x_1 \right )^T\left ( x_2-x_1 \right )\geq 0$, we have $f\left ( x_2 \right )\geq f\left ( x_1 \right )$, or equivalently if $f\left ( x_1 \right )>f\left ( x_2 \right )$ then $\bigtriangledown f\left ( x_1 \right )^T\left ( x_2-x_1 \right )<0$

Pseudoconcave function

Let $f:S\rightarrow \mathbb{R}$ be a differentiable function and S be a non-empty convex set in $\mathbb{R}^n$, then f is said to be pseudoconvex if for each $x_1, x_2 \in S$ with $\bigtriangledown f\left ( x_1 \right )^T\left ( x_2-x_1 \right )\geq 0$, we have $f\left ( x_2 \right )\leq f\left ( x_1 \right )$, or equivalently if $f\left ( x_1 \right )>f\left ( x_2 \right )$ then $\bigtriangledown f\left ( x_1 \right )^T\left ( x_2-x_1 \right )>0$

Remarks

  • If a function is both pseudoconvex and pseudoconcave, then is is called pseudolinear.

  • A differentiable convex function is also pseudoconvex.

  • A pseudoconvex function may not be convex. For example,

    $f\left ( x \right )=x+x^3$ is not convex. If $x_1 \leq x_2,x_{1}^{3} \leq x_{2}^{3}$

    Thus,$\bigtriangledown f\left ( x_1 \right )^T\left ( x_2-x_1 \right )=\left ( 1+3x_{1}^{2} \right )\left ( x_2-x_1 \right ) \geq 0$

    And, $f\left ( x_2 \right )-f\left ( x_1 \right )=\left ( x_2-x_1 \right )+\left ( x_{2}^{3} -x_{1}^{3}\right )\geq 0$

    $\Rightarrow f\left ( x_2 \right )\geq f\left ( x_1 \right )$

    Thus, it is pseudoconvex.

    A pseudoconvex function is strictly quasiconvex. Thus, every local minima of pseudoconvex is also global minima.

Strictly pseudoconvex function

Let $f:S\rightarrow \mathbb{R}$ be a differentiable function and S be a non-empty convex set in $\mathbb{R}^n$, then f is said to be pseudoconvex if for each $x_1,x_2 \in S$ with $\bigtriangledown f\left ( x_1 \right )^T\left ( x_2-x_1 \right )\geq 0$, we have $f\left ( x_2 \right )> f\left ( x_1 \right )$,or equivalently if $f\left ( x_1 \right )\geq f\left ( x_2 \right )$ then $\bigtriangledown f\left ( x_1 \right )^T\left ( x_2-x_1 \right )<0$

Theorem

Let f be a pseudoconvex function and suppose $\bigtriangledown f\left ( \hat{x}\right )=0$ for some $\hat{x} \in S$, then $\hat{x}$ is global optimal solution of f over S.

Proof

Let $\hat{x}$ be a critical point of f, ie, $\bigtriangledown f\left ( \hat{x}\right )=0$

Since f is pseudoconvex function, for $x \in S,$ we have

$$\bigtriangledown f\left ( \hat{x}\right )\left ( x-\hat{x}\right )=0 \Rightarrow f\left ( \hat{x}\right )\leq f\left ( x\right ), \forall x \in S$$

Hence, $\hat{x}$ is global optimal solution.

Remark

If f is strictly pseudoconvex function, $\hat{x}$ is unique global optimal solution.

Theorem

If f is differentiable pseudoconvex function over S, then f is both strictly quasiconvex as well as quasiconvex function.

Remarks

  • The sum of two pseudoconvex fucntions defined on an open set S of $\mathbb{R}^n$ may not be pseudoconvex.

  • Let $f:S\rightarrow \mathbb{R}$ be a quasiconvex function and S be a non-empty convex subset of $\mathbb{R}^n$ then f is pseudoconvex if and only if every critical point is a global minima of f over S.

  • Let S be a non-empty convex subset of $\mathbb{R}^n$ and $f:S\rightarrow \mathbb{R}$ be a function such that $\bigtriangledown f\left ( x\right )\neq 0$ for every $x \in S$ then f is pseudoconvex if and only if it is a quasiconvex function.

There are four types of convex programming problems −

Step 1 − $min \:f\left ( x \right )$, where $x \in S$ and S be a non-empty convex set in $\mathbb{R}^n$ and $f\left ( x \right )$ is convex function.

Step 2 − $min \: f\left ( x \right ), x \in \mathbb{R}^n$ subject to

$g_i\left ( x \right ) \geq 0, 1 \leq m_1$ and $g_i\left ( x \right )$ is a convex function.

$g_i\left ( x \right ) \leq 0,m_1+1 \leq m_2$ and $g_i\left ( x \right )$ is a concave function.

$g_i\left ( x \right ) = 0, m_2+1 \leq m$ and $g_i\left ( x \right )$ is a linear function.

where $f\left ( x \right )$ is a convex fucntion.

Step 3 − $max \:f\left ( x \right )$ where $x \in S$ and S be a non-empty convex set in $\mathbb{R}^n$ and $f\left ( x \right )$ is concave function.

Step 4 − $min \:f\left ( x \right )$, where $x \in \mathbb{R}^n$ subject to

$g_i\left ( x \right ) \geq 0, 1 \leq m_1$ and $g_i\left ( x \right )$ is a convex function.

$g_i\left ( x \right ) \leq 0, m_1+1 \leq m_2$ and $g_i\left ( x \right )$ is a concave function.

$g_i\left ( x \right ) = 0,m_2+1 \leq m$ and $g_i\left ( x \right )$ is a linear function.

where $f\left ( x \right )$ is a concave function.

Cone of feasible direction

Let S be a non-empty set in $\mathbb{R}^n$ and let $\hat{x} \in \:Closure\left ( S \right )$, then the cone of feasible direction of S at $\hat{x}$, denoted by D, is defined as $D=\left \{ d:d\neq 0,\hat{x}+\lambda d \in S, \lambda \in \left ( 0, \delta \right ), \delta > 0 \right \}$

Each non-zero vector $d \in D$ is called feasible direction.

For a given function $f:\mathbb{R}^n \Rightarrow \mathbb{R}$ the cone of improving direction at $\hat{x}$ is denoted by F and is given by

$$F=\left \{ d:f\left ( \hat{x}+\lambda d \right )\leq f\left ( \hat{x} \right ),\forall \lambda \in \left ( 0,\delta \right ), \delta >0 \right \}$$

Each direction $d \in F$ is called an improving direction or descent direction of f at $\hat{x}$

Theorem

Necessary Condition

Consider the problem $min f\left ( x \right )$ such that $x \in S$ where S be a non-empty set in $\mathbb{R}^n$. Suppose f is differentiable at a point $\hat{x} \in S$. If $\hat{x}$ is a local optimal solution, then $F_0 \cap D= \phi$ where $F_0=\left \{ d:\bigtriangledown f\left ( \hat{x} \right )^T d < 0 \right \}$ and D is a cone of feasible direction.

Sufficient Condition

If $F_0 \cap D= \phi$ f is a pseudoconvex function at $\hat{x}$ and there exists a neighbourhood of $\hat{x},N_\varepsilon \left ( \hat{x} \right ), \varepsilon > 0$ such that $d=x-\hat{x}\in D$ for any $x \in S \cap N_\varepsilon \left ( \hat{x} \right )$, then $\hat{x}$ is local optimal solution.

Proof

Necessary Condition

Let $F_0 \cap D\neq \phi$, ie, there exists a $d \in F_0 \cap D$ such that $d \in F_0$ and $d\in D$

Since $d \in D$, therefore there exists $\delta_1 >0$ such that $\hat{x}+\lambda d \in S, \lambda \in \left ( 0,\delta_1 \right ).$

Since $d \in F_0$, therefore $\bigtriangledown f \left ( \hat{x}\right )^T d <0$

Thus, there exists $\delta_2>0$ such that $f\left ( \hat{x}+\lambda d\right )< f\left ( \hat{x}\right ),\forall \lambda \in f \left ( 0,\delta_2 \right )$

Let $\delta=min \left \{\delta_1,\delta_2 \right \}$

Then $\hat{x}+\lambda d \in S, f\left (\hat{x}+\lambda d \right ) < f\left ( \hat{x} \right ),\forall \lambda \in f \left ( 0,\delta \right )$

But $\hat{x}$ is local optimal solution.

Hence it is contradiction.

Thus $F_0\cap D=\phi$

Sufficient Condition

Let $F_0 \cap D\neq \phi$ nd let f be a pseudoconvex function.

Let there exists a neighbourhood of $\hat{x}, N_{\varepsilon}\left ( \hat{x} \right )$ such that $d=x-\hat{x}, \forall x \in S \cap N_\varepsilon\left ( \hat{x} \right )$

Let $\hat{x}$ is not a local optimal solution.

Thus, there exists $\bar{x} \in S \cap N_\varepsilon \left ( \hat{x} \right )$ such that $f \left ( \bar{x} \right )< f \left ( \hat{x} \right )$

By assumption on $S \cap N_\varepsilon \left ( \hat{x} \right ),d=\left ( \bar{x}-\hat{x} \right )\in D$

By pseudoconvex of f,

$$f\left ( \hat{x} \right )>f\left ( \bar{x} \right )\Rightarrow \bigtriangledown f\left ( \hat{x} \right )^T\left ( \bar{x}-\hat{x} \right )<0$$

$\Rightarrow \bigtriangledown f\left ( \hat{x} \right) ^T d <0$

$\Rightarrow d \in F_0$

hence $F_0\cap D \neq \phi$

which is a contradiction.

Hence, $\hat{x}$ is local optimal solution.

Consider the following problem:$min \:f\left ( x\right )$ where $x \in X$ such that $g_x\left ( x\right ) \leq 0, i=1,2,...,m$

$f:X \rightarrow \mathbb{R},g_i:X \rightarrow \mathbb{R}^n$ and X is an open set in $\mathbb{R}^n$

Let $S=\left \{x:g_i\left ( x\right )\leq 0,\forall i \right \}$

Let $\hat{x} \in X$, then $M=\left \{1,2,...,m \right \}$

Let $I=\left \{i:g_i\left ( \hat{x}\right )=0, i \in M\right \}$ where I is called index set for all active constraints at $\hat{x}$

Let $J=\left \{i:g_i\left ( \hat{x}\right )<0,i \in M\right \}$ where J is called index set for all active constraints at $\hat{x}$.

Let $F_0=\left \{ d \in \mathbb{R}^m:\bigtriangledown f\left ( \hat{x} \right )^T d <0 \right \}$

Let $G_0=\left \{ d \in \mathbb{R}^m:\bigtriangledown gI\left ( \hat{x} \right )^T d <0 \right \}$

or $G_0=\left \{ d \in \mathbb{R}^m:\bigtriangledown gi\left ( \hat{x} \right )^T d <0 ,\forall i \in I \right \}$

Lemma

If $S=\left \{ x \in X:g_i\left ( x\right ) \leq 0, \forall i \in I\right \}$ and X is non-empty open set in $\mathbb{R}^n$. Let $\hat{x}\in S$ and $g_i$ are different at $\hat{x}, i \in I$ and let $g_i$ where $i \in J$ are continuous at $\hat{x}$, then $G_0 \subseteq D$.

Proof

Let $d \in G_0$

Since $\hat{x} \in X$ and X is an open set, thus there exists $\delta_1 >0$ such that $\hat{x}+\lambda d \in X$ for $\lambda \in \left ( 0, \delta_1\right )$

Also since $g_\hat{x}<0$ and $g_i$ are continuous at $\hat{x}, \forall i \in J$, there exists $\delta_2>0$, $g_i\left ( \hat{x}+\lambda d\right )<0, \lambda \in \left ( 0, \delta_2\right )$

Since $d \in G_0$, therefore, $\bigtriangledown g_i\left ( \hat{x}\right )^T d <0, \forall i \in I$ thus there exists $\delta_3 >0, g_i\left ( \hat{x}+\lambda d\right )< g_i\left ( \hat{x}\right )=0$, for $\lambda \in \left ( 0, \delta_3\right ) i \in J$

Let $\delta=min\left \{ \delta_1, \delta_2, \delta_3 \right \}$

therefore, $\hat{x}+\lambda d \in X, g_i\left ( \hat{x}+\lambda d\right )< 0, i \in M$

$\Rightarrow \hat{x}+\lambda d \in S$

$\Rightarrow d \in D$

$\Rightarrow G_0 \subseteq D$

Hence Proved.

Theorem

Necessary Condition

Let $f$ and $g_i, i \in I$, are different at $\hat{x} \in S,$ and $g_j$ are continous at $\hat{x} \in S$. If $\hat{x}$ is local minima of $S$, then $F_0 \cap G_0=\phi$.

Sufficient Condition

If $F_0 \cap G_0= \phi$ and f is a pseudoconvex function at $\left (\hat{x}, g_i 9x \right ), i \in I$ are strictly pseudoconvex functions over some $\varepsilon$ - neighbourhood of $\hat{x}, \hat{x}$ is a local optimal solution.

비고

  • 허락하다 $\hat{x}$ 실현 가능한 지점이 $\bigtriangledown f\left(\hat{x} \right)=0$, 다음 $F_0 = \phi$. 그러므로,$F_0 \cap G_0= \phi$ 그러나 $\hat{x}$ 최적의 솔루션이 아닙니다

  • 그러나 만약 $\bigtriangledown g\left(\hat{x} \right)=0$, 다음 $G_0=\phi$, 따라서 $F_0 \cap G_0= \phi$

  • 문제 고려 : 분 $f\left(x \right)$ 그런 $g\left(x \right)=0$.

    이후 $g\left(x \right)=0$따라서 $ g_1 \ left (x \ right) = g \ left (x \ right) <0 $ 및 $g_2\left(x \right)=-g\left(x \right) \leq 0$.

    허락하다 $\hat{x} \in S$, 다음 $g_1\left(\hat{x} \right)=0$ 과 $g_2\left(\hat{x} \right)=0$.

    그러나 $\bigtriangledown g_1\left(\hat{x} \right)= - \bigtriangledown g_2\left(\hat{x}\right)$

    그러므로, $G_0= \phi$ 과 $F_0 \cap G_0= \phi$.

필요한 조건

정리

문제를 고려하십시오- $min f\left ( x \right )$ 그런 $x \in X$ 여기서 X는 열린 집합입니다. $\mathbb{R}^n$ 그리고하자 $g_i \left ( x \right ) \leq 0, \forall i =1,2,....m$.

허락하다 $f:X \rightarrow \mathbb{R}$ 과 $g_i:X \rightarrow \mathbb{R}$

허락하다 $\hat{x}$ 가능한 해결책이되고 f와 $g_i, i \in I$ 차별화 가능 $\hat{x}$ 과 $g_i, i \in J$ 연속적이다 $\hat{x}$.

만약 $\hat{x}$ 위의 문제를 로컬로 해결하면 $u_0, u_i \in \mathbb{R}, i \in I$ 그런 $u_0 \bigtriangledown f\left ( \hat{x} \right )+\displaystyle\sum\limits_{i\in I} u_i \bigtriangledown g_i \left ( \hat{x} \right )$= 0

어디 $u_0,u_i \geq 0,i \in I$ 과 $\left ( u_0, u_I \right ) \neq \left ( 0,0 \right )$

또한 $g_i,i \in J$ 또한 $\hat{x}$, 위의 조건은 다음과 같이 쓸 수 있습니다-

$u_0 \bigtriangledown f\left ( \hat{x}\right )+\displaystyle\sum\limits_{i=1}^m u_i \bigtriangledown g_i\left ( \hat{x} \right )=0$

$u_ig_i\left (\hat{x} \right )$= 0

$u_0,u_i \geq 0, \forall i=1,2,....,m$

$\left (u_0,u \right ) \neq \left ( 0,0 \right ), u=\left ( u_1,u_2,s,u_m \right ) \in \mathbb{R}^m$

비고

  • $u_i$ 라그랑주 승수라고합니다.

  • 조건 $\hat{x}$ 주어진 문제에 대해 실현 가능하다는 것을 원시 실현 가능 조건이라고합니다.

  • 요구 사항 $u_0 \bigtriangledown f\left (\hat{x} \right )+\displaystyle\sum\limits_{i=1}^m u-i \bigtriangledown g_i\left ( x \right )=0$ 이중 타당성 조건이라고합니다.

  • 조건 $u_ig_i\left ( \hat{x} \right )=0, i=1, 2, ...m$이를 보완 여유 상태라고합니다. 이 조건은$u_i=0, i \in J$

  • 원시 실행 가능 조건, 이중 실행 가능성 조건 및 보완 여유를 함께 사용하여 프리츠-존 조건이라고합니다.

충분한 조건

정리

존재하는 경우 $\varepsilon$-이웃 $\hat{x}N_\varepsilon \left ( \hat{x} \right ),\varepsilon >0$ f가 위가 볼록하도록 $N_\varepsilon \left ( \hat{x} \right )\cap S$ 과 $g_i,i \in I$ 엄격히 유사 볼록 $N_\varepsilon \left ( \hat{x}\right )\cap S$, 다음 $\hat{x}$위에서 설명한 문제에 대한 로컬 최적의 솔루션입니다. f가 가상 볼록면$\hat{x}$ 그리고 만약 $g_i, i \in I$ 엄격하게 pseudoconvex 및 quasiconvex 함수입니다. $\hat{x},\hat{x}$ 위에서 설명한 문제에 대한 글로벌 최적 솔루션입니다.

  • $min \:f\left ( x_1,x_2 \right )=\left ( x_1-3 \right )^2+\left ( x_2-2 \right )^2$

    그런 $x_{1}^{2}+x_{2}^{2} \leq 5, x_1+2x_2 \leq 4, x_1,x_2 \geq 0$ 과 $\hat{x}=\left ( 2,1 \right )$

    허락하다 $g_1\left (x_1,x_2 \right )=x_{1}^{2}+x_{2}^{2} -5,$

    $g_2\left (x_1,x_2 \right )=x_1+2x_2-4,$

    $g_3\left (x_1,x_2 \right )=-x_1$ 과 $g_4\left ( x_1, x_2 \right )= -x_2$.

    따라서 위의 제약 조건은 다음과 같이 작성할 수 있습니다.

    $g_1\left (x_1,x_2 \right )\leq 0,$

    $g_2\left (x_1,x_2 \right )\leq 0,$

    $g_3\left (x_1,x_2 \right )\leq 0$ 과

    $g_4\left (x_1,x_2 \right )\leq 0$ 그러므로, $I = \left \{1,2 \right \}$ 따라서, $u_3=0,u_4=0$

    $\bigtriangledown f \left (\hat{x} \right )=\left (2,-2 \right ),\bigtriangledown g_1\left (\hat{x} \right )=\left (4,2 \right )$ 과 $\bigtriangledown g_2\left (\hat{x} \right )=\left (1,2 \right )$

    따라서 이러한 값을 Fritz-John 조건의 첫 번째 조건에 넣으면 다음과 같이됩니다.

    $u_0=\frac{3}{2} u_2, \:\:u_1= \frac{1}{2}u_2,$ 그리고하자 $u_2=1$따라서 $u_0= \frac{3}{2},\:\:u_1= \frac{1}{2}$

    따라서 Fritz John 조건이 충족됩니다.

  • $min f\left (x_1,x_2\right )=-x_1$.

    그런 $x_2-\left (1-x_1\right )^3 \leq 0$,

    $-x_2 \leq 0$ 과 $\hat{x}=\left (1,0\right )$

    허락하다 $g_1\left (x_1,x_2 \right )=x_2-\left (1-x_1\right )^3$,

    $g_2\left (x_1,x_2 \right )=-x_2$

    따라서 위의 제약 조건은 다음과 같이 작성할 수 있습니다.

    $g_1\left (x_1,x_2 \right )\leq 0,$

    $g_2\left (x_1,x_2 \right )\leq 0,$

    그러므로, $I=\left \{1,2 \right \}$

    $\bigtriangledown f\left (\hat{x} \right )=\left (-1,0\right )$

    $\bigtriangledown g_1 \left (\hat{x} \right )=\left (0,1\right )$ 과 $g_2 \left (\hat{x} \right )=\left (0, -1 \right )$

    따라서 이러한 값을 Fritz-John 조건의 첫 번째 조건에 넣으면 다음과 같이됩니다.

    $u_0=0,\:\: u_1=u_2=a>0$

    따라서 Fritz John 조건이 충족됩니다.

문제를 고려하십시오-

$min \:f\left ( x \right )$ 그런 $x \in X$, 여기서 X는 $\mathbb{R}^n$ 과 $g_i \left ( x \right )\leq 0, i=1, 2,...,m$

허락하다 $S=\left \{ x \in X:g_i\left ( x \right )\leq 0, \forall i \right \}$

허락하다 $\hat{x} \in S$ 그리고하자 $f$ 과 $g_i,i \in I$ 차별화 가능 $\hat{x}$ 과 $g_i, i \in J$ 연속적이다 $\hat{x}$. 더욱이,$\bigtriangledown g_i\left ( \hat{x} \right), i \in I$선형 적으로 독립적입니다. 만약$\hat{x}$ 위의 문제를 로컬로 해결하면 $u_i,i \in I$ 그런

$\bigtriangledown f\left ( x\right)+\displaystyle\sum\limits_{i\in I} u_i \bigtriangledown g_i\left ( \hat{x} \right)=0$, $\:\:u_i \geq 0, i \in I$

만약 $g_i,i \in J$ 또한 $\hat{x}$. 그때$\hat{x}$, 다음

$\bigtriangledown f\left ( \hat{x}\right)+\displaystyle\sum\limits_{i= 1}^m u_i \bigtriangledown g_i\left ( \hat{x} \right)=0$

$u_ig_i\left ( \hat{x} \right)=0, \forall i=1,2,...,m$

$u_i \geq 0 \forall i=1,2,...,m$

다음 문제를 고려하십시오-

$min \:f\left ( x_1,x_2 \right )=\left ( x_1-3\right )^2+\left ( x_2-2\right )^2$

그런 $x_{1}^{2}+x_{2}^{2}\leq 5$,

$x_1,2x_2 \geq 0$ 과 $\hat{x}=\left ( 2,1 \right )$

허락하다 $g_1\left ( x_1, x_2 \right)=x_{1}^{2}+x_{2}^{2}-5$,

$g_2\left ( x_1, x_2 \right)=x_{1}+2x_2-4$

$g_3\left ( x_1, x_2 \right)=-x_{1}$ 과 $g_4\left ( x_1,x_2 \right )=-x_2$

따라서 위의 제약 조건은 다음과 같이 작성할 수 있습니다.

$g_1 \left ( x_1,x_2 \right)\leq 0, g_2 \left ( x_1,x_2 \right) \leq 0$

$g_3 \left ( x_1,x_2 \right)\leq 0,$ 과 $g_4 \left ( x_1,x_2 \right) \leq 0$ 그러므로, $I=\left \{ 1,2 \right \}$ 따라서, $ u_3=0,\:\: u_4=0$

$\bigtriangledown f \left ( \hat{x} \right)=\left ( 2,-2 \right), \bigtriangledown g_1 \left ( \hat{x} \right)= \left ( 4,2 \right)$ 과

$\bigtriangledown g_2\left ( \hat{x} \right ) =\left ( 1,2 \right )$

따라서 이러한 값을 Karush-Kuhn-Tucker 조건의 첫 번째 조건에 넣으면 다음과 같이됩니다.

$u_1=\frac{1}{3}$ 과 $u_2=\frac{2}{3}$

따라서 Karush-Kuhn-Tucker 조건이 충족됩니다.

가파른 하강 방법

이 방법은 Gradient 방법 또는 Cauchy의 방법이라고도합니다. 이 방법은 다음 용어를 포함합니다-

$$x_{k+1}=x_k+\alpha_kd_k$$

$d_k= - \bigtriangledown f\left ( x_k \right )$ 또는 $ d_k= -\frac{\bigtriangledown f\left ( x_k \right )}{\left \| \bigtriangledown f\left ( x_k \right ) \right \|}$

허락하다 $\phi \left (\alpha \right )=f\left ( x_k +\alpha d_k\right )$

차별화함으로써 $\phi$ 0과 같게하면 $\alpha$.

따라서 알고리즘은 다음과 같습니다.

  • 초기화 $x_0$,$\varepsilon_1$,$\varepsilon_2$ 및 설정 $k=0$.

  • 세트 $d_k=-\bigtriangledown f\left ( x_k \right ) $또는 $d_k=-\frac{\bigtriangledown f\left (x_k \right )}{\left \|\bigtriangledown f\left (x_k \right ) \right \|}$.

  • 찾기 $\alpha_k$ 최소화하도록 $\phi\left ( \alpha \right )=f\left ( x_k+\alpha d_k \right )$.

  • 세트 $x_{k+1}=x_k+\alpha_kd_k$.

  • $ \ 왼쪽 \ | x_ {k + 1-x_k} \ 오른쪽 \ | <\ varepsilon_1 $ 또는$\left \| \bigtriangledown f\left ( x_{k+1} \right ) \right \| \leq \varepsilon_2$, 6 단계로 이동하고 그렇지 않으면 설정 $k=k+1$ 2 단계로 이동합니다.

  • 최적의 솔루션은 $\hat{x}=x_{k+1}$.

뉴턴 방법

뉴턴 방법은 다음과 같은 원리로 작동합니다-

$f\left ( x \right )=y\left ( x \right )=f\left ( x_k \right )+\left ( x-x_k \right )^T \bigtriangledown f\left ( x_k \right )+\frac{1}{2}\left ( x-x_k \right )^T H\left ( x_k \right )\left ( x-x_k \right )$

$\bigtriangledown y\left ( x \right )=\bigtriangledown f\left ( x_k \right )+H\left ( x_k \right )\left ( x-x_k \right )$

에서 $x_{k+1}, \bigtriangledown y\left ( x_{k+1} \right )=\bigtriangledown f\left ( x_k \right )+H\left ( x_k \right )\left ( x_{k+1}-x_k \right )$

에 대한 $x_{k+1}$ 최적의 솔루션 $\bigtriangledown y\left ( x_k+1 \right )=0$

그러므로, $x_{k+1}=x_k-H\left ( x_k \right )^{-1} \bigtriangledown f\left ( x_k \right )$

여기 $H\left ( x_k \right )$ 단수가 아니어야합니다.

따라서 알고리즘은 다음과 같습니다.

Step 1 − 초기화 $x_0,\varepsilon$ 및 설정 $k=0$.

Step 2 − 찾기 $H\left ( x_k \right ) \bigtriangledown f\left ( x_k \right )$.

Step 3 − 선형 시스템 풀기 $H\left ( x_k \right )h\left ( x_k \right )=\bigtriangledown f\left ( x_k \right )$ ...에 대한 $h\left ( x_k \right )$.

Step 4 − 찾기 $x_{k+1}=x_k-h\left ( x_k \right )$.

Step 5− $ \ left \ | x_ {k + 1} -x_k \ right \ | <\ varepsilon $ 또는$\left \| \bigtriangledown f\left ( x_k \right ) \right \| \leq \varepsilon$ 그런 다음 6 단계로 이동하고 그렇지 않으면 $k=k+1$ 2 단계로 이동합니다.

Step 6 − 최적의 솔루션은 $\hat{x}=x_{k+1}$.

켤레 기울기 방법

이 방법은 다음 유형의 문제를 해결하는 데 사용됩니다.

$min f\left ( x \right )=\frac{1}{2}x^T Qx-bx$

여기서 Q는 양의 정부 호 nXn 행렬이고 b는 상수입니다.

주어진 $x_0,\varepsilon,$ 계산하다 $g_0=Qx_0-b$

세트 $d_0=-g_0$ ...에 대한 $k=0,1,2,...,$

세트 $\alpha_k=\frac{g_{k}^{T}g_k}{d_{k}^{T}Q d_k}$

계산 $x_{k+1}=x_k+\alpha_kd_k$

세트 $g_{k+1}=g_k+\alpha_kd_k$

계산 $\beta_k=\frac{g_{k}^{T}g_k}{d_{k}^{T}Qd_k}$

계산 $x_{k+1}=x_k+\alpha_kd_k$

세트 $g_{k+1}=x_k+\alpha_kQd_k$

계산 $\beta_k=\frac{g_{k+1}^{T}g_{k+1}}{g_{k}^{T}gk}$

세트 $d_{k+1}=-g_{k+1}+\beta_kd_k$.