강의

https://www.youtube.com/watch?v=wsRznzNgTS0&list=PLoROMvodv4rMJqxxviPa4AmDClvcbHi6h&index=8

정리

• two-way partitioning은 n개의 객체를 두 개의 그룹으로 나누는 것.

• 그룹을 나누는 방법은 벡터 x로 표현, x_i가 +1이면 첫 번째 그룹, -1이면 두 번째 그룹에 속한다는 것.

• $x^\top Wx = \sum(W_{ij} * x_i * x_j)$

  • x_i, x_j는 각각 +1 또는 -1 : 곱이 1이면 같은 그룹, -1이면 다른 그룹에 속한다는 의미.
    • 이 의미는 같은 그룹에 있는 W의 합에서 다른 그룹에 있는 W의 합을 뺀 값
    • 최소화 문제

• 이 문제는 비선형인 이유는,

  • W가 양의 준정부호 행렬(positive semi-definite matrix)일 필요가 없음(명시 안함)
    • W가 양의 준정부호면, 이중 함수를 취한 후에는 목적 함수와 $\nu_i$를 곱한 항 추가
      • 이러면 이차 함수가 되어, 그 결과는 상수항이 더해진 이차 형태의 최소화 문제로 변형
  • ${x_i}^2$이 1이어야 해서 비선형인데, 1 이하라면 볼록함수임.

• Lagraian constraints는 제약조건을 목적함수에 합쳐서 하나의 함수로 표현하는 것

• 이후, dual function을 만들고 Dual 함수를 정의하는 것임

• 람다(λ)와 뉴(ν)로 매개변수화된 최적값의 하한(lower bound) 으로 볼 수 있는데, 어떤 λ와 ν 값을 넣든지 간에 하한을 하나 얻을 수 있음

  • 많은 경우에 λ와 ν를 아무 값이나 막 집어넣으면 얻게 되는 하한은 마이너스 무한대(-∞)

    • 이 케이스는 모든 경우에 적용되는 '보편적인 하한'이긴 한데, 아무 의미 없는 값

  • 그렇지만, 하한을 얻었을때 좀 흥미로운 값을 얻을 수 있는 것 중 하나가 분할 문제

    $$ \begin{align} &\text{minimize } \; x^\top Wx \\ &\text{subject to } x_{i}^{2} = 1, \; i = 1, ...,n \end{align} $$

• 분할 문제는 Convex가 아닌 문제임.

  1. W가 양의 준정부호(positive semi-definite)라고 말하지 않아, 목적 함수가 Convex가 아니어도 됨
  2. 제약조건이 제곱이 1과 같아야 한다는 문제.
  3. 부등식 제약조건은 affine이어야함.

• 해결책 : 라그랑지안으로부터 Dual Function 얻기

  $$ \begin{align} g(v) &= \inf_x(x^\top Wx+\sum_i\nu_i({x_{1}}^2-1)) \\ & =\inf_xx^\top(W+\text{diag}(\nu))x - 1^\top\nu \\ & = \begin{cases} -1^\top\nu \; W +\text{diag}(\nu) \ge 0 \\ -\infty \end{cases} \end{align} $$

  • Dual function을 얻기 위해서 x에 inf를 취해 최소화
  • (3)의 식은 (4)의 식으로 전개되는데, 다음과 같이 표현 가능
  • $W+\text{diag}(\nu)$가 0 이상이면, 하한이 0으로 가니까 $-1^\top\nu$
    • 왜냐면 이차함수(quadratic form)에서는 positive semi-definite면 최솟값은 0임
    • 그러나 matrix가 음의 고유값을 갖는다면, 최소값은 음의 무한대임. (고유값 따라가다보면 값이 계속해서 작아짐)

• 현실에서는 정확하게 풀 필요가 없음

  • 휴리스틱한 방법으로는 spectral partitioning(스펙트럴 파티셔닝), 그리디 방식 등이 있음
  • 현실에서 문제를 푼다면 벡터를 랜덤하게 +1 또는 마이너스 1로 초기화하고 인덱스 순회
    • 부호를 뒤집으면 목적함수가 좋아지는가 물어보며 좋아지면 부호 바꾸고 계속 진행하며 좋아지지 않을 때까지 계속 (1-opt : 어떤 하나의 변수라도 바꿔서 목적함수를 더 좋게 만들 방법이 없다)
    • 두개의 원소 쌍을 바꿔보는걸 추가해볼 수도 있음(2-opt : 어떤 두개의 변수를 바꿔도 더이상 좋아질 수 없음)
    • 이건 최적은 아니고 그저 이산(discrete) 집합 내에서의 국소 최적(local optimum)일 뿐

• non-convex 문제에서는 $2^n$개의 discrete points들을 가지고 있음

• 켤레 함수와의 연관성

  • 최적화 문제이나, convex일 필요 없음
  • 선형 부등식 제약 조건이 있어서, 해공간(feasible set)은 다면체(polyhedral)

• 만약 이 문제를 최적화 후에 x_i가 실수로 나오면 반올림을 하거나 부호를 취하는 방법으로 접근 가능