우리나라 말로 번역하면, 선형계획법 또는 이차계획법인 걸로 알고 있다.
약어로 LP, QP로 자주 사용한다.
참고로 Programming이라고 이름이 붙어있지만 이는 computer programming과는 상관이 없고, optimization problem(최적화 문제)를 가르키는 용어이다.
컴퓨터 프로그래밍이 이렇게 널리 사용되기 이전부터 사용되던 용어라고 하는데 programming이라는 의미가 사실 잘 안 와닿는 프로그래머라... ==;;
최적화에선 programming을 problem 또는 optimization problem으로 바꿔 읽으면 된다.
optimization problem은 object function과 constraints들로 정의가 되기 때문에, optimization problem이 LP인지 QP인지를 결정하는 것도 object function과 constraints이다.
Linear Programming (LP, 선형계획법)
objective function과 contraints들이 모두 linear인 optimization programming을 가르켜 linear programming이라고 한다.
variables (or parameters)에 대해 objective functino과 constraints가 degree(차수)가 1인 경우임.
degree(차수)에 대해 개념이 헷갈리면 다음 URL의 degree참고: 2023.06.03 - [.../Math] - [Math] Monomial and Polynomial (단항식 과 다항식)
Quadratic Programming (QP, 이차계획법)
LP에서 objective function을 second degree polynomial로 확장한 것이 바로 QP이다.
constraints들은 여전히 first degree polynomial임.
수학적기법으로 optimization을 할 때 가장 널리 사용되는 convex optimizaion이 바로 QP에 속한다.
참고로 object function이나 contraints 에서 nolinear한 것이 있을 경우 nonlinear optimization (or nonlinear programming)이다.
읽어보면 좋은 자료들
LP에 대한 이해를 쉽게 해주는 좋은 글 (앞부분의 예를 보시면 LP가 무엇인지 알게 됨) : https://gazelle-and-cs.tistory.com/17
'... > Math' 카테고리의 다른 글
[Math] Stationary point (or Critical point) (0) | 2023.07.10 |
---|---|
[Math] Second Order Condition : Convexity (0) | 2023.07.10 |
[Math] A regular point of the feasible set. (0) | 2023.07.07 |
[Math] Duality (쌍대성) 이란 : Optimization에서 (0) | 2023.07.07 |
[Math] Slater's Condition (0) | 2023.07.06 |