05-03 Quadratically Constrained Quadratic Programming (QCQP)

Quadratic program에서 inequality constraint function이 이차식(convex quadratic)으로 교체되면, 이는 Quadratically constrained quadratic program(QCQP)이라고 불린다.

Quadratically Constrained Quadratic Program

$$\begin{array}{rlrl}& {\text{minimize}}_x& & (1/2)x^T{P}_{0}x+q_0^{T}x+r_0\\ \\ & \text{subject to }& & (1/2)x^T{P}_{i}x+q_i^{T}x+r_i\le 0,i=1,\dots ,m\\ \\ & & & Ax=b,\\ \\ & \text{where }& & P_i\in {\mathbb{S}}_{+}^n\text{ for }i=0,\dots ,m\text{, and }A\in {\mathbb{R}}^{\text{p x n}}.\end{array}$$

QP and equivalent QCQP

QCQP의 inequality constraint에서 $P_i=0,\text{ for }i=1,\dots ,m$이면 QP의 형태와 동일해짐을 알 수 있다. 즉, QP는 QCQP의 한가지 특수한 경우에 해당하며, QP $\subseteq$ QCQP의 관계가 성립한다.

Recall: Quadratic Program

$$\begin{array}{rlrl}& {\text{minimize}}_x& & (1/2)x^{T}Px+q^{T}x+r\\ \\ & \text{subject to }& & Gx⪯h\\ \\ & & & Ax=b,\\ \\ & \text{where }& & P\in {\mathbb{S}}_{+}^n,G\in {\mathbb{R}}^{\text{m x n}}\text{, and }A\in {\mathbb{R}}^{\text{p x n}}.\end{array}$$