05. Canonical Problems

Canonical Problems

첫 번째 장에서 convex optimization problem이 다음과 같이 정의됨을 알아보았다.

• The domain set is convex
• The objective function \(f\) and the inequality constraint function \(g_i\) are convex
• The equality constraint function \(h_j\) is affine

이때 objective function과 constraint function의 유형에 따라 optimization problem은 다양한 범주로 나뉘어지게 된다. 이 장에서는 그 중 다음 6가지 세부항목에 대해 알아보도록 할 것이다.

• Linear Programming (LP)
• Quadratic Programming (QP)
• Quadratically Constrained Quadratic Programming (QCQP)
• Second-Order Cone Programming (SOCP)
• Semidefinite Programming (SDP)
• Conic Programming (CP)

위의 문제들은 다음과 같은 포함관계를 가지고 있으며, 우측으로 갈수록 좀 더 일반화된 형식이라고 볼 수 있다.

\(LP \subseteq QP \subseteq QCQP \subseteq SOCP \subseteq SDP \subseteq CP\)

• 05-01 Linear Programming (LP)
• 05-02 Quadratic Programming (QP)
• 05-03 Quadratically Constrained Quadratic Programming (QCQP)
• 05-04 Second-Order Cone Programming (SOCP)
• 05-05 Semidefinite Programming (SDP)
• 05-06 Conic Programming (CP)