비선형 프로그래밍

수학에서 비선형 프로그래밍(NLP)은 제약 조건 또는 목적 함수의 일부가 비선형인 최적화 문제를 해결하는 과정입니다.최적화 문제는 일련의 미지의 실변수에 대한 목적함수의 극단(최대값, 최소값 또는 정지점)의 계산 중 하나이며, 집합적으로 제약이라고 불리는 등식 및 부등식의 시스템의 만족에 조건부이다.선형적이지 않은 문제를 다루는 것은 수학적 최적화의 하위 분야입니다.

적용 가능성

대표적인 비볼록형 문제는 다양한 연결성과 용량 제약으로 규모의 경제를 나타내는 운송 방법 중 하나 이상의 집합에서 선택함으로써 운송 비용을 최적화하는 것이다.파이프라인, 철도 유조선, 도로 유조선, 하천 바지선 또는 연안 탱크선의 선택 또는 조합이 주어진 석유 제품 운송이 그 예입니다.경제적 배치 규모 때문에 비용 함수는 원활한 변경 외에도 불연속성을 가질 수 있다.

실험 과학에서는 일부 단순한 데이터 분석(예: 알려진 위치와 모양의 피크 합계에 스펙트럼을 맞추는 것)을 선형 방법으로 수행할 수 있지만, 일반적으로 이러한 문제도 비선형적이다.일반적으로 변수 매개변수가 포함된 연구 대상 시스템의 이론 모델과 알 수 없는 매개변수가 있을 수 있는 실험 또는 실험 모델이 있습니다.숫자적으로 가장 적합한 것을 찾으려고 한다.이 경우 결과의 정밀도 측정과 최적의 적합도를 원하는 경우가 많습니다.

정의.

n, m, p를 양의 정수라고 합니다.X를 R의 부분ⁿ 집합으로 하고, f, g_i 및_j h를 {1, …, m}의 각 i에 대해 X에 대한 실수치 함수, 그리고_j {1, …, p}의 각 j를 f_i, g 및 h 중 적어도 하나가 비선형 함수라고 합니다.

비선형 최소화 문제는 형태의 최적화 문제입니다.

${\displaystyle {\text{aligned}{\text}}{\text{i}(x)\leq 0 텍스트{각}}i\in\{1,\dotsc,m\}\\h_{j}(x)=0 텍스트{\dot1,\sc},\sc}에 대해 {\g_i}\leq 0 텍스트{i}를 표시합니다.\end { aligned}}$

비선형 최대화 문제도 마찬가지로 정의된다.

가능한 제약 조건 집합 유형

피지블 세트 또는 피지블 영역이라고도 하는 제약 조건 세트의 성질에는 몇 가지 가능성이 있습니다.

실행할 수 없는 문제는 선택 변수의 값 집합이 모든 제약 조건을 충족하지 않는 문제입니다.즉, 제약조건은 서로 모순되며 해결방법은 존재하지 않습니다.실현 가능한 집합은 빈 집합입니다.

실행 가능한 문제는 모든 제약 조건을 충족하는 선택 변수에 대해 적어도 하나의 값 세트가 존재하는 문제입니다.

무한 문제는 목표 함수를 주어진 유한값보다 더 좋게 만들 수 있는 실현 가능한 문제입니다.따라서 최적의 솔루션은 없습니다. 왜냐하면 주어진 어떤 제안 솔루션보다 더 나은 객관적인 함수 값을 제공하는 실현 가능한 솔루션이 항상 존재하기 때문입니다.

문제 해결 방법

목적함수가 오목함수(최대화 문제) 또는 볼록함수(최소화 문제)이고 제약조건 집합이 볼록함수인 경우 프로그램을 볼록함수라고 하며 볼록최적화의 일반적인 방법을 사용할 수 있다.

목적 함수가 2차이고 제약조건이 선형일 경우 2차 프로그래밍 기법이 사용됩니다.

목적함수가 오목함수와 볼록함수의 비율(최대화 사례에서)이고 제약조건이 볼록한 경우, 문제는 분수 프로그래밍 기법을 사용하여 볼록 최적화 문제로 변환될 수 있다.

볼록하지 않은 문제를 해결하기 위해 몇 가지 방법을 사용할 수 있다.한 가지 방법은 선형 프로그래밍 문제의 특수 공식을 사용하는 것입니다.또 다른 방법은 분기 및 경계 기술의 사용을 포함하며, 여기서 프로그램은 볼록(최소화 문제) 또는 세분화 내 전체 비용에 하한을 형성하는 선형 근사치로 해결되는 하위 클래스로 나뉩니다.후속 분할을 통해 어느 시점에서 대략적인 솔루션에 대해 얻어진 최선의 하한값과 동일한 비용을 갖는 실제 솔루션을 얻을 수 있을 것이다.이 솔루션은 최적의 솔루션이지만 고유하지는 않을 수 있습니다.또한 알고리즘은 발견된 최적의 점으로부터 공차 내에 최적의 솔루션이 있는지 확인하기 위해 조기에 정지할 수도 있습니다. 이러한 점을 "최적"이라고 합니다.일반적으로 "최적" 포인트로 종단하는 것은 유한 종단을 보장하기 위해 필요합니다.이는 특히 크고 어려운 문제와 불확실한 비용이나 가치가 있는 문제, 적절한 신뢰성 추정을 통해 불확실성을 추정할 수 있는 문제에 유용하다.

차별화 및 제약 조건 하에서 Karush-Khn-Tucker(KKT) 조건은 솔루션이 최적화하는 데 필요한 조건을 제공한다.볼록한 상태에서는 이러한 조건도 충분합니다.일부 기능이 미분할 수 없는 경우 Karush-Kuhn-Tucker(KKT) 조건의 하위 차등 버전을 사용할 ^[1]수 있다.

수치 예시

2차원 예시

간단한 문제(그림에 표시)는 제약조건으로 정의할 수 있습니다.

x₁ 0 0

x₂ 0 0

x₁² + x₂² 1 1

x₁² + x₂² 2 2

최대화해야 할 객관적 기능을 가지고

f(x) = x₁ + x₂

여기서 x = (x₁, x₂)입니다.

3차원 예시

다른 간단한 문제(그림 참조)는 제약조건으로 정의할 수 있습니다.

x₁²₂² - x + x₃² 2 2

x₁² + x₂² + x₃² 10 10

최대화해야 할 객관적 기능을 가지고

f(x) = xx₁₂ + xx₂₃

여기서 x = (x₁, x₂, x₃)입니다.

「 」를 참조해 주세요.

• 곡선 피팅
• 최소 제곱 최소화
• 선형 프로그래밍
• nl(형식)
• 비선형 최소 제곱
• 최적화 소프트웨어 목록
• 2차 제약 2차 프로그래밍
• 비선형 프로그래밍의 기초를 만든 Werner Fenchel

레퍼런스

추가 정보

• Avriel, Mordecai (2003)비선형 프로그래밍: 분석 및 방법.도버 출판사ISBN 0-486-43227-0.
• 바자라, 모크타르 S.와 셰티, C. M.(1979).비선형 프로그래밍. 이론과 알고리즘.John Wiley & Sons.ISBN 0-471-78610-1.
• 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 3-540-35445-X. MR 2265882.
• Luenberger, David G.; Ye, Yinyu (2008). Linear and nonlinear programming. International Series in Operations Research & Management Science. Vol. 116 (Third ed.). New York: Springer. pp. xiv+546. ISBN 978-0-387-74502-2. MR 2423726.
• Nocedal, Jorge and Wright, Stephen J.(1999)수치 최적화스프링거.ISBN 0-387-98793-2.
• Jan Brinkhuis와 Vladimir Tikhomirov, 최적화: Insights and Applications, 2005, Princeton University Press

외부 링크

• 수학 프로그래밍 용어집