개요

페널티법(벌금법)에 대해 공부했으므로, 그 메모로서 여기에 기재합니다.

©️ 유루 유리 (귀여운 ...)

공식화

이제 변수 $x, y$의 에너지 $f(x, y)$가 주어지고 있다고 가정합니다 (이 $f$는 QUBO와 같은 변환에 의해 이미 2 차 형식으로 2 값 ($x, y\in {0, 1}$)의 수식이 있다고 가정합니다.) 그 에너지가 최소가 되도록 $x, y$를 취합시다. 이것을 수식으로 표현하면

\min_{x, y} f(x, y) \tag{*1}

같아요. 간단하네요.

제약 도입

여기에서

x + y = K \tag{*2}

라는 제약을 도입합시다. 즉, 이 제약을 지키면서 (*1)의 $f$를 최소화하라는 문제가 되었습니다.

제약 조건에서 제한없이 변환, 페널티 방법

제약이라고 하는(*2)을 채우면서(*1)식을 도달한다, 라고 하면 식이 2개로 나누어져 있는 일도 있어, 복잡함이 늘어나고 있는 것처럼 느끼네요. 그럼 어떻게 할까... 대답은 그렇게, 제약을 제약이라고 생각되지 않게 되는 1개의 수식에 정리해 주면 됩니다.
이를 위해 비용 함수를 소개합시다. 이 제약으로부터 어긋남이 생겼을 때에 코스트를 증가시키는 함수를 생각하면 좋다고 하면, 가장 간단한 형태는 다음과 같이 됩니다.

E 
= f(x, y) + \lambda (x+y-K)^2 \tag{*3}

여기서 $\lambda$는 제약의 어긋남에 걸리는 가중치의 상수입니다. 이 $E$를 최소화하면 자동으로 (*1)식을 채우고 제약(*2)도 성립하는 $x, y$가 선택됩니다.
하지만 조심해야 할 것은 $\lambda$의 크기입니다. $\lambda\gg 1$를 선택하면 모처럼(*1)이 채워져 있어도, $x, y$가 제약을 조금 깨고 있는 것만으로 비용 $E$가 커져 버립니다.

OpenJij에서 프로그래밍에 도전!

OpenJij 라는 파이썬 모듈을 사용하면 실제로 최적화 문제를 해결할 수 있습니다.

$ pip install openjij

에서 쉽게 설치할 수 있습니다. 실제로 사용해 보면 좋을 것입니다.

결언

이번에는 최적화 문제에서 자주 사용되는 기초적인 방법의 페널티법(벌금법)을 소개했습니다. 이 상태에서 다른 최적화 문제의 기사도 게재할 예정입니다. 거지 기대해 주세요.

어드밴스: 확장 라그랑주 미정승수법

자세한 것은 생략(아래, 저자가 공부중)하겠습니다만, 이하와 같은 확장 라그랑주 미정승수법을 사용하는 것으로, 보다 정밀도 좋게 코스트를 줄이고 제약을 만족시키는 $x, y$를 발견한다 것으로 알려져 있습니다.

E 
= f(x, y) + \lambda (x+y-K)^2 + \alpha (x+y-K)