Convex Optimization - Lecture 6

 

Create time: Feb 15, 2020 11:40 AM Update time: Feb 16, 2020 11:31 PM

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

objective function이 위와같은 꼴을 가질때 linear fractional program 이라고 함.

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

이떄, objective function 의 domain 은 위와같이 분모 > 0 임.

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

그리고, 이 objective function은 quasiconvex function임. quasiconvex 를 나타내는 부등식에 분모를 양변에 곱하여 비교해보자.

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

linear fractional program 은 feasible set 이 non-empty 라면, LP 로 변환할 수 있음.

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

y 와 z 를 다음과 같이 선언함. 그럼 objective function은 아래와 같이 변환됨.

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

결국 원 domain x 는 위 식으로 치환되어 풀리게됨.

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

linear-fractional program 을 generalize 한 형태. 여러개의 quasiconvex function의 pointwise maximum을 구하는것이므로 여전히 quasiconvex 임.

r=1 이면 standraf linear fractional program.

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

objective function이 quadratic form 이고, constraint funciton이 affine 이면 quadratic program 이라 부름.

기하학적으로 보면, constraint 로 만들어진 polyhedron 형태의 feasible set 위에서, ellipsoid 형태의 objective function 을 minimize 하는 task 이다.

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

예시.

affine function의 norm 의 square 형태를 minimize 하는 task.

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

식을 풀어보면 위와같이 quadratic form 이 나옴.

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

QP 의 constraint funciton이 quadratic form 을 가진다면, quadratically constrained quadratic program 이라고 부름.

이는 feasible set이 intersection of ellipsoid 인 공간에서 ellipsoid 형태의 objective function을 최소화 하는것.

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

LP 에서 inequality constraint function이 second-order cone constraint 로 바뀌면, Second order cone programming 이라고 함.

standard form

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

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

linear programming 에서 parameter 들이 uncertain 한 경우, 어떻게 최적화 할지에 대한 방법이다.

deterministic model 과 stochastic model 이 있음.

  • deterministic model

가능한 모든 값을 포함시키는것.

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

uncertain 한 A 가 위 ellipoisd 영역 어딘가에서 정의된다고 해보자.

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

가능한 모든 A 가 ellipsoid 안에 있다면, 그럼 AX 의 supremum 이 b 보다 작으면 위 inequality constraint 가 성립할것이다.

이 아이디어를 위 수식으로 풀어내면 최종 형태는 SOCP 형태로 변환됨.

  • stochastic model

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

A 가 특정 probability distrubution 을 따른다고 가정하는것이다.

이번에는 가우시안 분포를 따른다고 가정해보자.

그럼 inequality constraint 를 만족할 경우가 확률을 가질탠데, 이 확률에 confidence score 를 적용한다.

최소한 얼만큼의 확률보다는 믿을만 해야한다 라는 의미로.

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

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

위와같이 변수를 치환하면, 아래 처럼 수식이 변형됨.

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

이는 CDF 형태로 나타낼 수 있음. 가우시안 분포의 CDF 는 아래 식.

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

이제 치환해두었던 variable 들을 다시 복구한다.

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

https://strutive07.github.io/assets/images/Lecture_6/1920px-Normal_Distribution_CDF.svg.png

만약, confidence score 가 0.5 보다 크다면, 위 그래프에 따라 아래 수식을 만족함.

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

따라서, 이제 robust linear program 을 second order cone program 형태로 변환을 성공하였음.

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

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

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

objective function 과 inequality constraint function이 posynomial 이고, equality constraint function이 monomial 인 경우, 이를 geometric program 이라고 부름.

이 geometric program은 보통 convex optimization problem 이 아님. 그러나 convex problem 으로 변환될 수 있음.

새로운 변수 y 를 다음과같이 선언해보자.

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

그럼 monomial function은 다음과같이 변환될 수 있다.

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

posynomai function은 다음과같이 변환될 수 있다.

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

위 두 함수 모두 affine function 형태.

그럼 이제 GP 는 다음과같은 형태로 나타낼 수 있음.

https://strutive07.github.io/assets/images/Lecture_6/Untitled%2029.png

여기에 log 를 씌움.

objective function과 inqeuality function 은 convex function 이고, equality function은 affine function 이므로, convexity 가 유지됨.

https://strutive07.github.io/assets/images/Lecture_6/Untitled%2030.png

최종적으로 GP 를 Convex problem 형태로 변환.