1차 최적성 측정값
1차 최적성 측정값이란?
1차 최적성은 점 x가 최적해에 얼마나 가까운지를 측정한 값입니다. 알고리즘에 따라 정의가 다르기는 하지만 대부분의 Optimization Toolbox™ 솔버가 이 측정값을 사용합니다. 1차 최적성은 필요 조건이지만 충분 조건은 아닙니다. 즉, 다음과 같습니다.
1차 최적성 측정값의 최솟값은 0이어야 합니다.
1차 최적성이 0인 점이 반드시 최솟값이지는 않습니다.
1차 최적성에 대한 일반적인 정보는 Nocedal과 Wright의 문헌[31]을 참조하십시오. Optimization Toolbox 솔버의 1차 최적성 측정값에 대한 구체적인 정보는 제약 조건이 없는 최적성, 제약 조건이 있는 최적성 이론, 솔버 형식에서 제약 조건이 있는 최적성 항목을 참조하십시오.
1차 최적성과 관련된 중지 규칙
OptimalityTolerance
허용오차는 1차 최적성 측정값과 관련이 있습니다. 일반적으로, 1차 최적성 측정값이 OptimalityTolerance
보다 작은 경우 솔버 반복이 종료됩니다.
일부 솔버 또는 알고리즘은 중지 기준으로 상대적인 1차 최적성을 사용합니다. 1차 최적성 측정값이 μ와 OptimalityTolerance
의 곱보다 작으면 솔버 반복이 종료됩니다. 여기서 μ는 다음 중 하나에 해당됩니다.
x0
에서의 목적 함수 기울기에 대한 무한대 노름(최댓값)linprog
의f
또는b
, 혹은quadprog
의H
와 같이 솔버에 대한 입력값의 무한대 노름(최댓값)
상대적 측정값은 문제의 규모를 고려하여 적용이 됩니다. 목적 함수에 아주 큰 숫자나 아주 작은 숫자를 곱해도 상대적 중지 기준의 중지 조건이 변경되지 않지만, 스케일링되지 않은 중지 기준인 경우 중지 조건은 변경됩니다.
향상된 종료 메시지를 사용하는 솔버는 상대적 1차 최적성을 사용할 때 이를 중지 조건 세부 정보에 표시합니다.
제약 조건이 없는 최적성
매끄러운 제약 조건이 없는 문제의 경우,
1차 최적성 측정값은 ∇f(x)의 무한대 노름(즉, 최대 절댓값)이며, 다음과 같습니다.
이 최적성 측정값은 매끄러운 함수가 최솟값에 도달하는 데 대한 친숙한 조건(즉, 기울기가 0이어야 함)을 기반으로 합니다. 제약 조건이 없는 문제의 경우, 1차 최적성 측정값이 거의 0이면 목적 함수의 기울기도 거의 0이 되므로 목적 함수가 최솟값에 근접할 가능성이 있다는 의미입니다. 1차 최적성 측정값이 작지 않으면 목적 함수가 최소가 아닌 것입니다.
제약 조건이 있는 최적성 이론
이 섹션에서는 제약 조건이 있는 문제의 1차 최적성 측정값에 대한 정의의 기반이 되는 이론을 요약하여 설명합니다. Optimization Toolbox 함수에 사용된 정의는 솔버 형식에서 제약 조건이 있는 최적성에 나와 있습니다.
매끄러운 제약 조건이 있는 문제에 대해 g 및 h가 모든 부등식 제약 조건과 등식 제약 조건(즉, 범위 제약 조건, 선형 제약 조건, 비선형 제약 조건)을 각각 나타내는 벡터 함수라고 가정합니다.
이 경우 1차 최적성이 가지는 의미는 제약 조건이 없는 문제에 대해서보다 더 복잡합니다. 이 정의는 카루쉬-쿤-터커(KKT) 조건을 기반으로 합니다. KKT 조건은 최소점에서 기울기가 0이어야 하는 조건과 비슷하나 제약 조건을 고려하기 위해 변형되었습니다. 차이점은 KKT 조건은 제약 조건이 있는 문제에 대해 적용된다는 것입니다.
KKT 조건은 보조 라그랑주 함수를 사용합니다.
(1) |
KKT 조건은 다음과 같습니다.
(2) |
(3) |
(4) |
수식 2와 관련된 최적성 측정값은 다음과 같습니다.
(5) |
(6) |
결합된 최적성 측정값은 수식 5 및 수식 6에서 계산된 값의 최댓값입니다. 비선형 제약 조건 함수를 받는 솔버는 제약 조건 위반 값 g(x) > 0 또는 |h(x)| > 0를 ConstraintTolerance
위반으로 보고합니다. 허용오차와 중지 기준 항목을 참조하십시오.
솔버 형식에서 제약 조건이 있는 최적성
대부분의 제약 조건이 있는 툴박스 솔버는 1차 최적성 측정값 계산을 범위, 선형 함수, 비선형 함수로 분리합니다. 이 측정값은 수식 5 및 수식 6에 대응되는 다음 두 노름의 최댓값입니다.
(7) |
(8) |
여기서 수식 7 및 수식 8의 벡터의 노름은 무한대 노름(최댓값)입니다. 라그랑주 승수의 첨자는 솔버 라그랑주 승수 구조체에 대응됩니다. 라그랑주 승수 구조체 항목을 참조하십시오. 수식 7의 합들의 범위에는 모든 제약 조건을 포함합니다. 범위가 ±Inf
인 경우 그 항에는 제약 조건이 없으므로 합에 포함되지 않습니다.
선형 등식만 포함
선형 등식만 있는 일부 대규모 문제에 대해 1차 최적성 측정값은 사영된 기울기의 무한대 노름입니다. 다시 말해서, 1차 최적성 측정값은 Aeq
의 영공간으로 사영된 기울기의 크기입니다.
유계 최소제곱 솔버와 Trust-Region-Reflective 솔버
최소제곱 솔버와 trust-region-reflective 알고리즘에 대해 범위만 포함하는 문제에서 1차 최적성 측정값은 |vi*gi|의 i에 대한 최댓값입니다. 여기서 gi는 기울기의 i번째 성분이고, x는 현재 점이며, 다음과 같습니다.
xi가 경계에 있는 경우, vi는 0입니다. xi가 경계에 있지 않는 경우 최소화 점에서 기울기 gi는 0이어야 합니다. 따라서 1차 최적성 측정값은 최소화 점에서 0이어야 합니다.