[Math] Slater's Condition

2023. 7. 6. 23:17·.../Math
728x90
728x90

Slater's condition은

  • Strong Duality의 Sufficient Condition으로 유명하고,
  • 동시에, Slater's condition을 만족하는 경우에는 KKT가 necessary condition이 되기 위해 선행적으로 요구되는 Regularity Condtion이 성립된다는 성질을 가지고 있는 조건임.

Slater's condition은 convex optimization인 경우에만 성립되는 조건인데,

KKT conditions가 convex optimization에서는 necessary sufficient condition이 되기 때문에,

결국 Slater's condition을 만족할 경우, KKT conditions를 통해 optimal solution을 찾을 수 있게 된다.

 

쉽게 말하면, Slater's condition을 만족하는 경우,

  • dual problem으로도 optimal solution을 찾을 수 있으며,
  • KKT conditions를 통해서도 optimal solution을 찾을 수 있다.

 

즉, Slater's condition을 만족하면 최적해를 구하기 위한 다양한 방법이 가능해진다.

 

Definition

우선 Standard form of Optimization이 다음과 같이 주어진다.

Equailty constraints와 Ineqaulity contraints를 가지고 있는 optimization problem (minimization의 경우)은 다음과 같이 표현된다.

$$\begin{aligned}&\text{minimize }f(\textbf{x}) \\ & \text{s.t:} \\ & g_i(\textbf{x}) \le 0, i=1,\dots,m \\ & h_j(\textbf{x})=0,j=1,\dots,k \end{aligned}$$

이같은 Optimization problem이 Slater's condition을 만족하려면, 다음을 만족시키는 $\textbf{x}^*$가 존재해야함.

  1. 우선 Convex Optimization Problem이어야 함.
    • $f(\textbf{x})$는 $f:\mathbb{R}^n\to\mathbb{R}$이면서 convex function이어야 함.
    • 모든 $\forall i$에 대해서 $g_i(\textbf{x})$는 convex function이어야함.
    • 모든 $\forall j$에 대해서 $h_i(\textbf{x})$는 affine function이어야 함 : $h_i(\textbf{x})=A\textbf{x}+\textbf{b},\quad\text{ where } A \text{ is matrix and }\textbf{b}\text{ is a vector}$
  2. 모든 $\forall i$에 대해서 $g_i(\textbf{x}^*) < 0$이 성립해야함. (등호가 없음.)
    • 만약 $g_i(\textbf{x})=A\textbf{x}+\textbf{b}$와 같은 affine function이라면, $g_i(\textbf{x}^*) \le 0$여도 됨.

 

Slater's condition 에 해당하는 convex optimization problem에서는 equality constraints와 inequality constraints를 만족하는 input $\textbf{x}$를 하나만 찾아도 strong duality가 성립하게 된다. 

'... > Math' 카테고리의 다른 글

[Math] A regular point of the feasible set.  (0) 2023.07.07
[Math] Duality (쌍대성) 이란 : Optimization에서  (0) 2023.07.07
[Math] Lagrangian from Standard Form using Indicator Function  (0) 2023.07.06
[Math] Lagrangian Primal and Lagrangian Dual  (0) 2023.07.05
[Math] Upper Bound (상계) and Lower Bound (하계)  (0) 2023.07.05
'.../Math' 카테고리의 다른 글
  • [Math] A regular point of the feasible set.
  • [Math] Duality (쌍대성) 이란 : Optimization에서
  • [Math] Lagrangian from Standard Form using Indicator Function
  • [Math] Lagrangian Primal and Lagrangian Dual
dsaint31x
dsaint31x
    반응형
    250x250
  • dsaint31x
    Dsaint31's blog
    dsaint31x
  • 전체
    오늘
    어제
    • 분류 전체보기 (739)
      • Private Life (13)
      • Programming (56)
        • DIP (104)
        • ML (26)
      • Computer (119)
        • CE (53)
        • ETC (33)
        • CUDA (3)
        • Blog, Markdown, Latex (4)
        • Linux (9)
      • ... (350)
        • Signals and Systems (103)
        • Math (171)
        • Linear Algebra (33)
        • Physics (42)
        • 인성세미나 (1)
      • 정리필요. (54)
        • 의료기기의 이해 (6)
        • PET, MRI and so on. (1)
        • PET Study 2009 (1)
        • 방사선 장해방호 (4)
        • 방사선 생물학 (3)
        • 방사선 계측 (9)
        • 기타 방사능관련 (3)
        • 고시 (9)
        • 정리 (18)
      • RI (0)
      • 원자력,방사능 관련법 (2)
  • 블로그 메뉴

    • Math
    • Programming
    • SS
    • DIP
  • 링크

    • Convex Optimization For All
  • 공지사항

    • Test
    • PET Study 2009
    • 기타 방사능관련.
  • 인기 글

  • 태그

    SS
    SIGNAL
    numpy
    linear algebra
    math
    Vector
    인허가제도
    Probability
    Convolution
    Python
    fourier transform
    function
    random
    signal_and_system
    Term
    Programming
    signals_and_systems
    opencv
    검사
    Optimization
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.3
dsaint31x
[Math] Slater's Condition
상단으로

티스토리툴바