이차 제약 2차 프로그램
Quadratically constrained quadratic program수학적 최적화에서, QCQP는 목적 함수와 제약 조건이 모두 2차 함수인 최적화 문제입니다.그것은 형태를 가지고 있다.
여기서0 P, …, P는m n-by-n 행렬이고 x µn R은 최적화 변수입니다.
만약0m P, …, P가 모두 양의 반확정이라면, 문제는 볼록하다.이러한 행렬이 양의 행렬도 음의 행렬도 아닌 경우 문제는 볼록하지 않습니다.P1, …, P가m 모두 0일 경우 제약조건은 사실상 선형이며 문제는 2차 프로그램입니다.
경도
일반적인 사례를 해결하는 것은 NP-난해한 문제입니다.이를 확인하기 위해 두 개의1 제약 조건 x1(x - 1) and 0 및1 x1(x - 1) are 0은 제약1 조건 x1(x - 1) = 0과 동일하며, 이는 제약1 조건 x 0 {0, 1)와 동등하다는 점에 유의하십시오.따라서, 0-1 정수 프로그램(모든 변수가 0 또는 1이어야 함)은 2차 구속 2차 프로그램으로 공식화할 수 있다.0 – 1 정수 프로그래밍은 일반적으로 NP-hard이므로 QCQP도 NP-hard입니다.
릴렉스
QCQP에는 반정의 프로그래밍(SDP)과 재구성 선형화 기법(RLT)의 두 가지 주요 완화 사항이 있습니다.QCQP 문제의 일부 클래스(정확히는 데이터 매트릭스에 대각 요소가 0인 QCQP), SDP 완화와 동일한 객관 값을 제공하는 2차 원뿔 프로그래밍(SOCP) 및 선형 프로그래밍(LP) 완화를 사용할 [1]수 있습니다.
비양성 오프 대각선 요소를 가진 비볼록 QCQP는 SDP 또는 SOCP [2]완화로 정확하게 해결할 수 있으며,[3] 정확히는 일반 QCQP의 SDP 완화에는 다항식 시간 체크 가능한 충분한 조건이 있다.또한,[3] 랜덤 일반 QCQP의 클래스는 제약조건의 수가 변수 수의 고정 다항식보다 빠르게 증가하지 않는 한 높은 확률로 정확한 반무한 완화를 갖는 것으로 나타났다.
반무한 프로그래밍
P, …, P가m 모두 양의 정의 행렬일 경우0, 문제는 볼록하고 반정의 프로그래밍에서처럼 내부 점 방법을 사용하여 쉽게 해결할 수 있습니다.
예
Max Cut은 NP-hard인 그래프 이론의 문제입니다.그래프에서 문제는 정점을 두 세트로 나누어 가능한 한 많은 가장자리가 한 세트에서 다른 세트로 이동하도록 하는 것입니다.Max Cut은 QCQP로 공식화할 수 있으며 듀얼의 SDP 완화는 양호한 하한을 제공합니다.
솔버 및 스크립트(프로그래밍) 언어
| 이름. | 간단한 정보 |
|---|---|
| 아르텔리스 니트로 | Nitro는 비선형 최적화에 특화된 해결사이지만 선형 프로그래밍 문제, 2차 프로그래밍 문제, 2차 원뿔 프로그래밍, 비선형 방정식 시스템 및 평형 제약 문제를 해결합니다. |
| 피코 엑스프레스 | 선형 프로그래밍, 비선형 프로그래밍, 혼합 정수 선형 프로그래밍, 볼록 2차 프로그래밍, 볼록 2차 제약 2차 프로그래밍, 2차 콘 프로그래밍 및 이들의 혼합 정수 대응용 상용 최적화 솔버. |
| 앰프 | |
| 컴플렉스 | 여러 프로그래밍 언어용 API로 인기 있는 해결사입니다.학문은 무료입니다. |
| 모섹 | 여러 언어(C++, java,.net, Matlab 및 python)에 대한 API를 통한 대규모 최적화 솔루션 |
| 탐랩 | MATLAB에 대한 전역 최적화, 정수 프로그래밍, 모든 유형의 최소 제곱, 선형, 2차 및 제약 없는 프로그래밍을 지원합니다.TOMLAB은 CPLEX, SNOPT, NITRO 등의 솔버를 지원합니다. |
레퍼런스
- ^ Kimizuka, Masaki; Kim, Sunyoung; Yamashita, Makoto (2019). "Solving pooling problems with time discretization by LP and SOCP relaxations and rescheduling methods". Journal of Global Optimization. 75 (3): 631–654. doi:10.1007/s10898-019-00795-w. ISSN 0925-5001.
- ^ Kim, Sunyoung; Kojima, Masakazu (2003). "Exact Solutions of Some Nonconvex Quadratic Optimization Problems via SDP and SOCP Relaxations". Computational Optimization and Applications. 26 (2): 143–154. doi:10.1023/A:1025794313696.
- ^ a b Burer, Samuel; Ye, Yinyu (2019-02-04). "Exact semidefinite formulations for a class of (random and non-random) nonconvex quadratic programs". Mathematical Programming. 181: 1–17. arXiv:1802.02688. doi:10.1007/s10107-019-01367-2. ISSN 0025-5610.
- Boyd, Stephen; Lieven Vandenberghe (2004). Convex Optimization. Cambridge: Cambridge University Press. ISBN 978-0-521-83378-3.
추가 정보
통계 정보
- Albers C. J., Critchley F., Gower, J. C. (2011). "Quadratic Minimisation Problems in Statistics" (PDF). Journal of Multivariate Analysis. 102 (3): 698–713. doi:10.1016/j.jmva.2009.12.018. hdl:11370/6295bde7-4de1-48c2-a30b-055eff924f3e.
{{cite journal}}: CS1 maint: 여러 이름: 작성자 목록(링크)
