Nonlinear programming — 비선형 계획법

비선형 프로그래밍(NLP)은 수학적 프로그래밍 및 운용과학의 한 분야로, 목적 함수 및/또는 하나 이상의 제약 조건이 결정 변수에 대한 비선형 함수인 최적화 문제를 다룹니다.

NLP는 선형 프로그래밍의 일반화이며, 변수 간의 관계가 엄격하게 비례하지 않는(즉, 직선이 아닌 곡선으로 표현되는) 더 광범위한 실제 시스템과 과정을 모델링할 수 있습니다.

주제 및 목적

비선형 프로그래밍은 다음과 같은 상황에서 최적해를 찾는 데 사용됩니다:

• 관리 가능한 매개변수에 대한 목표 지표(이익, 비용, 효율성 등)의 의존성이 비선형인 경우(예: 규모에 따른 체감 수익, 이차 비용).
• 자원 또는 기술 공정에 대한 제약 조건이 비선형 관계로 표현되는 경우(예: 화학 반응, 물리 법칙, 경제적 의존성).

NLP 문제는 여러 분야에서 발생합니다:

• 공학 설계(구조물, 공정의 최적화).
• 경제 및 금융(위험을 고려한 포트폴리오 최적화, 시장 모델링).
• 화학 공학(반응기 운전 조건의 최적화).
• Machine Learning(Neural Network 학습, 지지 벡터 머신).
• 생산 공정 관리. 물류(비선형 비용을 고려한 경우).

NLP 문제의 수학적 정식화

비선형 프로그래밍의 일반적인 문제는 다음과 같이 공식화됩니다:

비선형 목적 함수를 최대화하거나 최소화하는 결정 변수의 값 집합을 찾아야 합니다. 이때 변수의 값은 제약 조건 시스템을 만족해야 하며, 이 제약 조건은 부등식 형태(예: "양 A는 B보다 작거나 같아야 한다")와 등식 형태(예: "양 C는 정확히 D와 같아야 한다") 모두로 표현될 수 있습니다. 중요한 점은 목적 또는 제약 조건을 설명하는 함수 중 적어도 하나가 비선형이어야 한다는 것입니다. 변수의 값이 0보다 크거나 같아야 한다는 비음수 조건이 자주 추가됩니다.

제약 조건을 만족하는 모든 변수 값의 집합은 실행 가능 영역(feasible region)을 형성합니다.

선형 프로그래밍과의 차이점

비선형 프로그래밍은 선형 프로그래밍(LP)과 본질적으로 다릅니다:

• 비선형성: 목적 함수 또는 제약 조건(또는 둘 다)에 비선형 의존성이 포함됩니다.
• 실행 가능 영역의 특성: NLP의 실행 가능 영역은 비볼록(non-convex)일 수 있습니다(LP에서는 실행 가능 영역이 항상 볼록 다면체인 것과 달리).
• 최적점의 특성: NLP에서 최적해는 반드시 실행 가능 영역의 꼭짓점에 위치하지 않으며, 영역의 경계 또는 내부에 있을 수 있습니다. NLP에서는 전역 최적이 아닌 지역 최적이 존재할 수 있습니다.
• 풀이의 복잡성: NLP 문제는 일반적으로 LP 문제보다 훨씬 풀기 어렵습니다. 모든 NLP 문제에 적용 가능한 단일 범용 알고리즘(심플렉스 방법과 같은)은 존재하지 않습니다.

NLP의 주요 어려움과 과제

비선형 프로그래밍 문제를 푸는 것은 여러 어려움을 수반합니다:

• 지역 극값의 존재: 대부분의 NLP 방법은 지역 최적(어떤 근방에서 가장 좋은 해)만을 찾는 것을 보장합니다. 전역 최적(전체 실행 가능 영역에서 가장 좋은 해)을 찾는 것은 특히 비볼록 문제의 경우 어려운 과제입니다.
• 비볼록성: 문제가 볼록하지 않은 경우(목적 함수 또는 실행 가능 영역이 비볼록), 여러 지역 최적이 존재할 수 있으며, 표준 경사법이 그 중 하나에 "갇힐" 수 있습니다.
• 계산 복잡성: NLP 풀이 알고리즘은 LP에 비해 훨씬 더 많은 계산 자원을 필요로 하는 경우가 많습니다.

NLP 문제의 중요한 분류

일반적인 복잡성에도 불구하고, 효율적인 풀이 방법이 개발된 중요한 NLP 문제의 하위 분류들이 존재합니다:

• 볼록 프로그래밍: 볼록 집합의 실행 가능 영역에서 볼록 함수를 최소화(또는 오목 함수를 최대화)하는 문제. 핵심 특성: 모든 지역 최솟값은 동시에 전역 최솟값이기도 합니다. 이는 최적해 탐색을 크게 단순화합니다.
• 이차 프로그래밍: 목적 함수가 이차 함수이고 모든 제약 조건이 선형인 경우.
• 분리 가능 프로그래밍: 목적 함수와 제약 조건이 각각 하나의 변수에만 의존하는 함수들의 합으로 표현될 수 있는 경우.

NLP 문제의 풀이 방법

비선형 프로그래밍(NLP) 문제의 풀이 방법

I. 비제약 최적화 방법(제약 없는 최적화):

• 경사법(최급강하법, 켤레 경사법);
• 뉴턴 방법 및 준뉴턴 방법(예: BFGS);
• 헤시안 근사를 활용한 방법.

II. 제약 최적화 방법(제약 있는 최적화):

• 변환 방법:
  • 벌칙 함수법(penalty methods);
  • 장벽 함수법(barrier methods).
• 직접 방향 탐색 방법:
  • 가능 방향법.
• 최적성 조건 기반 방법:
  • 카루시-쿤-터커 방법(KKT 조건);
  • 라그랑주 승수법.
• 반복 방법:
  • 순차적 이차 프로그래밍(SQP);
  • 내부점 방법.

III. 전역 최적화 방법:

• 휴리스틱 및 메타휴리스틱 방법:
  • 유전 알고리즘;
  • 모의 담금질;
  • 금기 탐색(tabu search).
• 결정론적 방법:
  • 분기 한정법(branch and bound);
  • 특수 구조를 가진 문제에 대한 전역 최적화 알고리즘.

참고 문헌

• Bazaraa M., Shetty C. Nonlinear Programming: Theory and Algorithms. — М.: Мир, 1982.
• Fiacco A., McCormick G. Nonlinear Programming: Sequential Unconstrained Minimization Techniques. — М.: Мир, 1972.
• Himmelblau D. Applied Nonlinear Programming. — М.: Мир, 1975.
• Nocedal, Jorge; Wright, Stephen J. Numerical Optimization. — Springer, 2006. (2nd ed.)

참고 항목

• 운용과학
• 최적화
• 선형 프로그래밍
• 볼록 프로그래밍
• 목적 함수
• 제약 조건
• 실행 가능 영역