[Math] Linear Programming and Quadratic Programming

Linear Programming and Quadratic Programming

우리나라 말로 번역하면, 선형계획법 또는 이차계획법 으로 불림.

약어로 LP, QP로 자주 사용한다.

참고로 Programming이라고 이름이 붙어있지만 이는 computer programming과는 상관이 없고,
optimization problem(최적화 문제)를 가르키는 용어이다.

컴퓨터 프로그래밍이 이렇게 널리 사용되기 이전부터 사용되던 용어임.
Optimization에서 사용되는 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 (단항식 과 다항식)

[Math] Monomial and Polynomial (단항식 과 다항식)

Monomial (단항식) constant와 variable의 product로 이루어진 algebraic expression. 수학에서 monomial은 하나의 term(항)으로 구성된 algebraic expression (대수적 표현식)임. 이 하나의 term은 constant, variable, 또는 constant

dsaint31.tistory.com

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)이다.

"Programming"이라는 용어가 선형 계획법(linear programming)에 붙은 이유.

1940년대 후반, 미 공군의 수학자였던 조지 단치히(George Dantzig)가 군사 물류 및 자원 할당 문제를 해결하기 위해

linear programming을 개발함.

당시 "programming"이라는 용어는 현재와 달리 계획(plan)이나 스케줄(schedule)을 의미하는 것으로 사용됨
신문에 있는 TV Program을 생각하자.

Linear Programming에서 "programming"은
어떤 목표를 달성하기 위한 일련의 계획이나 절차를 의미함.

즉, "linear programming"은 선형 방정식 및 부등식을 사용하여 자원을 최적으로 배분하고 관리하는 계획을 세우는 방법으로 개발된 것으로 여기서 "programming"은 컴퓨터 프로그래밍과는 관련이 없으며, 그보다는 자원 배분 문제를 해결하기 위한 체계적인 방법론을 가리키는 용어임.

요약하면, 선형 계획법에서 "programming"이라는 용어는

역사적으로 자원 배분 및 최적화 문제를 해결하기 위한 체계적인 계획 수립 과정을 의미하는 것임.

읽어보면 좋은 자료들

LP에 대한 이해를 쉽게 해주는 좋은 글 (앞부분의 예를 보시면 LP가 무엇인지 알게 됨) : https://gazelle-and-cs.tistory.com/17

[선형 계획법] 쌍대성(Duality)

Linear programming은 최적화 분야에서 잘 알려지고 연구되었으며 실제로도 많이 응용되는 기법입니다. 줄여서 LP라고도 하며, 우리말로는 선형계획법으로 불립니다. 이름이 뭔가 멋들어져서 괜스레

gazelle-and-cs.tistory.com

2024.06.01 - [.../Math] - [Math] Optimization Problem 의 종류

[Math] Optimization Problem 의 종류

Optimization Problem의 종류Minimization Problem vs. Maximization Problem 일반적인 최적화 문제는 최소화 문제로 공식화될 수 있음. 이는 다음과 같이 표현됨:$$\underset{\boldsymbol{\omega}}{\min} f(\boldsymbol{\omega})$$이