04-01 Basic terminology

Convex Optimization Basic

Convex optimization 문제에서 사용되는 기본적인 용어들을 살펴보자.
일단 convex optimization 문제는 다음과 같이 정의된다.

minimizexDf(x)subject togi(x)0,i=1,,mhj(x)=0,j=1,,r,

where f and gi, i=1,,m are all convex, hj,j=1,,r are all affine, and the optimization domain is D=dom(f)i=1mdom(gi)j=1rdom(hj).

  • fcriterion 또는 objective function이라 부른다.
  • gi(x)inequality constraint function이라고 한다.
  • hj(x)equality constraint function이라고 한다.
  • 만약 xD이고, gi(x)0,i=1,,mhj(x)=0,j=1,,r를 만족하면 xfeasible point다.
  • 모든 feasible point x에 대해 f(x)의 최솟값을 optimal value라 부르고, f으로 쓴다.
  • x가 feasible하고 f(x)=f일때, xoptimal, solution, 또는 minimizer라 부른다.
  • x가 feasible하고 f(x)f+ϵ일때, xϵ-suboptimal이라 부른다.
  • x가 feasible하고 gi(x)=0일때, gix에서 active하다고 한다.
  • Convex minimization 문제는 concave maximization 문제로 변환할 수 있다.
maximizexDf(x)subject togi(x)0,i=1,..,mhj(x)=0,j=1,,r,

where f and gi, i=1,,m are all convex, hj,j=1,,r are all affine, and the optimization domain is D=dom(f)i=1mdom(gi)j=1rdom(hj).