그라디언트 디센트 (제약 조건 포함)

Question

그라데이션 디센트를 사용하여 N 매개 변수에서 함수의 최소값을 찾으려고합니다. 그러나 매개 변수의 절대 값의 합을 1 (또는 < = 1, 중요하지 않음)로 제한하면서이를 수행하려고합니다. 이런 이유로 저는 lagrange multipliers의 방법을 사용하고 있습니다. 만약 함수가 f (x)라면 f (x) + lambda * (g (x) -1)를 최소화 할 것입니다. 여기서 g (x)는 부드러운 근사입니다. 파라미터의 절대치의 합

이제는 g (x) = 1 일 때이 함수의 그래디언트 만 0이 될 것이므로 로컬 최소값을 찾는 방법은 내 조건이 충족되는 최소한의 함수를 찾아야합니다. 문제는이 함수가 무한대로 추가되어 Gradient Descent가 더 크고 큰 매개 변수 (절대 값)를 가진 더 크고 더 큰 람다를 찾고 수렴하지 않는다는 것입니다.

현재 CG의 파이썬 (scipy) 구현을 사용하고 있으므로 CG 코드를 직접 다시 작성하거나 조정할 필요가없는 제안을 선호하지만 기존 방법을 사용하십시오.

Answer 1

문제는 라그랑주 승수를 사용할 때 중요한 포인트가 라그랑지안의 로컬 미니 마에서 발생하지 않는다는 것인데, 라그랑 지 승수는 대신 안장 지점에서 발생합니다. 그라디언트 디센트 알고리즘은 로컬 최소 점을 찾기 위해 설계되었으므로 제약 조건에 문제가있을 때 수렴하지 못합니다.

• 사용 안장 점을 발견 할 수있는 수치 방법, 예를 들면 :

  는 일반적으로 세 가지 솔루션이 있습니다 뉴튼의 방법. 그러나 일반적으로 그라디언트와 헤 시안 모두에 대한 분석식이 필요합니다.

• 페널티 방법을 사용하십시오. 여기에서 비용 함수에 여분의 (부드러운) 항을 추가합니다.이 조건은 제약 조건이 만족 될 때 (또는 거의 충족 될 때) 0이며 충족되지 않을 때 매우 커집니다. 평소대로 그래디언트 디센트를 실행할 수 있습니다. 그러나 매개 변수가 제약 조건을 충족시키는 지 확인하기 위해 여러 가지 작은 조정이 이루어지기 때문에 종종 컨버전스 특성이 좋지 않습니다.
• 라그랑지안의 임계점을 찾는 대신 라그랑지안의 그래디언트의 제곱을 최소화하십시오. 분명히, 라그랑지안의 모든 파생물이 0이라면, 그래디언트의 제곱은 0이 될 것이고, 어떤 것이 제로가 될 수 없기 때문에, 라그랑지안을 극단화함으로써 당신과 같은 해결책을 발견하게 될 것입니다. 그러나 그래디언트 디센트를 사용하려면 Lagrangian의 그래디언트 사각형의 그래디언트에 대한 표현식이 필요합니다.이 표현식은 쉽게 도달하지 않을 수 있습니다.

개인적으로 나는 세 번째 접근법을 사용하고 라그랑지안 그라디언트의 제곱의 그라디언트를 수치 해석 적으로 계산하기가 어렵다면 수치 적으로 찾을 수 있습니다.

또한 그라디언트 디센트 또는 CG (접합 그라디언트)를 사용하고 있습니까?

Answer 2

아마 너무 늦게 영업 이익에 도움이 될하지만 같은 상황에서 다른 사람에게 유용 할 수 있습니다 :

절대 값의 제한의 문제점은 종종에 의해, 선형 제약이있는 해당 문제로 공식화 될 수있다 몇 가지 "도우미"변수가 추가되었습니다.

예를 들어, 문제 1 고려해

찾기 (X1, X2) 비선형 제약에 F (X1, X2) 제목을 최소화 | X1 | + | X2 | < = 10.

1. 다음 선형 제약 F (X1, X2) 제목을 최소화

   찾기 (X1, X2, X3, X4) : 선형 제약 버전 문제 (2)가있다

   X1 = X3 <

2. -X1 < = X3
3. < X2 = X4
4. -X2 < = X4
,536 91,363,210
5. X3의 + X4의 < = 10

참고

• (X1, X2, X3, X4)는 문제 2 제약 조건을 만족하는 경우는, 다음 (X1, X2)가 1 문제 제약 (만족
• 문제 1에 대한 제약 조건을 만족하면 문제에 대한 제약 조건을 만족하는 (x1, x2, x3, x4)까지 확장 할 수있다. (x1, x2, x3, x4) x3 = abs (x1), x4 = abs (x2),
• x3, x4는 목표 함수에 아무런 영향을 미치지 않는다.

문제 2에 대한 최적 조건을 발견하면 문제 1에 대한 최적 성을 얻을 수 있으며 반대의 경우도 마찬가지입니다.