# Optimization for Expensive Function
contributed by <`kylekylehaha`>
###### tags: `Data Science`

例如: 想知道該藥是否對人有好處，但召集人的成本很高，無法瘋狂的測試不同配方

我們可以先建立一個小型 model, 該 model 和 objective function 很像。故我們在 model 上就可以瘋狂測試，找到一個不錯的後再去 objective function 測試。

---

## Surrogate-based Optimization
> Create a function to approximate the expensive function

**Surrogate-based methodology**
Given:
- A set of parameters $\theta$ to find $\theta=\{\theta_1, \theta_2, ... , \theta_n\}$
- A function $f$ take $\theta$ as input and output a real value
- Lower **bound** and upper **bound** of parameters
- $Lower_i \le \theta_i \le Upper_i$
- Sometimes, special constraint may be exist
- $(\theta_i)^2+(\theta_j)^2 \le d$

Output:
- A set of parameters $\theta^*={\theta^*_1, \theta^*_2,...,\theta^*_n}$ such that $f(\theta^*)$ is minimized, and the constraints can be satisfied.

The **objective function** is the function we want to optimize.

The object function is expensive for resources, like time. So, we create a cheap function, **surrogate function**, to approximate the object function.

We run an optimization algorithm on the surrogate function to find a **promising point**, like the optimum. Feed the promising point to the objective function.


- Observed points: 已知在 objective function 上的值，用來建構 surrogate optimization.


---

## Surrogate Function
We use **regression** function to build **surrogate function**. Introduce 3 regressions:
- Quadratic regression
- RBF
- SVR

---

### Quadratic regression
Simple regression
$$
S(x)=x^TQx+w^Tx+b
$$

Find $argmin_{Q,w,b} \sum_{\theta \in O}||S(\theta)-F(\theta)||$, with the method of Least Square.
> (1) Build surrogate funciton

---

因為這個 S 只有以下三種型態，故可以直接公式解得知 optimum, 也就是 promising point.


> (2) Select next promising point

---

Advantage:
- It can rapidly find the minimal point by formula, instead of optimization algorithms.

Disadvantage:
- It has bad performance for many observed points with outliers.
- The generality is not good.


可以看到 minimal on surrogate 和實際的 minimal objective function 有落差。

---

### RBF Regression (Radial basis function)
- Radial function $\phi:[0, \infty)->R$
- a is called center of radial function $\phi(||x-a||)$

RBF regression:
$$
S(x)=\sum^n_{i=1}\lambda_i \phi(||x-\theta_i||)
$$
- n is the number of observed points.
- 每個點都有一個 rbf(一個波)
- $\lambda$ 讓 rbf 長高
- 而最後的 regression 為所有長高後的波加總起來，形成 continuous function。


---

How to get $\lambda_i$?
> (1) Build surrogate function

observed point 的值和 surrogate function 值相同(一開始紅色的部分)

只有接近 observed point 的地方不是 0

---

How to select $\hat{\theta}$?
> Select next promising point

1. FInd the minimal point $\theta^*$ in **observed points O**
2. Use random search to generate **sample points** centered on $\theta^*$
3. Select the point among the **sample points** with minimum $S(\cdot)$ as the selected point $\hat{\theta}$

---

Advantage:
- It can fit continuous funciton

Disadvantage:
- The RBF function only fits area near observed point
- efficiency lower than quadratic regression(because use formula to solve)

---