內點法主要思想

1。 內點法在迭代中總是從內點出發，並保持在可行域內部搜尋

2。 透過引入效用函式的方法將約束最佳化問題轉換成無約束問題，再利用最佳化迭代過程不斷地更新效用函式，以使得演算法收斂。

內點法適用範圍

只能處理不等式約束

內點法實現思路

例如：

minf(x)

s. t

g_{i}(x)\geq0 i=1,2,3,...,m

(1)

f(x)

、

g_{i}(x)

是

E^{n}

上連續的函式，

將可行域記作

S

= {

{x|g_{i}\geq0,i=1,2,3,...,m}

}

(2)

保持迭代點含於可行域內部的方法是定義障礙函式

G(x,r)=f(x)+rB(x)

(3)

其中

B(x)

是連續函式，當點

x

趨向可行域邊界時，

B(x)\rightarrow

+

無窮大

B(x)

函式的兩個重要的形式：

B(x) = \sum_{i}^{m}{\frac{1}{g_{i}(x)}}

(4)

B(x) =-\sum_{i}^{m}{log g_{i}(x)}

(5)

r

是很小的正數，這樣，當

x

趨向邊界時，函式

G(x,r)\rightarrow+

無窮大；否則，由於

r

很小，則函式

G(x,r)

的取值近似

f(x)

。因此，可透過求解下列問題得到

(1)

的近似解：

minG(x,r)

s.t

x\epsilon

intS

(6)

由於

B(x)

的存在，在可行域形成“圍牆”，因此

(6)

的解

\bar{x}_{r}

比含於可行域的內部

(6)

仍是約束問題，但由於

B(x)

的阻擋作用是自動實現的，因此從計算的觀點看，

(6)

可當作無約束問題來處理

內點法計算步驟

顯然，

r

取值越小，

(6)

的最優解越接近

(1)

的最優解。但是，如果

r

太小，則將給

(6)

的計算帶來很大的困難

因此，仍採取序列無約束極小化方法

(SUMT)

，取一個嚴格單調遞減且趨於零的罰因子（也叫障礙因子）數列{

{r_{k}}

}，對於每一個

k

，從內部出發，求解問題：

min G(x,r_{k})

s.t

x\epsilon

intS

(7)

給定初始內點

x_{0}\epsilon

intS

，允許誤差

\varepsilon\succ0

，初始引數

r_{1}

，縮小系數

\beta\epsilon(0,1)

，令

k=1

以

x^{(k-1)}

為初始點，求解無約束問題

minf(x)+r_{k}B(x)

s.t

x\epsilon

intB

設其極小點為

x_{k}

3。 若

r_{k}B(x_{k})<\varepsilon

，則停止計算，得到點

x_{k}

；否則，令

r_{k+1}=\beta r_{k}

，令

k:=k+1

，返回步2

具體案例

例：

min \frac{1}{12}(x_{1}+1)^3+x_{2}

s.t

x_{1}-1 \geq0

x_{2}\geq0

令

G(x,r_{k})=\frac{1}{12}(x_{1}+1)^3+x_{2}+r_{k}(\frac{1}{x_{1}-1}+\frac{1}{x_{2}})

(1)

用解析法求解：（其實就是高數中的求偏導並令其等於零）

\frac{∂G(x)}{∂x_1}=\frac{1}{4}(x_{1}+1)^2-\frac{r_{k}}{x_{1}-1}=0

(2)

\frac{∂G(x)}{∂x_2}=1-\frac{r_{k}}{x^2_{2}} = 0

(3)

由

(1)

式可得，

x_1 = \sqrt{1+2\sqrt{r_k}}

； 由

(2)

式可得，

x_2 = \sqrt{r_k}

，故：

\bar{x_{r_{k}}} = (x_{1},x_{2}) = (\sqrt{1+2\sqrt{r_k}},\sqrt{r_k})

當

r_k\rightarrow0

時，

\bar{x_{r_k}}\rightarrow\bar{x}=(1,0)

，

\bar{x}

就是原問題的最優解。