BFGS 최적화 알고리즘은 철저하게 볼록한 문제에 대해 수렴 적으로 수렴하지만 비 철저하게 볼록한 문제에 대해서는 분석이 있습니다. 예를 들어, f (x)가 스칼라 x에 대해 볼록하다고 가정합니다. 그런 다음 g (x1, x2) = f (x1 + x2) 이상으로 최적화한다고 가정합니다. 이것은 여전히 초 선형 적으로 수렴적일 것인가?convex over-parameterized 문제에 대한 BFGS의 수렴
내가 틀렸다면 정정 해주세요. 그러나이 경우 "해결책"은 실제로 한 줄이 아니라 한 줄이되지 않습니까? x '가 f (x)에 대한 최소화자인 경우 g (x1, x2)에 어떤 방법을 적용 할 때 최선의 방법은 x2 = x'- x1 선으로 수렴하는 것입니다.
줄의 모든 점이 해결책입니다. –
BFGS가 볼록하지 않은 문제를 수렴하는지 여부는 여전히 열려있는 문제입니다. 실제로 1984 년 Powell은 부정확 한 행 검색 검색을 사용하는 BFGS가 수렴하지 못하는 것을 보여주는 반대 사례를 제시했습니다. 로컬 미니 마 x *가 주어지면 x * 근처의 공간 영역에 결국 입력하면 BFGS는 초 선형 적으로 수렴 할 것입니다. 그 이유는 x * 근처에서는 목적 함수가 convex quadratic으로 정확하게 모델링 될 수 있기 때문입니다.
당신이 준 구성 기능으로 알려진 것에 대해서는 확실하지 않습니다. BFGS의 속성에 대한 자세한 설명은 Dennis와 Schnabel 또는 Nocedal과 Wright를 참조하십시오.
행운을 빈다.
실제로 나는 신중하게 쓰여진 알고리즘이 수렴하지만 반드시 수퍼 선형 적이지는 않다는 것을 발견했다. 반올림 오류가 범인입니다. 컨버전스 기준이 적용됩니다. "거의"볼록하지 않은 함수, 즉 "뻣뻣한"함수에서도 마찬가지입니다.
이론상의 헤 시안이 아니더라도 Hessian이 양의 "충분한"상태를 유지하도록 BFGS 업데이트에주의해야합니다. 내가하는 일은 헤 시안 그 자체 인 또는 그 반전이 아닌 헤 시안의 콜레 스키 분해를 유지하고 업데이트하는 것입니다.
"알고리즘"또는 "수치 해석"과 같은 태그를 몇 번 더 사용해보십시오. 여기서 "최적화"는 일반적으로 "이 비트의 코드를 어떻게 최적화합니까?"라는 의미입니다. MathOverflow.net이이 질문을하기에 더 좋은 곳이 될지 확실하지 않습니다. 그 (것)들을위한 단단한 (ie 연구 수준) 질문이이지 않을지도 모르지 않았다. – celion