sun非線性規(guī)劃一維搜索教程課件

1、非線性規(guī)劃Nonlinear ProgrammingLudong University第1頁，共23頁。非線性規(guī)劃求解方法分類1一、無約束情形1一維最優(yōu)化 斐波那契（Fibonacci）法 黃金分割法（0.618法） 牛頓法（切線法） 中點法 插值法2022/8/202Ludong University第2頁，共23頁。非線性規(guī)劃求解方法分類2(i)采用導(dǎo)數(shù)：(a)梯度法(最速下降法)(b)共軛梯度法(c) 牛頓法(d)變尺度法(ii)不采用導(dǎo)數(shù)：(a)直接法(模式搜索法)(b)可變多面體法(c)鮑威爾法(Powell法)(d)隨機(jī)搜索法2多維最優(yōu)化2022/8/203Ludong Unive

2、rsity第3頁，共23頁。非線性規(guī)劃求解方法分類3二、有約束情形(多維情形） (i)線性逼近法用線性規(guī)劃逐步逼近非線性規(guī)劃的方法. (ii)懲罰函數(shù)法（制約函數(shù)法） (iii)可行方向法（簡約梯度法）非線性規(guī)劃的求解方法很多，上面列出的僅是一些常用的方法。后面將簡單介紹幾個最基本解法的思路和步驟。2022/8/204Ludong University第4頁，共23頁。第四章 非線性規(guī)劃基本概念凸函數(shù)和凸規(guī)劃一維搜索方法無約束最優(yōu)化方法約束最優(yōu)化方法0.618法（黃金分割法）Newton 法2022/8/205Ludong University第5頁，共23頁。一維搜索方法 一維搜索問題又稱為

3、線性搜索問題，它是指目標(biāo)函數(shù)為單變量函數(shù)的非線性規(guī)劃問題，它是多變量函數(shù)最優(yōu)化的基礎(chǔ)。 按照求解問題的不同原則，算法分為兩類：精確一維搜索及非精確一維搜索。2022/8/206Ludong University第6頁，共23頁。一維搜索方法一元函數(shù)求極小及線性搜索均為一維搜索。常用于求：縮小區(qū)間的精確一維搜索1.0.618法考慮問題(P)：2022/8/207Ludong University第7頁，共23頁。圖4-2-1 2022/8/208Ludong University第8頁，共23頁。圖4-2-2 2022/8/209Ludong University第9頁，共23頁。圖4-2-3

4、0 a a2 t* t1 t2 b t y2022/8/2010Ludong University第10頁，共23頁。圖4-2-3 0 a t3 t* t1 t2 b t y2022/8/2011Ludong University第11頁，共23頁。圖4-2-4 at1 t2bt2要求插入點 的位置相對于區(qū)間a,b兩端點具有對稱性。2022/8/2012Ludong University第12頁，共23頁。2.0.618法算法步驟2022/8/2013Ludong University第13頁，共23頁。2.Example Iterationabx1x2f(x1)f(x2)1131.76392

5、.236114.361714.222021.763932.23612.527914.222014.426331.76392.52792.05572.236114.191014.222041.76392.23611.94432.055714.219114.191051.94432.23612.05572.124614.191014.192661.94432.12462.01322.055714.197014.19102022/8/2014Ludong University第14頁，共23頁。二、牛頓法（切線法）一維搜索函數(shù)，假定一給出極小點的一個較好的近似點，因為一個連續(xù)可微的函數(shù)在極小點附近與

6、一個二次函數(shù)很接近，因此，在 點附近用一個二次函數(shù) 逼近。2022/8/2015Ludong University第15頁，共23頁。求二次函數(shù) 的極小點作為極小點的新近似點即依次繼續(xù)下去，可得牛頓法迭代公式：2022/8/2016Ludong University第16頁，共23頁。牛頓法的計算步驟：給定初始點 ，控制誤差 ，并令k=1。1）計算2）求3)若則求得近似解，停止計算，否則作4。4）令轉(zhuǎn)1。2022/8/2017Ludong University第17頁，共23頁。優(yōu)點：收斂速度快。缺點：每一點都要進(jìn)行二階導(dǎo)數(shù)，工作量大；要求初始點離極小點不太遠(yuǎn)，否則有可能使極小化發(fā)散或收斂到非

7、極小點。2022/8/2018Ludong University第18頁，共23頁。3.Newtons MethodGolden Section SearchFor any xk, we need to evaluate f(xk)Newtons Method:For any xk, assume we can evaluate f(xk), f (xk), and f (xk).The motivation of Newtons Method is to use a Taylor quadratic function g(x) to approximate f(x) at point xk.

8、g(x) = f(xk) + f (xk)(xxk)+0.5f (xk)(xxk)2.We haveg(xk) = f(xk)g(x) = f (xk)+f (xk)(xxk), and g(xk) = f (xk)g(x) = f (xk)At xk, g(x) and f(x) have the same objective function value, derivative, and second derivative.2022/8/2019Ludong University第19頁，共23頁。3.Newtons MethodIf we want to minimize g(x), w

9、e should find a point xk+1 such that g(xk+1) = f (xk)+f (xk)(xk+1xk)=0,i.e. xk+1= xk f (xk) / f (xk).Newtons Method Start from an initial point x0, and calculate xk+1 from xk until the series converges.Stop Conditions 2022/8/2020Ludong University第20頁，共23頁。3.Example Iteration No.xf(x)f(x)f(x)1214.2-0

10、.253.2522.07692314.190028-0.013722.90209832.0816514.189996-4.7E-052.88237442.08166614.189996-5.4E-102.88230752.08166614.18999602.882307xk+1= xk f (xk) / f (xk)2022/8/2021Ludong University第21頁，共23頁。黃金分割把一條線段分割為兩部分，使其中一部分與全長之比等于另一部分與這部分之比。其比值是一個無理數(shù)，取其前三位數(shù)字的近似值是0.618。由于按此比例設(shè)計的造型十分美麗，因此稱為黃金分割，也稱為中外比。這是一個十分有趣的數(shù)字，我們以0.618來近似，通過簡單的計算就可以發(fā)現(xiàn)： 1/0.618=1.618 (1-0.618)/0.6