선형-수축 프로그래밍

수학적 최적화에서 선형-굴절 프로그래밍(LFP)은 선형 프로그래밍(LP)의 일반화다.선형 프로그램의 객관적 함수는 선형 함수인 반면, 선형 굴절 프로그램에서의 객관적 함수는 두 개의 선형 함수의 비율이다.선형 프로그램은 분모가 상수함수 1인 선형 굴절 프로그램의 특수한 경우라고 볼 수 있다.

선형 프로그래밍과의 관계

선형 프로그래밍과 선형 굴절 프로그래밍은 모두 선형 방정식과 선형 불평등을 사용한 최적화 문제를 나타내며, 각 문제-인스턴스에 대해 실현 가능한 집합을 정의한다.분수 선형 프로그램은 보다 풍부한 객관적 기능들을 가지고 있다.비공식적으로, 선형 프로그래밍은 최대 이익이나 최저 비용과 같은 최상의 결과를 제공하는 정책을 계산한다.이와는 대조적으로, 선형 굴절 프로그래밍은 가장 높은 효율을 나타내는 비율인 비용 대 결과의 가장 높은 비율을 달성하기 위해 선형 굴절 프로그래밍을 사용한다.예를 들어, LP의 맥락에서 우리는 객관적 기능 이익 = 수익 - 원가를 최대화하며 최대 100원(수익의 1100원 - 원가의 1000원)의 이익을 얻을 수 있다.따라서 LP에서는 100원/\1000원 = 0.1의 효율성을 갖는다.LFP를 사용하면 10달러/\$50 = 0.2의 효율을 얻을 수 있고 10달러의 이익만 얻을 수 있지만 50달러의 투자만 필요하다.

정의

형식적으로, 선형 굴절 프로그램은 다면체에 대한 아핀 함수의 비율을 최대화(또는 최소화)하는 문제로 정의된다.

${\displaystyle {\begin{aligned}{\text{maximize}}\quad &{\frac {\mathbf {c} ^{T}\mathbf {x} +\alpha }{\mathbf {d} ^{T}\mathbf {x} +\beta }}\\{\text{subject to}}\quad &A\mathbf {x} \leq \mathbf {b} ,\end{aligned}}}$

where ${\displaystyle \mathbf {x} \in \mathbb {R} ^{n}}$ represents the vector of variables to be determined, ${\displaystyle \mathbf {c} ,\mathbf {d} \in \mathbb {R} ^{n}}$ and ${\displaystyle \mathbf {b} \in \mathbb {R} ^{m}}$ are vectors of (known) coefficients, ${\displaystyle A\in {\mathbb{R}}^{}}$${\displaystyle m^{}}$ ${\displaystyle {\times }^{}}$ ${\displaystyle n^{}}$ ${\$은(는) 계수의 (알려진) 행렬이고 $\alpha {\displaystyle }$, ${\displaystyle \beta }$ ${\displaystyle \in }$ ${\displaystyle R\mathbb{}}$ ${\$은 상수이다$$.제약조건은 실현 가능한 영역을{ x +> ${\dstyle \{\mathbf {x} \mathbf {d} ^{T}\mathbf {x} +\beta >0\}$로 제한해야 한다 즉, 분모가 양의 영역이다.^[1][2]또는 목표함수의 분모는 실현 가능한 전체 영역에서 엄격히 음수여야 한다.

선형 프로그램으로 변환

실현 가능한 지역이 비어 있지 않고 한정되어 있다는 가정 하에, 카네스-쿠퍼 변환^[1].

${\displaystyle \mathbf {y} ={\frac {1}{\mathbf {d} ^{T}\mathbf {x} +\beta }}\cdot \mathbf {x} \;\\t={\frac {1}{{t}\mathbf {x} +bf}}}}}}}}}}}}}}}}}}\beta}}}}}}}}}}}}}}}}}}}}}}}}}}}}}$

위의 선형 프로그램을 등가 선형 프로그램으로 변환:

${\displaystyle {\begin{aligned}{\text{maximize}}\quad &\mathbf {c} ^{T}\mathbf {y} +\alpha t\\{\text{subject to}}\quad &A\mathbf {y} \leq \mathbf {b} t\\&\mathbf {d} ^{T}\mathbf {y} +\beta t=1\\&t\geq 0.\end{정렬}}}$

그런 $다음{\displaystyle \mathbf{}}$ y$${\$displaystyle \mathbf {y}$ $및$ t$${\$displaystyle t}$에 대한 솔루션으로 원래 문제의 해결 방법을 다음과 같이 산출한다$$.

${\displaystyle \mathbf {x} ={\frac {1}{t}}\mathbf {y} .}$

이중성

Let the dual variables associated with the constraints ${\displaystyle A\mathbf {y} -\mathbf {b} t\leq \mathbf {0} }$ and ${\displaystyle \mathbf {d} ^{T}\mathbf {y} +\beta t-1=0}$ be denoted by ${\displaystyle \mathbf {u} }$ and ${\displaystyle \lambda }$, respectively.그렇다면 위의 LFP의 이중은 다음과 같다.

${\displaystyle {\begin{aigned}{\text{minimize}\quad &\lambda \\text{data}}}\quad &A^{data.T}\mathbf {u} +\lambda \mathbf {d} =\mathbf {c} \\&-\mathbf {b} ^{T}\mathbf {u} +\lambda \beta \geq \alpha \\&\mathbf {u} \in \mathbb {R} _{+}^{m},\lambda \in \mathbb {R} ,\end{aligned}}}$

이것은 LP이고 Charnes-Cooper 변환에 따른 등가 선형 프로그램의 이중과 일치한다.

속성 및 알고리즘

선형 굴절 문제에서 객관적 함수는 단조특성인 유사성인 퀘이콘케이브와 퀘이콘벡스(hence quasilinar) 둘 다로 퀘이콘벡스보다 강한 성질이다.선형 굴절 목적 함수는 유사수축과 유사수축으로, 따라서 유사수축이다.LFP는 LP로 변환할 수 있기 때문에 심플렉스 알고리즘(조지 B의) 등 어떤 LP 솔루션 방식으로도 해결할 수 있다. 단치히),^[5][6][7][8] 크리스크로스 알고리즘 ^[9]또는 내부 포인트 방법.

메모들

참조

• Craven, B. D. (1988). Fractional programming. Sigma Series in Applied Mathematics. Vol. 4. Berlin: Heldermann Verlag. p. 145. ISBN 978-3-88538-404-5. MR 0949209.
• Illés, Tibor; Szirmai, Ákos; Terlaky, Tamás (1999). "The finite criss-cross method for hyperbolic programming". European Journal of Operational Research. 114 (1): 198–214. CiteSeerX 10.1.1.36.7090. doi:10.1016/S0377-2217(98)00049-6. Zbl 0953.90055. Postscript preprint.
• Kruk, Serge; Wolkowicz, Henry (1999). "Pseudolinear programming". SIAM Review. 41 (4): 795–805. doi:10.1137/S0036144598335259. JSTOR 2653207. MR 1723002.
• Mathis, Frank H.; Mathis, Lenora Jane (1995). "A nonlinear programming algorithm for hospital management". SIAM Review. 37 (2): 230–234. doi:10.1137/1037046. JSTOR 2132826. MR 1343214.
• Murty, Katta G. (1983). "3.10 Fractional programming (pp. 160–164)". Linear programming. New York: John Wiley & Sons, Inc. pp. xix+482. ISBN 978-0-471-09725-9. MR 0720547.

추가 읽기

• Bajalinov, E. B. (2003). Linear-Fractional Programming: Theory, Methods, Applications and Software. Boston: Kluwer Academic Publishers.
• Barros, Ana Isabel (1998). Discrete and fractional programming techniques for location models. Combinatorial Optimization. Vol. 3. Dordrecht: Kluwer Academic Publishers. pp. xviii+178. ISBN 978-0-7923-5002-6. MR 1626973.
• Martos, Béla (1975). Nonlinear programming: Theory and methods. Amsterdam-Oxford: North-Holland Publishing Co. p. 279. ISBN 978-0-7204-2817-9. MR 0496692.
• Schaible, S. (1995). "Fractional programming". In Reiner Horst and Panos M. Pardalos (ed.). Handbook of global optimization. Nonconvex optimization and its applications. Vol. 2. Dordrecht: Kluwer Academic Publishers. pp. 495–608. ISBN 978-0-7923-3120-9. MR 1377091.
• Stancu-Minasian, I. M. (1997). Fractional programming: Theory, methods and applications. Mathematics and its applications. Vol. 409. Translated by Victor Giurgiutiu from the 1992 Romanian. Dordrecht: Kluwer Academic Publishers Group. pp. viii+418. ISBN 978-0-7923-4580-0. MR 1472981.

소프트웨어

• WinGULF – 특수 옵션(선행, 가격, 분기 변수 등)이 많은 교육용 인터렉티브 선형 및 선형 추출 프로그래밍 솔루션
• JOptimizer – Java 볼록 최적화 라이브러리(오픈 소스)