Quadratic Program

목적 함수( objective function )란?

• "최적화하려는 대상"의 식
• "가장 작게" or "가장 크게"하려는 값
• QP에서는 2차식으로 되어있다.
• ex
  • 자동차 공장 : 생산 비용 (이걸 최소화)
  • 로봇 : 이동 거리 / 에너지 소모 (이걸 최소화)
  • 금융 : 위험 (이걸 최소화)

 

 

제약 조건

• "반드시 지켜야 하는 조건들"
• 제한선 , 규칙
• QP에서는 항상 1차식으로 표현된다.
• ex
  • 자동차 공장 : "A부품은 100개 이상 , B부품은 200개 이하 생산해야 한다"
  • 로봇 : " 벽을 넘을 수 없다" , "배터리 용량은 10 이하여야 한다."
  • 금융 : "총 투자 금액은 1000만원을 넘으면 안된다"

 

 

 

Quadratic Program란?

• QP는 "목적함수( objective function )"가 2차( Quadraic )이고, "제약조건(constrains)"이 모두 1차(Linear)인 최적화 문제이다.
  • 즉, 목적함수를 최소화(or 극대화)하면서, 모든 제약조건을 지키는 변수(해)를 찾는것이다.
• 일반적인 QP의 형태는 아래와 같다.

 

 

 

 

Quadratic Program의 제약조건

• Ax ≤ b
  • m개의 1차식(직선)을 이용한 "부등식 제약"
  • 각 행이  "a_1 * x_1 + a_2 * x_2 + .... ≤ b" 와 깉은 꼴.
    • ex.  2x_1 + 3x_2 ≤ 5
• Ex = d
  • p개의 1차 등식 제약
  • ex,  x_1 - x_2 = 3
• ==> 즉, 변수 X는 위의 제약(조건)을 모두 만족하면서, 목적함수를 최소화 해야한다.

 

 

 

예시