볼록 최적화

📚 콘텐츠 개요

복잡한 최적화 이론, 응용 및 수치 알고리즘을 다루는 고급 대학원 수준의 강의 및 교재. 공학과 과학 분야에서 볼록 최적화 문제를 인식하고 구성하는 데 중점을 둡니다.

공학 및 데이터 과학을 위한 볼록 최적화의 수학적 기초와 실용적인 알고리즘을 숙지하세요.

저자: 스티븐 보이드, 리벤 반덴베르헤

감사의 말: NSF의 일부 지원과 스탠퍼드 및 유에에스에이의 학생 및 동료들의 기여를 통해 지원되었으며, 아카디 네미로브스키와 키샨 바헤티에게 특별히 언급합니다.

🎯 학습 목표

1. 목적 함수, 제약 조건, 변수를 포함한 수학적 최적화 문제의 구성 요소를 정의합니다.
2. 수학적 성질에 따라 최소제곱법, 선형 프로그래밍, 볼록 최적화 문제를 구분합니다.
3. 국소 최적화 전략과 전역 최적화 전략을 비교하고 각각의 계산 복잡도를 평가합니다.
4. 형식적 조합 표기법을 사용하여 애핀 집합, 볼록 집합, 원뿔을 정의하고 구분합니다.
5. 유클리드 공, 타원체, 다면체, 양의 준정부정 원뿔 등 표준 볼록 집합을 식별하고 표현합니다.
6. 교차, 애핀 변환, 사영 함수 등 볼록성을 유지하는 연산을 적용하여 집합의 성질을 검증합니다.
7. 점별 최대값(점별 상한)과 벡터 조합 규칙 등 볼록성을 유지하는 연산을 식별하고 적용합니다.
8. 다양한 함수의 라그랑주 쌍대를 도출하고 영의 부등식을 적용합니다.
9. 하위레벨 집합과 1차/2차 미분 조건을 사용하여 준볼록성(quasiconvexity)을 특성화합니다.
10. 포맷화 및 변환: 슬랙 변수와 제약 조건 제거를 통해 원시 최적화 문제를 표준 볼록 형태로 변환합니다.

🔹 수업 1: 수학적 최적화 소개

개요: 이 수업은 수학적 최적화의 기초 개념을 소개하며, 일반적인 문제 설정에서부터 최소제곱법과 선형 프로그래밍 같은 해결 가능한 특정 클래스로 나아갑니다. 볼록 최적화와 비볼록 최적화 사이의 중요한 차이를 강조하며, 볼록 방법이 효율성에 대한 신뢰할 수 있는 "하천" 역할을 하며 더 어려운 비선형 문제를 해결하는 데 필수적인 도구를 제공한다는 점을 설명합니다.

학습 결과:

• 목적 함수, 제약 조건, 변수를 포함한 수학적 최적화 문제의 구성 요소를 정의합니다.
• 수학적 성질에 따라 최소제곱법, 선형 프로그래밍, 볼록 최적화 문제를 구분합니다.
• 국소 최적화 전략과 전역 최적화 전략을 비교하고 각각의 계산 복잡도를 평가합니다.

🔹 수업 2: 볼록 집합 이론

개요: 이 수업은 최적화의 기초 기하학을 탐구하며, 기본적인 선형 구조에서 볼록 집합과 원뿔의 복잡한 성질로 넘어갑니다. 애핀 집합과 볼록 집합의 수학적 정의를 다루고, 다면체와 양의 준정부정 원뿔과 같은 구체적인 기하학적 구조를 분석하며, 고차원 공간에서 볼록 집합을 특성화하고 조작할 수 있게 해주는 연산과 정리를 설명합니다.

학습 결과:

• 형식적 조합 표기법을 사용하여 애핀 집합, 볼록 집합, 원뿔을 정의하고 구분합니다.
• 유클리드 공, 타원체, 다면체, 양의 준정부정 원뿔 등 표준 볼록 집합을 식별하고 표현합니다.
• 교차, 애핀 변환, 사영 함수 등 볼록성을 유지하는 연산을 적용하여 집합 성질을 검증합니다.

🔹 수업 3: 볼록 함수와 성질

개요: 이 수업은 볼록성을 유지하는 고급 연산, 예를 들어 점별 상한과 특정 조합 규칙을 탐구하며, 라그랑주 쌍대 함수를 소개합니다. 볼록성 개념을 준볼록 함수와 로그-볼록 함수로 확장하면서, 일반화된 불평등에 대한 볼록성과 스흐어 보완과 같은 행렬 전용 성질을 살펴봅니다. 이러한 개념들은 복잡한 최적화 문제를 식별하고 구성하는 수학적 기반을 형성합니다.

학습 결과:

• 점별 상한(점별 최대값)과 벡터 조합 규칙 등 볼록성을 유지하는 연산을 식별하고 적용합니다.
• 다양한 함수의 라그랑주 쌍대를 도출하고 영의 부등식을 적용합니다.
• 하위레벨 집합과 1차/2차 미분 조건을 사용하여 준볼록성을 특성화합니다.

🔹 수업 4: 볼록 최적화 문제의 형식화

개요: 이 수업은 볼록 최적화 문제의 공식적 구조와 변환에 대해 다룹니다. 표준 형태와 최적성 조건부터 선형 프로그래밍(LP), 이차 프로그래밍(QP), 준정부정 프로그래밍(SDP) 등의 특정 문제 클래스까지 다룹니다. 학생들은 전역 최적성을 확인하는 방법, 준볼록 문제에 대한 이분법을 활용하는 방법, 다기준 벡터 최적화에 대한 스칼라화 기법을 배웁니다.

학습 결과:

• 포맷화 및 변환: 슬랙 변수와 제약 조건 제거를 통해 원시 최적화 문제를 표준 볼록 형태로 변환합니다.
• 최적성 분석: 기울기 기반 최적성 기준을 적용하여 점이 전역적으로 최적인지 판단합니다.
• 분류 및 해결: LP, QP, SOCP, GP, SDP를 구분하고, 준볼록 함수에 대해 이분법과 같은 전문 방법을 적용합니다.

🔹 수업 5: 라그랑주 이중성과 KKT 조건

개요: 이 수업은 라그랑주 이중성의 기본 이론을 탐구하며, 라그랑주 이중 함수의 정의에서 시작해 이중 문제의 구성으로 나아갑니다. 원래 문제와 이중 문제 간의 최적 값 사이의 중요하지만 중요한 차이를 다루고, 이러한 관계의 기하학적 및 게임 이론적 해석을 설명하며, 최적해를 특성화하는 카루슈-쿤-타커(KKT) 조건을 소개합니다. 마지막으로, 이 개념들을 민감도 분석과 그림 가격(셔도우 프라이스)으로 확장합니다.

학습 결과:

• 다양한 최적화 문제에 대해 라그랑주 이중 함수를 도출하고 이중 문제를 구성합니다.
• 약한/강한 이중성과 슬레이터 제약 조건을 사용하여 원래 문제와 이중 문제 간의 관계를 평가합니다.
• 볼록 및 비볼록 문제에 대해 최적해를 해결하고 검증하기 위해 KKT 최적성 조건을 적용합니다.

🔹 수업 6: 근사, 피팅, 정규화

개요: 이 수업은 선형 방정식 시스템의 해를 근사하고 데이터에 함수를 피팅하는 수학적 기초와 실제 응용을 탐구합니다. 노름 기반 근사, 패널티 함수와 정규화를 통해 이상치와 희소성 관리 방법을 다루며, 데이터 불확실성을 다루기 위한 강건 최적화 기법도 포함합니다. 또한 볼록성과 단조성과 같은 특정 제약 조건 하에서 함수 피팅 방법을 자세히 설명합니다.

학습 결과:

• 최소제곱법, 체비셰프, L1 접근법 간의 기하학적 및 통계적 차이를 이해하고, 노름 근사 문제를 형식화하고 해결합니다.
• 잔차 오차, 해의 크기, 희소성 간의 트레이드오프를 달성하기 위해 정규화된 근사 모델을 설계하고 구현합니다.
• 데이터 행렬의 불확실성을 반영하기 위한 강건 근사 프레임워크를 구성합니다.

🔹 수업 7: 통계 추정 및 추론

개요: 이 수업은 통계적 추론과 볼록 최적화의 교차점에 초점을 맞춥니다. 최대우도, 비모수적 분포 추정, 최적 감지기 설계 등 추정 문제를 볼록 프로그램으로 형식화합니다. 학생들은 최적화를 통해 매개변수를 찾고 정보성 있는 실험을 설계하는 방법을 배웁니다.

학습 결과:

• 최대우도 추정(MLE) 및 로지스틱 회귀 문제를 볼록 최적화 문제로 형식화하고 해결합니다.
• 선형 프로그래밍(LP)을 사용하여 최적 감지기를 설계하고, 수신기 작동 특성(ROC)을 해석합니다.
• 최대 엔트로피와 쿨백-라이블러 발산 최소화를 포함한 비모수 추정 기법을 적용합니다.

🔹 수업 8: 기하학적 문제와 분류

개요: 이 수업은 볼록 최적화를 기하학적 문제에 적용합니다. 집합 위로 점을 투영하거나 집합 간 거리를 계산하며, 집합 중심을 특성화하는 방법을 다룹니다. 이러한 기하학적 원리를 현실 세계 작업인 선형 및 비선형 분류, 최적 시설 위치 지정, 기하학적 프로그래밍을 이용한 플로어 플래닝에 확장합니다.

학습 결과:

• KKT 조건과 이중 표현을 사용하여 볼록 집합 간의 투영 및 거리 문제를 형식화하고 해결합니다.
• 극한 부피 타원체를 사용하여 복잡한 볼록 집합을 근사하고, 효율성 계수를 식별합니다.
• 다양한 집합 중심을 계산하고, 강건한 분류 및 식별에 적용합니다.

🔹 수업 9: 무제약 최소화 알고리즘

개요: 이 수업은 볼록 함수에 대한 무제약 최소화의 이론적 기초와 알고리즘 구현을 다룹니다. 1차 경사하강법에서 2차 뉴턴법까지 다양한 내림방향 방법을 설명하며, 강력한 볼록성과 자기일관성의 아핀 불변 이론에 기반한 수렴 분석에 큰 부분을 할애합니다.

학습 결과:

• 강력한 볼록성을 정의하고, 이를 통해 최적해로부터의 오차와 비최적성 상한을 제공합니다.
• 유클리드, 이차, L1 노름 하에서 경사하강법과 가장 낮은 하강법을 비교하고 대조합니다.
• 뉴턴 스텝과 뉴턴 감소량을 계산하고, 왜 뉴턴 법이 아핀 불변인지 설명합니다.

🔹 수업 10: 등식 제약 최소화

개요: 이 수업은 선형 등식 제약 조건을 가진 볼록 최적화 문제를 해결하는 방법을 탐구합니다. 뉴턴 스텝의 도출과 구현에 중점을 두며, 가능해와 불가능한 시작 방법을 비교하고, 원시-이중 프레임워크 내에서 이 스텝을 해석합니다. 특히, KKT 시스템의 블록 소거를 통한 효율적인 수치 구현에 특별한 주목을 합니다.

학습 결과:

• 등식 제약 문제에 대한 뉴턴 스텝과 감소량을 계산하고 해석합니다.
• 등식 제약을 가진 뉴턴 법과 해당 제약 조건을 제거하는 것의 동등성을 보여줍니다.
• 불가능한 시작 뉴턴 방법을 구현하고, 원시-이중 잔차 감소 성질을 설명합니다.

🔹 수업 11: 내부점 방법

개요: 이 수업은 불등식 제약 조건을 가진 볼록 최적화 문제를 해결하는 내부점 방법을 다룹니다. 뉴턴 법을 일련의 등식 제약 문제에 적용하며, 로그 보행 함수의 핵심 개념을 중심으로, 최적해로 향하는 중심 경로를 따라가고, 원시-이중 프레임워크를 활용해 효율성과 강건성을 높입니다.

학습 결과:

• 로그 보행 함수를 정의하고 구성하며, 중심 경로와 관련된 이중 점을 특성화합니다.
• 보행 방법을 구현하며, 중심화 단계와 외부 반복 사이의 트레이드오프를 이해합니다.
• 엄격하게 타당한 시작점을 찾기 위해 단계 1 타당성 문제를 형식화하고 해결합니다.