[최적화] Semi-definite program

이우준·2021년 10월 28일
0

Optimization

목록 보기
3/6

이번 포스팅에서는 semi-definite program (SDP)에 대해 알아보자.

여기서 다룰 내용은 크게 세 가지 이다.

  1. SDP가 무엇이고, 이는 convex problem이 맞는지
  2. SDP가 LP, LS, QP, SOCP를 포함하는 개념이 맞는지
  3. Schur complement lemma란 무엇인지

Semi-definite program (SDP)

Standard form

먼저, SDP의 standard form은 아래와 같다.

minxRd wx:G+x1F1++xdFd0Cxe=0G,FiRm×mCRp×d,eRp\begin{aligned} \min_{x \in \mathbf{R}^d}& \textrm{ } w^{\intercal}x: \\ &\quad G + x_1F_1 + \cdots + x_dF_d \succeq 0 \\ &\quad Cx-e = 0 \\ &\quad G, F_i \in \mathbf{R}^{m \times m} \\ &\quad C \in \mathbf{R}^{p \times d}, e\in \mathbf{R}^p \end{aligned}

참고로 GGFiF_isymmetric matrices 이다. 여기서 주목할 점은 inequality constraint 인데, 식을 보면 여러개의 행렬이 x:=(x1,x2,,xd)x:=(x_1,x_2,\cdots,x_d)의 성분들과 linear 하게 연산되어 있는 것을 알 수 있다. 따라서 이를 Linear matrix inequality 즉, LMI 라고 부른다.

Convexity

다음으로 SDP의 convexity를 증명해보자. Standard form을 보면 wxw^{\intercal}xCx=eCx=e는 모두 affine 이므로, 우리는 inequality constraint에 의해 유도되는 set SS가 convex 임을 보이기만 하면 된다.

S:={x:G+x1F1++xdFd0}\begin{aligned} S := \{x: G + x_1F_1 + \cdots + x_dF_d \succeq 0 \} \end{aligned}

증명은 x,ySx, y\in Sλ[0,1]\lambda \in [0,1]에 대한 convex combination λx+(1λ)y\lambda x + (1-\lambda) ySS 안에 있는지 확인하는 방식으로 할 수 있다.

G+(λx1+(1λ)y1)F1++(λxd+(1λ)yd)Fd= λ[G+x1F1++xdFd]+(1λ)[G+y1F1++ydFd]0\begin{aligned} & G + \left( \lambda x_1 + (1-\lambda) y_1 \right) F_1 + \cdots + \left( \lambda x_d + (1-\lambda) y_d \right) F_d \\ = \textrm{ }& \lambda \left[ G+x_1F_1+\cdots+x_dF_d \right] + (1-\lambda) \left[ G+y_1F_1+\cdots+y_dF_d \right] \succeq 0 \end{aligned}

즉, 'x,ySx, y \in S' 라는 가정과 'PSD matrix 2개의 convex combination 또한 PSD' 라는 사실로 인해 SS 는 convex set 이다.
\Rightarrow 따라서, SDP는 convex problem 이다.

참고로, 두 PSD의 convex combination이 PSD 인 이유는 다음과 같다.
Proof: Let A,BRm×m0A, B \in \mathbf{R}^{m\times m} \succeq 0 and vRmλA+(1λ)B0 ?v \in \mathbf{R}^m \Rightarrow \lambda A + (1-\lambda) B \succeq 0 \textrm{ ?}
λA+(1λ)B\lambda A + (1-\lambda) B 의 양 옆에 vv를 곱하면 다음과 같다.
v(λA+(1λ)B)v=λvAv+(1λ)vBv0(A,B0,λ[0,1])v^{\intercal} (\lambda A + (1-\lambda) B) v = \lambda v^{\intercal} A v + (1-\lambda)v^{\intercal} B v \succeq 0 \quad (\because A,B \succeq 0, \lambda \in [0,1])

Relation with other methods

이제 SDP가 다른 방법들을 포함할 수 있는지 알아보자. 이에 앞서 SDP의 standard form을 다시 remind 해보면 다음과 같다.

minxRd wx:G+x1F1++xdFd0Cxe=0\begin{aligned} \min_{x \in \mathbf{R}^d}& \textrm{ } w^{\intercal}x: \\ &\quad G + x_1F_1 + \cdots + x_dF_d \succeq 0 \\ &\quad Cx-e = 0 \end{aligned}

편의를 위해 위의 식을 ()(*) 로 하자.

LP

()(*) 에서 GGFiF_idiagonal matrix (대각 행렬) 이라 하자. 그렇다면 우리는 식을 아래와 같이 표현할 수 있다.

[G]ii+[F1]iix1++[Fd]iixd0  (i=1,,m)[G]_{ii} + [F_1]_{ii}\cdot x_1 + \cdots +[F_d]_{ii}\cdot x_d \geq 0 \textrm{ }\textrm{ }(i=1,\cdots,m)

이때 [A]ii[A]_{ii}AA(i,i)(i,i) 성분을 의미한다.

여기서 우리는 diagonal PSD가 non-negative 한 성분들로 이루어진다는 성질을 이용했다. 즉 위의 과정을 통해 우리는 LP가 SDP의 특정 case 임을 알 수 있다. (LP의 inequality constraints로 바뀌었기 때문이다.)

LS and QP

LS와 QP에 대한 포함 관계를 보이는 것은 SOCP를 보이는 것만큼이나 어렵다. (포스팅에서 다루지는 못했지만) 앞선 강의에서 SOCP가 LS 및 QP를 포함한다는 것을 보였기 때문에, 여기서는 SDP가 SOCP를 포함하는지에 초점을 맞춰볼 것이다. (이를 보이면 LS와 QP도 SDP에 포함된다는 것이기 때문)

SOCP

SOCP의 standard form을 생각해보자.

minxRd wx:Aixbicix+ei  (i=1,,m)Fx=gw,xRdAiRki×d,bRki,ciRd,eiRFRp×d,gRp\begin{aligned} \min_{x \in \mathbf{R}^d}& \textrm{ } w^{\intercal}x: \\ &\quad \vert\vert A_i x-b_i \vert\vert \leq c_i^{\intercal}x + e_i \textrm{ }\textrm{ }(i=1,\cdots,m) \\ &\quad Fx = g \\ &\quad w, x \in \mathbf{R}^d\\ &\quad A_i \in \mathbf{R}^{k_i \times d}, b \in \mathbf{R}^{k_i}, c_i \in \mathbf{R}^d, e_i \in \mathbf{R} \\ &\quad F \in \mathbf{R}^{p \times d}, g \in \mathbf{R}^{p}\\ \end{aligned}

우리가 보여야 할 것은 SOC constraint에서 LMI로의 변환이 항상 가능하다는 것이다. 위의 식에서 SOC constraint를 다음의 형태로 바꿔보자.
(To be feasible cix+ei0\rightarrow c^{\intercal}_i x + e_i \geq 0)

(cix+ei)2Aixbi2\begin{aligned} (c_i^{\intercal}x + e_i)^2 \geq \vert\vert A_ix-b_i \vert\vert^2 \\ \end{aligned}

(Remind LMI: G+x1F1++xdFd0G + x_1F_1 + \cdots + x_dF_d \succeq 0)

여기서 WLOG (without loss of generality), cix+ei>0c^{\intercal}_i x + e_i >0 라 둘 수 있다. 만약 cix+ei=0c^{\intercal}_i x + e_i=0 이면 Aixbi=0A_ix-b_i =0 인데, 이때 두 식은 Fx=gFx = g (equality constraint)에 합쳐질 수 있고, 이는 LP와 같기 때문이다.

이제 식을 마저 정리해보자. cix+ei>0c_i^{\intercal}x + e_i >0 이므로, 이를 양변에 나누면 다음과 같다.

(cix+ei)Aixbi2cix+ei ()\begin{aligned} (c_i^{\intercal}x + e_i) \geq \frac{\vert\vert A_ix-b_i \vert\vert^2}{c_i^{\intercal}x + e_i} \\ \end{aligned} \quad \quad \cdots \textrm{ } (**)

()(**)는 아래와 같이 표현할 수 있다. (Iki×ki:ki×ki identity matrix)(I_{k_i \times k_i}: k_i \times k_i \textrm{ identity matrix})

(cix+ei)(Aixbi){(cix+ei)Iki×ki}1(Aixbi)0\begin{aligned} (c_i^{\intercal}x + e_i) - (A_ix-b_i)^{\intercal} \left\{ (c_i^{\intercal}x + e_i) I_{k_i \times k_i} \right\}^{-1} (A_ix-b_i)\geq 0 \end{aligned}

이때, 위의 식에서 좌변을 행렬 (cix+ei)Iki×ki(c_i^{\intercal}x + e_i) I_{k_i \times k_i}Schur complement 라고 한다. Formal 한 definition은 아래와 같다.

Schur complement

Definition: Suppose that pp and qq are non-negative integers. And ARp×p,BRp×q,CRq×qA\in\mathbf{R}^{p\times p}, B\in\mathbf{R}^{p\times q}, C\in\mathbf{R}^{q\times q}.
Let X:=[ABBC]R(p+q)×(p+q)X := \begin{bmatrix} A&B\\ B^{\intercal}&C\\ \end{bmatrix} \in \mathbf{R}^{(p+q) \times (p+q)}. Then if AA is invertible, the Schur complement SS of the block AA in matrix XX is defined as S:=CBA1B.S := C-B^{\intercal}A^{-1}B.

이제 정의를 알았으니 앞선 계산식에 대응시켜보면, formal definition을 기준으로 C=cix+eiC=c_i^{\intercal}x + e_i, B=AixbiB=A_ix-b_i 그리고 A=(cix+ei)Iki×kiA=(c_i^{\intercal}x + e_i) I_{k_i \times k_i} 인 상황임을 알 수 있다.

한편 Schur complement와 관련된 매우 유명한 lemma를 하나 사용하면, 우리는 SDP의 standard form에 있는 inequality constraints를 유도해낼 수 있다. 해당 lemma는 다음과 같다: Schur complement lemma

Schur complement lemma
Suppose ARp×p0A \in \mathbf{R}^{p \times p} \succ 0 and CC is symmetric. Then,
X:=[ABBC]0S:=CBA1B0X := \begin{bmatrix} A&B\\ B^{\intercal}&C\\ \end{bmatrix} \succeq 0 \Leftrightarrow S:= C-B^{\intercal}A^{-1}B \succeq 0

이제 앞서 대응시킨 변수들을 대입하면, SOC constraint를 다음의 형태로 바꿀 수 있다.

Fi(x):=[(cix+ei)Iki×kiAixbi(Aixbi)cix+ei]0F_{i}(x) := \begin{bmatrix} (c_{i}^{\intercal}x+e_{i}) I_{k_i \times k_i}& A_ix-b_i \\ (A_ix-b_i)^{\intercal}&c_{i}^{\intercal}x+e_{i}\\ \end{bmatrix} \succeq 0

여기서 Fi(x)R(ki+1)×(ki+1)F_{i}(x) \in \mathbf{R}^{(k_i+1) \times (k_i+1)} 는 symmetric 이고 PSD이며, 각 원소들은 xx에 대해 affine 이다. 그렇다면 이는 LMI 일까? 이에 대한 대답은 Yes 이다. 증명은 다음과 같다.

Proof: (Subscript index ii는 생략)
F(x):=[(cx+e)Ik×kAxb(Axb)cx+e]0F(x) := \begin{bmatrix} (c^{\intercal}x+e) I_{k \times k}& Ax-b \\ (Ax-b)^{\intercal}&c^{\intercal}x+e\\ \end{bmatrix} \succeq 0 is an LMI?
(LMI: G+x1F1++xdFd0G + x_1F_1 + \cdots + x_dF_d \succeq 0)

LMI는 xx와 관련이 있느냐 없느냐에 따라 크게 두 부분으로 나눠볼 수 있다. (e.g., 행렬 GGxx 와 관련이 없는 부분)

따라서 F(x)F(x)도 두 부분으로 나눠보면 다음과 같이 전개할 수 있다.

[(cx+e)Ik×kAxb(Axb)cx+e]=[eIk×kbbe]+[cxIk×kAxxAcx]\begin{bmatrix} (c^{\intercal}x+e) I_{k \times k}& Ax-b \\ (Ax-b)^{\intercal}&c^{\intercal}x+e\\ \end{bmatrix} = \begin{bmatrix} e I_{k \times k}& -b \\ -b^{\intercal}&e\\ \end{bmatrix} + \begin{bmatrix} c^{\intercal}x I_{k \times k}& Ax \\ x^{\intercal}A^{\intercal}&c^{\intercal}x\\ \end{bmatrix}

이때 G=[eIk×kbbe]G=\begin{bmatrix} e I_{k \times k}& -b \\ -b^{\intercal}&e\\ \end{bmatrix} 임을 알 수 있고, 이는 symmetric 이다.

다음으로 남은 한 부분을 보자. 이는 xx에 대한 함수인데, 우리의 목적은 이를 i=1dxiFi\sum^d_{i=1} x_iF_i 꼴로 표현하는 것이다.

각각을 보면 먼저 cxc^{\intercal}xi=1dcixi\sum^d_{i=1} c_ix_i 로 표현할 수 있다. 다음으로 AxAxi=1d\sum^d_{i=1} \square 의 형태로 어떻게 표현할 수 있을까.

현재 AA의 크기는 Rk×d\mathbf{R}^{k \times d} 이므로 column은 총 dd 개다. 각 column을 aiRka_i \in \mathbf{R}^{k} 로 두면 AA[a1,a2,,ad][a_1, a_2, \cdots,a_d] 로 나타낼 수 있고, Ax=i=1daixiAx=\sum^d_{i=1} a_ix_i 와 같다. 마찬가지로 나머지 원소에 대해서도 같은 방식을 적용하면, xix_i는 scalar 값이므로 transpose에 영향을 받지 않기 때문에 다음과 같이 표현할 수 있다.

[cxIk×kAxxAcx]=[i=1dcixiIk×ki=1daixii=1daixii=1dcixi]=i=1dxi[ciIk×kaiaici]\begin{aligned} \begin{bmatrix} c^{\intercal}x I_{k \times k}& Ax \\ x^{\intercal}A^{\intercal}&c^{\intercal}x\\ \end{bmatrix} &= \begin{bmatrix} \sum^d_{i=1} c_ix_iI_{k \times k}& \sum^d_{i=1} a_ix_i \\ \sum^d_{i=1} a^{\intercal}_ix_i&\sum^d_{i=1} c_ix_i\\ \end{bmatrix} \\ &=\sum^{d}_{i=1} x_i \begin{bmatrix} c_iI_{k \times k}& a_i \\ a^{\intercal}_i& c_i\\ \end{bmatrix} \end{aligned}

우리는 마지막 식에서 [ciIk×kaiaici]\begin{bmatrix} c_iI_{k \times k}& a_i \\ a^{\intercal}_i& c_i\\ \end{bmatrix}FiF_i 로 볼 수 있다. 그렇다면 마지막으로 확인할 것은 FiF_i의 symmetric 여부인데, 행렬 꼴을 보았을 때 이는 symmetric 이다.

따라서 F(x):=[(cx+e)Ik×kAxb(Axb)cx+e]0F(x) := \begin{bmatrix} (c^{\intercal}x+e) I_{k \times k}& Ax-b \\ (Ax-b)^{\intercal}&c^{\intercal}x+e\\ \end{bmatrix} \succeq 0 는 LMI 이다.

(Remind SOCP)

minxRd wx:[(cix+ei)Iki×kiAixbi(Aixbi)cix+ei]0Fx=gw,xRdAiRki×d,bRki,ciRd,eiRFRp×d,gRp\begin{aligned} \min_{x \in \mathbf{R}^d}& \textrm{ } w^{\intercal}x: \\ &\quad \begin{bmatrix} (c_{i}^{\intercal}x+e_{i}) I_{k_i \times k_i}& A_ix-b_i \\ (A_ix-b_i)^{\intercal}&c_{i}^{\intercal}x+e_{i}\\ \end{bmatrix} \succeq 0 \\ &\quad Fx = g \\ &\quad w, x \in \mathbf{R}^d\\ &\quad A_i \in \mathbf{R}^{k_i \times d}, b \in \mathbf{R}^{k_i}, c_i \in \mathbf{R}^d, e_i \in \mathbf{R} \\ &\quad F \in \mathbf{R}^{p \times d}, g \in \mathbf{R}^{p}\\ \end{aligned}

지금까지 우리는 Fi(x)0F_i(x) \succeq 0 이 LMI 라는 것을 확인했다. 그런데 생각해보면 SOCP에서 ii 의 범위는 1im1 \leq i \leq m 이기 때문에, SDP에서 하나의 LMI를 다뤘던 것과는 달리 여기서는 총 mm 개의 multiple LMIs 를 다룬다.

따라서 SDP의 form을 맞춰주기 위해서는 multiple LMIs를 single LMI로 바꾸는 추가적인 연산이 필요하다.

각각의 LMI를 보자. F1(x)0F_1(x) \succeq 0 이고, F2(x)0,,Fm(x)0F_2(x) \succeq 0, \cdots, F_m(x) \succeq 0 이다. 그렇다면 우리는 다음의 large matrix를 생각해볼 수 있다.

[F1(x)000F2(x)000Fm(x)] ()\begin{bmatrix} F_1(x)& 0& \cdots &0 \\ 0& F_2(x) & \cdots & \vdots \\ \vdots& \vdots & \ddots & 0 \\ 0& \cdots & 0 & F_m(x) \\ \end{bmatrix} \quad \quad \cdots \textrm{ } (***)

한편, 위의 행렬에 대해 다음과 같은 관계식이 성립한다. 증명은 PSD의 definition을 통해 쉽게 할 수 있다.

F1(x),,Fm(x)0F(x):=[F1(x)000F2(x)000Fm(x)]0\begin{aligned} F_1(x), \cdots, F_m(x) \succeq 0 \Leftrightarrow F(x) := \begin{bmatrix} F_1(x)& 0& \cdots &0 \\ 0& F_2(x) & \cdots & \vdots \\ \vdots& \vdots & \ddots & 0 \\ 0& \cdots & 0 & F_m(x) \\ \end{bmatrix} \succeq 0 \end{aligned}

참고로 ()(***) 은 symmetric 이기 때문에 G+i=1dxiFiG + \sum_{i=1}^d x_iF_i 의 형식으로 표현할 수 있고, 또한 ()(***) 은 PSD 이므로 이는 LMI 이다.

SDP:

minxRd wx:[F1(x)000F2(x)000Fm(x)]0Fi(x):=[(cix+ei)Iki×kiAixbi(Aixbi)cix+ei]Fx=g\begin{aligned} \min_{x \in \mathbf{R}^d}& \textrm{ } w^{\intercal}x: \\ &\quad \begin{bmatrix} F_1(x)& 0& \cdots &0 \\ 0& F_2(x) & \cdots & \vdots \\ \vdots& \vdots & \ddots & 0 \\ 0& \cdots & 0 & F_m(x) \\ \end{bmatrix} \succeq 0\\ &\quad F_i(x) :=\begin{bmatrix} (c_{i}^{\intercal}x+e_{i}) I_{k_i \times k_i}& A_ix-b_i \\ (A_ix-b_i)^{\intercal}&c_{i}^{\intercal}x+e_{i}\\ \end{bmatrix} \\ &\quad Fx = g \\ \end{aligned}

Proof of Schur complement lemma

Schur complement lemma
Suppose A0A\succ0 (PD) and CC is symmetric. Then,
X=[ABBC]0S:=CBA1B0X = \begin{bmatrix} A&B\\ B^{\intercal}&C\\ \end{bmatrix} \succeq 0 \Leftrightarrow S:= C-B^{\intercal}A^{-1}B \succeq 0
(SS 는 block AA 의 Schur complement)

()\left( \Rightarrow \right)

다음과 같은 f(x,y)f(x,y)를 생각해보자. (xRp,yRq)(\rightarrow x\in \mathbf{R}^p, y\in \mathbf{R}^q)

f(x,y)=[xy][ABBC][xy]=xAx+2xBy+yCy\begin{aligned} f(x,y) &= \begin{bmatrix} x^{\intercal}&y^{\intercal} \end{bmatrix} \begin{bmatrix} A&B\\ B^{\intercal}&C\\ \end{bmatrix} \begin{bmatrix} x \\ y \\ \end{bmatrix} \\ &= x^{\intercal} A x + 2x^{\intercal}By + y^{\intercal}Cy \end{aligned}

여기서 f(x,y)f(x,y)xx 에 대한 2차식인 것을 알 수 있다. 가정에 의하면 AA 는 PD 이고, 따라서 AA는 invertible 하다. (또한 AA의 모든 eigen-value가 strictly positive)

그렇다면 f(x,y)f(x,y)xx 에 대한 convex function 이다. 왜냐하면 AA 가 symmetric 하고 PD 이기 때문이다. (엄밀히 말하면, PSD가 아닌 PD 이므로 strictly convex in xx)

이제 아래와 같이 g(y)g(y) 를 설정하고, 그에 해당하는 xx 값 (stationary point)를 넣어 전개해보자.

g(y):= minxf(x,y) x=A1By= (A1By)A(A1By)2(A1By)By+yCy= y(CBA1B)y= ySy( S  is Schur complement )\begin{aligned} g(y) :=\textrm{ }& \min_x f(x,y) \quad \leftarrow \textrm{ } x^* = -A^{-1}By \\ =\textrm{ }& (A^{-1}By)^{\intercal} A(A^{-1}By) -2(A^{-1}By)^{\intercal}By +y^{\intercal}Cy \\ =\textrm{ }& y^{\intercal}(C-B^{\intercal}A^{-1}B)y\\ =\textrm{ }& y^{\intercal}Sy \quad \quad (\because \textrm{ } S \textrm{ }\textrm{ is Schur complement }) \end{aligned}

정리하면, XX는 PSD 이다. PSD의 정의를 생각해보면, 모든 (x,y)(x,y) 에 대해 f(x,y)=[xy][ABBC][xy]0f(x,y) = \begin{bmatrix} x^{\intercal}&y^{\intercal} \end{bmatrix} \begin{bmatrix} A&B\\ B^{\intercal}&C\\ \end{bmatrix} \begin{bmatrix} x \\ y \\ \end{bmatrix} \geq 0 이 성립한다.

그리고 우리가 보이고 싶은 것은 SS 가 PSD 라는 것이다. g(y)g(y)f(x,y)f(x,y)에서 xxxx^* 로 고정된 것이기 때문에 S0S \succeq 0 이다.

()\left( \Leftarrow \right)

PSD의 definition을 사용하자. 즉, 모든 yy 에 대해 다음이 성립한다.

g(y)=f(x,y)=ySy0\begin{aligned} g(y) = f(x^*,y) = y^{\intercal}Sy \geq 0 \end{aligned}

또한 앞선 g(y)g(y)의 정의를 생각해보면, g(y)f(x,y)g(y) \leq f(x,y) 이다. 따라서 (x,y)\forall (x,y)에 대해 0f(x,y)0 \leq f(x,y) 의 관계가 성립한다.

f(x,y)=[xy][ABBC][xy]0\begin{aligned} f(x,y) &= \begin{bmatrix} x^{\intercal}&y^{\intercal} \end{bmatrix} \begin{bmatrix} A&B\\ B^{\intercal}&C\\ \end{bmatrix} \begin{bmatrix} x \\ y \\ \end{bmatrix} \end{aligned} \geq 0

즉, XX는 PSD 이다.

Reference

카이스트 서창호 교수님 강의 - EE424: 최적화개론 lecture 12.

1개의 댓글

comment-user-thumbnail
2023년 10월 17일

정말 수준 높은 포스팅입니다. 감사합니다.

답글 달기