Math/Optimization (6) 썸네일형 리스트형 Knapsack problem knapsack은 한국어로 배낭을 의미한다.maximum weight $b$를 담을 수 있는 배낭, knapscak을 생각한다. 그리고 $n$개의 아이템을 생각하고, $i$ 아이템은 무게가 $a_i$이다. $i$ 아이템을 $x_i$개 담으면서 모든 아이템들의 무게의 합이 knapsack의 총 용량 $b$가 넘지 않도록 설계해야 한다, 즉, $\sum^n_{i=1}a_ix_i\leq b$이다.다음과 같은 집합을 생각해보자:$$K=\{ x\in \{0,1\}^n : \sum^n_{i=1}a_ix_i\leq b\}.$$ Minimal cover는 다음과 같이 정의된다:$$\sum_{i \in C \notin \{ j \} } a_i \leq b, \quad \forall j \in C.$$Minimal co.. Hermite Form 해당 책을 참고하여 정리한 내용입니다:Conforti, Michele, et al. Integer programming models. Springer International Publishing, 2014. 우선, Hermite Form은 다음과 같이 정의된다:Definition : $A\in\mathbb{Q}^{m\times n}$은 Hermite normal form은 $A= [ D \; O]$ 이고 $D$는 lower triangular matrix이고 $d_{ii}>0$ for $i=1,\dots,m$이고 $d_{ij}- Hermite normal form은 full row-rank라는 것을 확인할 수 있다. 이제 unimodular operation에 대해 알아보겠다:1. Interhcange.. Oracle Complexity Nesterov의 lectures on convex optimization 1.1.3 (Complexity Bounds for Global Optimziation) 관련해서 읽기 좋은 자료 : https://class.ece.uw.edu/546/2016spr/lectures/introduction.pdf Smoothness Lemma 1 ( Bubeck ) Beta-Smoothness Let $f$ be a $\beta$-smooth function. then for any $x,y$ $$| f(x) - f(y) - \nabla f(y)^T (x-y) | \leq \frac{\beta}{2} ||x-y||^2$$ Proof ) \begin{align} | f(x) - f(y) - \nabla f(y)^T (x-y) | &= |\int^1_0 \nabla f(y+t(x-y))^T(x-y) dt - \nabla f(y)^T (x-y) | \\ &\leq | \int^1_0 ||\nabla f(y+t(x-y)) - \nabla f(y)^T|| ||(x-y)| |\\ &\leq \int^1_0 \beta t ||x-y||^2 \\.. Proximal Gradient and Mirror Descent References [1] https://www.youtube.com/watch?v=0uIL-ADxvmw&list=PLsQI3WOaT8hgnhaqobr8ny41Pk5Q5bu7D&index=21 [2] First-Order Method - Beck Proximal Gradient Gradient Descent는 는 이차 근사함수를 최소화하는 방법이라고 할 수 있다. $x_{t+1}=x_t - \gamma \nabla g(x_t) = arg\min_y g(x_t) _ \nabla g(x_t)^T(y-x_t) + \frac{1}{2\gamma}||y-x_t||^2$ 만약 convex 하지만 non differentiable 한 $h(x)$가 있다면 , $f(x)=g(x) + h(x)$ 아래와 같이 Gradie.. Duality Boyd , Convex Optimization을 일부 정리한 내용입니다. The Lagrangian Lagrangian $L: R^n \times R^m \times R^p \rightarrow R$은 domain이 unconstrained 되어 있다. $$L(x,\lambda,\nu)= f_0(x) + \sum\limits^m_{i=1}\lambda_i f_i(x) + \sum\limits^p_{i=1}\nu_i h_i (x)$$ The Lagrange dual function Dual function은 $g:R^m\times R^p \rightarrow R$인 함수이다. Dual function의 domain도 unconstrained 이다. $$g(\lambda,\nu) = \inf_{x\in\m.. 이전 1 다음