알고리즘 선택하기

fmincon 알고리즘

fmincon에는 다음과 같이 5가지 알고리즘 옵션이 있습니다.

'interior-point'(디폴트 값)
'trust-region-reflective'
'sqp'
'sqp-legacy'
'active-set'

명령줄에서 Algorithm 옵션을 설정하려면 optimoptions를 사용하십시오.

권장 사항

권장 사항
`'interior-point'` 알고리즘을 먼저 사용해 보십시오. 최소화에 실패할 경우 도움말을 보려면 솔버가 실패한 경우 항목 또는 솔버가 성공했을 수 있는 경우 항목을 참조하십시오. 소규모 또는 중간 규모 문제에 대해 속도를 높이기 위해 최적화를 재실행하려면 이후에 `'sqp'`를 사용한 후 `'active-set'`를 마지막으로 사용해 보십시오. 가능한 경우 `'trust-region-reflective'`를 사용해 보십시오. 문제에는 기울기와 함께, 범위 또는 선형 등식 제약 조건 중 하나만 포함하는 목적 함수가 있어야 합니다. Interior-Point 알고리즘 사용 시 발생할 수 있는 잠재적 부정확성 문제 항목을 참조하십시오.

'interior-point' 알고리즘을 먼저 사용해 보십시오.
최소화에 실패할 경우 도움말을 보려면 솔버가 실패한 경우 항목 또는 솔버가 성공했을 수 있는 경우 항목을 참조하십시오.
소규모 또는 중간 규모 문제에 대해 속도를 높이기 위해 최적화를 재실행하려면 이후에 'sqp'를 사용한 후 'active-set'를 마지막으로 사용해 보십시오.
가능한 경우 'trust-region-reflective'를 사용해 보십시오. 문제에는 기울기와 함께, 범위 또는 선형 등식 제약 조건 중 하나만 포함하는 목적 함수가 있어야 합니다.

Interior-Point 알고리즘 사용 시 발생할 수 있는 잠재적 부정확성 문제 항목을 참조하십시오.

권장 사항에 대한 근거

'interior-point'는 대규모 희소 문제는 물론 소규모의 조밀한 문제도 처리합니다. 이 알고리즘은 모든 반복에서 범위를 충족하고 NaN 또는 Inf 결과에 대해 대처할 수 있습니다. 이는 대규모 알고리즘입니다. 대규모 알고리즘과 중간 규모 알고리즘 비교 항목을 참조하십시오. 이 알고리즘은 대규모 문제에 특수한 기법을 사용할 수 있습니다. 자세한 내용은 fmincon options의 Interior-Point 알고리즘을 참조하십시오.
'sqp'는 모든 반복에서 범위를 충족합니다. 이 알고리즘은 NaN 또는 Inf 결과에 대해 대처할 수 있습니다. 이는 대규모 알고리즘이 아닙니다. 대규모 알고리즘과 중간 규모 알고리즘 비교 항목을 참조하십시오.
'sqp-legacy'는 'sqp'와 유사하지만, 일반적으로 더 느리고 더 많은 메모리를 사용합니다.
'active-set'은 큰 스텝을 취할 수 있으며, 이는 속도를 높입니다. 이 알고리즘은 매끄럽지 않은 제약 조건이 있는 일부 문제에 효과적입니다. 이는 대규모 알고리즘이 아닙니다. 대규모 알고리즘과 중간 규모 알고리즘 비교 항목을 참조하십시오.
'trust-region-reflective'를 사용하려면 기울기 값을 입력해야 하며, 범위 또는 선형 등식 제약 조건 중 하나만 제공할 수 있습니다. 이러한 제한 사항 내에서, 이 알고리즘은 대규모 희소 문제와 소규모의 조밀한 문제 모두를 효율적으로 처리합니다. 이는 대규모 알고리즘입니다. 대규모 알고리즘과 중간 규모 알고리즘 비교 항목을 참조하십시오. 이 알고리즘은 헤세 행렬의 곱셈 함수와 같이 메모리 사용량을 절약하는 특수한 기법을 사용할 수 있습니다. 자세한 내용은 fmincon options의 Trust-Region-Reflective 알고리즘을 참조하십시오.

알고리즘에 대한 설명은 제약 조건이 있는 비선형 최적화 알고리즘 항목을 참조하십시오.

fsolve 알고리즘

fsolve에는 다음과 같이 3가지 알고리즘이 있습니다.

'trust-region-dogleg'(디폴트 값)
'trust-region'
'levenberg-marquardt'

명령줄에서 Algorithm 옵션을 설정하려면 optimoptions를 사용하십시오.

권장 사항

권장 사항
`'trust-region-dogleg'` 알고리즘을 먼저 사용해 보십시오. `fsolve`가 실패할 경우 도움말을 보려면 솔버가 실패한 경우 항목 또는 솔버가 성공했을 수 있는 경우 항목을 참조하십시오. 야코비 행렬의 곱셈 함수를 사용하는 경우이거나 내부 알고리즘을 조정하려는 경우 방정식을 다시 풀려면(`fsolve` `options`의 Trust-Region 알고리즘 참조) `'trust-region'`을 사용해 보십시오. `'levenberg-marquardt'`를 포함하여 모든 알고리즘의 시간을 측정하면 문제에 가장 효과적인 알고리즘을 찾을 수 있습니다.

'trust-region-dogleg' 알고리즘을 먼저 사용해 보십시오.
fsolve가 실패할 경우 도움말을 보려면 솔버가 실패한 경우 항목 또는 솔버가 성공했을 수 있는 경우 항목을 참조하십시오.
야코비 행렬의 곱셈 함수를 사용하는 경우이거나 내부 알고리즘을 조정하려는 경우 방정식을 다시 풀려면(fsolve options의 Trust-Region 알고리즘 참조) 'trust-region'을 사용해 보십시오.
'levenberg-marquardt'를 포함하여 모든 알고리즘의 시간을 측정하면 문제에 가장 효과적인 알고리즘을 찾을 수 있습니다.

권장 사항에 대한 근거

'trust-region-dogleg'는 비선형 방정식을 풀도록 특별히 설계된 유일한 알고리즘입니다. 타 알고리즘은 함수의 제곱합을 최소화하려고 시도합니다.
'trust-region' 알고리즘은 희소 문제에 효과적입니다. 이 알고리즘은 대규모 문제에 야코비 행렬의 곱셈 함수와 같은 특수한 기법을 사용할 수 있습니다.

알고리즘에 대한 설명은 방정식 풀이 알고리즘 항목을 참조하십시오.

fminunc 알고리즘

fminunc에는 다음과 같이 두 가지 알고리즘이 있습니다.

'quasi-newton'(디폴트 값)
'trust-region'

명령줄에서 Algorithm 옵션을 설정하려면 optimoptions를 사용하십시오.

권장 사항

권장 사항
목적 함수에 기울기가 포함되어 있으면 `'Algorithm' = 'trust-region'`을 사용하고 `SpecifyObjectiveGradient` 옵션을 `true`로 설정하십시오. 그렇지 않은 경우 `'Algorithm' = 'quasi-newton'`을 사용하십시오. 최소화에 실패할 경우 도움말을 보려면 솔버가 실패한 경우 항목 또는 솔버가 성공했을 수 있는 경우 항목을 참조하십시오.

목적 함수에 기울기가 포함되어 있으면 'Algorithm' = 'trust-region'을 사용하고 SpecifyObjectiveGradient 옵션을 true로 설정하십시오.
그렇지 않은 경우 'Algorithm' = 'quasi-newton'을 사용하십시오.

최소화에 실패할 경우 도움말을 보려면 솔버가 실패한 경우 항목 또는 솔버가 성공했을 수 있는 경우 항목을 참조하십시오.

알고리즘에 대한 설명은 제약 조건이 없는 비선형 최적화 알고리즘 항목을 참조하십시오.

최소제곱 알고리즘

lsqlin

lsqlin에는 다음과 같이 3가지 알고리즘이 있습니다.

'interior-point'(디폴트 값)
'trust-region-reflective'
'active-set'

명령줄에서 Algorithm 옵션을 설정하려면 optimoptions를 사용하십시오.

권장 사항

권장 사항
`'interior-point'`를 먼저 사용해 보십시오. 팁 입력 행렬 `C`에서 많은 부분이 0이 아닌 요소로 구성된 경우 성능을 높이려면 `C`를 일반 double형 행렬로 지정하십시오. 마찬가지로, `C`에서 0이 아닌 요소가 상대적으로 적은 경우 성능을 높이려면 `C`를 희소 행렬로 지정하십시오. 데이터형에 대한 세부 정보는 희소 행렬 항목을 참조하십시오. `'LinearSolver'` 옵션을 사용하여 내부 선형 대수 유형을 설정할 수도 있습니다. 제약 조건이 전혀 없거나 범위 제약 조건만 있는 경우, 더 높은 정확도 또는 더 높은 속도를 원하거나 Jacobian Multiply Function with Linear Least Squares를 사용하려면 `'trust-region-reflective'`를 사용해 보십시오. 선형 제약 조건은 많지만 변수는 많지 않다면 `'active-set'`를 사용해 보십시오. 최소화에 실패할 경우 도움말을 보려면 솔버가 실패한 경우 항목 또는 솔버가 성공했을 수 있는 경우 항목을 참조하십시오. Interior-Point 알고리즘 사용 시 발생할 수 있는 잠재적 부정확성 문제 항목을 참조하십시오.

'interior-point'를 먼저 사용해 보십시오.
팁
입력 행렬 C에서 많은 부분이 0이 아닌 요소로 구성된 경우 성능을 높이려면 C를 일반 double형 행렬로 지정하십시오. 마찬가지로, C에서 0이 아닌 요소가 상대적으로 적은 경우 성능을 높이려면 C를 희소 행렬로 지정하십시오. 데이터형에 대한 세부 정보는 희소 행렬 항목을 참조하십시오. 'LinearSolver' 옵션을 사용하여 내부 선형 대수 유형을 설정할 수도 있습니다.
제약 조건이 전혀 없거나 범위 제약 조건만 있는 경우, 더 높은 정확도 또는 더 높은 속도를 원하거나 Jacobian Multiply Function with Linear Least Squares를 사용하려면 'trust-region-reflective'를 사용해 보십시오.
선형 제약 조건은 많지만 변수는 많지 않다면 'active-set'를 사용해 보십시오.

최소화에 실패할 경우 도움말을 보려면 솔버가 실패한 경우 항목 또는 솔버가 성공했을 수 있는 경우 항목을 참조하십시오.

Interior-Point 알고리즘 사용 시 발생할 수 있는 잠재적 부정확성 문제 항목을 참조하십시오.

알고리즘에 대한 설명은 최소제곱(모델 피팅) 알고리즘 항목을 참조하십시오.

lsqcurvefit과 lsqnonlin

lsqcurvefit 및 lsqnonlin에는 다음과 같이 세 가지 알고리즘이 있습니다.

'trust-region-reflective'(제약 조건이 없는 문제 또는 범위 제약 조건이 있는 문제의 디폴트 값)
'levenberg-marquardt'
'interior-point'(선형 제약 조건 또는 비선형 제약 조건이 있는 문제의 디폴트 값)

명령줄에서 Algorithm 옵션을 설정하려면 optimoptions를 사용하십시오.

권장 사항

권장 사항
범위 제약 조건만 있는 문제의 경우 `'trust-region-reflective'` 또는 `'levenberg-marquardt'`를 먼저 사용해 보십시오. 범위 제약 조건이 있는 문제가 부족 결정(방정식 수가 차원 수보다 적음) 문제인 경우 `'levenberg-marquardt'`를 먼저 사용해 보십시오. 문제에 선형 제약 조건 또는 비선형 제약 조건이 있는 경우 `'interior-point'`를 사용하십시오. 최소화에 실패할 경우 도움말을 보려면 솔버가 실패한 경우 항목 또는 솔버가 성공했을 수 있는 경우 항목을 참조하십시오.

범위 제약 조건만 있는 문제의 경우 'trust-region-reflective' 또는 'levenberg-marquardt'를 먼저 사용해 보십시오.
범위 제약 조건이 있는 문제가 부족 결정(방정식 수가 차원 수보다 적음) 문제인 경우 'levenberg-marquardt'를 먼저 사용해 보십시오.
문제에 선형 제약 조건 또는 비선형 제약 조건이 있는 경우 'interior-point'를 사용하십시오.

최소화에 실패할 경우 도움말을 보려면 솔버가 실패한 경우 항목 또는 솔버가 성공했을 수 있는 경우 항목을 참조하십시오.

알고리즘에 대한 설명은 최소제곱(모델 피팅) 알고리즘 항목을 참조하십시오.

선형 계획법 알고리즘

linprog에는 다음과 같이 3가지 알고리즘이 있습니다.

'dual-simplex'(디폴트 값)
'interior-point-legacy'
'interior-point'

명령줄에서 Algorithm 옵션을 설정하려면 optimoptions를 사용하십시오.

권장 사항

권장 사항
`'dual-simplex'` 알고리즘 또는 `'interior-point'` 알고리즘을 먼저 사용해 보십시오. 최소화에 실패할 경우 도움말을 보려면 솔버가 실패한 경우 항목 또는 솔버가 성공했을 수 있는 경우 항목을 참조하십시오. Interior-Point 알고리즘 사용 시 발생할 수 있는 잠재적 부정확성 문제 항목을 참조하십시오.

'dual-simplex' 알고리즘 또는 'interior-point' 알고리즘을 먼저 사용해 보십시오.

최소화에 실패할 경우 도움말을 보려면 솔버가 실패한 경우 항목 또는 솔버가 성공했을 수 있는 경우 항목을 참조하십시오.

Interior-Point 알고리즘 사용 시 발생할 수 있는 잠재적 부정확성 문제 항목을 참조하십시오.

권장 사항에 대한 근거

대개 'dual-simplex' 알고리즘과 'interior-point' 알고리즘이 빠르며 메모리를 가장 적게 사용합니다.
'interior-point-legacy' 알고리즘은 'interior-point'와 유사하지만 'interior-point-legacy'가 더 느리거나 덜 견고하거나 더 많은 메모리를 사용할 수 있습니다.

알고리즘에 대한 설명은 선형 계획법 알고리즘 항목을 참조하십시오.

2차 계획법 알고리즘

quadprog에는 다음과 같이 3가지 알고리즘이 있습니다.

'interior-point-convex'(디폴트 값)
'trust-region-reflective'
'active-set'

명령줄에서 Algorithm 옵션을 설정하려면 optimoptions를 사용하십시오.

권장 사항

권장 사항
볼록 문제를 풀거나 문제가 볼록인지 여부를 알지 못하는 경우 `'interior-point-convex'`를 사용하십시오. 팁 헤세 행렬 `H`에서 많은 부분이 0이 아닌 요소로 구성된 경우 성능을 높이려면 `H`를 일반 double형 행렬로 지정하십시오. 마찬가지로, `H`에서 0이 아닌 요소가 상대적으로 적은 경우 성능을 높이려면 `H`를 희소 행렬로 지정하십시오. 데이터형에 대한 세부 정보는 희소 행렬 항목을 참조하십시오. `'LinearSolver'` 옵션을 사용하여 내부 선형 대수 유형을 설정할 수도 있습니다. 범위 또는 선형 등식 중 하나만 포함하는 비볼록 문제가 있는 경우 `'trust-region-reflective'`를 사용하십시오. 선형 제약 조건은 많지만 변수는 많지 않은 양의 준정부호 문제가 있는 경우 `'active-set'`를 사용해 보십시오. 최소화에 실패할 경우 도움말을 보려면 솔버가 실패한 경우 항목 또는 솔버가 성공했을 수 있는 경우 항목을 참조하십시오. Interior-Point 알고리즘 사용 시 발생할 수 있는 잠재적 부정확성 문제 항목을 참조하십시오.

볼록 문제를 풀거나 문제가 볼록인지 여부를 알지 못하는 경우 'interior-point-convex'를 사용하십시오.
팁
헤세 행렬 H에서 많은 부분이 0이 아닌 요소로 구성된 경우 성능을 높이려면 H를 일반 double형 행렬로 지정하십시오. 마찬가지로, H에서 0이 아닌 요소가 상대적으로 적은 경우 성능을 높이려면 H를 희소 행렬로 지정하십시오. 데이터형에 대한 세부 정보는 희소 행렬 항목을 참조하십시오. 'LinearSolver' 옵션을 사용하여 내부 선형 대수 유형을 설정할 수도 있습니다.
범위 또는 선형 등식 중 하나만 포함하는 비볼록 문제가 있는 경우 'trust-region-reflective'를 사용하십시오.
선형 제약 조건은 많지만 변수는 많지 않은 양의 준정부호 문제가 있는 경우 'active-set'를 사용해 보십시오.

최소화에 실패할 경우 도움말을 보려면 솔버가 실패한 경우 항목 또는 솔버가 성공했을 수 있는 경우 항목을 참조하십시오.

Interior-Point 알고리즘 사용 시 발생할 수 있는 잠재적 부정확성 문제 항목을 참조하십시오.

알고리즘에 대한 설명은 2차 계획법 알고리즘 항목을 참조하십시오.

대규모 알고리즘과 중간 규모 알고리즘 비교

최적화 알고리즘은 비희소 행렬을 저장할 필요가 없거나 비희소 행렬에서 연산할 필요가 없는 선형 대수를 사용할 때는 대규모 알고리즘입니다. 이는 희소 행렬을 저장하고 가능한 경우에 항상 계산에 희소 선형 대수를 사용함으로써 내부적으로 수행될 수 있습니다. 또한, 내부 알고리즘은 희소성을 유지하거나(예: 희소 촐레스키 분해), 행렬을 생성하지 않습니다(예: 켤레 기울기법).

이와 대조적으로, 중간 규모 방법은 내부적으로 비희소 행렬을 만들고 조밀한 선형 대수를 사용합니다. 문제가 충분히 큰 경우 비희소 행렬은 상당량의 메모리를 차지하며 조밀한 선형 대수를 실행하는 데 긴 시간이 필요할 수 있습니다.

“대규모”라는 명칭을 오해하지 마십시오. 소규모 문제에 대규모 알고리즘을 사용할 수도 있습니다. 또한, 대규모 알고리즘을 사용하기 위해 희소 행렬을 지정할 필요가 없습니다. 추가 제약 조건 유형과 같은 추가 기능을 이용하거나 가능한 경우 성능을 높이려면 중간 규모 알고리즘을 선택하십시오.

Interior-Point 알고리즘 사용 시 발생할 수 있는 잠재적 부정확성 문제

fmincon, quadprog, lsqlin, linprog의 interior-point 알고리즘에는 적은 메모리 사용량 및 대규모 문제를 신속하게 풀 수 있는 기능과 같은 많은 훌륭한 특징이 있습니다. 하지만, 이 알고리즘의 해는 다른 알고리즘의 해보다 정확성이 약간 떨어질 수 있습니다. 이러한 부정확성 문제가 발생할 수 있는 이유는 (내부적으로 계산된) 장벽 함수가 반복이 부등식 제약 조건 경계에 가까워지지 않도록 유지하기 때문입니다.

대부분의 실사용 목적에서는, 이 부정확성이 대개 매우 작습니다.

부정확성을 줄이려면 다음 방법을 사용해 보십시오.

더 작은 StepTolerance, OptimalityTolerance 및 가능한 경우 ConstraintTolerance 허용오차를 사용하여 솔버를 다시 실행합니다(단, 허용오차를 합당한 수준으로 유지해야 함). 허용오차와 중지 기준 항목을 참조하십시오.
Interior-point 해부터 시작하여 다른 알고리즘을 실행합니다. 일부 알고리즘이 과도한 메모리나 시간을 사용할 수 있고 모든 linprog 알고리즘과 일부 quadprog 알고리즘은 초기점을 받지 않으므로 이 작업은 실패할 수 있습니다.

예를 들어, 하한이 0으로 설정된 상태로 함수 x를 최소화해 보겠습니다. fmincon의 디폴트 interior-point 알고리즘을 사용하는 경우 다음과 같이 합니다.

options = optimoptions(@fmincon,'Algorithm','interior-point','Display','off');
x = fmincon(@(x)x,1,[],[],[],[],0,[],[],options)

x =

   2.0000e-08

fmincon의 sqp 알고리즘을 사용하는 경우 다음과 같이 합니다.

options.Algorithm = 'sqp';
x2 = fmincon(@(x)x,1,[],[],[],[],0,[],[],options)

x2 =

   0

마찬가지로, linprog의 interior-point-legacy 알고리즘을 사용하여 동일한 문제를 풉니다.

opts = optimoptions(@linprog,'Display','off','Algorithm','interior-point-legacy');
x = linprog(1,[],[],[],[],0,[],1,opts)

x =

   2.0833e-13

linprog의 dual-simplex 알고리즘을 사용하는 경우 다음과 같이 합니다.

opts.Algorithm = 'dual-simplex';
x2 = linprog(1,[],[],[],[],0,[],1,opts)

x2 =

     0

위의 경우들을 보면 interior-point 알고리즘의 정확도는 떨어지지만 그 답은 정답에 매우 가깝습니다.