[LG Aimers] [수학-2] Convex Optimization

1️⃣ Optimization Using Gradient Descent

Unconstrained Optimization and Gradient Algorithms

• 목표

• 경사 기반 알고리즘(Gradient-Type Algorithms)
• 반복적으로 다음과 같이 업데이트

• 보조정리
• 을 만족하는 모든 방향 는 에서의 하강 방향임
• 즉, 로 정의했을 때,

• 가장 가파른 경사 하강법
• 하강 방향 를 기울기의 음수 방향으로 선택:

Taxonomy

• 목표
• n개의 훈련 데이터를 사용하여 손실 함수 를 최소화

• 훈련 데이터 사용량에 따른 분류
• Batch Gradient Descent
• 전체 데이터 을 사용
• Mini-Batch Gradient Descent
• 일부 데이터 을 사용
• Stochastic Gradient Descent(SGD)
• 일부 데이터 을 사용하며, 편향 없는 기울기 추정값을 계산

• 업데이트 적응형 방법에 의한 분류
• Momentum, NAG, Adagrad, RMSprop, Adam, etc

Stochastic Gradient Descent(SGD)

• 기본 가정
• 손실 함수 는 개의 데이터로 이루어진 경우 가정:

• 경사 업데이트(Gradient Update)
• Stochastic Gradient Descent: 무작위로 선택된 데이터 하위 집합 에 대해 편향 없는 기울기 추정을 사용:
i.e., 이는 실제 기울기의 노이즈가 포함된 근사치를 의미함

2️⃣ Constrained Optimization and Lagrange Multipliers

Standard Constrained Optimization Problem

• 목표

• 제약 조건
• 부등식 제약 조건(Inequality Constraints)
• 등식 제약 조건(Equality Constraints)

• 변수(Variables):
• 가정: 제약 조건을 만족하는 유효 해 집합이 비어있지 않음

• 최적 값(Optimal value): , 최적 해(Optimizer):

Problem Solving via Langrange Multipliers

• 이중성 사고방식(Duality Mentality)
• 다른 최적화 문제를 통해 하나의 최적화 문제를 경계 짓거나 해결
• 일반적인 최적화 문제를 위한 라그랑주 이중성 이론을 개발하고, 이후 볼록 최적화(Convex Optimization)에 특화
• 아이디어: 목적 함수에 제약 조건들의 가중치 합을 더하기
• 라그랑지안:
• 라그랑주 승수(쌍대 변수):
• 라그랑주 쌍대 함수:
• 를 고정했을 때 에 대한 하한(infimum) 값

Lower Bound on the Optimal Value

• 쌍대 함수 는 최적 값 의 하한임

• 정리

• 증명
• 유효한 해를 를 고려:
• 조건:
• 따라서, 모든 유효한 에 대해:

Lagrangian Dual Problem

• 라그랑주 쌍대 함수 에서 나오는 하한은 에 따라 달라짐

• 질문
• 가장 좋은 하한은 무엇인가?
• 라그랑지안 쌍대 문제

• 쌍대 변수:

• 특징
• 항상 볼록 최적화 문제(Convex Optimization):
• 는 항상 에 대해 오목(Concave)임
• 이는 에 대한 선형 함수들의 집합에서 하한(Infimum)을 계산하기 때문임

Weak Duality

• 쌍대 문제의 최적 값 와 원래 문제의 최적 값 사이의 관계는 무엇인가?

• 약한 쌍대성(Weak Duality)

• 특징
• 항상 성립: 약한 쌍대성은 원래 문제가 볼록(convex)이 아니더라도 항상 성립함

• 최적 쌍대 차이(Optimal Duality Gap):

• 효율적인 하한 생성:
• 이중 문제를 통해 최적 값의 하한을 효율적으로 계산할 수 있음

3️⃣ Convex Sets and Functions

Convex Optimization

• 볼록 최적화 문제 정의
• 목표:
• : 볼록 함수(Convex Function)
• : 볼록 집합(Convex Set)

• 쉽게 풀 수 있는 문제와 풀기 어려운 문제를 구분 짓는 핵심 요소는 볼록성(Convexity)임

Convex Set

• 집합 가 볼록 집합(convex set)이라는 것은, 내의 임의의 두점 에 대해 그 사이의 모든 선분이 에 포함되는 경우를 의미함

• 볼록 집합과 비볼록 집합의 예시

Convex Functions

• 정의
• 함수 가 볼록 함수(convex function)라는 것은, 정의역이 볼록 집합(convex set)이고, 임의의 와 에 대해 다음이 성립하는 경우를 말함:

• 특수한 경우
• 엄격히 볼록 함수(Strictly Convex):
• 위 부등식이 이고 일 때 엄격히 성립하면 는 엄격히 볼록 함수임
• 오목 함수(Concave Function):
• 가 볼록 함수이면, 는 오목 함수임

• 모든 선형 함수는 볼록성과 오목성을 동시에 가짐

• Jensen’s inequality(옌센 부등식):
• 확률 변수 에 대해:

Conditions of Convex Functions

• 1차 조건(First-Order Condition)
• 미분 가능한 함수 가 볼록 함수가 되기 위한 필요충분조건:

• 2차 조건(Second-Order Condition)
• 두 번 미분 가능한 함수 가 볼록 함수가 되기 위한 필요충분조건:

Convexity-Preserving Operations

• 가중합
• 가 모두 볼록이고 일 때, 는 볼록

• 선형 변환
• 가 볼록 함수이면 도 볼록 함수

• 함수의 최대값
• 가 모두 볼록 함수라면 도 볼록

• 함수의 합성
• k = 1일 때:
• 가 볼록이고 비감소(nondecreasing)하며 가 볼록이면, 는 볼록
• 또는 가 볼록이고 비증가(nonincreasing)하며 가 오목 함수이면, 는 볼록

Point-wise Supremum

• 볼록성 유지
• 함수 가 에 대해 볼록(convex)이고, 에 대해 정의된 경우:
• 는 볼록 함수임

• 오목성 유지
• 함수 가 에 대해 오목(concave)이고, 에 대해 정의된 경우:
• 는 오목 함수임

• 예시
• 집합 에서 가장 먼 점까지의 거리:
• 는 볼록 함수임
• 라그랑주 쌍대 함수:
• 는 오목 함수임

4️⃣ Convex Optimization

Standard Convex Optimization

• 변수 에 대한 문제 정의:
여기서 는 모두 볼록 함수

• 요구 조건
• 목적 함수:
• 볼록 함수 를 최소화하거나, 오목 함수 를 최대화
• 부등식 제약 조건:
• 볼록 함수 로 정의된 제약 조건 (결과적으로 제약 조건 집합이 볼록 집합이 됨)
• 등식 제약 조건:
• 반드시 아핀 함수(affine functions)로 구성된 등식이어야 함 (아핀 함수로만 구성될 때 볼록 집합을 형성)

Strong Duality

• 정의
• 강한 쌍대성(Strong Duality)

• 특징
• 강한 쌍대성이 성립하면, 쌍대 문제(Dual Problem)를 해결하는 것이 원문제(Primal Problem)를 해결하는 것과 동등함
• 하지만 강한 쌍대성이 항상 성립하지는 않음

• 볼록성과 제약 조건 자격이 만족되면 강한 쌍대성이 성립함

• 강한 쌍대성은 볼록 최적화(Convex Optimization)가 비교적 쉽게 해결 가능한 이유 중 하나임

KKT Condition

• 가 를 에 대해 최소화한다고 가정:

• KKT 최적 조건
• 제약 조건:

• 강한 쌍대성이 성립하는 최적화 문제에서, KKT 조건은 원문제와 쌍대 문제의 최적성을 위한 필요 조건임

• 볼록 최적화 문제에서, KKT 조건은 원문제와 쌍대 문제의 최적성을 위한 충분 조건이 됨

Linear Programming & Quadractic Programming