최속강하법을 사용하여 함수의 최소값을 구합니다. 최속강하법
문제 설명
기능을 부여하자 에프엑스(f(x)) Rn
필수의 에프엑스(f(x)) X = Rn
검색 전략
xk
} , k = 0.1,...,
그렇게 
, k = 0.1,...
. 시퀀스 포인트( xk
)는 규칙에 따라 계산됩니다.
요점은 어디에 있습니까? x 0 사용자 정의; 단계 크기 ㅋㅋㅋ 각 값에 대해 결정됨 케이 조건에서
문제 (3)은 필요최소조건을 적용한 후, 충분최소조건을 확인함으로써 해결할 수 있다. 이 경로는 최소화할 매우 간단한 기능이나 다소 복잡한 기능의 예비 근사에 사용할 수 있습니다. 
다항식 P(tk)
(보통 2급 또는 3급) 조건은 조건으로 대체되고 조건은 조건으로 대체됩니다. 
시퀀싱 (xk)
지점에서 끝남 xk
, , 어디에서 ε
- 주어진 작은 양수, 또는 k ≥ M
, 어디 중
- 반복 횟수를 제한하거나 두 부등식을 두 번 동시에 실행하는 경우 
, 
어디 ε 2
- 작은 양수. 문제는 포인트가 가능한지 여부입니다. xk
원하는 로컬 최소점의 발견된 근사치로 간주됩니다. 엑스*
, 추가 연구를 통해 해결되었습니다.
방법의 기하학적 해석 n=2 그림에서. 4.
좌표 하강 방법
문제 설명
기능을 부여하자 에프엑스(f(x)) , 세트에서 아래로 제한됨 Rn 모든 점에서 연속 부분 도함수를 가집니다.
에프엑스(f(x)) 실행 가능한 솔루션 세트에 대해 X = Rn , 즉. 그런 점을 찾아라.
검색 전략
문제를 해결하기 위한 전략은 일련의 점을 구성하는 것입니다( xk
} , k = 0.1,...,
그렇게 , k = 0.1,...
. 시퀀스 포인트( xk
)는 규칙에 따라 사이클에 걸쳐 계산됩니다.
(4)
어디 j - 계산 사이클 수; j = 0,1,2,...; 케이 - 루프 내부의 반복 번호, k = 0,1,...,n - 1; e k +1 , k = 0,l,...,n - 1 -단위 벡터, (k+1) -번째 투영은 1과 같습니다. 점 x00 사용자 정의, 단계 크기 ㅋㅋㅋ 조건에서 선택됩니다.
또는 
.
현재 선택된 조건인 경우 ㅋㅋㅋ
충족되지 않으면 단계가 절반으로 줄어들고 기간이 종료됩니다. 
다시 계산됩니다. 고정된 j에 대해 숫자를 사용한 한 번의 반복으로 쉽게 알 수 있습니다. 케이
점의 투영은 하나만 변경됩니다. xjk
, 번호가 있음 k+1
, 그리고 전체 주기 동안 숫자 j
, 즉. 에서 시작 k = 0
그리고 결말 k = n -1
, 점 변화의 모든 n 투영 xj0
. 이 시점 이후 xjn
번호가 할당되어 있습니다 xj + 1.0
이며, 이는 계산의 시작점으로 간주됩니다. j+1
주기. 계산은 그 시점에서 끝납니다 xjk
세 가지 계산 종료 기준 중 하나 이상이 충족되는 경우: 
, 또는 , 또는 불평등의 이중 실행.
계산 결과로 얻은 포인트는 시퀀스의 요소로 기록될 수 있습니다. (특대), 어디 l=n*j+k - 포인트의 일련번호,
n = 2에 대한 방법의 기하학적 해석이 그림 1에 나와 있습니다. 5.
4. 프랭크-울프 방법 .
오목 함수의 최대값을 찾아야 한다고 가정합니다.
조건 하에서
이 문제의 특징은 제약 조건 시스템에 선형 부등식만 포함되어 있다는 것입니다. 이 기능은 연구 대상 지점 부근에서 비선형 목적 함수를 선형 함수로 대체하기 위한 기초이며, 이로 인해 원래 문제의 해가 선형 계획법 문제의 순차적 해로 축소됩니다.
문제에 대한 해결책을 찾는 과정은 문제에 대한 가능한 해결책 영역에 속하는 지점을 식별하는 것부터 시작됩니다.
270
다차 이것이 요점이 되도록 하라 X(k)
이 시점에서 함수 (57)의 기울기가 계산됩니다.
그리고 선형 함수를 구성합니다.
그런 다음 제한 사항 (58)과 (59)에서 이 함수의 최대값을 찾으십시오. 이 문제에 대한 해결책을 요점으로 결정하십시오. Z(k)
. 그런 다음 해당 점의 좌표는 원래 문제에 대한 새로운 실행 가능한 솔루션으로 사용됩니다. X(k+1)
:
어디 λk - 계산 단계라고 하며 0과 1 사이에 포함된 특정 숫자(0<λk < 1). Это число λk 임의로 취하거나 결정한 것
그래서 그 지점에서 함수의 값은 X (k +1) f(X (k +1)) , 에 따라 λk , 최대였습니다. 이렇게 하려면 방정식에 대한 해를 찾고 가장 작은 근을 선택해야 합니다. 값이 1보다 크면 다음을 입력해야 합니다. λk=1 . 개수를 정한 후 λk 점의 좌표를 구하다 X(k+1) 목적 함수의 값을 계산하고 새로운 지점으로 이동할 필요성을 결정합니다. X(k+2) . 그러한 필요가 있으면 그 시점에서 계산하십시오. X(k+1) 목적 함수의 기울기에 해당하는 선형 계획법 문제로 이동하여 해를 구합니다. 점의 좌표를 결정하고 X(k+2) 추가 계산의 필요성을 조사합니다. 유한한 수의 단계를 거친 후에는 원래 문제에 대한 솔루션이 필요한 정확도로 얻어집니다.
따라서 Frank-Wolfe 방법을 이용하여 문제 (57)~(59)에 대한 해결책을 찾는 과정은 다음과 같은 단계를 포함한다.:
1. 문제에 대한 초기 실행 가능한 솔루션을 결정합니다.
2. 허용되는 해 지점에서 함수(57)의 기울기를 구합니다.
3. 함수 (60)을 구성하고 조건 (58)과 (59)에서 최대값을 찾습니다.
4. 계산 단계를 결정합니다.
5. 공식 (61)을 사용하여 새로운 실현 가능한 솔루션의 구성 요소를 찾습니다.
6. 다음 실현 가능한 솔루션으로 넘어갈 필요성을 확인하십시오. 필요한 경우 2단계로 진행하고, 그렇지 않은 경우 원래 문제에 대해 수용 가능한 해결책을 찾습니다.
페널티 함수의 방법.
오목 함수의 최대값을 결정하는 문제를 고려하십시오.
f(x1, x2, ....xn)조건 하에서 나는 (x 1, x 2, .... x n) ≤ b i (i=l, m) , xj ≥ 0 (j=1, n) , 어디 나는 (x 1, x 2, .... x n) - 볼록한 기능.
이 문제를 직접 해결하는 대신 함수의 최대값을 찾으세요. F(x1, x2, ...., xn)= f(x1, x2, ...., xn) +H(x 1, x 2, ...., x n) 이는 문제의 목적 함수와 일부 함수의 합입니다.
H(x 1, x 2, ...., x n), 제한 시스템에 의해 정의되고 호출됩니다. 페널티 기능. 페널티 함수는 다양한 방식으로 구성될 수 있습니다. 그러나 대부분의 경우 다음과 같습니다.
에이 나는 > 0
- 가중치 계수를 나타내는 일부 상수.
페널티 기능을 사용하여 수용 가능한 솔루션을 얻을 때까지 한 지점에서 다른 지점으로 순차적으로 이동합니다. 이 경우 다음 공식을 사용하여 다음 지점의 좌표를 찾습니다.
마지막 관계에서 이전 점이 원래 문제에 대한 실현 가능한 해 영역에 있는 경우 대괄호 안의 두 번째 항은 0과 같고 다음 점으로의 전환은 목적의 기울기에 의해서만 결정됩니다. 기능. 지정된 점이 허용 가능한 솔루션 영역에 속하지 않는 경우 후속 반복에서 이 항으로 인해 허용 가능한 솔루션 영역으로 돌아가는 것이 달성됩니다.
결정. 동시에, 덜 나는
, 허용 가능한 솔루션을 더 빨리 찾을 수 있지만 결정의 정확도는 감소합니다. 따라서 반복 프로세스는 일반적으로 상대적으로 작은 값에서 시작됩니다. 나는
계속해서 이러한 값은 점차 증가합니다.
따라서 페널티 함수 방법을 사용하여 볼록 계획법 문제에 대한 해결책을 찾는 과정에는 다음 단계가 포함됩니다.
1. 초기 실현 가능한 솔루션을 결정합니다.
2. 계산 단계를 선택하세요.
3. 모든 변수에 대해 문제에 대한 실현 가능한 해의 범위를 결정하는 목적 함수와 함수의 편도함수를 찾습니다.
4. 공식 (72)를 사용하여 문제에 대한 가능한 새로운 해결책을 결정하는 점의 좌표를 찾습니다.
5. 찾은 점의 좌표가 문제제약체계를 만족하는지 확인합니다. 그렇지 않은 경우 다음 단계로 넘어갑니다. 발견된 지점의 좌표가 문제에 대한 허용 가능한 솔루션을 결정하는 경우 다음 허용 가능한 솔루션으로 이동할 필요성이 조사됩니다. 필요한 경우 2단계로 진행합니다. 그렇지 않으면 원래 문제에 대한 수용 가능한 해결책을 찾았습니다.
6. 가중치 계수 값을 설정하고 4단계로 진행합니다.
Arrow-Hurwitz 방법.
페널티 함수 방법을 사용하여 비선형 프로그래밍 문제에 대한 솔루션을 찾을 때 우리는 다음 값을 선택했습니다. 나는 , 임의로 이로 인해 실행 가능한 솔루션 영역에서 결정된 지점의 거리가 크게 변동되었습니다. 이 단점은 Arrow-Hurwitz 방법으로 문제를 해결하면 제거됩니다. 이에 따라 다음 단계에서 숫자는 다음과 같습니다. 나는 (k) 공식으로 계산
초기값으로는 나는 (0) 음수가 아닌 임의의 숫자를 취하십시오.
예제 솔루션
실시예 1.
함수의 국소 최소값 찾기
포인트 정의 xk
1. 설정해 봅시다.
2. 넣어보자 k = 0 .
3 0 . 계산해보자
4 0 . 계산해보자 
. 5단계로 넘어가겠습니다.
5 0 . 상태를 확인해 볼까요 
. 6단계로 넘어가겠습니다.
6 0 . 설정하자 t0 = 0.5 .
7 0 . 계산해보자
8 0 . 비교해 보자 
. 우리는 
. 결론: 조건 k = 0
실행되지 않습니다. 설정하자 t0 = 0.25
, 7, 8단계를 반복합니다.
7 01. 계산해 봅시다.
8 01. 비교해 보자 f(x1) 및 f(x0) . 결론: 에프(x1)< f (x 0) . 9단계로 넘어가겠습니다.
9 0 . 계산해보자
결론: 우리는 믿는다 k=1 그리고 3단계로 넘어갑니다.
3 1. 계산해보자
4 1. 계산해보자 
. 5단계로 넘어가겠습니다.
5 1. 상태를 확인해 볼까요 k ≥ M: k = 1< 10 = M . 6단계로 넘어가겠습니다.
6 1. 설정하자 t 1 = 0.25.
7 1. 계산해보자
8 1. 비교해 보자 f(x 2)와 f(x 1) . 결론: 에프(x2)< f (х 1). 9단계로 넘어가겠습니다.
9 1. 계산해보자
결론: 우리는 믿는다 k = 2 그리고 3단계로 넘어갑니다.
3 2. 계산해보자
4 2. 계산해 봅시다. 5단계로 넘어가겠습니다.
5 2. 상태를 확인해 볼까요 k ≥ M : k = 2< 10 = М , 6단계로 이동하세요.
6 2. 설정하자 t 2 =0,25 .
7 2. 계산해보자
8 2. 비교해 보자 에프(x3) 그리고 에프(x2) . 결론: 에프(x3)< f (х 2) .9단계로 이동합니다.
9 2. 계산해보자 
결론: 우리는 믿는다 k = 3 그리고 3단계로 넘어갑니다.
3 3 . 계산해보자
4 3 . 계산해 봅시다. 5단계로 넘어가겠습니다.
5 3. 상태를 확인해 볼까요 k ≥ M : k = 3<10 = М , 6단계로 이동하세요.
6 3. 설정하자 t 3 = 0.25.
7 3. 계산해보자
8 3. 비교해 보자 에프(x4) 그리고 f (x 3) : f (x 4)< f (х 3) .
9 3. 계산해보자 
다음과 같은 경우 조건이 충족됩니다. k = 2.3 . 계산
완성된. 포인트 발견
그림에서. 결과로 나온 3개의 점은 점선으로 연결됩니다.
II. 포인트 분석 4개 .
기능 
는 두 번 미분 가능하므로 해당 지점에서 최소값에 대한 충분 조건을 확인하겠습니다. 4개
. 이를 위해 헤세 행렬을 분석해 보겠습니다.
행렬은 일정하고 양의 정부호입니다(즉, . H > 0
) 각도 마이너가 모두 양수이기 때문입니다. 그러므로 요점은 
로컬 최소점의 발견된 근사치이며 값은 
발견된 값의 근사치입니다. 에프(엑스 *) =0
. 조건이니 참고하세요 H > 0
, 동시에 함수의 엄격한 볼록성에 대한 조건이 있습니다. 
. 결과적으로 전역 최소점의 근사치가 발견되었습니다. 에프엑스(f(x))
최소값은 R 2
. ■
실시예 2
함수의 국소 최소값 찾기
I. 포인트의 정의 xk, 계산 완료 기준 중 하나 이상을 충족합니다.
1. 설정해 봅시다.
임의의 지점에서 함수의 기울기를 구해보자
2. 넣어보자 k = 0 .
3 0 . 계산해보자
4 0 . 계산해보자 . 5단계로 넘어가겠습니다.
5 0 . 상태를 확인해 볼까요 
. 6단계로 넘어가겠습니다.
6° 다음 점은 공식으로 구합니다
좌표에 대해 얻은 표현식을 다음으로 대체하겠습니다.
함수의 최소값을 구해보자 에프(티 0) 에 의해 t 0 무조건 극값에 필요한 조건을 사용합니다.
여기에서 티 0 =0.24
. 왜냐하면 
, 발견된 단계 값은 함수의 최소값을 제공합니다. 에프(티 0)
에 의해 t 0
.
정의해보자 
7 0 . 우리는 찾을 것이다
8°. 계산해보자
결론: 우리는 믿는다 k = 1 그리고 3단계로 넘어갑니다.
3 1. 계산해보자
4 1. 계산해보자 
5 1. 상태를 확인해 볼까요 k ≥ 1: k = 1< 10 = М.
6 1. 정의해보자
7 1. 우리는 찾을 것이다 
:
8 1. 계산해보자
우리는 믿는다 k = 2 그리고 3단계로 넘어갑니다.
3 2. 계산해보자
4 2. 계산해보자
5 2. 상태를 확인해 볼까요 k ≥ M: k = 2< 10 = M .
6 2. 정의해보자
7 2. 우리는 찾을 것이다 
8 2. 계산해보자
우리는 믿는다 k=3 그리고 3단계로 넘어갑니다.
3 3 . 계산해보자
4 3 . 계산해 봅시다.
계산이 완료되었습니다. 포인트 발견
II. 포인트 분석 x 3 .
예제 1.1(2장 §1)에서는 다음 함수가 표시되었습니다. 에프엑스(f(x)) 는 엄격하게 볼록하므로 점3에서 전역 최소점의 근사치가 발견됩니다. 엑스* .
예시 3.
함수의 국소 최소값 찾기
I. 포인트의 정의 xjk , 계산 완료 기준 중 하나 이상을 충족합니다.
1. 설정하자
임의의 지점에서 함수의 기울기를 구해보자 
2. 설정하자 j = 0.
3 0 . 조건이 맞는지 확인해 볼까요?
4 0 . 설정하자 k = 0.
5 0 . 조건이 맞는지 확인해 볼까요?
6 0 . 계산해보자
7 0 . 상태를 확인해 볼까요 
8 0 . 설정하자
9 0 . 계산해보자 
, 어디
10 0 . 상태를 확인해 볼까요
결론: 가정하고 9단계로 넘어갑니다.
9 01. 계산해보자 x01 증분으로
10 01. 상태를 확인해 볼까요 
11 0 . 조건을 확인해보자
우리는 믿는다 k=1 그리고 5단계로 가세요.
5 1. 상태를 확인해 볼까요
6 1. 계산해보자
7 1. 상태를 확인해 볼까요
8 1. 설정하자
9 1. 계산해보자
10 1. 상태를 확인해 볼까요 
:
11 1. 조건을 확인해보자
우리는 믿는다 k = 2 , 5단계로 이동하세요.
5 2. 상태를 확인해 보겠습니다. 설정하고 3단계로 이동합니다.
3 1. 상태를 확인해 볼까요
4 1. 설정하자 k = 0.
5 2. 상태를 확인해 볼까요
6 2. 계산해보자
7 2. 상태를 확인해 볼까요
8 2. 설정하자
9 2. 계산해보자
10 2. 상태를 확인해 볼까요 
11 2. 조건을 확인해보자
우리는 믿는다 k=1 그리고 5단계로 가세요.
5 3. 상태를 확인해 볼까요
6 3. 계산해보자
7 3. 조건을 확인해보자
8 3. 설정하자
9 3. 계산해보자
10 3. 상태를 확인해 볼까요 
11 3. 조건을 확인해보자
설정하자 k = 2 그리고 5단계로 가세요.
5 4 . 상태를 확인해 볼까요 
우리는 믿는다 j = 2, x 20 = x 12 그리고 3단계로 넘어갑니다.
3 2. 상태를 확인해 볼까요
4 2. 설정하자 k=0 .
5 4 . 상태를 확인해 볼까요
6 4. 계산해보자
7 4. 상태를 확인해 볼까요
8 4. 설정하자
9 4. 계산해보자
10 4. 상태를 확인하고 11단계로 넘어가겠습니다.
11 4. 조건을 확인해보자
조건은 숫자가 포함된 두 개의 연속 주기에서 충족됩니다. j = 2 그리고 j -1= 1 . 계산이 완료되었습니다. 포인트를 찾았습니다.
그림에서. 결과로 나온 6개의 점은 점선으로 연결됩니다.
좌표 하강 방법에서는 좌표축에 평행한 직선 세그먼트로 구성된 파선을 따라 하강합니다.
II. x21 포인트 분석.
예제 1.1에서는 다음 함수가 표시되었습니다. 에프엑스(f(x))
엄격하게 볼록하고 고유한 최소값을 가지므로 점 
전역 최소점의 발견된 근사치입니다.
위에서 설명한 모든 그래디언트 방법에서 점의 시퀀스는 (xk) 함수의 정지점으로 수렴 에프엑스(f(x)) 이 기능의 속성에 관한 상당히 일반적인 제안을 사용합니다. 특히 다음 정리는 참입니다.
정리. 함수 f(x)가 아래에 국한된 경우 해당 기울기는 Lipschitz 조건()과 값 선택을 충족합니다. 테네시 위에서 설명한 방법 중 하나로 생성된 경우 시작점이 무엇이든 간에 x 0 :
에 .
계획의 실제 구현에서
k =1, 2, … n.
모든 경우 반복이 중지됩니다. 나, 나는 = 1, 2, ..., n , 다음과 같은 조건
,
최소값을 찾는 정확도를 나타내는 특정 숫자는 어디에 있습니까?
정리 조건 하에서 기울기 방법은 함수 또는 정확한 하한으로의 수렴을 보장합니다(함수가 다음과 같은 경우). 에프엑스(f(x)) 최소값이 없습니다. 쌀. 7) 또는 수열의 한계인 어떤 정지점에서의 함수 값 (xk). 이 시점에서 안장이 구현되면 예를 드는 것은 어렵지 않으며 최소한은 아닙니다. 실제로 경사하강법은 안장점을 우회하고 목적 함수의 최소값(일반적으로 로컬 함수)을 찾습니다.
결론
그라디언트 비제약 최적화 방법의 예는 위에서 논의되었습니다. 수행된 작업의 결과로 다음과 같은 결론을 내릴 수 있습니다.
1. 제한이 있는 상태에서 극값을 찾는 다소 복잡한 문제에는 특별한 접근 방식과 방법이 필요합니다.
2. 제약이 있는 문제를 해결하기 위한 많은 알고리즘에는 제약이 없는 최소화가 일부 단계로 포함됩니다.
3. 다양한 하강 방법은 하강 방향과 이 방향에 따른 계단 길이를 선택하는 방식이 서로 다릅니다.
4. 문제의 공식화를 설명하는 기능의 모든 특징을 고려한 이론은 아직 없습니다. 문제를 해결하는 과정에서 관리하기 쉬운 방법을 선호해야 합니다.
실제 적용된 최적화 문제는 매우 복잡합니다. 현대의 최적화 방법은 사람의 도움 없이 실제 문제를 해결하는 데 항상 대처할 수는 없습니다.
참고자료
1. 코소루코프 O.A. 운영 연구: 교과서. 2003년
2. 판틀리프 A.V. 예제와 문제의 최적화 방법: 교과서. 혜택. 2005년
3. Shishkin E.V. 운영 연구: 교과서. 2006년
4. Akulich I.L. 예제와 문제를 통한 수학적 프로그래밍. 1986년
5. 벤젤 E.S. 운영 연구. 1980년
6. Ventzel E.S., 오브차로프 L.A. 확률이론과 그 공학적 응용. 1988년
©2015-2019 사이트
모든 권리는 해당 저작자에게 있습니다. 이 사이트는 저작권을 주장하지 않지만 무료로 사용할 수 있습니다.
페이지 생성일 : 2017-07-02
주석: 본 강의에서는 최속하강법, Davidon-Fletcher-Powell 방법 등 다중 매개변수 최적화 방법을 폭넓게 다루고 있습니다. 또한 가장 효과적인 방법을 결정하기 위해 위의 방법에 대한 비교 분석을 수행하고 장점과 단점을 식별합니다. 또한 계곡법(ravine method), 다극법(multiextremal method)과 같은 다차원 최적화 문제도 고려합니다.
1. 최속강하법
이 방법의 핵심은 앞서 언급한 방법을 사용한다는 것입니다. 좌표 하강법검색은 축 중 하나와 평행한 방향의 주어진 지점에서 이 방향의 최소 지점까지 수행됩니다. 그런 다음 다른 축과 평행한 방향으로 검색이 수행됩니다. 물론 방향은 정해져 있습니다. 각 단계에서 최소점 검색이 "최적" 방향을 따라 수행되도록 이 방법을 수정하는 것이 합리적으로 보입니다. 어느 방향이 "최선"인지는 확실하지 않지만, 그라데이션 방향함수가 가장 빠르게 증가하는 방향입니다. 따라서 반대 방향은 함수가 가장 빠르게 감소하는 방향입니다. 이 속성은 다음과 같이 정당화될 수 있습니다.
점 x에서 다음 점 x + hd로 이동한다고 가정합니다. 여기서 d는 특정 방향이고 h는 특정 길이의 계단입니다. 결과적으로 이동은 지점 (x 1, x 2, ..., x n)에서 지점으로 이루어집니다. (x1 + zx1, x2 + zx2, ..., xn + zxn), 어디
함수 값의 변화는 관계식에 의해 결정됩니다.
| (1.3) |
1차 zx i 까지, 부분 도함수는 x 지점에서 계산됩니다. 함수 df의 가장 큰 변화 값을 얻기 위해 방정식 (1.2)을 만족하는 방향 d i를 어떻게 선택해야 합니까? 제약 조건이 있는 최대화 문제가 발생하는 곳입니다. 함수를 결정하는 데 도움이 되는 라그랑주 승수 방법을 적용해 보겠습니다.
제약 조건 (1.2)을 만족하는 df 값은 다음과 같은 경우 최대값에 도달합니다.
최대치에 도달합니다. 그 파생물
따라서,
 |
(1.6) |
그러면 di ~ df/dx i이고 d 방향은 x 지점에서 V/(x) 방향과 평행합니다.
따라서, 지역 최대 증가주어진 작은 스텝 h에 대한 함수는 d가 Vf(x) 또는 g(x) 방향일 때 발생합니다. 따라서 가장 가파른 하강법의 방향은 다음과 같습니다.
더 간단한 형태로 방정식 (1.3)은 다음과 같이 작성할 수 있습니다.
벡터 Vf(x)와 dx 사이의 각도는 어디에 있습니까? 주어진 dx 값에 대해 dx 방향이 -Vf(x) 방향과 일치하도록 선택하여 df를 최소화합니다.
논평. 그라데이션 방향일정한 높이의 선 위의 모든 점에 수직입니다. 왜냐하면 이 선을 따라 함수가 일정하기 때문입니다. 따라서 (d 1, d 2, ..., d n)이 레벨 라인을 따라 작은 단계인 경우
그러므로
 |
(1.8) |
함수 입력 규칙
안에 최속하강법함수 ▽f(x)의 기울기 벡터 방향과 반대 방향인 벡터가 검색 방향으로 선택됩니다. 수학적 분석을 통해 벡터 grad f(x)=▽f(x)는 함수의 가장 빠른 증가 방향을 특징으로 하는 것으로 알려져 있습니다(함수의 기울기 참조). 따라서 벡터 - grad f(X) = -▽f(X)가 호출됩니다. 안티그라디언트가장 빠르게 감소하는 방향입니다. 최속강하법이 구현되는 반복 관계는 X k +1 =X k - λ k ▽f(x k), k = 0,1,...,
여기서 λ k >0은 단계 크기입니다. 선택한 단계 크기에 따라 그라데이션 방법에 대한 다양한 옵션을 얻을 수 있습니다. 최적화 프로세스 중에 단계 크기 λ가 고정된 경우 이 방법을 이산 단계를 사용하는 그래디언트 방법이라고 합니다. λ k =min f(X k + λS k) 조건에서 λ k 를 선택하면 첫 번째 반복의 최적화 프로세스가 상당히 가속화될 수 있습니다.
λk를 결정하기 위해 임의의 1차원 최적화 방법이 사용됩니다. 이 경우의 방법을 최속강하법이라 한다. 일반적으로, 한 단계로는 함수의 최소값을 달성하는 데 충분하지 않으며 후속 계산에서 결과가 향상될 때까지 프로세스가 반복됩니다.
일부 변수에서 공간이 매우 길어지면 "협곡"이 형성됩니다. 검색 속도가 느려지고 "협곡" 바닥을 가로질러 지그재그로 이동할 수 있습니다. 때로는 허용 가능한 시간 내에 솔루션을 얻을 수 없는 경우도 있습니다.
이 방법의 또 다른 단점은 중지 기준 ||▽f(X k)||<ε k , так как этому условию удовлетворяет и седловая точка, а не только оптимум.
예. x k =(-2, 3) 점에서 시작하여 최속하강법을 사용하여 함수를 최소화하는 점 x k +1을 결정합니다.
검색 방향으로 현재 지점의 그래디언트 벡터를 선택합니다. 
정지 기준을 확인해 보겠습니다. 우리는 
초기점 f(X 1) = 35에서 함수의 값을 계산해 보겠습니다.
반경사 방향을 따라 단계
새로운 지점에서 함수의 값을 계산해 봅시다
f(X 2) = 3(-2 + 19 λ 1) 2 + (3-8 1) 2 - (-2 + 19 1)(3-8 1) - 4(-2 + 19 1)
이 방향을 따라 목적 함수가 최소값에 도달하는 단계를 찾아보겠습니다. 함수의 극한이 존재하기 위한 필요조건으로부터
f'(X 2) = 6(-2 + 19λ 1) 19 + 2(3-8λ 1)(-8) – (73 - 304 λ 1) – 4*19
또는 f'(X 2) = 2598 λ 1 – 425 = 0.
우리는 단계 λ 1 = 0.164를 얻습니다.
이 단계를 완료하면 요점으로 연결됩니다. 
여기서 그라디언트 값은 
, 함수값 f(X 2) = 0.23. 반구배 방향을 따라 한 걸음 더 나아간 지점부터 정확도가 달성되지 않습니다.
f(X 2) = 3(1.116 – 1.008 λ 1) 2 + (1.688-2.26 λ 1) 2 - (1.116 – 1.008 1)(1.688-2.26 1) - 4(1.116 – 1.008 1)
f'(X 2) = 11.76 – 6.12λ 1 = 0
우리는 λ 1 = 0.52를 얻습니다. 
그라데이션 방향에서 가장 좋은 지점을 검색하는 것이 아니라 현재 지점보다 더 나은 지점을 검색할 수도 있습니다.
모든 로컬 최적화 방법 중 구현이 가장 쉽습니다. 수렴 조건이 다소 약한 편이나 수렴 속도가 상당히 낮습니다(선형). 그래디언트 방법 단계는 Fletcher-Reeves 방법과 같은 다른 최적화 방법의 일부로 자주 사용됩니다.
설명 [ | ]
개량[ | ]
경사하강법은 계곡을 따라 이동할 때 속도가 매우 느린 것으로 나타났으며, 목적 함수의 변수 수가 증가할수록 이러한 방법의 동작이 일반적이 됩니다. 이 현상을 방지하기 위해 사용되며 그 본질은 매우 간단합니다. 두 단계의 경사하강법을 거쳐 세 개의 점을 얻은 후, 세 번째 단계는 계곡 바닥을 따라 첫 번째 점과 세 번째 점을 연결하는 벡터 방향으로 진행해야 합니다.
2차 함수에 가까운 함수의 경우 켤레 기울기 방법이 효과적입니다.
인공 신경망에서의 응용[ | ]
약간 수정된 경사하강법은 퍼셉트론 훈련에 널리 사용되며 인공 신경망 이론에서는 역전파 방법으로 알려져 있습니다. 퍼셉트론 형태의 신경망을 훈련시킬 때 일련의 훈련 입력 데이터가 입력에 공급될 때 신경망 출력의 평균 오류가 최소화되도록 네트워크의 가중치 계수를 변경하는 것이 필요합니다. 공식적으로 경사하강법을 사용하여 한 단계만 수행하려면(네트워크 매개변수를 한 번만 변경) 전체 학습 데이터 세트를 네트워크 입력에 순차적으로 제출하고 각 객체에 대한 오류를 계산해야 합니다. 훈련 데이터를 수집하고 필요한 네트워크 계수 수정을 계산합니다(그러나 이 수정은 수행하지 않음). 모든 데이터를 제출한 후 각 네트워크 계수(그라디언트의 합) 수정 금액을 계산하고 계수를 "한 단계" 수정합니다. . 분명히 대규모 훈련 데이터 세트를 사용하면 알고리즘이 매우 느리게 작동하므로 실제로 각 훈련 요소 후에 네트워크 계수가 조정되는 경우가 많습니다. 여기서 기울기 값은 단 하나의 훈련에서만 계산되는 비용 함수의 기울기로 근사화됩니다. 요소. 이 방법은 확률적 경사하강법 또는 조작적 경사하강법 . 확률적 경사하강법은 확률적 근사의 한 형태입니다. 확률론적 근사 이론은 확률론적 경사하강법의 수렴을 위한 조건을 제공합니다.
모래밭 [ | ]
- J. 매튜스.가장 가파른 내리막 또는 경사법을 위한 모듈. (사용할 수 없는 링크)
문학 [ | ]
- 아쿨리치 I. L.예제와 문제를 통한 수학적 프로그래밍. -M .: 고등 학교, 1986. -P. 298-310.
- 길 F., 머레이 W., 라이트 M.실용적인 최적화 = 실용적인 최적화. -M .: 미르, 1985.
- Korshunov Yu.사이버네틱스의 수학적 기초. -M .: Energoatomizdat, 1972.
- Maksimov Yu.A., Fillipovskaya E.A.비선형 계획법 문제를 해결하기 위한 알고리즘. -M .: MEPHI, 1982.
- 막시모프 A.선형 및 이산 프로그래밍을 위한 알고리즘. -M .: MEPHI, 1980.
- 콘 G., 콘 T.과학자와 엔지니어를 위한 수학 핸드북. -M .: Nauka, 1970. -P. 575-576.
- S. Yu. Gorodetsky, V. A. Grishagin.비선형 프로그래밍 및 다극 최적화. - 니즈니 노브고로드: 니즈니 노브고로드 대학 출판사, 2007. - P. 357-363.
최속강하법은 가변 단계를 갖는 경사법입니다. 각 반복에서 단계 크기 k는 하강 방향의 함수 f(x)의 최소 조건에서 선택됩니다. 즉,
이 조건은 함수 f(x)의 값이 감소하는 한 반경사를 따른 움직임이 발생함을 의미합니다. 수학적 관점에서 각 반복마다 함수별 1차원 최소화 문제를 해결하는 것이 필요합니다.
()=f(x(k) -f(x(k)))
이를 위해 황금비 방법을 사용해 보겠습니다.
최속강하법의 알고리즘은 다음과 같다.
시작점 x(0)의 좌표가 지정됩니다.
x(k)점, k = 0, 1, 2, ...에서 기울기 값 f(x(k))가 계산됩니다.
단계 크기 k는 다음 함수를 사용하여 1차원 최소화로 결정됩니다.
()=f(x(k)-f(x(k))).
x(k) 점의 좌표가 결정됩니다.
x i (k+1) = x i (k) - k f i (x (k)), i=1, …, n.
반복 프로세스를 중지하기 위한 조건이 확인됩니다.
||f(x(k +1))|| .
충족되면 계산이 중지됩니다. 그렇지 않으면 1단계로 진행합니다. 최속강하법의 기하학적 해석은 그림 1에 나와 있습니다. 1.
쌀. 2.1. 최속강하법의 블록 다이어그램.
프로그램에서 방법 구현:
최속하강법.
쌀. 2.2. 최속강하법 구현.
결론: 우리의 경우 방법은 7번의 반복으로 수렴되었습니다. A7 지점(0.6641; -1.3313)은 극점입니다. 공액 방향의 방법. 2차 함수의 경우 수렴 시간이 유한하고 변수 수 n과 동일한 그래디언트 방법을 만들 수 있습니다.
다음과 같은 경우 양의 정부호 헤스 행렬 H에 대해 특정 방향과 켤레를 호출해 보겠습니다.
즉, 단위 H의 경우 공액 방향은 수직을 의미합니다. 일반적인 경우 H는 중요하지 않습니다. 일반적인 경우 공액은 헤스 행렬을 벡터에 적용하는 것입니다. 이는 이 벡터를 어떤 각도로 회전시키거나 늘리거나 압축하는 것을 의미합니다.
이제 벡터는 직교합니다. 즉, 공액은 벡터의 직교성이 아니라 회전된 벡터의 직교성입니다.
쌀. 2.3. 켤레 방향 방법의 블록 다이어그램.
프로그램에서 방법 구현: 공액 방향 방법.
쌀. 2.4. 공액 방향 방법의 구현.
쌀. 2.5. 켤레 방향 방법의 그래프.
결론: A3 지점(0.6666; -1.3333)은 3번의 반복에서 발견되었으며 극점입니다.
3. 제한이 있는 경우 함수의 최소값과 최대값을 결정하는 방법 분석
일반적인 제한된 최적화 문제는 다음과 같습니다.
f(x) ® 최소, x О W,
여기서 W는 Rm의 진부분집합입니다. 등호 유형 제약 조건이 있는 문제의 하위 클래스는 집합 가 다음 형식의 제약 조건으로 정의된다는 사실로 구별됩니다.
f i (x) = 0, 여기서 f i: R m ®R (i = 1, …, k).
따라서, W = (x О R m: fi (x) = 0, i = 1, …, k)입니다.
함수 f에 대해 인덱스 "0"을 쓰는 것이 편리할 것입니다. 따라서 동등 유형 제약 조건이 있는 최적화 문제는 다음과 같이 작성됩니다.
f 0 (x) ® 최소, (3.1)
f i (x) = 0, i = 1, …, k. (3.2)
이제 f를 R k의 값으로 R m에 대한 함수로 표시하면 좌표 표기법은 f(x) = (f 1 (x), ..., f k (x)) 형식입니다. 3.1)–(3.2) 다음과 같은 형식으로 작성할 수도 있습니다.
f 0 (x) ® 최소, f(x) = Q.
기하학적으로, 등식 유형 제약 조건의 문제는 다양체 에 대한 함수 f 0 그래프의 가장 낮은 점을 찾는 문제입니다(그림 3.1 참조).
모든 제한 사항을 충족하는 점(예: 집합 의 점)을 일반적으로 허용 가능하다고 합니다. 허용 가능한 점 x*는 제약 조건 f i (x) = 0, i = 1, ..., k(또는 문제 (3.1)–(3.2))에 대한 해법 하에서 함수 f 0의 조건부 최소값이라고 합니다. 허용되는 모든 지점에 대해 x f 0 (x *) f 0 (x). (3.3)
(3.3)이 x* 지점의 일부 이웃 V x *에 있는 허용 가능한 x에 대해서만 만족되는 경우 로컬 조건부 최소값에 대해 이야기합니다. 조건부 엄격한 로컬 및 전역 최소값의 개념은 자연스러운 방식으로 정의됩니다.
