Lecture 1 : Convex Optimization (Stanford)

Introduction

---

• mathematical optimization (수학적 최적화)
• least-squares and linear programming (최소 제곱과 선형 계획법)
• convex optimization (볼록 최적화)
• example (예시)
• course goals and topics (코스 목표 및 주제)
• nonlinear optimization (비선형 최적화)
• brief history of convex optimization (볼록 최적화의 간략한 역사)

Mathematical Optimization

---

Optimization Problem의 정의 : 

• $x = (x_{1}, ..., x_{n})$ : Optimization variables(최적화 변수), Decision variables(결정 변수)
• $f_{0} : R^{n} \rightarrow R$ : objective function(목적함수)
• $f_{i} : R^{n} \rightarrow R, i = 1,...,m$ : constraint function (제약 함수)

최적의 솔루션 $x^{*}$은 제약조건(constraints)을 충족하는 모든 벡터 중에서 가장 작은 $f_{0}$값을 가집니다.

Examples

---

portfolio optimization

• variables : 다른 자산에 투자된 금액
• constraints : 예산, 자산당 최대 / 최소 투자, 최소 수익률
• objective : 전체 위험 또는 수익률 분산

device sizining in electronic circuits

• variables : 장치의 폭 및 길이
• constraints : 제조 한계, 타이밍 요건, 최대 면적
• objective : 전력 소비량

data fitting

• variables : 모델의 매개변수
• constraints : 이전의 정보, 매개 변수의 한계
• objective : 부적합 또는 예측 오차의 척도

Solving optimization problems

---

general optimization problem

• 매우 풀기 어렵습니다.
• 방법론에는 약간의 다음과 같은 타협을 포함합니다. e.g 매우긴 시간, 또는 항상 해결책을 찾는 것은 아닙니다.

exceptions : 특정 클래스의 문제는 효율적이고 안정적으로 해결할 수 있습니다.

• 최소자승 문제들
• 선형 계획 문제들
• 볼록 최적화 문제들

Least-squares

---

최소제곱문제는 Squared-uclidean-norm인$\left \| Ax-b \right \|^{2}_{2}$을 최소화하는 것으로 정의됩니다.

Solving least-squares problems

• 분석적 해결책은 다음과 같습니다. : $x^{*}=(A^{T}A)^{-1}A^{T}b$
• 안정적이고 효율적인 알고리즘 및 소프트웨어임.
• 시간복잡도는 $n^{2}k(A \in R^{k \times n})$에 비례합니다. A가 Sparse한 경우 그보다 훨씬 작습니다.(n은 x의 크기, k는 행의 수. 따라서 이것이 회귀문제인 경우 또는 이런식으로, k는 예제의 수 또는 데이터 측정이나 데이터 요소같은 것이며, n은 우리가 아는 수, 기능 또는 회귀 변수)
• 매우 큰 문제를 해결할 수 있습니다.

using least-squares

• least-squares문제는 알아보기 쉽습니다.
• 몇가지 표준 기술을 통해 유연성을 향상 시킬 수 있습니다.(e.g. weighted least-squares, regularzation)

Linear programming

---

Solving linear programs

• 일반적으로 해결책을 위한 분석적 공식이 없음.
• 안정적이고 효율적인 알고리즘 및 소프트웨어임.
• 시간복잡도는 $n^{2}m \ \ if \ \ m \geq n;$며 이것은 least-square과 같습니다.

using linear programming

• least-square문제처럼 알아보기는 쉽지 않습니다.
• 문제들을 linear program으로 변환시켜 사용할 수 있는 몇가지 표준적인 트릭이 존재합니다. (e.g., l1 또는 l2-norms, piecewise-linear functions)

Convex optimization problem

---

목적함수와 제약함수가 convex하다면 다음과 같은 부등식을 만족한다.

$$f_{i}(\alpha x + \beta y) \leq \alpha f_{i}(x) + \beta f_{i}(y)$$

만약 $\alpha + \beta = 1,\ \alpha \geq 0, \ \beta \geq 0$

solving convex optimization problems

• 일반적으로 분석적인 해결책이 없음.
• 안정적이고 효율적인 알고리즘 및 소프트웨어임.
• 시간복잡도는 least-square과 거의 같음.${n^{3},n^{2}m,F}$ (F는 모든 기능을 평가하는데 드는 비용임. 1차 및 2차 도함수 같은 것.)

using convex optimization

• 볼록함수를 인식하는 것은 실제로 쉽지 않음.
• 문제들을 convex form으로 변환시키는 다양한 트릭들이 있음.
• 놀랍게도 많은 문제들이 convex optimization을 통해서 해결될 수 있음.

Example

---

- problem

Solution

---

how to solve?

1. 균일한 힘을 사용 : $p_{j}=p$, vary $p$

2. least-squares 사용 : $$minimize \ \ \sum^{n}_{k=1}(I_{k} - I_{des})^{2}$$

round $p_{j}$ if $p_{j} > p_{max}$ or $p_{j} < 0$

3. weight least-squares 사용 : $$minimize \ \ \sum^{n}_{k=1}(I_{k} - I_{des})^{2}+\sum^{m}_{j=1}w_{j}(p_{j}-p_{max}/2)^{2}$$ 

iteratively adjust weights $w_{j}$ until $0 \leq p_{j} \leq p_{max}$

4. linear programming 사용:

선형 계획법을 통해 해결할 수 있습니다.

5. Convex optimization 사용 : 문제는 다음과 같음

with $h(u)=$ max{$u,1/u$}

볼록함수의 최대가 볼록하기 때문에 $f_{0}$는 convex하다.

노력으로 얻은 정확한 solution $\approx$ 적당한 요소 x least-squares 노력

additional constraints : 아래에 1개 또는 2개를 추가하면 문제가 복잡해지나?

1. 10 개의 램프에 총 전력의 절반 이하
2. 램프의 절반 이상이 켜져 있지 않음.($p_{j} > 0) 

• 정답 : 1번은 해결하기 쉬우나, 2번을 사용한다면 매우 어려움.
• moral : (훈련되지 않은) 직관이 항상 작동하는 것은 아님. 적절한없이 배경 매우 쉬운 문제는 매우 어려운 문제와 매우 유사하게 나타날 수 있음.

Course goals and topics

---

goals

1. 문제(조명 문제 등)를 볼록 최적화 문제로 인식 또는 정식화하는 것
2. 적당한 크기의 문제에서 코드 개발.(1000개의 램프와, 5000개의 패치)
3. 최적화 solution을 특성화(파워 분배 최적), 성능을 제한.

topics

1. convex sets, functions, optimization problems
2. examples and applications
3. algorithms

Nonlinear optimization

---

 

local optimization methods (nonlinear programming)

• 근처의 실현가능한 점 중에서 $f_{0}$를 최소화하는 점을 찾으면 됨.
• 빠르고, 큰 문제들을 다룰 수 있음.
• 초기에는 추측이 필요할 수 있음.
• 전역 최적점과의 거리에 대한 정보를 제공하지 않음.

global optimization methods

• global solution을 찾는 것
• 최악의 복잡성은 문제 크기에 따라서 기하급수적으로 증가함.

이러한 알고리즘은 종종 하위 문제 해결을 기반으로 함.