제약된 최적화

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 제약 조건 만족 문제와의 관계
3. 일반적인 형태
4. 해결 방법
- 4.1. 등식 제약 조건
  - 4.1.1. 대입법
  - 4.1.2. 라그랑주 승수법
- 4.2. 부등식 제약 조건
참조

1. 개요

제약된 최적화는 최적화될 목적 함수를 포함하는 제약 만족 문제(CSP)의 일반화이다. 제약 조건은 등식 또는 부등식 형태로 표현되며, 목적 함수는 이러한 제약 조건을 충족하면서 최적화되어야 한다. 제약 최적화 문제는 대입법, 라그랑주 승수법, 선형 계획법, 비선형 계획법, 이차 계획법, KKT 조건, 분기 한정법, 버킷 제거 등 다양한 방법을 통해 해결될 수 있다.

더 읽어볼만한 페이지

제약 프로그래밍 - AC-3 알고리즘
AC-3 알고리즘은 제약 만족 문제 해결에 사용되며, 변수, 도메인, 제약 조건을 기반으로 아크 일관성을 유지하며 도메인을 축소시켜 해를 찾는 알고리즘이다.
제약 프로그래밍 - 제약 충족 문제
제약 충족 문제는 주어진 제약 조건을 만족하는 변수 값을 찾는 문제로, 백트래킹, 제약 전파 등의 방법으로 해결하며, 특정 조건에서는 다항 시간 내에 해결 가능하다.
수학적 최적화 - 모서리해
모서리 해는 경제학에서 소비자가 예산 제약 하에 효용을 극대화할 때, 두 상품 중 하나만 소비하는 경우를 의미하며, 이는 소비자의 극단적인 선택이나 완전 대체재 관계에서 가격이 낮은 상품만 구매하는 경우 등에 나타나는 현상입니다.
수학적 최적화 - 효용 극대화
효용 극대화는 소비자가 제한된 예산으로 상품 구매를 통해 얻는 만족을 최대로 하려는 경제 행위이며, 한계효용균등의 법칙에 따라 지출 배분을 결정하고 생산자의 이윤 극대화에도 적용된다.

제약된 최적화
제약된 최적화
제약된 최적화 문제의 예시
개요
분야	수학 컴퓨터 과학 경제학 경영 과학
다른 이름	제약 조건이 있는 최적화
연구 분야	최적화, 수리 계획법
일반 형태
목적 함수	f(x)
인수	x ∈ {x₁, x₂, ... ,xₙ}
최소화	최소화
제약 조건
부등식 제약 조건	gᵢ(x) ≤ 0
등식 제약 조건	hⱼ(x) = 0
해법
선형 계획법	심플렉스 알고리즘
비선형 계획법	순차 2차 계획법 준 뉴턴 방법
관련 항목
관련 항목	최적화 최적화 알고리즘 라그랑주 승수 KKT 조건 수리 계획법 최적 제어

2. 제약 조건 만족 문제와의 관계

제약 최적화 문제(COP)는 고전적인 제약 만족 문제(CSP) 모델을 크게 일반화한 것이다.^[7]^[1] COP는 최적화될 ''목적 함수''를 포함하는 CSP이다. 최적화 부분을 처리하기 위해 많은 알고리즘이 사용된다.

3. 일반적인 형태

제약된 일반적인 최소화 문제는 다음과 같이 표현할 수 있다.

: $\begin{array}{rcll}\min &~& f(\mathbf{x}) & \\\mathrm{subject~to} &~& g_i(\mathbf{x}) = c_i &\text{for } i=1,\ldots,n \quad \text{등식 제약} \\&~& h_j(\mathbf{x}) \geq d_j &\text{for } j=1,\ldots,m \quad \text{부등식 제약}\end{array}$

여기서 $g_i(\mathbf{x}) = c_i ~\mathrm{for~} i=1,\ldots,n$ 및 $h_j(\mathbf{x}) \ge d_j ~\mathrm{for~} j=1,\ldots,m$ 는 충족되어야 하는 제약 조건(강성 제약)이며, $f(\mathbf{x})$ 는 제약 조건을 충족하면서 최적화되어야 하는 목적 함수이다.

어떤 문제에서는, 종종 ''제약 최적화 문제''라고 불리는데, 목적 함수는 실제로 각 연성 제약 (충족되는 것이 바람직하지만 반드시 충족되어야 하는 것은 아님)이 위반된 정도(있는 경우)를 페널티하는 비용 함수의 합이다.

4. 해결 방법

많은 제약 최적화 알고리즘은 페널티 방법을 사용하여 비제약 문제에 적용될 수 있다. 그러나 비제약 방법으로 수행된 탐색 단계가 제약 문제에 대해 허용되지 않아 수렴 문제가 발생할 수 있는데, 이를 마라토스 효과라고 한다.

4. 1. 등식 제약 조건

4. 1. 1. 대입법

매우 간단한 문제, 예를 들어 단일 등식 제약 조건이 있는 두 변수의 함수인 경우 대입법을 적용하는 것이 가장 실용적이다.^[4] 아이디어는 제약 조건의 영향을 통합하는 함수 합성을 만들기 위해 제약 조건을 목적 함수에 대입하는 것이다. 예를 들어, 목적이 ''f''(''x'',''y'') = ''x'' · ''y''를 ''x'' + ''y'' = 10의 제약 조건 하에서 최대화하는 것이라고 가정해 보자. 제약 조건은 ''y'' = 10 - ''x''를 의미하며, 이를 목적 함수에 대입하여 ''p''(''x'') = ''x'' (10 - ''x'') = 10''x'' - ''x''²를 만들 수 있다. 1차 필요 조건은 ∂''p''/∂''x'' = 10 - 2''x'' = 0을 제공하며, 여기서 ''x''=5를 풀 수 있고, 결과적으로 ''y'' = 10 - 5 = 5이다.

4. 1. 2. 라그랑주 승수법

라그랑주 승수 방법을 사용하여 제약 조건을 변환하여 변수의 수가 원래 변수의 수와 원래 등식 제약 조건의 수를 더한 제약 없는 문제로 바꿀 수 있다. 제약 조건이 모두 등식 제약 조건이고 모두 선형인 경우, 다른 변수를 기준으로 일부 변수를 풀어내고, 전자를 목적 함수에서 대체하여 변수의 수가 더 적은 제약 없는 문제를 만들 수 있다.

4. 2. 부등식 제약 조건

부등식 제약 조건이 있는 경우, 문제는 기하학적 최적성 조건, 프리츠 존 조건 및 카루쉬-쿠-터커 조건으로 특징지을 수 있으며, 이를 통해 간단한 문제를 해결할 수 있다.

4. 2. 1. 선형 계획법

만약 목적 함수와 모든 하드 제약 조건이 선형이고 일부 하드 제약 조건이 부등식이라면, 그 문제는 선형 계획법 문제입니다. 이 문제는 일반적으로 문제 크기에 대해 다항 시간 안에 작동하지만 보장되지는 않는 심플렉스 방법이나, 다항 시간 안에 작동하도록 보장된 내부점 방법으로 해결할 수 있습니다.

4. 2. 2. 비선형 계획법

목적 함수 또는 제약 조건 중 일부가 비선형이고 일부 제약 조건이 부등식인 경우, 이 문제는 비선형 계획법 문제이다.

4. 2. 3. 이차 계획법

만약 모든 제약 조건이 선형이고 일부가 부등식이며 목적 함수가 이차 함수인 경우, 이 문제는 이차 계획법 문제이다. 이는 비선형 계획법의 한 유형이다. 목적 함수가 볼록 함수이면 엘립소이드 방법으로 다항 시간 내에 풀 수 있지만, 그렇지 않으면 이 문제는 NP-hard일 수 있다.

4. 2. 4. KKT 조건

KKT 조건은 부등식 제약 조건을 허용하여 라그랑주 승수법을 일반화한 비선형 프로그래밍 방법이다. 미분 가능성과 볼록성 하에서 적용될 수 있다.

4. 2. 5. 분기 한정법

분기 한정법 알고리즘을 사용하여 제약 최적화 문제를 해결할 수 있다. 이 알고리즘은 실행 중에 발견된 최적 해의 비용을 저장하고 이를 사용하여 검색의 일부를 피하는 백트래킹 알고리즘이다. 좀 더 정확하게는, 알고리즘이 저장된 최적 비용보다 더 나은 비용의 해를 형성하도록 확장할 수 없는 부분 해를 만날 때마다, 이 해를 확장하려는 시도 대신 백트래킹을 수행한다.

비용을 최소화해야 한다고 가정할 때, 이러한 알고리즘의 효율성은 부분 해를 확장하여 얻을 수 있는 비용을 평가하는 방법에 따라 달라진다. 실제로 알고리즘이 부분 해로부터 백트래킹할 수 있다면, 검색의 일부가 건너뛰어진다. 추정 비용이 낮을수록 알고리즘이 더 효율적인데, 추정 비용이 낮을수록 지금까지 발견된 최적 해의 비용보다 낮을 가능성이 더 높기 때문이다.

반면에, 이 추정 비용은 해를 확장하여 얻을 수 있는 실제 비용보다 낮을 수 없는데, 그렇지 않으면 알고리즘이 지금까지 발견된 최적 해보다 더 나은 해가 존재함에도 백트래킹할 수 있기 때문이다. 결과적으로 알고리즘은 부분 해를 확장하여 얻을 수 있는 비용에 대한 상한을 필요로 하며, 이 상한은 가능한 한 작아야 한다.

이 접근 방식의 변형인 한센 방법은 구간 방법을 사용한다.^[5] 이는 본질적으로 직사각형 제약을 구현한다.

4. 2. 6. 버킷 제거

버킷 제거 알고리즘은 제약 최적화에 적용될 수 있다. 주어진 변수는 이를 포함하는 모든 완화 제약 조건을 새로운 완화 제약 조건으로 대체하여 문제에서 제거될 수 있다. 이 새로운 제약 조건의 비용은 제거된 변수의 모든 값에 대해 최댓값을 가정하여 계산된다. 공식적으로, 제거할 변수가

x

이고, 이를 포함하는 완화 제약 조건이

C_1,\ldots,C_n

이며,

y_1,\ldots,y_m

이

x

를 제외한 해당 변수일 경우, 새로운 완화 제약 조건은 다음과 같이 정의된다.

:

C(y_1=a_1,\ldots,y_n=a_n) = \max_a \sum_i C_i(x=a,y_1=a_1,\ldots,y_n=a_n).

버킷 제거는 변수의 (임의의) 순서로 작동한다. 모든 변수는 제약 조건의 버킷과 연관된다. 변수의 버킷에는 순서상 해당 변수를 가장 높게 갖는 모든 제약 조건이 포함된다. 버킷 제거는 마지막 변수에서 처음 변수로 진행된다. 각 변수에 대해 버킷의 모든 제약 조건은 위와 같이 해당 변수를 제거하도록 대체된다. 결과 제약 조건은 적절한 버킷에 배치된다.

참조

_[1] 간행물 Chapter 1 – Introduction http://www.sciencedi[...] Elsevier 2006-01-01
_[2] 서적 Engineering Design Optimization https://www.research[...] Cambridge University Press 2021
_[3] 서적 Optimization Theory and Methods: Nonlinear Programming Springer 2010
_[4] 서적 Basic Mathematics for Economists Routledge
_[5] 서적 Numerical Analysis and Scientific Computation Addison Wesley
_[6] 논문 Russian doll search for solving constraint optimization problems https://web.archive.[...] 1996
_[7] 인용 Chapter 1 – Introduction http://www.sciencedi[...] Elsevier 2006-01-01

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com