순차 2차 프로그래밍

이 글은 주제를 잘 모르는 사람들에게 불충분한 맥락을 제공한다. 독자에게 더 많은 컨텍스트를 제공하여 기사를 개선할 수 있도록 도와주십시오. (2009년 10월) (이 템플리트 메시지를 제거하는 방법과 시기 알아보기)

순차 2차 프로그래밍(SQP)은 제한된 비선형 최적화를 위한 반복 방법이다.SQP 방법은 객관적 함수와 제약조건이 연속적으로 2배 이상 차이가 나는 수학 문제에 사용된다.

SQP 방법은 일련의 최적화 하위 문제를 해결하며, 각각은 제약조건의 선형화에 따라 목표의 2차 모델을 최적화한다.만약 문제가 구속되지 않는다면, 그 방법은 목적의 기울기가 사라지는 지점을 찾는 뉴턴의 방법으로 줄어든다.문제가 평등 제약만 가지고 있다면, 그 방법은 뉴턴의 방법을 문제의 1차 최적성 조건, 즉 카루시-쿤-터커 조건에 적용하는 것과 같다.

알고리즘 기본 사항

다음 형식의 비선형 프로그래밍 문제를 고려하십시오.

${\displaystyle {\cHB{rarray}{rl}\min \in \nmbox{pack to}}{x}&b(x)\geq 0\&c(x)=0.\end{array}}}$

이^[1] 문제의 라그랑지안은

${\displaystyle {\mathcal{L}(x,\lambda ,\sigma )=f(x)-\lambda b(x)-\sigma c(x),}$

여기서 $\lambda {\displaystyle }$ ${\displaystyle \lambda$ $}$과($와{\displaystyle }$)$display$ {\displaystyle \$sigma }$은(는) Lagrange 승수다.반복 $x{\displaystyle {}_{}}$ ${\displaystyle k_{}}$ ${\$에서 기본 순차 2차 프로그래밍 알고리즘은 2차 프로그래밍 하위 문제에 대한 솔루션으로서$$ 적절한 검색 방향 $d{\displaystyle {}_{}}$ ${\$을 정의한다$.$

${\displaystyle {\read}{rl}\min \fo_{d}&f(x_{k})+\possla f(x_{k}})^{d}T}d+{\tfrac {1}{2}}d^{{}T}\\nabla _{xx}^{2}{\mathcal{L}(x_{k},\lambda _{k},\sigma _{k}d\\\\\mathrm {s.t.} &b(x_{k})+\nabla b(x_{k})^{k}^{{{{{{}}}}}}}}}}}}}}}^{{{{{}}}}}}^{{{{{}}}}}}T}d\geq 0\\&c(x_{k})+\nabla c(x_{k})^{{{k}^{{}}T}d=0.\end{array}}$

${\displaystyle \underset{}{위}}$의 표현식에서$$ $f{\displaystyle }$( ${\displaystyle x_{}}$ k${\displaystyle {}_{}}$) ${\displaystyle f(x_{k}})$라는 용어는 ${\displaystyle \underset{}{최소}}$ d ${\$ 연산자$$ 아래에서 일정하므로 최소화 문제에 대해 생략할 수 있다는 점에 유의하십시오.

대체 접근 방식

• 순차 선형 프로그래밍
• 순차 선형 2차 프로그래밍
• 증강라그랑기법

구현

SQP 방법은 MATLAB, GNU 옥타브와 같은 잘 알려진 수치 환경에서 구현되었다.오픈 소스를 포함한 수많은 소프트웨어 라이브러리도 존재한다.

• SciPy(과학 파이썬의 사실상의 표준)는 scipy.optimize.minimize(method=')를 가지고 있다.SLSQP') 해결사.
• NLopt(C/C++ 구현, Julia, Python, R, MATLAB/Octave를 포함한 수많은 인터페이스 포함), Dieter Kraft가 최적의 제어를 위해 패키지의 일부로 구현하고 S. G. Johnson이 수정했다.^[2][3]
• 랩뷰
• 니트로^[4](C, C++, C#, 자바, 파이톤, 줄리아, 포트란)
• NPSOL(포트란)
• SNOPT(포트란)
• NLPQL(Fortran)
• 매트랩
• 수안슈 (자바)

참고 항목

• 뉴턴의 방법
• 세컨트법

메모들

참조

• Bonnans, J. Frédéric; Gilbert, J. Charles; Lemaréchal, Claude; Sagastizábal, Claudia A. (2006). Numerical optimization: Theoretical and practical aspects. Universitext (Second revised ed. of translation of 1997 French ed.). Berlin: Springer-Verlag. pp. xiv+490. doi:10.1007/978-3-540-35447-5. ISBN 978-3-540-35445-1. MR 2265882.
• Jorge Nocedal and Stephen J. Wright (2006). Numerical Optimization. Springer. ISBN 978-0-387-30303-1.

외부 링크

• NEOS 가이드의 순차 2차 프로그래밍