약한 이중성

응용수학에서 약한 이중성은 최적화의 개념으로 이중성 격차가 항상 0보다 크거나 같음을 명시한다.즉, 이중(최소화) 문제에 대한 해결책은 항상 관련 원시 문제에 대한 해결책보다 크거나 같음을 의미한다.이것은 특정한 경우에만 있는 강한 이중성에 반대한다.^[1]

사용하다

많은 원시-이중 근사 알고리즘은 취약한 이중성의 원리에 기초한다.^[2]

취약한 이중성 정리

근본적인 문제:

A x ≤ b, x ≥ 0에 따라 cx를^T 최대화한다;

이중 문제,

Ay^T ≥ c, y ≥ 0에 따라^T 최소화한다.

약한 이중성 정리에는 cx^T ≤ by가^T 명시되어 있다.

Namely, if ${\displaystyle (x_{1},x_{2},....,x_{n})}$ is a feasible solution for the primal maximization linear program and ${\displaystyle (y_{1},y_{2},....,y_{m})}$ is a feasible solution for the dual minimization linear program, then the weak dualitytheorem can be stated as ${\displaystyle \sum _{j=1}^{n}c_{j}x_{j}\leq \sum _{i=1}^{m}b_{i}y_{i}}$, where ${\displaystyle c_{j}}$ and ${\displaystyle b_{i}}$ are the coefficients of the respective objective functions.

증명: cx^T = xc^T ≤ xAy^TT ≤ by^T

일반화

보다 일반적으로 $x{\displaystyle }$ ${\displaystyle$ $x$$}$이(가) 원시 최대화 문제에 대해 실현 가능한 솔루션이고 $y{\displaystyle }$ ${\displaystyle y}$이(가) 이중 최소화 문제에 대해 실현 가능한 솔루션이라면$$, 약한 이중성은 $f{\displaystyle }$ ( $x{\displaystyle }$${\displaystyle }$)${\displaystyle \le }$ g${\displaystyle }$(${\displaystyle y)}$ ${\$$displaystyle$ f($x)\$$leq$ g$}$을 의미하며$,$ 여기서 f$$ ${\displaystystystystyleg}$은 g}이다$$.e 각각 원시 및 이중 문제에 대한 객관적 기능.

참고 항목

• 볼록 최적화
• 최대-최소 불평등

참조