minpack 에 대한 최근 질문에 대한 설명을 요청 하고 다음과 같은 의견을 얻었습니다.
모든 방정식 시스템은 최적화 문제와 동일하므로 최적화의 뉴턴 기반 방법이 비선형 방정식 시스템을 해결하기위한 뉴턴 기반 방법과 매우 유사합니다.
이 주석 (및 minpack과 같은 특수 비선형 최소 제곱 솔버에 대한 관련 부정적인 의견) 에 대해 저를 혼란스럽게 만드는 것은 켤레 구배 방법 의 예에서 가장 잘 설명 될 수 있습니다 . 이 방법은 대칭 양수 한정 행렬 A 가있는 시스템 적용 할 수 있습니다 . 또한 최소 최소 제곱 문제를 해결하는 데 사용될 수 있습니다. 최소 x | | A x − b | | 임의 행렬 A의 경우 2
Ax=bA
minx||Ax−b||2
A
권장하지는 않습니다. 우리가 이것을하지 말아야 할 이유 중 하나는 시스템의 조건 수가 크게 증가한다는 것입니다.
그러나 방정식 시스템을 최적화 문제로 바꾸는 것이 선형 경우에도 문제가되는 것으로 여겨지면 왜 일반적인 경우에 문제가 덜됩니까? 약간 오래된 비선형 최소 제곱 솔버를 사용하는 대신 최첨단 최적화 알고리즘을 사용하는 것과 관련이있는 것 같습니다. 그러나 실제로 사용되는 최적화 알고리즘과는 독립적으로 정보를 버리고 시스템의 조건 수를 늘리는 것과 관련된 문제가 아닌가?
답변
내 답변 중 하나가 인용되었으므로 MINPACK 대신 IPOPT 사용을 제안한 이유를 분명히하려고 노력할 것입니다.
MINPACK 사용에 대한 저의 반대 의견은 MINPACK이 사용하는 알고리즘 및 구현과 관련된 모든 것과 관련이 없습니다. 저의 주요 반대 의견은 소프트웨어가 1980 년으로 거슬러 올라가고 1999 년에 마지막으로 업데이트되었다는 것입니다. Jorge Moré는 은퇴했습니다. 그 또는 다른 소프트웨어 제작자가 더 이상 탭을 사용하지 않는 것이 의심스럽고 적극적으로 지원하는 팀이 없습니다. 소프트웨어에서 찾을 수있는 유일한 문서는 Jorge Moré와 다른 MINPACK 저자가 작성한 1980 년 Argonne 기술 보고서 원본입니다. (챕터 1-3은 여기 에서 찾을 수 있고 , 4 장은 여기 에서 찾을 수 있습니다..) MINPACK 소스 코드를 검색하고 설명서를 숙독 한 후 (PDF는 이미지를 스캔하여 검색 할 수 없음) 제약 조건을 수용 할 수있는 옵션이 표시되지 않습니다. 비선형 최소 제곱 문제의 원래 포스터는 제한된 비선형 최소 제곱 문제를 해결하려고했기 때문에 MINPACK은이 문제를 해결하지도 않습니다.
IPOPT 메일 링리스트를 보면 일부 사용자는 비선형 최소 제곱 (NLS) 문제에서 패키지 성능이 Levenberg-Marquardt 알고리즘 및보다 특수한 NLS 알고리즘과 비교하여 혼합되어 있음을 나타냅니다 ( 여기 , 여기 및 여기 참조 ). NLS 알고리즘에 대한 IPOPT의 성능은 물론 문제에 따라 다릅니다. 이러한 사용자 피드백을 고려할 때 IPOPT는 NLS 알고리즘과 관련하여 합리적인 권장 사항처럼 보입니다.
그러나 NLS 알고리즘을 조사해야한다는 것이 좋습니다. 동의한다. MINPACK보다 현대적인 패키지를 사용해야한다고 생각합니다. 왜냐하면 그것이 더 잘 작동하고 더 유용하며 지원 될 것이라고 믿기 때문입니다. Ceres 는 흥미로운 후보 패키지처럼 보이지만 지금은 제한된 문제를 처리 할 수 없습니다. 타오고전적인 Levenberg-Marquardt를 구현하지는 않지만 대신 파생되지 않은 알고리즘을 구현하지만 상자가 제한된 최소 제곱 문제에 대해서는 작동합니다. 미 분산 알고리즘은 대규모 문제에 적합하지만 소규모 문제에는 사용하지 않습니다. 소프트웨어 엔지니어링에 큰 자신감을 불어 넣은 다른 패키지를 찾을 수 없었습니다. 예를 들어, GALAHAD는 언뜻보기에 버전 관리 나 자동 테스트를 사용하지 않는 것 같습니다. MINPACK도 그러한 일을하지 않는 것 같습니다. 더 나은 소프트웨어에 대한 MINPACK 또는 권장 사항에 대한 경험이 있다면, 나는 귀를 기울입니다.
그 모든 것을 염두에두고 내 의견의 인용문으로 돌아갑니다.
모든 방정식 시스템은 최적화 문제와 동일하므로 최적화의 뉴턴 기반 방법이 비선형 방정식 시스템을 해결하기위한 뉴턴 기반 방법과 매우 유사합니다.
더 나은 의견은 아마도 다음과 같은 영향을 미칩니다.
n
n
g(x)=0
이 문장은 제약 조건 하에서 방정식 시스템을 풀기위한 것입니다. 변수에 제약이있는 경우 “등식 해결사”로 간주되는 알고리즘을 모릅니다. 내가 아는 일반적인 접근 방식은 아마도 최적화 과정에서 여러 학기의 최적화 과정과 연구에 의해 황달이 될 수 있으며 방정식 시스템의 제약 조건을 최적화 공식에 통합하는 것입니다. 방정식 해결을 위해 Newton-Raphson과 유사한 구성표의 제약 조건을 사용하려고 시도하면 제약 된 최적화에 사용 된 방법과 매우 유사하게 투영 된 기울기 또는 투영 된 신뢰 영역 방법으로 끝날 수 있습니다.
답변
경우 주어진 비선형 시스템이 최적화 문제에 대한 1 차 최적의 조건이다, 우리는 종종 그 정보를 사용하여보다 강력한 알고리즘을 생성 할 수 있습니다. 예를 들어
여기에는 고유 한 최소값이 있으며 시작 지점에 관계없이 최적화 방법으로 찾을 수 있습니다. 그러나 1 차 최적 조건 만 살펴보면 의 해 를 찾고 있습니다 [Wolfram Alpha]
x ∇f(x)=0
독특한 솔루션을 가지고 있지만 많은 근본 찾기 방법이 최소한으로 국한 될 수 있습니다.
그라디언트의 제곱을 최소화하기 위해 새로운 최적화 문제를 재구성한다면, 우리 는 다중 최소값을 갖는 [Wolfram Alpha] 의 전역 최소 를 찾고 있습니다.
x ‖∇f(x)‖2
요약하자면, 우리는 분석법이 찾도록 보장 할 수있는 고유 한 솔루션을 가진 최적화 문제로 시작했습니다. 로컬에서 식별 할 수있는 고유 한 솔루션이있는 비선형 루트 찾기 문제로 재구성되었지만 루트 찾기 방법 (예 : Newton)이 도달하기 전에 정체 될 수 있습니다. 그런 다음 근본 발견 문제를 여러 로컬 솔루션이있는 최적화 문제로 재편성했습니다 (전세계 최소값이 아님을 식별하기 위해 로컬 측정 값을 사용할 수 없음).
일반적으로 문제를 최적화에서 루트 찾기로 또는 그 반대로 변환 할 때마다 사용 가능한 방법과 관련 수렴 보장이 약해집니다. 메소드의 실제 메커니즘은 종종 매우 유사하므로 비선형 솔버와 최적화간에 많은 코드를 재사용 할 수 있습니다.