이완(대략)

수학적 최적화 및 관련 분야에서 이완은 모델링 전략이다.이완은 풀기 쉬운 가까운 문제에 의한 어려운 문제의 근사치다.완화된 문제의 해결책은 원래의 문제에 대한 정보를 제공한다.

예를 들어, 정수 프로그래밍 문제의 선형 프로그래밍 완화는 통합성 제약조건을 제거하므로 비정수자의 합리적 해결책을 허용한다.조합 최적화의 복잡한 문제에 대한 라그랑고의 완화는 일부 제약조건의 위반을 처벌하여 더 쉬운 문제를 해결할 수 있게 한다.이완 기법은 결합 최적화의 분기 및 결합 알고리즘을 보완하거나 보완한다. 선형 프로그래밍과 라그랑지안 이완은 정수 프로그래밍을 위한 분기 및 결합 알고리즘의 한계를 얻기 위해 사용된다.^[1]

이완의 모델링 전략은 연속적인 과완화(특수 작전 소요)와 같은 반복적인 이완 방법과 혼동해서는 안 된다. 이완의 반복적인방법은 미분 방정식, 선형 최소 제곱 및 선형 프로그래밍의 문제를 해결하는 데 사용된다.[2][3][4]그러나 라그랑쥬의 이완을 해결하기 위해 반복적인 이완 방법이 사용되어 왔다.^[a]

정의

최소화 문제의 완화

${\displaystyle z=\min\{c(x):x\in X\subseteq \mathbf {R} ^{n}\}}$

양식의 또 다른 최소화 문제

${\displaystyle z_{R}=\min\{c_{R}(x):x\in X_{R}\subseteq \mathbf {R}^{n}\}}}$

이 두 가지 특성으로

1. ${\displaystyle X_{R}\supseteq X}$
2. ${\displaystyle {}_{}}$${\displaystyle c}$ ${\displaystyle R_{}}$( ${\displaystyle x}$) ${\displaystyle \le }$ c${\displaystyle }$( ${\displaystyle x}$) ${\displaystyle c_{R}(x)\leq c(x)}$ 모든$$ $x{\displaystyle }$) X ${\displaystyle x\in$ X$}$.

첫 번째 속성은 원래 문제의 실현 가능한 영역이 완화된 문제의 실현 가능한 영역의 부분집합이라고 명시한다.두 번째 속성은 원래 문제의 객관적 기능이 완화된 문제의 객관적 기능보다 크거나 같다고 명시한다.^[1]

특성.

If ${\displaystyle x^{*}}$ is an optimal solution of the original problem, then ${\displaystyle x^{*}\in X\subseteq X_{R}}$ and ${\displaystyle z=c(x^{*})\geq c_{R}(x^{*})\geq z_{R}}$. Therefore, ${\displaystyle x^{*}\in X_{R}}$$z{\displaystyle {}_{}}$ ${\displaystyle R_{}}$ ${\$에 상한을 제공한다$.$

$c{\displaystyle {}_{}}$ ${\displaystyle R_{}}$( ${\displaystyle x}$)${\displaystyle }$= ${\displaystyle c}$ (${\displaystyle x}$ ) = c ( x${\displaystyle }$) ${\displaystyle c_{R}(x)($x)=$c($x$)\},{\displaystyle \mathrm{}}$$$${\displaystyle \in }$ x {$$X {\$displaystyle \forall$x\in $X},$holds ${\displaystyle x}$}, 만약 완화 문제에 대한 최적의 해결책이 원래 문제에 대해 실현 가능하다면, 그러면 원래의 문제에 최적이다.^[1]

약간의 휴식 기법

• 선형 프로그래밍 이완
• 라그랑의 휴식
• 반피니트 이완
• 대리 이완과 이중성

메모들

참조

• Buttazzo, G. (1989). Semicontinuity, Relaxation and Integral Representation in the Calculus of Variations. Pitman Res. Notes in Math. 207. Harlow: Longmann.
• Geoffrion, A. M. (1971). "Duality in Nonlinear Programming: A Simplified Applications-Oriented Development". SIAM Review. 13 (1): 1–37. JSTOR 2028848.
• Goffin, J.-L. (1980). "The relaxation method for solving systems of linear inequalities". Math. Oper. Res. 5 (3): 388–414. doi:10.1287/moor.5.3.388. JSTOR 3689446. MR 0594854.
• Minoux, M. (1986). Mathematical programming: Theory and algorithms. Chichester: A Wiley-Interscience Publication. John Wiley & Sons. ISBN 978-0-471-90170-9. MR 0868279. Steven Vajda가 번역함
• Murty, Katta G. (1983). "16 Iterative methods for linear inequalities and linear programs (especially 16.2 Relaxation methods, and 16.4 Sparsity-preserving iterative SOR algorithms for linear programming)". Linear programming. New York: John Wiley & Sons. ISBN 978-0-471-09725-9. MR 0720547.
• Nemhauser, G. L.; Rinnooy Kan, A. H. G.; Todd, M. J., eds. (1989). Optimization. Handbooks in Operations Research and Management Science. Vol. 1. Amsterdam: North-Holland Publishing Co. ISBN 978-0-444-87284-5. MR 1105099.
  • W. R. 풀리블랭크, 다면 결합제(pp. 371–446);
  • 조지 L.넴하우저와 로렌스 A.Wolsey, 정수 프로그래밍(pp. 447–527);
  • Claude Lemaréchal, 비차별적 최적화(pp. 529–572);
• Rardin, Ronald L. (1998). Optimization in operations research. Prentice Hall. ISBN 978-0-02-398415-0.
• Roubíček, T. (1997). Relaxation in Optimization Theory and Variational Calculus. Berlin: Walter de Gruyter. ISBN 978-3-11-014542-7.