非線性最小化與曲線擬合最佳化模型

非線性函式最小化在工程和科學領域中是一個常見問題。對於凸函式，可以採用分段線性化方法逼近最優解，透過迭代逐步提高精確度。但對於非凸函式，線性規劃方法可能導致錯誤解，需要引入整數規劃和額外約束來解決。曲線擬合是另一個重要的應用，最小二乘法是最常用的方法，但也可以根據需求選擇其他距離度量，例如絕對值偏差之和或最大偏差。多項式曲線擬合可以使用線性規劃模型實作，透過引入雙倍不等式或雙倍變數來處理絕對值函式的非線性特性。網路模型在視覺化和解決最佳化問題中扮演著重要角色，特別是線性網路模型通常具有整數最佳解，並可應用於社交網路分析、交通網路最佳化等領域。最大流問題是網路模型中的一個經典問題，可以透過線性規劃模型來求解，並透過修改目標函式來處理多個最優解的情況。

非線性最小化問題的線性化處理

在處理非線性函式的最小化問題時，我們可以利用線性規劃的方法來逼近最優解。特別是在函式為凸函式的情況下，這種方法尤其有效。

凸函式的最小化

對於一個非線性但為凸的函式，我們可以透過將其分段線性化來進行最小化。這種方法涉及將函式的定義域分成多個區間，並在每個區間內用線性函式來近似原函式。

表 3-5：非線性最小化的最優解

從表 3-5 中可以看到，隨著迭代的進行，解的精確度不斷提高。每三行代表一次迭代，分別對應於$x$的斷點、函式在這些點的值、以及區間引數$\delta$。最右邊兩列給出了對應的最優$x$和$f(x)$。

非凸函式的挑戰

然而，當函式為非凸時，上述方法可能會失敗。例如，如果單位成本隨著數量增加而不斷下降，如表 3-6 和圖 3-4 所示，則線性規劃求解器可能會找到一個非連續點的組合，從而得到一個錯誤的最優解，如表 3-7 所示。

表 3-7：非凸目標函式的錯誤解

在這種情況下，儘管$\delta$的總和為1，且決策變數的值正確，但總成本卻是無意義的。這是因為求解器考慮了$f(0)$和$f(924)$之間的直線，這條直線低於$f(x)$，從而對$x$的中間值產生了較低的成本。

改進方法

幸運的是，透過使用整數規劃並新增額外的約束，可以解決非凸函式的最小化問題。這將在第7章的第7.2節中進一步討論。

曲線擬合

一個常見的問題是將一組資料點轉換為這些資料的解析表示。統計學家稱之為迴歸；應用數學家稱之為引數估計；工程師則稱之為曲線擬合。

最小二乘法

最簡單和最著名的例子是假設一個下落物體遵循$f(t) = a_2t^2 + a_1t + a_0$形式的曲線，但不知道$a_0$、$a_1$和$a_2$的適當值。透過實驗收集資料（見表3-8），然後使用最小二乘法來確定這些係數。

表 3-8：二次曲線擬合資料示例

| $t_i$ | $f_i$ | |

:

:| | $ $ |$ $ $ | 最小二乘法涉及最小化資料點與擬合曲線之間的歐幾裡得距離的平方和。這可以透過求解一個線性方程組（即所謂的正規方程）來實作。

其他距離度量

除了歐幾裡得距離外，還可以使用偏差的絕對值之和或最大偏差作為目標函式。後者在處理公差時尤其有用，即所有誤差必須在某個最大範圍內。

建立模型

我們將分階段描述這個相當複雜的模型。首先，假設我們需要確定一個$k$次多項式的係數$a_0, a_1, …, a_k$，使得資料點與多項式之間的偏差（無論是總和還是最大值）最小。

程式碼實作

import numpy as np
from scipy.optimize import curve_fit

# 定義二次函式
def func(t, a2, a1, a0):
    return a2 * t**2 + a1 * t + a0

# 生成模擬資料
t_data = np.array([0.1584, 0.8454, 2.1017, 
                   # ... 其他資料點
                  ])
f_data = np.array([0.0946, 
                   # ... 其他資料點
                  ])

# 使用curve_fit進行曲線擬合
popt, pcov = curve_fit(func, t_data, f_data)

# 輸出擬合引數
print("擬合引數：", popt)

程式碼解析：

1. 首先，我們匯入必要的函式庫：numpy用於數值計算，scipy.optimize中的curve_fit用於曲線擬合。
2. 定義了一個二次函式func，它接受時間t和係數a2、a1、a0作為輸入，傳回對應的函式值。
3. 生成或載入實驗資料t_data和f_data。
4. 使用curve_fit函式對資料進行曲線擬合，得到最佳擬合引數popt。
5. 輸出擬合得到的引數。

這種方法可以根據具體需求選擇不同的目標函式，從而靈活地解決各種曲線擬合問題。

多項式曲線擬合的最佳化模型

在資料分析和建模中，曲線擬合是一種常見的技術，用於找到一條最佳的曲線來描述一組資料點。本章節將探討如何使用線性規劃來實作多項式曲線擬合，並介紹相關的最佳化模型。

問題描述

給定一組資料點 $(t_i, f_i)$，我們的目標是找到一個多項式函式 $f(t) = a_0 + a_1t + a_2t^2 + \cdots + a_nt^n$，使得該函式能夠最好地擬合這些資料點。這裡的“最好”可以根據不同的標準來定義，例如最小化最大偏差或最小化偏差總和。

模型建立

為了建立最佳化模型，我們首先需要定義偏差。對於每個資料點 $(t_i, f_i)$，偏差 $e_i$ 定義為實際值 $f_i$ 與理論值 $f(t_i)$ 之間的絕對差值，即 $|f(t_i) - f_i|$。

處理非線性約束

由於絕對值函式是非線性的，我們需要將其轉換為線性形式。有兩種常見的方法：

1. 雙倍不等式法：透過引入兩個不等式來取代 $|e_i| \leq e$，即 $f(t_i) - f_i \leq e$ 和 $f_i - f(t_i) \leq e$。這種方法適用於最小化最大偏差的情況。
2. 雙倍變數法：引入兩個非負變數 $u_i$ 和 $v_i$，使得 $f(t_i) - f_i = u_i - v_i$。這樣，偏差可以表示為 $u_i + v_i$。這種方法可以用於最小化偏差總和或最大偏差。

可執行模型

Listing 3-3 提供了一個 Python 實作的多項式曲線擬合模型，使用了雙倍變數法。模型的輸入包括資料點集合 D、多項式的階數 deg 以及目標函式的型別 objective（0 表示最小化偏差總和，1 表示最小化最大偏差）。

def solve_model(D, deg=1, objective=0):
    s, n = newSolver('Polynomial fitting'), len(D)
    b = s.infinity()
    a = [s.NumVar(-b, b, 'a[%i]' % i) for i in range(1 + deg)]
    u = [s.NumVar(0, b, 'u[%i]' % i) for i in range(n)]
    v = [s.NumVar(0, b, 'v[%i]' % i) for i in range(n)]
    e = s.NumVar(0, b, 'e')
    for i in range(n):
        s.Add(D[i][1] == u[i] - v[i] + sum(a[j] * D[i][0]**j for j in range(1 + deg)))
    for i in range(n):
        s.Add(u[i] <= e)
        s.Add(v[i] <= e)
    if objective:
        Cost = e
    else:
        Cost = sum(u[i] + v[i] for i in range(n))
    s.Minimize(Cost)
    rc = s.Solve()
    return rc, ObjVal(s), SolVal(a)

內容解密：

1. 變數定義：a 表示多項式的係數，u 和 v 表示每個資料點的偏差，e 表示最大偏差。
2. 約束條件：第一個迴圈建立了每個資料點的理論值與實際值之間的關係。第二個迴圈確保了每個偏差都不超過最大偏差 e。
3. 目標函式：根據 objective 的值選擇最小化最大偏差或最小化偏差總和。
4. 求解：呼叫求解器求解最佳化問題，並傳回結果。

變化與擴充套件

本章節介紹的多項式曲線擬合模型是處理軟約束問題的一個特例。在實際應用中，軟約束問題非常常見，例如在學生排課系統中，由於資源限制，可能無法滿足所有學生的請求。這時，可以使用類別似的方法，將硬約束轉換為軟約束，並透過最佳化模型找到一個儘量好的解決方案。

線性網路模型

網路理論的基本元素！這個概念以及相關的戲劇、電影和遊戲，比多年的公共教育更有效地向大眾介紹了網路理論的基本元素。電影愛好者玩「凱文·貝肯遊戲」，試圖透過與凱文·貝肯共同出演的電影將兩位演員聯絡起來。數學家們驕傲地宣佈他們的艾德洛什數（如果有的話），即他們與著名數學家保羅·艾德洛什共同撰寫的論文之間的距離。

網路模型的重要性

在本章中，網路在視覺化問題方面扮演著至關重要的角色。網路是由節點（例如人）和弧（表示關係的存在）組成的物件。這是數學家數百年前發明的一種工具，用於幫助建模和解決問題。我們將使用網路來幫助構建最佳化模型。在某種意義上，我們正在進行元建模。

網路最佳化模型的特點

根據網路的最佳化模型通常具有一個有趣的特性：如果輸入資料都是整數，那麼存在一個整數最佳解。此外，求解器通常能夠有效地找到這個整數解。網路模型的這種特性使其在許多實際應用中非常有用。

網路模型的應用

網路模型可用於各種領域，例如社交網路分析、交通網路最佳化、物流和供應鏈管理等。在這些應用中，網路模型可以幫助我們理解複雜系統的結構和行為，並找到最佳的解決方案。

社交網路分析

在社交網路分析中，網路模型可以用來研究人們之間的關係和互動。例如，我們可以使用網路模型來找出社交網路中的關鍵人物或群體。

交通網路最佳化

在交通網路最佳化中，網路模型可以用來最佳化交通流和減少擁堵。例如，我們可以使用網路模型來設計最優的交通訊號控制策略。

程式碼實作

以下是一個簡單的程式碼範例，用於建立一個基本的網路模型：

import networkx as nx

# 建立一個新的網路
G = nx.Graph()

# 新增節點
G.add_node("A")
G.add_node("B")
G.add_node("C")

# 新增弧
G.add_edge("A", "B")
G.add_edge("B", "C")
G.add_edge("C", "A")

# 列印網路的節點和弧
print("節點：", G.nodes())
print("弧：", G.edges())

內容解密：

1. 我們首先匯入 networkx 函式庫，這是一個用於建立和操作網路的Python套件。
2. 我們建立一個新的網路 G，並新增三個節點 “A”、“B” 和 “C”。
3. 我們新增三個弧，分別連線 “A” 和 “B”、“B” 和 “C”、“C” 和 “A”。
4. 最後，我們列印出網路的節點和弧，以驗證我們的建立是否正確。

線性網路模型中的最大流問題

在許多實際應用中，網路流問題扮演著重要的角色。這些問題通常涉及在具有容量限制的網路中，最大化從來源節點到達目的節點的流量。本章節將探討最大流問題，並建立一個線性規劃模型來解決它。

最大流問題的定義

最大流問題是指在一個有向圖中，每條邊都有一個容量限制，我們需要找到從來源節點到達目的節點的最大流量。這個問題在許多領域中都有應用，例如網路通訊、交通運輸和物流管理等。

建立模型

要解決最大流問題，我們需要定義決策變數。在這個例子中，我們使用一個二維變數 $x_{i,j}$ 來表示從節點 $i$ 到節點 $j$ 的流量。

決策變數

$x_{i,j}$：從節點 $i$ 到節點 $j$ 的流量

目標函式

我們的目標是最大化從來源節點到達目的節點的總流量。這可以透過最大化來源節點的淨流出量來實作：

max ∑_{i ∈ S, j ∈ N} x_{i,j} - ∑_{j ∈ N, i ∈ S} x_{j,i}

這個目標函式確保了我們最大化了從來源節點到達目的節點的總流量。

限制條件

在建立模型時，我們需要考慮以下限制條件：

1. 容量限制：每條邊的流量不能超過其容量限制。
2. 流量守恆：除了來源節點和目的節點之外，其他節點的流入量必須等於流出量。

處理多個最優解

在某些情況下，最大流問題可能有多個最優解。為了避免這種情況，我們可以引入一個額外的目標函式，即最小化流入來源節點的流量。這可以透過修改目標函式來實作：

max 2 * ∑_{i ∈ S, j ∈ N} x_{i,j} - ∑_{i ∈ S, j ∈ N} x_{j,i} - ∑_{j ∈ N, i ∈ S} x_{j,i}

內容解密：

這個修改後的目標函式結合了最大化淨流出量和最小化流入來源節點的流量。這樣可以確保我們在多個最優解中選擇一個最合理的解。

圖示說明

@startuml
skinparam backgroundColor #FEFEFE
skinparam defaultTextAlignment center
skinparam rectangleBackgroundColor #F5F5F5
skinparam rectangleBorderColor #333333
skinparam arrowColor #333333

title 圖示說明

rectangle "x_0,1" as n1
rectangle "x_1,2" as n2
rectangle "x_1,0" as n3

n1 --> n2
n2 --> n3

@enduml

此圖示展示了一個簡單的最大流問題的網路結構。

內容解密：

這個圖示說明瞭來源節點、中間節點和目的節點之間的流量關係。其中，$x_{0,1}$ 表示從來源節點到中間節點的流量，$x_{1,2}$ 表示從中間節點到目的節點的流量，而 $x_{1,0}$ 表示從中間節點迴流到來源節點的流量。