Seonglae ChoLagrangian Dual Problem, Dual optimization problem
primal Optimization 문제와 관련된 새로운 최적화 문제
- primal 최적화 문제와 동일한 solution 가짐
- primal 최적화 문제보다 더 간단한 형태
- 일부 경우 primal 최적화 문제보다 더 효율적인 알고리즘
Dual problem notion
Duality (optimization)
In mathematical optimization theory, duality or the duality principle is the principle that optimization problems may be viewed from either of two perspectives, the primal problem or the dual problem. If the primal is a minimization problem then the dual is a maximization problem (and vice versa). Any feasible solution to the primal (minimization) problem is at least as large as any feasible solution to the dual (maximization) problem. Therefore, the solution to the primal is an upper bound to the solution of the dual, and the solution of the dual is a lower bound to the solution of the primal.[1] This fact is called weak duality.
https://en.wikipedia.org/wiki/Duality_(optimization)