Convex Optimization - Lecture 7

 

Create time: Feb 16, 2020 11:46 AM Update time: Feb 16, 2020 11:32 PM

https://strutive07.github.io/assets/images/Lecture_7/Untitled.png

inequality constraint function을 vector valued 형태로 변환하면 이를 generalized inequality 라 부름.

generalized inequality 를 가지느 가장 간단한 convex optimization problem 은 conic form problem 이다.

이는 linear objective function 을 가지고, K-convex한 하나의 affine inequality constraint function을 가진다.

https://strutive07.github.io/assets/images/Lecture_7/Untitled%201.png

https://strutive07.github.io/assets/images/Lecture_7/Untitled%202.png

inequality constraint 가 LMI(linear matrix inequality) 형태라면, 이를 Semidefinite program(SDP) 라고 함.

만약 matrix 가 모두 diagonal 형태라면, 각 element 를 분해하여 linear inequality 로 변형시킬 수 있음

https://strutive07.github.io/assets/images/Lecture_7/Untitled%203.png

https://strutive07.github.io/assets/images/Lecture_7/Untitled%204.png

https://strutive07.github.io/assets/images/Lecture_7/Untitled%205.png

LMI 가 여러개 존재하는 SDP 의 경우, 각 LMI들을 element 로 가지는 큰 matrix 를 구성한다. 이때 이 element 들은 위에서 봤었던 diagonal matrix 형태로 구성한다. 왜냐? diagnoal matrix 형태 구성해야 하나의 matrix 로 합칠 수 있음. 위의 하나의 LMI 를 여러 linear inequality 로 분해하려면 diagonal matrix 여야 했던것과 동일.

https://strutive07.github.io/assets/images/Lecture_7/Untitled%206.png

다른 여러 문제들을 SDP 로 변형시켜보자. LP 는 diagnoal matrix 형태로 나타내면 되므로 생략.

SOCP 를 SDP 로 변환하는것은 살짝 까다롭다.

이는 schur complement 를 사용하여 식을 변형시켜야 하기 때문. 식을 하나의 block matrix 형태로 변환하는 과정.

  • schur complement

ORF523_S16_Lec9_gh.pdf

https://strutive07.github.io/assets/images/Lecture_7/Untitled%207.png

https://strutive07.github.io/assets/images/Lecture_7/Untitled%208.png

식을 거꾸로 올라가보자.

기존 inequality 를 제곱한다. 여기서 좌측항이 항상 non-negative 이여야 다시 돌아올 수 있음.

https://strutive07.github.io/assets/images/Lecture_7/Untitled%209.png

식을 shur complement 형태로 변환. 여기서 A, B, C, D 를 알 수 있음.

https://strutive07.github.io/assets/images/Lecture_7/Untitled%2010.png

A

https://strutive07.github.io/assets/images/Lecture_7/Untitled%2011.png

B

https://strutive07.github.io/assets/images/Lecture_7/Untitled%2012.png

C

https://strutive07.github.io/assets/images/Lecture_7/Untitled%2013.png

D

https://strutive07.github.io/assets/images/Lecture_7/Untitled%2014.png

https://strutive07.github.io/assets/images/Lecture_7/Untitled%2015.png

eigenvalue 를 최소화.

https://strutive07.github.io/assets/images/Lecture_7/Untitled%2016.png

eigenvalue 보다 큰 하나의 값을 설정.

이 값을 minimize 하는 형식으로 SDP form 을 변환.

https://strutive07.github.io/assets/images/Lecture_7/Untitled%2017.png

https://strutive07.github.io/assets/images/Lecture_7/Untitled%2018.png

matrix norm 은 위와같이 특정 variable 과의 관계로 나타낼 수 있음.

s 가 non-negative 라면, 제곱을 통해 위의 식으로 변환 가능.

https://strutive07.github.io/assets/images/Lecture_7/Untitled%2019.png

이 식을 또 shur complement로 matrix 형태로 다시 풀어내면, SDP 형태로 변환할 수 있음.

https://strutive07.github.io/assets/images/Lecture_7/Untitled%2020.png

이제 object function 이 vector 공간에서 존재할 수 있도록 해보자.

vector 공간에서 minimize 를 하기 위해서는, 가장 기초적으로 두 value 의 비교가 가능해야함.

이를 위해 cone 을 사용.

K-Convex cone 위에서 두 vector 를 비교하는것은 가능. 따라서 objective function은 k-convex 한 fucntion 이여야 minimize할 수 있음.

https://strutive07.github.io/assets/images/Lecture_7/Untitled%2021.png

feasible set에서 minimum value 가 존재한다면, 그 x 는 optimal.

feasible set 에서 minimal value 가 존재한다면, 그 x 들은 pareto optimal

https://strutive07.github.io/assets/images/Lecture_7/Untitled%2022.png

multicriterion optimization은 여러개의 object function을 가지고있음. multi-objective optimization problem 이라고도 불림.

F1~Fq 는 각각의 다른 scalar objective function.

만약 x, y 가 feasible set 에 있고, x 가 y 보다 좋다(better) 라면, f_i(x) ≤ f_i(y) 을 만족하고, 1~q 중 하나는 f_i(x) < f_i(y) 을 만족한다.

https://strutive07.github.io/assets/images/Lecture_7/Untitled%2023.png

그리고 paretor optimal point 가 있고, feasible y 가 f_0(y) ≤ f_0(x_po) 를 만족하면, 이때는 무조건 f_0(y) = f_0(x_po) 이다.

https://strutive07.github.io/assets/images/Lecture_7/Untitled%2024.png

https://strutive07.github.io/assets/images/Lecture_7/Untitled%2025.png

scalarization은 vector optimization problem 에서 pareto optimal 이나 optimal point 를 찾기 위해 사용되는 방법이다.

https://strutive07.github.io/assets/images/Lecture_7/Untitled%2026.png

위 조건을 만족하는 하나의 vector를 찾는다. 그리고 feasible set 에서 이 vector 를 방향으로 하는 접선을 만든다.

https://strutive07.github.io/assets/images/Lecture_7/Untitled%2027.png

이중에서 최소가 되는 지점을 찾는다. 그럼 almost 대부분의 pareto optimal point 를 찾을 수 있다.

almost 인 이유는 위 그림에서 x_3 같은 영역은 찾지 못한다.

https://strutive07.github.io/assets/images/Lecture_7/Untitled%2028.png

multicriterion problem 에서는 arbiterey 하게 선택하는 람다를 각 objective function에 하나하나 선택하고, 위 식을 다 만족하는 paretor optimal point를 찾는것 이라 생각하면됨.

vector 에서 생각하면 하나의 vector 람다 를 선택하고, feasible set 에서 그 점에서의 접선을 긋는것?. 이 개념은 아직 잘 모르겠다.