2차 프로그래밍

2차 프로그래밍(QP)은 2차 함수를 포함하는 특정 수학적 최적화 문제를 해결하는 과정입니다.특히 변수에 대한 선형 제약 조건이 따르는 다변량 이차 함수를 최적화(최소화 또는 최대화)하려고 합니다.2차 프로그래밍은 비선형 프로그래밍의 한 유형입니다.

여기서 '프로그래밍'은 수학 문제를 푸는 형식적인 절차를 말합니다.이 사용법은 1940년대로 거슬러 올라가며, "컴퓨터 프로그래밍"이라는 최근의 개념과는 특별히 관련이 없습니다.혼란을 피하기 위해 일부 실무자들은 "최적화", 예를 들어 "2차 ^[1]최적화"라는 용어를 선호합니다.

문제공식화

n개의 $변수$ 와 m개의 제약 조건을 $갖는$ 2차 프로그래밍 문제는 ^[2]다음과 같이 공식화될 수 있습니다.주어진:

실수 값 n차원 $벡터$ c,
$n \times$ n차원 실수 대칭 $행렬$ Q,
$m \times$ n차원 실수 $행렬$ A, 및
m차원 실수 $벡터$ b,

2차 프로그래밍의 목적은 n차원 $벡터$ x를 찾는 것입니다.

최소화하다	${\tfrac {1}{2}}\mathbf {x} ^{\mathrm {T} }Q\mathbf {x} +\mathbf {c} ^{\mathrm {T}\mathbf {x}$
의 대상이 되는	$A\mathbf {x} \preceq \mathbf {b},$

$여기$ 서 x는 x의 $벡터$ 전치를 나타내고, $표기$ Ax ⪯ $b$ 는 $벡터$ Ax의 모든 항목이 $벡터$ b의 해당 항목보다 작거나 같다는 것을 의미합니다(성분별 부등식).

최소제곱

대칭적인 양-정의 값일 때 특수한 경우로, 비용 함수는 최소 제곱으로 줄어듭니다.

최소화하다	${\tfrac {1}{2}}\R\mathbf {x} -\mathbf {d} \^{2}$
의 대상이 되는	$A\mathbf {x} \preceq \mathbf {b},$

$여기$ 서 Q = $RR$ 은 $Q$ 와 $c$ = $-Rd$ 의 촐레스키 분해로부터 따릅니다. 반대로, 그러한 제한된 최소 제곱 프로그램은 일반적인 $비제곱$ R 행렬에 대해서도 2차 프로그래밍 문제로서 동등하게 프레임화될 수 있습니다.

일반화

일부 $기준점 0$ x의 $이웃$ 에서 함수 f를 최소화할 $때$ Q는 Hessian $행렬$ H $(f (x 0))$ 로 $설정$ 되고 c는 기울기 $θf (x 0)$ 로 설정됩니다.관련 프로그래밍 문제인 2차 제약 2차 프로그래밍은 변수에 2차 제약을 추가하여 제기할 수 있습니다.

해결방법

일반적인 문제의 경우 다음을 포함한 다양한 방법이 일반적으로 사용됩니다.

인테리어 포인트,
활성 집합,^[3]
증강 라그랑지안,^[4]
켤레 구배,
경사 투영,
심플렉스 ^[3]알고리즘의 확장입니다.

Q가 양의 확정인 경우, 문제는 볼록 최적화의 더 일반적인 필드의 특별한 경우입니다.

등속 제약 조건

Q가 양의 정(正)이고 동일한 제약 조건만 있는 $경우$ 에는 2차 프로그래밍이 특히 간단합니다. 구체적으로 솔루션 프로세스는 선형입니다.라그랑주 승수를 사용하고 라그랑주의 극한을 구함으로써, 등속 제한 문제의 해결책을 쉽게 보여줄 수 있습니다.

{\text{Minimize}}\quad {\tfrac {1}{2}}\mathbf {x} ^{\mathrm {T} }Q\mathbf {x} +\mathbf {c} ^{\mathrm {T}\mathbf {x}

{\text{subject to}}\mathbf {x} =\mathbf {d}

선형 시스템에 의해 주어집니다.

{\begin{bmatrix}Q&E^{\top }\\E&0\end{bmatrix}}{\begin{bmatrix}\mathbf {x} \\mathbf \end{bmatrix}}={\mathbf {c} \\mathbf {d} \end{bmatrix}

여기서 $ρ$ 는 x와 $함께$ 해에서 나오는 라그랑주 승수의 집합입니다.

이 시스템에 접근하는 가장 쉬운 방법은 직접 솔루션(예: LU 인수분해)이며, 이 솔루션은 작은 문제에도 매우 실용적입니다.큰 문제의 경우 시스템은 몇 가지 특이한 문제를 제기하며, 특히 문제가 결코 양의 확정적이지 않기 때문에(Q가 그렇다 $하더라도$ ) 잠재적으로 좋은 수치 접근법을 찾기가 매우 어려우며, 문제에 의존하여 선택할 수 있는 많은 접근법이 있습니다.

제약 조건이 변수를 너무 엄격하게 결합하지 않는 경우, 비교적 간단한 공격은 제약 조건이 무조건 충족되도록 변수를 변경하는 것입니다.예를 들어 = $0$ 이라고 $가정$ 합니다(0이 아닌 경우로 일반화하는 것은 간단합니다).제약 조건 방정식을 살펴봅니다.

E\mathbf {x} =0

에 의해 정의된 새로운 $변수$ 를 도입합니다.

Z\mathbf {y} =\mathbf {x}

$여기$ 서 y는 x의 $차원$ 에서 제약 조건의 수를 뺀 값을 갖습니다.그리고나서

EZ\mathbf {y} =\mathbf {0}

$EZ$ = 0이 $되도록$ $Z$ 를 선택하면 제약식은 항상 충족됩니다. $이러한$ Z를 찾는 것은 E의 $널$ 공간을 찾는 것을 수반하는데, E의 $구조$ 에 따라 다소 단순합니다.2차 형식에 대입하면 제약 없는 최소화 문제가 발생합니다.

{\tfrac {1}{2}}\mathbf {x} ^{\top}}Q\mathbf {x} +\mathbf {c} ^{\top}}\mathbf {x}\quad \imes \quad {\tfrac {1}{2}\mathbf {y} ^{\top }Z^{\top }QZ\mathbf {y} +\left(Z^{\top } \right)^{\top }\mathbf {y}

그 해결책은 다음과 같이 제시됩니다.

Z^{\top}}QZ\mathbf {y} =-Z^{\top}\mathbf {c}

Q의 $특정$ 조건에서 감소된 $행렬 T$ ZQZ는 양의 확정 행렬이 됩니다. $Z$ 의 ^[5]명시적인 계산을 회피하는 공액 구배법에 대한 변형을 작성할 수 있습니다.

라그랑주 이중성

2차 프로그래밍 문제의 라그랑지안 이중성도 2차 프로그래밍 문제입니다.이것을 보기 위해서 c = $0$ 이고 Q가 양의 정인 $경우$ 에 초점을 두자.우리는 라그랑지안 함수를 다음과 같이 씁니다.

L(x,\lambda )={\tfrac {1}{2}}x^{\top }Qx+\lambda^{\top }(Ax-b)

(라그랑지안) 이중 $함수$ g $($ λ $)$ 를 $g(\lambda )=\inf _{x}L(x,\lambda )$ g (λ $g(\lambda )=\inf _{x}L(x,\lambda )$ = $g(\lambda )=\inf _{x}L(x,\lambda )$ x $g(\lambda )=\inf _{x}L(x,\lambda )$ ( $g(\lambda )=\inf _{x}L(x,\lambda )$ λ ) $g(\lambda )=\inf _{x}L(x,\lambda )$ {\ $displaystyle$ g $(\$ lambda ) =\ $inf$ _ ${x}L(x,\lambda$ 로 정의하면 ∇ $\nabla _{x}L(x,\lambda )=0$ L ( $\nabla _{x}L(x,\lambda )=0$ λ ) = $\nabla _{x}L(x,\lambda )=0$ {\ $displaystyle \nabla$ _ ${x}L(x,\lambda$ ) = $0}$ 을 사용하여 최소 $L$ 을 찾을 수 있습니다.

x^{*}=-Q^{-1}A^{\top}\smooth .

따라서 이중함수는

g(\displaystyle g)=-{\tfrac {1}{2}}\display^{\top}AQ^{-1}A^{\top}}\displaystyle -\display^{\top}b,

따라서 2차 프로그래밍 문제의 라그랑지안 쌍성은

{\text{maximize}}_{\lambda \geq 0}\quad - {\tfrac {1}{2}}\lambda ^{\top}AQ^{-1}\lambda -\lambda ^{\top}b.

라그랑주 이중성 이론 외에도 다른 이중성 쌍들(예: 울프 등)이 있습니다.

복잡성

양의 $정$ Q의 경우, 타원체 방법은 다항식 ^[6]시간에 문제를 해결합니다. $반면$ 에 Q가 부정이면 문제는 ^[7]NP-hard입니다.이러한 비볼록 문제에 대해 몇 가지 정지 지점과 로컬 최소값이 있을 수 있습니다.실제로 Q가 음의 고유값을 하나만 $갖더라도$ 문제는 (강력하게) ^[8]NP-hard입니다.

정수 제약 조건

$벡터$ x의 하나 이상의 요소가 정수 값을 차지해야 하는 경우가 있습니다.이것은 혼합 정수 2차 프로그래밍(MIQP) ^[9]문제의 공식화로 이어집니다.MIQP의 적용은 수자원과^[10] 인덱스 ^[11]펀드의 구축을 포함합니다.

해결사 및 스크립트(프로그래밍) 언어

이름.	간략정보
AIMMS	최적화 및 스케줄링 문제 모델링 및 해결을 위한 소프트웨어 시스템
알글리브	이중 라이센스(GPL/프라이빗) 수치 라이브러리(C++, .NET).
AMPL	대규모 수학적 최적화를 위해 널리 사용되는 모델링 언어입니다.
AP 모니터	MATLAB과 Python에서 LP, QP, NLP, MILP, MINLP 및 DAE 시스템을 위한 모델링 및 최적화 스위트.
아틀리스 니트로	비선형 최적화를 위한 통합 패키지
CGAL	2차 프로그래밍 솔버를 포함하는 오픈 소스 계산 지오메트리 패키지.
CPLEX	API(C, C++, Java, .Net, Python, Matlab 및 R)를 갖춘 인기 있는 해결사.학자금 무료입니다.
Excel Solver 기능	함수 평가가 셀 재계산을 기반으로 하는 스프레드시트로 조정된 비선형 해결기입니다.Excel의 표준 추가 기능으로 제공되는 기본 버전.
GAMS	수학적 최적화를 위한 고난이도 모델링 시스템
GNU 옥타브	MATLAB과 유사한 수치 컴퓨팅을 위한 무료 범용 및 매트릭스 지향 프로그래밍 언어(라이선스는 GPLv3).GNU Octave의 2차 프로그래밍은 qp 명령을 통해 사용할 수 있습니다.
하이 GHS	선형 프로그래밍(LP), 혼합 정수 프로그래밍(MIP) 및 볼록 2차 프로그래밍(QP) 모델을 해결하기 위한 오픈 소스 소프트웨어
IMSL	프로그래머들이 소프트웨어 응용 프로그램에 내장할 수 있는 수학적 및 통계적 함수의 집합입니다.
IPOPT	IPOPT(Interior Point Optimizer)는 대규모 비선형 최적화를 위한 소프트웨어 패키지입니다.
메이플	수학을 위한 범용 프로그래밍 언어.Maple의 2차 문제 해결은 QPsolve 명령을 통해 이루어집니다.
매트랩	수치 계산을 위한 범용 및 행렬 지향 프로그래밍 언어.MATLAB에서 2차 프로그래밍을 하려면 기본 MATLAB 제품 외에 Optimization Toolbox가 필요합니다.
마테마티카	기호 및 숫자 기능을 포함한 수학을 위한 범용 프로그래밍 언어입니다.
모섹	여러 언어(C++, Java, .Net, Matlab 및 Python)용 API를 통해 대규모 최적화를 위한 솔루션입니다.
NAG 수치 도서관	여러 프로그래밍 언어(C, C++, Fortran, Visual Basic, Java 및 C#) 및 패키지(MATLAB, Excel, R, LabVIEW)를 위해 Numerical Algorithms Group이 개발한 수학 및 통계 루틴 모음.NAG 라이브러리의 최적화 장에는 희소 선형 제약 행렬과 희소하지 않은 선형 제약 행렬이 모두 있는 2차 프로그래밍 문제에 대한 루틴과 함께 비선형, 경계 또는 제약이 없는 선형 또는 비선형 함수의 제곱합을 최적화하기 위한 루틴이 포함되어 있습니다.NAG 라이브러리에는 로컬 및 글로벌 최적화와 연속 또는 정수 문제에 대한 루틴이 있습니다.
파이썬	대부분의 사용 가능한 해결사를 위한 바인딩이 포함된 고급 프로그래밍 언어입니다.2차 프로그래밍은 solve_qp 함수를 통해 또는 특정 솔버를 직접 호출하여 사용할 수 있습니다.
R(포트란)	GPL 라이선스된 범용 크로스 플랫폼 통계 계산 프레임워크.
SAS/OR	선형, 정수, 비선형, 도함수-자유(Derivative-Free), 네트워크, 조합 및 제약 최적화를 위한 해결사 모음, 대수 모델링 언어 OPTMODEL, 특정 문제/시장을 겨냥한 다양한 수직 솔루션, 이 모든 것이 SAS 시스템과 완전히 통합되어 있습니다.
쑤안슈	자바에서 LP, QP, SOCP, SDP, SQP를 해결하기 위한 오픈 소스 최적화 알고리즘 모음
티케이솔버	Universal Technical Systems, Inc.에서 상용화한 선언적 규칙 기반 언어 기반의 수학적 모델링 및 문제 해결 소프트웨어 시스템.
톰랩	MATLAB에 대해 전역 최적화, 정수 프로그래밍, 모든 유형의 최소 제곱, 선형, 2차 및 비제약 프로그래밍을 지원합니다.TOMLAB은 CPLEX, SNOPT, KNITRO와 같은 해결사를 지원합니다.
XPRESS	대규모 선형 프로그램, 2차 프로그램, 일반 비선형 및 혼합 정수 프로그램을 위한 해결사.여러 프로그래밍 언어에 대한 API를 보유하고 있으며, 모델링 언어 모젤을 보유하고 있으며 AMPL, GAMS와 협력하고 있습니다. 학술적으로 무료입니다.

참고 항목

참고문헌

^ Wright, Stephen J. (2015), "Continuous Optimization (Nonlinear and Linear Programming)", in Nicholas J. Higham; et al. (eds.), The Princeton Companion to Applied Mathematics, Princeton University Press, pp. 281–293
^ Nocedal, Jorge; Wright, Stephen J. (2006). Numerical Optimization (2nd ed.). Berlin, New York: Springer-Verlag. p. 449. ISBN 978-0-387-30303-1..
^ ^a ^b Murty, Katta G. (1988). Linear complementarity, linear and nonlinear programming. Sigma Series in Applied Mathematics. Vol. 3. Berlin: Heldermann Verlag. pp. xlviii+629 pp. ISBN 978-3-88538-403-8. MR 0949214. Archived from the original on 2010-04-01.
^ Delbos, F.; Gilbert, J.Ch. (2005). "Global linear convergence of an augmented Lagrangian algorithm for solving convex quadratic optimization problems" (PDF). Journal of Convex Analysis. 12: 45–69. Archived (PDF) from the original on 2022-10-09.
^ Gould, Nicholas I. M.; Hribar, Mary E.; Nocedal, Jorge (April 2001). "On the Solution of Equality Constrained Quadratic Programming Problems Arising in Optimization". SIAM J. Sci. Comput. 23 (4): 1376–1395. CiteSeerX 10.1.1.129.7555. doi:10.1137/S1064827598345667.
^ Kozlov, M. K.; S. P. Tarasov; Leonid G. Khachiyan (1979). "[Polynomial solvability of convex quadratic programming]". Doklady Akademii Nauk SSSR. 248: 1049–1051. 번역:{{cite journal}} 누락 또는 비어있음 (도움말)
^ Sahni, S. (1974). "Computationally related problems" (PDF). SIAM Journal on Computing. 3 (4): 262–279. CiteSeerX 10.1.1.145.8685. doi:10.1137/0203021.
^ Pardalos, Panos M.; Vavasis, Stephen A. (1991). "Quadratic programming with one negative eigenvalue is (strongly) NP-hard". Journal of Global Optimization. 1 (1): 15–22. doi:10.1007/bf00120662. S2CID 12602885.
^ Lazimy, Rafael (1982-12-01). "Mixed-integer quadratic programming". Mathematical Programming. 22 (1): 332–349. doi:10.1007/BF01581047. ISSN 1436-4646. S2CID 8456219.
^ Propato Marco; Uber James G. (2004-07-01). "Booster System Design Using Mixed-Integer Quadratic Programming". Journal of Water Resources Planning and Management. 130 (4): 348–352. doi:10.1061/(ASCE)0733-9496(2004)130:4(348).
^ Cornuéjols, Gérard; Peña, Javier; Tütüncü, Reha (2018). Optimization Methods in Finance (2nd ed.). Cambridge, UK: Cambridge University Press. pp. 167–168. ISBN 9781107297340.

추가열람

Cottle, Richard W.; Pang, Jong-Shi; Stone, Richard E. (1992). The linear complementarity problem. Computer Science and Scientific Computing. Boston, MA: Academic Press, Inc. pp. xxiv+762 pp. ISBN 978-0-12-192350-1. MR 1150683.
Garey, Michael R.; Johnson, David S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. ISBN 978-0-7167-1045-5. A6: MP2, 페이지 245.
Gould, Nicholas I. M.; Toint, Philippe L. (2000). "A Quadratic Programming Bibliography" (PDF). RAL Numerical Analysis Group Internal Report 2000-1.

외부 링크

[PrincetonCompanion-1] Wright, Stephen J. (2015), "Continuous Optimization (Nonlinear and Linear Programming)", in Nicholas J. Higham; et al. (eds.), The Princeton Companion to Applied Mathematics, Princeton University Press, pp. 281–293

[2] Nocedal, Jorge; Wright, Stephen J. (2006). Numerical Optimization (2nd ed.). Berlin, New York: Springer-Verlag. p. 449. ISBN 978-0-387-30303-1..

[ioe.engin.umich-3] Murty, Katta G. (1988). Linear complementarity, linear and nonlinear programming. Sigma Series in Applied Mathematics. Vol. 3. Berlin: Heldermann Verlag. pp. xlviii+629 pp. ISBN 978-3-88538-403-8. MR 0949214. Archived from the original on 2010-04-01.

[4] Delbos, F.; Gilbert, J.Ch. (2005). "Global linear convergence of an augmented Lagrangian algorithm for solving convex quadratic optimization problems" (PDF). Journal of Convex Analysis. 12: 45–69. Archived (PDF) from the original on 2022-10-09.

[5] Gould, Nicholas I. M.; Hribar, Mary E.; Nocedal, Jorge (April 2001). "On the Solution of Equality Constrained Quadratic Programming Problems Arising in Optimization". SIAM J. Sci. Comput. 23 (4): 1376–1395. CiteSeerX 10.1.1.129.7555. doi:10.1137/S1064827598345667.

[6] Kozlov, M. K.; S. P. Tarasov; Leonid G. Khachiyan (1979). "[Polynomial solvability of convex quadratic programming]". Doklady Akademii Nauk SSSR. 248: 1049–1051. 번역:{{cite journal}} 누락 또는 비어있음 (도움말)

[7] Sahni, S. (1974). "Computationally related problems" (PDF). SIAM Journal on Computing. 3 (4): 262–279. CiteSeerX 10.1.1.145.8685. doi:10.1137/0203021.

[8] Pardalos, Panos M.; Vavasis, Stephen A. (1991). "Quadratic programming with one negative eigenvalue is (strongly) NP-hard". Journal of Global Optimization. 1 (1): 15–22. doi:10.1007/bf00120662. S2CID 12602885.

[9] Lazimy, Rafael (1982-12-01). "Mixed-integer quadratic programming". Mathematical Programming. 22 (1): 332–349. doi:10.1007/BF01581047. ISSN 1436-4646. S2CID 8456219.

[10] Propato Marco; Uber James G. (2004-07-01). "Booster System Design Using Mixed-Integer Quadratic Programming". Journal of Water Resources Planning and Management. 130 (4): 348–352. doi:10.1061/(ASCE)0733-9496(2004)130:4(348).

[11] Cornuéjols, Gérard; Peña, Javier; Tütüncü, Reha (2018). Optimization Methods in Finance (2nd ed.). Cambridge, UK: Cambridge University Press. pp. 167–168. ISBN 9781107297340.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

v t 상보성 문제 및 알고리즘
상보성 문제	선형 프로그래밍(LP) 2차 프로그래밍(QP) 선형보상성문제(LCP) 혼합 선형(MLCP) 혼합(MCP) 비선형(NCP)
기저 교환 알고리즘	심플렉스(단치히) 수정 심플렉스 크로스 크로스 렘케

Search