高級優化理論與方法（二）

上節回顧
- Constrained
- Unconstrained
- FONC
- SONC
- example
這節課的內容
- SOSC
- - 定理敘述
  - 證明
  - 例子
One-dimensional Search Methods
- Iterative Method
- - Golden Section Search
  - - Method
    - Issues
    - 方法推理
    - 算法描述
    - Time
    - Example
  - Fibonacci Method
  - Bisection Method
  - Newton Method
  - - Example
  - Secant Method
  - Bracketing
總結

上節回顧

Constrained

$f(x)\\ s.t. x\in \Omega$

Unconstrained

$min f (x)$

FONC

$x^*$ is optimal, $\forall d, \nabla f(x^*)^Td \geq 0$
(interior) $\nabla f(x^*)=0$

SONC

$x^*$ local optimal, $\forall d, d^T\nabla F(x)^Td \geq 0$
(interior) $\nabla f(x^*)=0,F(x^*)\geq0$

example

$min f(x_1,x_2)=x_1^2-x_2^2$

$x^*=[0,0]^T$

$\nabla f(x)=[2x_1,-2x_2]^T$

$\nabla f(x^*)=[0,0]^T$

$H(x)=\begin{bmatrix} 2 & 0 \\ 0 & -2 \end{bmatrix}>0$
$d_1=[1,0]^T$

$d_1^TF(x^*)d_1=[2,0][1,0]^T=2>0$

$d_2=[0,1]^T$

$d_2^TF(x^*)d_2=-2<0$

根據SONC， $0,0]^T$ not local minimizer.

這節課的內容

SOSC

定理敘述

【Second-order Sufficient Condition]
Let $f\in C^2$ be defined on a region in which $x^*$ is an interior point.Suppose that:
① $\nabla f(x^*)=0$
② $F(x^*)>0$
Then, $x^*$ is a strict local minimizer of f. $\forall x\in N_{\epsilon}(x^*):f(x^*)<f(x)$
注：對于無約束優化問題，我們只能給出一些充分條件或者必要條件，充要條件是數學界的一個公開問題，目前還沒有答案。

證明

證：
$\in C^2 \Rightarrow F(x^*)=F(x^*)^T$
(由Clairaut’s Theorem and Schwarz’s Therem， $\forall i,j \in [1,n],\frac{\partial^2 f(x^*)}{\partial x_i \partial x_j}=\frac{\partial^2 f(x^*)}{\partial x_j \partial x_i}$ )

Rayleigh’s Inequality:for a $\in \mathbb{R}^{n \times n}$ ,symmetric, positive definite:
$\lambda_{min}(P)||x||^2\leq x^TPx \leq \lambda_{max}(P)||x||^2$

where $\lambda_{min}(P)$ and $\lambda_{max}(P)$ are the minmal and maximal eigenvalue value of P, respectively.

a symmetric matrix is positive definite $\Leftrightarrow$ all its eigenvalues are positive.

$\because d^TF(x^*)d \geq \lambda_{min}(F(x^*))||d||^2>0$

$\therefore f(x^*+d)-f(x^*)=\frac{1}{2}d^TF(x^*)d+o(||d||^2)>0$

例子

$f(x)=x_1^2+x_2^2$
$\nabla f(x)=[2x_1,2x_2]^T$
$H(x)=\begin{bmatrix} 2 & 0 \\ 0 & 2 \end{bmatrix}>0$
$x^*=[0,0]^T$

One-dimensional Search Methods

Iterative Method

Iterative Method意為迭代算法。此處算法用algorithm其實不太嚴謹，因為要設計到算法的復雜度證明、正確性證明、能否停止等等的算法嚴謹性問題，而method這個詞則不用考慮這么多。迭代意為由某個初始點出發，找一些方向，往某些方向更新的過程。

Golden Section Search

Assume f: unimodular on $a_0,b_0]$ (only one minimizer in $a_0,b_0]$ )
Basic Idea: “Narrow Down”
Binary Search does not work out.
Pick two instead of one points.

Method

input: $a_0,b_0,f,\epsilon$
1. $i = 0$

2.while $b_i-a_i\geq \epsilon$ do

3.Pick $x < y$ from [a_i,b_i]

4.If $f (x) < f (y)$ then $a_{i+1}=a_i,b_{i+1}=y$ ;
else $b_{i+1}=b_i,a_{i+1}=x$

5.i++

6.END while

Issues

1.# while-loop
2.# computation of $f(\cdot)$

方法推理

W.O.L.G.(Without Loss of Generality)
Assume $b_0-a_0=1$
$a_1-a_0=b_1-b_0=\rho<\frac{1}{2}$

$\forall i: b_{i+1}-a_{i+1}=(1-\rho)(b_i-a_i)$

$b_1-a_1=1-2\rho$

$b_1-a_1=\rho(b_1-a_0)=\rho(1-\rho) \Rightarrow 1-2\rho=\rho-\rho^2 \Rightarrow \rho^2-3\rho+1=0$

$\rho_1=\frac{3+\sqrt{5}}{2}>\frac{1}{2}$ （舍去）, $\rho_2=\frac{3-\sqrt{5}}{2}<\frac{1}{2}$

算法描述

1.compile $b_1=a_0+(1-\rho)(b_0-a_0),a_1=a_0+\rho(b_0-a_0),f(a_1),f(b_1)$

2.i=0

3.while $b_i-a_i\geq \epsilon$ do
if $f(a_{i+1})<f(b_{i+1})$ then
$b_{i+2}=a_{i+1},a_{i+2}=a_i+\rho(b_{i+1}-a_i),a_{i+1}=a_i$
else
$a_{i+2}=b_{i+1},b_{i+2}=b_i-\rho(b_i-a_{i+1}),b_{i+1}=b_i$

4.i++

5.END while

Time

1.While-Loop: time of $f(\cdot)$ +O(1)
2.Loop: $(1-\rho)^N(b_0-a_0)<\epsilon$
N= $argmin(log_{1-\rho}\frac{\epsilon}{b_0-a_0})$

Example

$\epsilon=0.3$
$f(x)=x^4-14x^3+60x^2-70x$
[0,2]
$(1-\rho)^N<\frac{0.3}{2}=0.15\Rightarrow N=4$

1. $a_1=a_0+\rho(b_0-a_0)=0.7633$
$b_1=a_0+(1-\rho)(b_0-a_0)=1.236$
$f(a_1)=-24.36$
$f(b_1)=-18.96$

2.[0,1.236]
$b_2=a_1=0.7639$
$a_1=a_0+\rho(1.236-0)=0.4721$
$f(b_2)=-24.36$
$KaTeX parse error: Expected 'EOF', got '}' at position 6: f(a_2}?=-21.10$

3.[0.4721,1.236]
$a_3=b_2=0.7639$
$b_3=a_2+(1-\rho)(1.236-0.4721)=0.9443$
$f(a_3)=-24.36$
$f(b_3)=-23.59$

4.[0.4721,0.9443]
$b_4=a_3=0.7639$
$a_4=0.4721+\rho(0.7443-0.4721)=0.6525$
$f(b_4)=-24.36$
$f(a_4)=-23.86

5.[0.6525,09443]
$0.9443-0.6525<0.3=\epsilon$
算法終止

Fibonacci Method

事實上，每一輪的 $\rho$ 不一定要固定，也可以變化。假設 $\rho$ 會變化，我們來推導一下每一輪之間 $\rho$ 的關系。
$\rho_1(1-\rho_0)=1-2\rho_0$
$\rho_{k+1}(1-\rho_k)=1-2\rho_k$
$\rho_{k+1}=1-\frac{\rho_k}{1-\rho_k}$

問題轉化為
min $(1-\rho_0)(1-\rho_1)\cdots (1-\rho_k)$
s.t. $\rho_{k+1}=1-\frac{\rho_k}{1-\rho_k}$

結論為 $\rho_0=1-\frac{F_N}{F_{N+1}},\rho_{N-1}=1-\frac{F_1}{F_2}$
$F_k$ 為Fibonacci數列的第 $k$ 項， $F_0=0,F_1=1,F_{k+2}=F_k+F_{k+1}$

注：用該方法來做比黃金分割法要快。

Bisection Method

Assume:f: unimodular on $a_0,b_0]$ , f continuously differentiable.

$f'(c)<0:[c,b_0]$
$f'(c)>0:[a_0,c]$
$f^{'} (c) = 0 :$ return $c$

$(\frac{1}{2})^N<\epsilon$

Newton Method

Assume: $\in C^2\Rightarrow x^*\in [a,b]: f'(x^*)=0$

$x_{k+1}=x_k-\frac{f(x_k)}{f'(x_k)}$ 或 $x_{k+1}=x_k-\frac{f'(x_k)}{f''(x_k)}$

該方法只有在初始點選的比較好的時候才管用，若初始點選的不好，可能產生振蕩不收斂的問題。

Example

$f(x)=\frac{1}{2}x^2-sinx$

$x_0=0.5$

$\epsilon=10^{-5}$

$f^{'} (x) = x ? cos x$

$f^{''} (x) = 1 + s in x$

$x_1=0.5-\frac{0.5-cos0,5}{1+sin0.5}=0.7552$

$x_2=0.7391$

$x_3=0.7390$

$x_4=0.7390$

Secant Method

secant意為切線。

$\in C^1$

$f''\approx\frac{f'(x_{k+1})-f'(x_k)}{x_{k+1}-x_k}$

$x_{k+1}=x_k-\frac{f'(x_k)(x_k-x_{k-1})}{f'(x_k)-f'(x_{k-1})}$

Bracketing

Find the initial $a_0,b_0$
Suffice: $a_0,c,b_0\leftarrow f(a_0)>f(c),f(b_0)>f(c)$
該方法用于求得一個理想的區間，然后使用其它算法來做，但在實際應用中比較少見，且不太好用。

總結

本節課先回顧了FONC和SONC這兩個找最值點的必要條件，然后給出了SOSC這個找最值點的充分條件。雖然看上去比較簡單，但是關于無約束優化的定理目前也只發展到這種程度。目前數學界還沒有找出一個充分必要條件。然后介紹了一維搜索方法中的迭代方法。重點介紹了黃金分割法，簡略介紹了斐波那契法、二分法、牛頓法、割線法等方法。

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/718979.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/718979.shtml
英文地址，請注明出處：http://en.pswp.cn/news/718979.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！