맨위로가기

2차 계획법

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
목차

1. 개요

2차 계획법은 선형 제약 조건 하에서 2차 함수를 최적화하는 수학적 최적화 문제이다. 문제 정의는 실수 벡터, 대칭 행렬, 행렬, 벡터를 사용하여 최소화 또는 최대화할 2차 함수와 제약 조건으로 구성된다. 2차 계획법은 내점법, 활성 집합 방법 등 다양한 해법을 통해 해결되며, Q 행렬이 양의 정부호 행렬인 경우 볼록 최적화의 특수한 경우로 볼 수 있다. 혼합 정수 2차 계획법(MIQP)은 변수 중 일부가 정수 값을 가져야 하는 경우에 적용되며, 수자원 관리 및 인덱스 펀드 구축 등에 활용된다. 2차 계획법 문제를 해결하기 위한 상용 및 오픈 소스 소프트웨어와 라이브러리가 다양하게 존재한다.

더 읽어볼만한 페이지

  • 최적화 알고리즘 및 방법 - 신뢰 영역
    신뢰 영역 방법은 비선형 최적화에서 함수의 모델을 신뢰할 수 있는 영역 내에서만 사용하여 최적화를 수행하는 방법으로, 다양한 분야에서 전역 최적해를 찾기 위한 도구로 활용된다.
  • 최적화 알고리즘 및 방법 - 확률적 계획법
    확률적 계획법은 불확실한 상황에서 최적의 의사 결정을 내리기 위한 수학적 방법론으로, 다양한 확률적 프로그래밍 기법을 포함하며, 생물학, 경제, 금융 공학 등 여러 분야에 응용된다.

2. 문제 정의

실수 값을 갖는 n차원 벡터 '''c''', ''n''×''n''차원 실수 대칭 행렬 Q, ''m''×''n''차원 실수 행렬 A, 그리고 ''m''차원 실수 벡터 '''b'''가 주어졌을 때, 2차 계획법의 목표는 다음 식을 최소화하는 n차원 벡터 '''x'''를 찾는 것이다.[2][16]

최소화\tfrac{1}{2} \mathbf{x}^\mathrm{T} Q\mathbf{x} + \mathbf{c}^\mathrm{T} \mathbf{x}
제약 조건A \mathbf{x} \preceq \mathbf{b},



여기서 '''x'''T는 벡터 '''x'''의 전치 행렬을 나타내며, ''A'''''x''' ⪯ '''b'''는 벡터 ''A'''''x'''의 모든 항목이 벡터 '''b'''의 해당 항목보다 작거나 같다는 것을 의미한다(성분별 부등식).

이차 제약 이차 계획법은 2차 계획법에서 2차 제약이 추가된 확장된 형태이다.

2. 1. 기본 형태

Quadratic programming영어(QP)는 n개의 변수와 m개의 제약 조건을 갖는 최적화 문제이며, 다음과 같이 공식화될 수 있다.[2]

주어진 조건은 다음과 같다.

  • 실수 값을 갖는 n차원 벡터 '''c''',
  • n × n 차원 실수 대칭 행렬 Q,
  • m × 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'''T는 벡터 '''x'''의 전치 행렬을 나타내며, 표기법 A'''x''' ⪯ '''b'''는 벡터 A'''x'''의 모든 항목이 벡터 '''b'''의 해당 항목보다 작거나 같다는 것을 의미한다(성분별 부등식).[16]

2. 2. 일반화

2차 계획법은 2차 제약 조건을 추가하여 확장될 수 있다. (2차 제약 2차 계획법)[2] 어떤 기준점 \mathbf{x}_0 근방에서 함수 f를 최소화할 때, Q는 헤세 행렬 \mathbf{H}(f(\mathbf{x}_0))로, \mathbf{c}는 기울기 \nabla f(\mathbf{x}_0)로 설정된다. 관련 프로그래밍 문제인 2차 제약 2차 계획법은 변수에 2차 제약을 추가하여 제시할 수 있다.[16]

3. 해법

2차 계획법 문제를 해결하기 위한 다양한 알고리즘이 존재한다. 일반적인 해법으로는 다음 방법들이 주로 사용된다.[3][4]


  • 내점법
  • 활성 집합 방법
  • 확장 라그랑지안 방법
  • 켤레 기울기 방법
  • 기울기 투영법
  • 단순법의 확장


만약 Q가 양의 정부호 행렬이면, 이 문제는 볼록 최적화의 특수한 사례가 된다.

3. 1. 일반적인 해법


  • 내점법
  • 활성 집합 방법[3]
  • 확장 라그랑지안 방법[4]
  • 켤레 기울기 방법
  • 기울기 투영법
  • 단순법의 확장[3]


가 양의 정부호 행렬인 경우, 이 문제는 보다 일반적인 볼록 최적화 분야의 특수한 사례이다.

3. 2. 등식 제약 조건만 있는 경우

Q가 양의 정부호 행렬이고 등식 제약 조건만 있는 경우, 2차 계획법 문제는 선형 시스템으로 변환되어 효율적으로 해결할 수 있다. 라그랑주 승수법을 사용하여 라그랑지안 함수의 극값을 구한다.

다음과 같은 형태의 최적화 문제를 생각해보자.

:\text{최소화} \quad \tfrac{1}{2} \mathbf{x}^\mathrm{T} Q\mathbf{x} + \mathbf{c}^\mathrm{T} \mathbf{x}

:\text{제약 조건} \quad E\mathbf{x} =\mathbf{d}

이 문제의 해는 다음 선형 시스템으로 주어진다.

:

\begin{bmatrix}

Q & E^\top \\

E & 0

\end{bmatrix}

\begin{bmatrix} \mathbf x \\ \lambda \end{bmatrix}

=

\begin{bmatrix} -\mathbf c \\ \mathbf d \end{bmatrix}



여기서 \lambda는 라그랑주 승수의 집합이며, \mathbf{x}와 함께 해로 얻어진다.

이 시스템을 푸는 가장 쉬운 방법은 LU 분해와 같은 직접 해법이며, 작은 문제에서는 매우 실용적이다. 큰 문제의 경우, 이 시스템은 몇 가지 어려움을 야기한다. 특히 Q가 양의 정부호 행렬이더라도, 이 문제는 양의 정부호 행렬이 아니라는 점이 수치적 접근을 어렵게 만든다. 문제에 따라 다양한 접근 방식이 존재한다.[5][19]

제약 조건이 변수들을 너무 꽉 묶지 않는다면, 변수를 변경하여 제약 조건이 항상 만족되도록 하는 방법이 있다. 예를 들어, \mathbf{d} = 0이라고 가정하자 (0이 아닌 경우로 일반화하는 것은 간단하다). 제약 방정식 E\mathbf{x} = 0을 고려하여, 다음과 같이 정의된 새로운 변수 \mathbf{y}를 도입한다.

:Z \mathbf{y} = \mathbf x

여기서 \mathbf{y}는 \mathbf{x}의 차원에서 제약 조건의 수를 뺀 차원을 갖는다. 그러면

:E Z \mathbf{y} = \mathbf 0

이 된다. Z를 EZ = 0이 되도록 선택하면, 제약 방정식은 항상 만족된다. 이러한 Z를 찾는 것은 E의 영공간을 찾는 것을 포함하며, 이는 E의 구조에 따라 다소 간단하다. 원래 식에 대입하면 제약 없는 최소화 문제는 다음과 같이 된다.

:\tfrac{1}{2} \mathbf{x}^\top Q\mathbf{x} + \mathbf{c}^\top \mathbf{x} \quad \implies \quad

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

이 문제의 해는 다음과 같이 주어지며,

:Z^\top Q Z \mathbf{y} = -Z^\top \mathbf{c}

Q에 대한 특정 조건 하에서, 축소된 행렬 Z^\top QZ는 양의 정부호 행렬이 된다. Z의 명시적인 계산을 피하는 켤레 기울기 방법의 변형을 작성하는 것도 가능하다.[20]

3. 3. 라그랑주 쌍대성

쌍대 문제도 참조

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) 로 정의하면, \nabla_{x} L(x,\lambda)=0과 ''Q''의 양의 정부호성을 사용하여 ''L''의 하한을 찾는다.

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

따라서 쌍대 함수는 다음과 같다.

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

그리고 2차 계획법 문제의 라그랑주 쌍대는 다음과 같다.

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

라그랑주 쌍대성 이론 외에도 다른 쌍대성 짝(예: Wolfe)이 있다.

4. 복잡도

양의 정부호 이차 형식 행렬 에 대해, 타원체법은 다항 시간 내에 2차 계획 문제를 풀 수 있다[21]。 의 부호가 부정인 경우, 2차 계획 문제는 NP-난해가 된다[22]。 실제로, 의 단 하나의 고유값만 음수이더라도, 2차 계획 문제는 NP-난해이다[23]。

4. 1. 볼록 2차 계획법

Q가 양의 정부호 행렬인 경우(볼록 문제)는 타원체 방법 등으로 다항 시간 내에 해결할 수 있다.[6][21] 예와 츠[7]는 카르마르카의 알고리즘을 선형 계획법에서 볼록 2차 계획법으로 확장하는 다항 시간 알고리즘을 제시했다. ''n''개의 변수와 ''L''개의 입력 비트를 갖는 시스템에서, 그들의 알고리즘은 O(L n)번의 반복을 필요로 하며, 각각 O(L n3)번의 산술 연산을 사용하여 총 실행 시간 복잡도는 O(''L''2 ''n''4)이다. 카푸어와 바이디아[8]는 O(''L'' * log ''L'' ''* n''3.67 * log ''n'')번의 산술 연산을 필요로 하는 또 다른 알고리즘을 제시했다.

일반적인 문제에 대해 내점법, 유효 제약법(active set)[17], 확장 라그랑주 승수법(Augmented Lagrangian method)[18], 켤레 기울기법, 기울기 투영법, 심플렉스법의 확장[17] 등 다양한 해법이 널리 사용된다. 행렬 Q가 정부호 이차 형식이면 문제는 보다 일반적인 볼록 최적화 영역의 특수한 경우가 된다.

4. 2. 비볼록 2차 계획법

Q가 부정부호 행렬인 경우(비볼록 문제) 이 문제는 NP-난해이다.[9] 비볼록 이차 제약 조건 ''xi''2 = ''xi''는 ''xi''가 {0,1}에 속한다는 것과 동일하며, 이는 ''xi''가 이진 정수 변수임을 의미한다. 따라서 이러한 제약 조건은 이진 변수를 가진 모든 정수 계획 문제를 모델링하는 데 사용될 수 있으며, 이는 NP-난해로 알려져 있다.

이러한 비볼록 문제는 여러 개의 정지점과 지역 최솟값을 가질 수 있다. Q가 단 하나의 음의 고유값만 가지더라도 문제는 (강하게) NP-난해이다.[10]

비볼록 이차 계획법의 KKT점을 찾는 것은 CLS-난해이다.[11]

5. 혼합 정수 2차 계획법 (MIQP)

벡터의 하나 이상의 요소가 정수 값을 가져야 하는 경우가 있다. 이로 인해 혼합 정수 2차 계획법(MIQP) 문제가 발생한다.[12] MIQP의 응용 분야에는 수자원[13] 및 인덱스 펀드 구축이 있다.[14]

6. 구현 및 소프트웨어

2차 계획법(QP) 문제를 해결하기 위한 다양한 상용 및 오픈 소스 소프트웨어와 라이브러리가 존재한다. 이러한 소프트웨어 및 라이브러리들은 각기 다른 기능과 특징을 가지고 있어, 사용자는 자신의 필요에 맞는 도구를 선택하여 문제를 해결할 수 있다.

6. 1. 주요 소프트웨어 및 라이브러리

이름간략 정보
AIMMS최적화 및 스케줄링 유형 문제를 모델링하고 해결하기 위한 소프트웨어 시스템이다.
ALGLIB이중 라이선스(GPL/전용) 수치 라이브러리(C++, .NET)이다.
AMPL대규모 수학적 최적화를 위한 널리 사용되는 모델링 언어이다.
APMonitorLP, QP, NLP, MILP, MINLP 및 DAE 시스템을 위한 MATLAB 및 Python의 모델링 및 최적화 제품군이다.
Artelys Knitro비선형 최적화를 위한 통합 패키지이다.
CGAL2차 계획법 솔버를 포함하는 오픈 소스 계산 기하학 패키지이다.
CPLEXAPI(C, C++, Java, .Net, Python, Matlab 및 R)가 있는 인기 있는 솔버이며, 학술용으로 무료이다.
Excel 솔버 기능함수 평가가 셀을 재계산하는 것을 기반으로 하는 스프레드시트에 맞게 조정된 비선형 솔버이며, 기본 버전은 Excel의 표준 추가 기능으로 제공된다.
GAMS수학적 최적화를 위한 고급 모델링 시스템이다.
GNU OctaveMATLAB과 유사한 수치 계산을 위한 자유(라이선스는 GPLv3) 범용 및 행렬 지향 프로그래밍 언어이다. GNU Octave의 2차 계획법은 [https://www.gnu.org/software/octave/doc/interpreter/Quadratic-Programming.html qp] 명령을 통해 사용할 수 있다.
HiGHS선형 프로그래밍(LP), 혼합 정수 프로그래밍(MIP) 및 볼록 2차 계획법(QP) 모델을 풀기 위한 오픈 소스 소프트웨어이다.
IMSL프로그래머가 소프트웨어 응용 프로그램에 포함할 수 있는 일련의 수학 및 통계 함수이다.
IPOPTIPOPT(내부 점 최적화기)는 대규모 비선형 최적화를 위한 소프트웨어 패키지이다.
Julia주목할 만한 솔루션 패키지인 [https://jump.dev/JuMP.jl/stable/ JuMP]가 있는 고급 프로그래밍 언어이다.
Maple수학을 위한 범용 프로그래밍 언어이다. Maple에서 2차 문제를 해결하는 것은 [http://www.maplesoft.com/support/help/Maple/view.aspx?path=Optimization/QPSolve QPSolve] 명령을 통해 수행된다.
MATLAB수치 계산을 위한 범용 및 행렬 지향 프로그래밍 언어이다. MATLAB에서 2차 계획법을 사용하려면 기본 MATLAB 제품 외에 최적화 도구 상자가 필요하다.
Mathematica기호 및 수치 기능을 포함하는 수학을 위한 범용 프로그래밍 언어이다.
MOSEK여러 언어(C++, Java, .Net, Matlab 및 Python)에 대한 API를 갖춘 대규모 최적화를 위한 솔버이다.
NAG여러 프로그래밍 언어(C, C++, Fortran, Visual Basic, Java 및 C#) 및 패키지(MATLAB, Excel, R, LabVIEW)에 대해 수치 알고리즘 그룹에서 개발한 수학 및 통계 루틴 모음이다. NAG 라이브러리의 최적화 장에는 희소 및 비희소 선형 제약 행렬이 있는 2차 계획법 문제에 대한 루틴과 비선형, 경계가 있거나 제약이 없는 선형, 비선형, 선형 또는 비선형 함수의 제곱합의 최적화를 위한 루틴이 포함되어 있다. NAG 라이브러리에는 로컬 및 글로벌 최적화와 연속 또는 정수 문제 모두에 대한 루틴이 있다.
Python대부분의 사용 가능한 솔버에 대한 바인딩이 있는 고급 프로그래밍 언어이다. 2차 계획법은 [https://pypi.org/project/qpsolvers/ solve_qp] 함수를 사용하거나 특정 솔버를 직접 호출하여 사용할 수 있다.
R (Fortran)GPL 라이선스가 있는 범용 크로스 플랫폼 통계 계산 프레임워크이다.
SAS/OR선형, 정수, 비선형, 파생물 없는, 네트워크, 조합 및 제약 최적화를 위한 일련의 솔버; 대수 모델링 언어 OPTMODEL; 특정 문제/시장을 목표로 하는 다양한 수직 솔루션은 모두 SAS 시스템과 완벽하게 통합되어 있다.
SuanShuLP, QP, SOCP, SDP, SQP를 Java로 풀기 위한 오픈 소스 최적화 알고리즘 모음이다.
TK Solver선언적 규칙 기반 언어를 기반으로 하는 수학적 모델링 및 문제 해결 소프트웨어 시스템으로 Universal Technical Systems, Inc.에서 상용화되었다.
TOMLABMATLAB에 대한 전역 최적화, 정수 프로그래밍, 모든 유형의 최소 제곱, 선형, 2차 및 제약 없는 프로그래밍을 지원한다. TOMLAB은 CPLEX, SNOPT 및 KNITRO와 같은 솔버를 지원한다.
XPRESS대규모 선형 프로그램, 2차 프로그램, 일반 비선형 및 혼합 정수 프로그램을 위한 솔버이다. 여러 프로그래밍 언어에 대한 API가 있으며, 모델링 언어 Mosel도 있으며 AMPL, GAMS와 함께 작동한다. 학술 용도로 무료이다.


참조

[1] 간행물 Continuous Optimization (Nonlinear and Linear Programming) Princeton University Press
[2] 서적 Numerical Optimization https://archive.org/[...] Springer-Verlag
[3] 서적 Linear complementarity, linear and nonlinear programming http://ioe.engin.umi[...] Heldermann Verlag
[4] 논문 Global linear convergence of an augmented Lagrangian algorithm for solving convex quadratic optimization problems http://www.helderman[...]
[5] 논문 On the Solution of Equality Constrained Quadratic Programming Problems Arising in Optimization 2001-04
[6] 논문 "[Polynomial solvability of convex quadratic programming]"
[7] 논문 An extension of Karmarkar's projective algorithm for convex quadratic programming https://doi.org/10.1[...] 1989-05-01
[8] 서적 Proceedings of the eighteenth annual ACM symposium on Theory of computing - STOC '86 Association for Computing Machinery 1986-11-01
[9] 논문 Computationally related problems http://www.cise.ufl.[...]
[10] 논문 Quadratic programming with one negative eigenvalue is (strongly) NP-hard
[11] arXiv The Complexity of Computing KKT Solutions of Quadratic Programs 2023
[12] 논문 Mixed-integer quadratic programming 1982-12-01
[13] 논문 Booster System Design Using Mixed-Integer Quadratic Programming 2004-07-01
[14] 서적 Optimization Methods in Finance https://www.cambridg[...] Cambridge University Press
[15] 간행물 Polynomial Optimization https://doi.org/10.1[...] Springer International Publishing 2023-12-16
[16] 서적 Numerical Optimization Springer-Verlag
[17] 서적 Linear complementarity, linear and nonlinear programming http://ioe.engin.umi[...] Heldermann Verlag
[18] 논문 Global linear convergence of an augmented Lagrangian algorithm for solving convex quadratic optimization problems http://www.helderman[...]
[19] Google Scholar Google search. https://scholar.goog[...]
[20] 논문 On the Solution of Equality Constrained Quadratic Programming Problems Arising in Optimization SIAM Journal of Scientific Computing 2001-04
[21] 논문 "[Polynomial solvability of convex quadratic programming]"
[22] 논문 Computationally related problems
[23] 논문 Quadratic programming with one negative eigenvalue is NP-hard
[24] 문서 Mixed Integer Nonlinear Programming. 混合整数非線形計画問題のこと。
[25] 웹사이트 Object-Oriented Software for Quadratic Programming (Paper) http://pages.cs.wisc[...] University of Wisconsin-Madison 2003-02-25
[26] 웹사이트 Source repository for OOQP, a quadratic programming solver (and more) https://github.com/e[...] 2014-07-11
[27] 논문 OptimJ used in an optimization model for mixed-model assembly lines http://www.in-ter-tr[...] University of Münster
[28] 논문 OptimJ used in an Approximate Subgame-Perfect Equilibrium Computation Technique for Repeated Games http://www.aaai.org/[...]


본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com