요약
선형 계획법 풀이 알고리즘이 최적해를 찾아가는 과정을 브라우저에서 직접 그려 보며 볼 수 있습니다.
에번 그랜드와 마이클 클램킨이 만든 웹 앱 lpviz입니다. 제작자는 HN에서 선형 계획법(선형 부등식 제약 아래 선형 목표를 최적화하는 문제) 수업이 문제를 세우는 법에 치중한다고 설명했습니다. 풀이기가 어떻게 움직이는지 감을 잡도록 그 빈틈을 메우려 했다고 합니다.
왜 중요한가
- 여러 풀이 알고리즘이 같은 문제를 서로 다른 길로 푸는 모습을 한 화면에서 비교할 수 있습니다.
- 고전적인 단체법부터 GPU 풀이기 PDLP의 바탕인 PDHG까지 한곳에서 다룹니다.
핵심 내용
- 격자를 클릭해 실행 가능 영역(모든 제약을 만족하는 점의 영역)을 그리고 화살표로 목표 방향을 정합니다.
- 단체법, 내부점법, PDHG, 액티브 셋, 타원체법 풀이기와 중심 경로 표시를 고를 수 있습니다.
- 반복 과정을 애니메이션으로 다시 볼 수 있고, 문제 설정은 링크 하나로 공유됩니다.
- 기본 화면은 변수 2개짜리 문제만 다루고, 변수 3개짜리는 별도 모드로 제공합니다.
- 풀이기는 TypeScript로 짜여 브라우저 안에서만 돌고, 코드는 MIT 라이선스로 공개돼 있습니다.
HN 반응
- 최적해는 꼭짓점에서 나온다는 설명에, 제작자는 최적점이 변 전체에 걸치는 반례를 링크로 보여 줬습니다.
- 갱신 규칙을 보며 한 단계씩 넘기는 기능을 바라는 요청이 나왔고, 제작자는 별도 화면을 구상 중이라고 답했습니다.
정말 멋지네요. 알고리즘을 돌리는 동안 정보가 조금만 더 나오면 좋겠습니다. 갱신 규칙을 보여 주고 "다음 반복" 같은 걸 눌러서 한 단계씩 넘어갈 수 있으면 흥미로울 것 같아요.
감사합니다! 네, 저도 계속 생각하던 건데 정말 멋질 것 같다는 데 동의해요. 다만 UX를 어떻게 할지는 아직 확신이 없어요. 예를 들면 별도 사이트(가령 lpviz.net/step. 지금 만들고 있는 3변수 모드 https://0b2df09c-lpviz.michael-4e4.workers.dev/3d 처럼요)를 만들어서 LaTeX 애니메이션으로 각 단계의 실제 계산을 보여 주는 식으로요.
지금 제가 뭘 보고 있는 건지 누가 설명해 주실 수 있나요?
선형계획법은 제약 최적화 문제의 가장 기본적인 유형입니다. 두 가지로 이루어져 있는데, 선형 부등식과 선형 목적 함수입니다.
선형 부등식을 제약 조건이라고 하고, 모든 부등식을 동시에 만족하는 점들의 집합을 실행 가능 영역이라고 합니다. 이 게임의 목표는 실행 가능 영역 안에서 선형 목적 함수를 최소로 만드는 점을 찾는 것입니다. 그 점의 좌표를 목적 함수에 대입했을 때, 실행 가능 영역 안의 어떤 점보다도 작은 값이 나온다는 뜻입니다.
2차원에서는 증명이 그리 어렵지 않은 재미있는 사실이 하나 있습니다. 선형계획법에 최적점이 존재하면(제약 조건이 볼록 다면체를 이루면 보장됩니다), 목적 함수의 최솟값은 그 다면체의 꼭짓점 중 하나에서 달성됩니다.
이 웹사이트에서는 실행 가능 영역의 모양과 목적 함수의 방향을 바꿀 수 있습니다(목적 함수는 선형이라서 최적화 관점에서의 동작은 방향 벡터만으로 완전히 정해집니다). 그러면 이 선형계획법을 푸는 유명한 알고리즘 여러 가지를 보여 줍니다.
예를 들어 심플렉스(Simplex)는 외부의 한 점에서 출발해 최적을 향해 이동합니다. 쌍대 심플렉스(Dual simplex)는 목적 함수 값이 최적인 점에서 출발해 실행 가능성을 향해 이동하는 식이고요.
쌍대 퇴화(dual degeneracy)가 없다고 가정할 때만 그렇죠 :) https://lpviz.net/?s=AsEABN_FCIDiCQC_ixGg4BQAAMCLEYCS9AEAZAA
최솟값은 꼭짓점에서 달성되는 게 맞아요. 다른 곳에서도 달성될 뿐이죠!
맞네요, 좋은 지적입니다 :)
lpviz는 여러 선형계획법(LP) 솔버 알고리즘이 어떻게 해에 도달하는지, 그리고 문제 정의를 조정하면 어떻게 반응하는지를 시각화해 줍니다. 사용하려면 먼저 꼭짓점 여러 개를 그려서 이른바 실행 가능 영역을 정의합니다. 그다음 목적 화살표를 가리켜서 개선 방향을 정하고요. 답, 즉 최적점은 실행 가능 영역 안에 있으면서 개선 방향으로 가장 멀리 있는 점입니다.
LP는 수많은 하위 분야에 쓰이지만, 현실의 전형적인 문제는 변수와 제약 조건이 수천에서 수백만 개에 이릅니다(lpviz는 변수가 2개로 제한됩니다). 수업에서는 보통 솔버가 어떻게 동작하는지보다 현실 문제를 LP로 모델링하는 방법에 집중합니다. lpviz는 그 빈틈을 메우려는 도구라서, 여러 알고리즘이 어떻게 동작하는지 직관을 기르실 수 있습니다.
LP를 소개하는 훌륭한 영상과 강의는 아주 많은데, 이 2분짜리 영상이 꽤 좋습니다: https://www.youtube.com/watch?v=7ZjmPATPVzI
훌륭하네요.
축하드립니다. 액티브 셋(active set) 방법은 왜 하나도 없나요?
제안 감사합니다. 솔버는 늘 더 추가하고 싶어요. 크리스크로스(criss-cross)와 근접 primal-dual 액티브 셋(proximal primal-dual active set)을 추가한 브랜치의 공유 링크입니다. Many Facets 프리셋에서 크리스크로스를 애니메이션으로 보면 꽤 멋져요:
https://9b7c882e-lpviz.michael-4e4.workers.dev/?s=AtUAHIDTDgCBL9jbAtWKAaDKAq_fAaKoAvGoArT3AcHjApS6AaWMA8hznaEDliedoQOVJ6WMA8dzweMCk7oB8agCs_cBr98BoagC1YoBn8oCgS_X2wKCL9fbAtaKAZ_KArDfAaGoAvKoArP3AcLjApO6AaaMA8dznqEDlSeeoQOWJ6aMA8hzwuMClLoB8qgCtPcBsN8BoqgC1ooBoMoC_su8BPGNywJkARIB
멋지네요.
3D에 대해 물어보려 했는데, 다른 답글에서 이미 다루고 계시다는 걸 봤습니다.
추천을 한 번 더 누를 수 있으면 좋겠네요.
Simplex는 있어요.