2차 계획법

2차 계획법 (Quadratic Programming)

목적 함수가 2차이고 제약이 선형인 최적화 문제를 Octave는 qp 함수로 해결해요. 문제의 형태부터 옵션, 반환 값까지 차근차근 다뤄볼게요.

출처: 문서

본문

Octave는 2차 계획법(Quadratic Programming) 문제도 풀 수 있어요. 문제는

min 0.5 x'*H*x + x'*q

이며 다음 제약 조건을 따릅니다.

     A*x = b
     lb <= x <= ub
     A_lb <= A_in*x <= A_ub

[x, obj, info, lambda] = qp (x0, H)
[x, obj, info, lambda] = qp (x0, H, q)
[x, obj, info, lambda] = qp (x0, H, q, A, b)
[x, obj, info, lambda] = qp (x0, H, q, A, b, lb, ub)
[x, obj, info, lambda] = qp (x0, H, q, A, b, lb, ub, A_lb, A_in, A_ub)
[x, obj, info, lambda] = qp (…, options)

qp

2차 계획법 문제를 풀어요. 다음 문제를

min 0.5 x'*H*x + x'*q
 x

제약 조건 아래에서

A*x = b
lb <= x <= ub
A_lb <= A_in*x <= A_ub

null-space active-set 방법을 사용해 풉니다.

어떤 제약(A, b, lb, ub, A_in, A_lb, A_ub)이든 없으면 빈 행렬([])로 설정할 수 있어요. 제약 A와 A_in은 각 행이 하나의 제약을 나타내는 행렬이에요. 나머지 제약은 제약의 수에 따라 스칼라 또는 벡터예요. 초기 추정값이 유효(feasible)할수록 알고리즘이 더 빨라요.

options는 알고리즘을 제어하는 추가 매개변수를 지정하는 구조체예요. 현재 qp는 "MaxIter", "TolX", "AllowSemidefinite" 옵션을 인식해요.

  • "MaxIter" — 최적화가 중단되기 전 최대 알고리즘 반복 횟수를 설정해요. 기본값은 200이고, 양의 정수여야 해요.
  • "TolX" — 미지 변수 x에 대한 종료 허용 오차를 지정해요. 기본값은 sqrt (eps), 대략 1e-8이에요.
  • "AllowSemidefinite" — 불리언 플래그예요. true는 양의 준정부호(positive semi-definite) 문제(헤시안의 고윳값 중 하나 이상이 0)를 허용하고, false는 양의 정부호(모든 고윳값이 양수)를 요구해요. 기본값은 false예요.

반환 시 x는 최솟값의 위치이고 fval은 그 지점에서 목적 함수의 값이에요.

info는 알고리즘에 대한 실행 시 정보를 담은 구조체예요. 다음 필드가 정의되어 있어요.

  • solveiter — 해를 찾는 데 필요한 반복 횟수.
  • info — 해의 상태를 나타내는 정수.
    • 0 — 문제가 유효(feasible)하고 볼록. 전역 해를 찾았어요.
    • 1 — 문제가 볼록하지 않음. 국소 해를 찾았어요.
    • 2 — 문제가 볼록하지 않고 무계(unbounded).
    • 3 — 최대 반복 횟수에 도달.
    • 6 — 문제가 유효하지 않음(infeasible).

See also: sqp.

pqpnonneg

x = pqpnonneg (c, d)
x = pqpnonneg (c, d, x0)
x = pqpnonneg (c, d, x0, options)
[x, minval] = pqpnonneg (…)
[x, minval, exitflag] = pqpnonneg (…)
[x, minval, exitflag, output] = pqpnonneg (…)
[x, minval, exitflag, output, lambda] = pqpnonneg (…)

(1/2 * x' * c * x + d' * x)을 x >= 0 제약 아래에서 최소화해요.

c와 d는 실수 행렬이어야 하고, c는 대칭이고 양의 정부호여야 해요.

x0는 해 x에 대한 선택적 초기 추정값이에요. options는 알고리즘 동작을 바꾸는 옵션 구조체예요(optimset 참고). pqpnonneg는 "MaxIter"라는 옵션 하나를 인식해요.

출력값:

  • x — 해 행렬.
  • minval — 달성된 최소 모델 값, 1/2*xmin'*c*xmin + d'*xmin.
  • exitflag — 수렴 표시. 0은 반복 횟수를 초과해 수렴에 도달하지 못했음을, >0은 수렴했음을 나타내요. (알고리즘은 안정적이며 충분한 반복 횟수가 주어지면 수렴해요.)
  • output — 두 필드를 가진 구조체: "algorithm"(사용된 알고리즘, "nnls")과 "iterations"(수행된 반복 횟수).
  • lambda — 라그랑주 승수. 이 값들이 0이 아니면 해당 x 값은 0이어야 하는데, 이는 해가 좌표 평면에 밀착돼 있음을 나타내요. 크기는 해당 방향에서 x >= 0 제약을 완화하면 잔차가 얼마나 개선될지를 나타내요.

See also: lsqnonneg, qp, optimset.

더 알아보기

  • 비선형 프로그래밍은 sqp 함수가 있는 Nonlinear Programming 항목을 참고하세요.
  • 최적화 옵션 구조체는 optimset 항목을 함께 보면 좋아요.