非線性規劃 Nonlinear Programming

Presentation on theme: "非線性規劃 Nonlinear Programming"— Presentation transcript:

1 非線性規劃 Nonlinear Programming
第十二章 非線性規劃 Nonlinear Programming 作業研究 二版 2009 © 廖慶榮

2 章節大綱 前言 非線性規劃的應用 極大值與極小值 凸函數與凹函數 非線性規劃的類別 單變數無限制式最佳化 多變數無限制式最佳化
限制式最佳化的KKT條件 作業研究 二版 Ch.12 非線性規劃

3 12.1 前言 作業研究 二版 Ch.12 非線性規劃

4 12.2 非線性規劃的應用 範例12.1 銷售量與單位售價、單位成本的關係 銷售量與利潤的關係 作業研究 二版 Ch.12 非線性規劃

5 範例12.3 /變動人力問題 問題 NLP模式： 每輛貨車由1位司機和1~3位搬運工組成搬運小組
每小組每年賺 (y-1) 萬元（y=搬運工人數） 公司每年支付每位司機70萬元、每位搬運工50萬元，公司每年有800萬的人力費用預算 該搬家公司應聘僱幾位司機以及幾位搬運工，才能獲得最大的利潤？ NLP模式： 作業研究 二版 Ch.12 非線性規劃

6 範例12.4 /倉儲中心位置問題 問題 NLP模式: 倉儲中心應設在何處（x-y座標），才能使由倉儲中心至各分店的總來回距離最短？
作業研究 二版 Ch.12 非線性規劃

7 範例12.5 /投資組合問題 問題：(1)股票9.8%、(2)債券4.6%、(3)基金5.3% NLP模式：
公司希望在達到每年6.0%的預期收益情況下，盡可能降低投資組合的風險，其風險衡量如下： NLP模式： 作業研究 二版 Ch.12 非線性規劃

8 12.3 極大值與極小值 /單變數 作業研究 二版 Ch.12 非線性規劃

9 12.3 極大值與極小值 /單變數 作業研究 二版 Ch.12 非線性規劃

10 範例12.6 考慮以下函數： 作業研究 二版 Ch.12 非線性規劃

11 局部極值與全域極值 局部極小值（極大值）與全域極小值（極大值） 作業研究 二版 Ch.12 非線性規劃

12 多變數 作業研究 二版 Ch.12 非線性規劃

13 多變數 判斷關鍵點是極小值、極大值或鞍點 利用該點的赫斯矩陣（Hessian matrix）： 此為對稱的（symmetric）矩陣
作業研究 二版 Ch.12 非線性規劃

14 赫斯矩陣定性的判斷方式 作業研究 二版 Ch.12 非線性規劃

15 判斷多變數的關鍵點 作業研究 二版 Ch.12 非線性規劃

16 範例12.7 /以赫斯矩陣判斷關鍵點 考慮以下函數： 作業研究 二版 Ch.12 非線性規劃

17 12.4 凸函數與凹函數 作業研究 二版 Ch.12 非線性規劃

18 凸函數與凹函數的圖形 嚴格凸的 嚴格凹的 作業研究 二版 Ch.12 非線性規劃

19 凸函數與凹函數的圖形 凸的 凹的 作業研究 二版 Ch.12 非線性規劃

20 凸函數與凹函數的圖形 非凸非凹的 若 f 是凸的，則 –f 是凹的 作業研究 二版 Ch.12 非線性規劃

21 判斷凸函數與凹函數 /單變數 作業研究 二版 Ch.12 非線性規劃

22 判斷凸函數與凹函數 /多變數 作業研究 二版 Ch.12 非線性規劃

23 範例12.8 /單變數 作業研究 二版 Ch.12 非線性規劃

24 範例12.9 /多變數 作業研究 二版 Ch.12 非線性規劃

25 12.5 非線性規劃的類別 無限制式NLP 線性限制式NLP 二次規劃（quadratic programming）
12.5 非線性規劃的類別 無限制式NLP 僅有目標函數，而無任何限制式 線性限制式NLP 所有限制式都是線性的 二次規劃（quadratic programming） 線性限制式NLP的特例，當f(x)僅能是線性或二次 凸規劃（convex programming） 對min問題，f(x)是凸的；對max問題，f(x)是凹的 對於≦限制式，g(x)是凸的；對於≧限制式，g(x)是凹的；對於=限制式，g(x)是線性的 作業研究 二版 Ch.12 非線性規劃

26 12.5 非線性規劃的類別 非凸規劃（nonconvex programming） 可分離規劃（separable programming）
12.5 非線性規劃的類別 非凸規劃（nonconvex programming） 不是凸規劃的所有其他NLP 可分離規劃（separable programming） 當f(x)及所有g(x)均為可分離函數 可分離函數 幾何規劃（geometric programming） 若f(x)及所有g(x)均為正多項式，且為min問題 正多項式（posynomial）： 分數規劃（fractional programming） f(x)呈分數的形式 作業研究 二版 Ch.12 非線性規劃

27 12.6 單變數無限制式最佳化 求解方法 一維搜尋法 若f (x) 是一個簡單的函數，則可用11.3節的導數方式求得最佳解
12.6 單變數無限制式最佳化 求解方法 若f (x) 是一個簡單的函數，則可用11.3節的導數方式求得最佳解 若f (x) 較為複雜而無法用導數求解時，須使用一維搜尋法（one dimensional search method）。 一維搜尋法 二分搜尋法 黃金搜尋法 平分搜尋法 若 f (x) 是凸函數，則一維搜尋法所找到的解即為全域極小值，否則所找的解僅是局部極小值 作業研究 二版 Ch.12 非線性規劃

28 二分搜尋法 二分搜尋法（dichotomous search method） 步驟（對min問題）
作法：將包含最佳解的不確定區間分割為兩部分，然後捨棄較差的部分並繼續分割保留的部分，直到不確定區間達到所指定的容許範 步驟（對min問題） 作業研究 二版 Ch.12 非線性規劃

29 二分搜尋法的圖示 作業研究 二版 Ch.12 非線性規劃

30 範例12.10 /二分搜尋法的應用 考慮無限制式NLP： 選擇 、 作業研究 二版 Ch.12 非線性規劃

31 黃金分割法 黃金分割法（golden section method） 基本概念：如圖所示 作業研究 二版 Ch.12 非線性規劃

32 黃金分割法 作業研究 二版 Ch.12 非線性規劃

33 黃金分割法 作業研究 二版 Ch.12 非線性規劃

34 範例12.11 /黃金分割法的應用 考慮以下 NLP： 設定 作業研究 二版 Ch.12 非線性規劃

35 平分搜尋法 平分搜尋法（bisection search method） 基本概念 作法
若一個可微分的（differentiable）函數 f(x) 是凸函數或凹函數，則最佳解的必要且充分條件為： 作法 藉由判斷不確定區間中間點（midpoint）之導數的正負號，來決定捨棄左半部或右半部，直到不確定區間達到所選擇的容許範圍為止 作業研究 二版 Ch.12 非線性規劃

36 平分搜尋法 步驟（f(x) 是可微分的凸函數；對min問題）： 作業研究 二版 Ch.12 非線性規劃

37 範例12.12 /平分搜尋法的應用 考慮以下無限制式的NLP： 作業研究 二版 Ch.12 非線性規劃

38 12.7 多變數無限制式最佳化 最陡峭遞降法（steepest descent method）： 基本概念
12.7 多變數無限制式最佳化 最陡峭遞降法（steepest descent method）： 屬斜率搜尋法（gradient search method） 基本概念 沿著能減少 f(x) 值最快的方向移動 因為斜率向量 是指向該函數值增加最快的方向，所以沿著斜率向量的反方向 移動 至於要移動多少，則是一個單變數無限制式最佳化的問題 作業研究 二版 Ch.12 非線性規劃

39 最陡峭遞降法 作業研究 二版 Ch.12 非線性規劃

40 範例12.13 /最陡峭遞降法的應用 考慮多變數NLP： 其斜率向量： 選擇 作業研究 二版 Ch.12 非線性規劃

41 12.8 限制式最佳化的KKT條件 KKT條件（KKT condition） 標準形式： 限制式NLP之最佳解的必要條件
亦為凸規劃最佳解的充分條件 標準形式： 定理12.7：對於標準形式， 為最佳解的必要條件： 存在 使得 作業研究 二版 Ch.12 非線性規劃

42 範例12.14 /以KKT條件求解最佳解 考慮以下NLP： 轉換為標準形式如下： 作業研究 二版 Ch.12 非線性規劃

43 範例12.14 此NLP的KKT條件如下： 作業研究 二版 Ch.12 非線性規劃

44 範例12.14 作業研究 二版 Ch.12 非線性規劃

45 Example 4 Find the local extreme values of
Solution: Using Equation (2) yields 50 X = 0 and 8 X2 + 4 = 0 The corresponding stationary point is x* = (2/5, -1/2). Because f(x) is a quadratic, its Hessian matrix is constant. The determinants of the leading submatrices of H are H1 = 50 and H2 = 400, so f(x) is strictly convex, implying that x* is the global minimum.

46 Example 5 Find the local extreme values of the nonquadratic function
Solution: ▽f(x)=(9x12 –9, 2x2 +4) T =(0, 0) T So x1 = ±1 and x2= -2. Checking x = (1, -2), we have

47 which is positive definite since vT H(l, -2)v =18 v12 + 2v22 > 0 when v≠0. Thus (1, -2) yields a strong local minimum. Next, consider x = (-1, -2) with Hessian matrix Now we have vT H(-l, -2)v =-18 v12 + 2v22, which may be less than or equal to 0 when v≠0. Thus, the sufficient condition for (-1, -2) to be either a local minimum or a local maximum is not satisfied. Actually, the second necessary condition (b) in Theorem 1 for either a local minimum or a local maximum is not satisfied. Therefore, x = (1, -2) yields the only local extreme value of f.

48 Example 6 Find the extreme values of f(x) = -2x12+ 4x1 x2-4x22 + 4x1 + 4x2 +10. Solution: Setting the partial derivatives equal to zero leads to the linear system -4 x1 + 4 x2+ 4 = and 4 x1 -8 x2+ 4 = 0 which yields x* = (3, 2). The Hessian matrix is Evaluating the leading principal determinants of H, we find H1= -4 and H2 = 16. Thus, f(x) is strictly concave and x* is a global maximum.

49 The gradient of this function is
Nonquadratic Forms When the objective function is not quadratic (or linear), the Hessian matrix will depend on the values of the decision variables x. Suppose The gradient of this function is

50 For the second component of the gradient to be zero , we must have x2=
For the second component of the gradient to be zero , we must have x2= Taking this into account, the first component is zero only when x1= 1, so x* = (1,1) is the sole stationary point. It was previously shown (in Section 9.3) that the Hessian matrix H(x) at this point is positive definite, indicating that it is a local minimum. Because we have not shown that the function is everywhere convex, further arguments are necessary to characterize the point as a global minimum. Logically, f(x)≧0 because each of its two component terms is squared. The fact that f(1,1) = 0 implies that (1,1) is a global minimum.