數(shù)模往屆2013無約束

4.

無約束規(guī)劃無約束規(guī)劃建?！裏o約束規(guī)劃模型無約束規(guī)劃的示意圖無約束規(guī)劃的性質(zhì)

無約束規(guī)劃重要算法用MATLAB解無約束規(guī)劃引例1：某城市要選定一個供應(yīng)中心(供電、供水、公天然氣、網(wǎng)絡(luò)接入等)的位置，該中心向城市中由固定位置的m個用戶提供服務(wù)。問如何確定這個中心的位置才是最合理的？解

設(shè)用戶位置為(ai,bi)(i=1,2,...,m)已知，而供應(yīng)中心的位置是(x1,x2)；假設(shè)運輸線路不受道路影響，只考慮直線距離，則可建立求總距離最短的數(shù)學(xué)模型為：mi

1

a

bx

x

min

f

(

x1

,

x2

)

2

21

i

2

i其中：c——運價(元/噸公里)；wi——第i個用戶的需求量.w

x

a

x

b

mi

1min

f

(

x1

,

x2

)

c2

2i

1

i

2

i若進一步考慮各單位的用量wi不同，而運價c按距離計算，則可建立求總總費用最小的數(shù)學(xué)模型為：“定位問題”——廠址選擇等即要求均方誤差最小——最小二乘問題，包括線性最小二乘和非線性最小二乘問題，在數(shù)學(xué)建模中有非常重要的應(yīng)用。mnj

121

f

(

x

,,

x

)“最小二乘問題”——解方程組引例2：在某些實際問題中，往往要求決策變量x1,x2,...,xn滿足(或近似滿足)某些平衡條件，它表現(xiàn)為要求x1,x2,...,xn滿足方程組f

j

(

x1

,,

xn

)

0,

j

1,2,,

p可轉(zhuǎn)化為求解問題：min無約束規(guī)劃模型標(biāo)準(zhǔn)形式：X

Rnmin

f

X

(

其中

f

:

R

n

R

)max

f

X

min

f

X

XRn

XRn轉(zhuǎn)化：x1x2f

(

x1

x2

)O1xx2等高線03510XX1X

2f

(

X

0

)

f

(

X1

)

f

(

X

2

)無約束規(guī)劃的示意圖多局部極小f

0

.

298f

0f

0

.

298唯一極小(全局極小)22

1

221

1

21

2f

(xx

3x

xx

)

2x

2x

x

2

2

f

2

fx

xx1x2n

2x

xn

1x

x2

n1

n

2

f

x

x

2

f

2

f

2

f

22

2

f

2

f

2

fx1

221x2

f

(

X

)

H

(

X

)

nx無約束規(guī)劃的性質(zhì)梯度x

x

xf

(

X

)

T

f

(

X

)

f

(

X

)f

(

X

)

1

2

n

,

,,

列向量梯度的特點：1)函數(shù)f(X)在X處增長最快的方向，負(fù)梯度方向是函數(shù)f(X)在X處下降最快的方向；2)梯度的模是函數(shù)最快的變化率;3)梯度為零是駐點，極值點是駐點，駐點不一定是極值點。

方、對x

x

稱矩陣海森(Hessian)矩陣無約束規(guī)劃的性質(zhì)梯度為0向量的點可能是局部最優(yōu)點，需要用海森矩陣類型進一步判定；凸函數(shù)的駐點必是全局最優(yōu)點；補充1)

f(X)是凸函數(shù)對任意定義域D中的元素X、Y和任意的數(shù)0≤a≤1，有：f(aX＋(1－a)Y)

≤af(X)+

(1－a)

f(Y)補充2)

對稱矩陣的分類類別A正定A半正定A負(fù)定半負(fù)定不定定義特征值>0特征值≥0(有0)特征值<0特征值≤0(有0)其它判別方法主子式都>0|A|=0;主子式≥0－A正定－A半正定無約束規(guī)劃的基本算法基本思路：先求駐點，在判定是否是極值點；(初始值),尋求使函數(shù)值下降一個方向,沿此方向找到一個更好的估計值,這樣往復(fù)迭代,直到某一點不能找到下降方向則終止算法.迭代算法的基本框架：選定初始點X0，令k＝0；在Xk處選定下降方向Sk(若找不到則終止算法);(3)

從Xk出發(fā)沿Sk一維搜索,找到Xk+1=Xk

+λkSk

,使得f(Xk+1)<f(Xk)；(4)

從k=k+1,轉(zhuǎn)(2).X

kX

k

1X

k

2SS

k基本方法——迭代算法:先給定極小點的估計值Sk

2kS

k無約束規(guī)劃的基本算法一維搜索基本原則：1)最優(yōu)原則：2)

可接受點原則：

Sk

)kk

kk

kS

)

min

f

(

X

:

f

(

X

0S

k

)

f

(

X

k

)kk

k

:

f

(

X

一維搜索方法：0.618法、插值法等下降方向：與梯度點乘為負(fù)值的方向f

(

X

k

)T

Sk

0

f

(

X

S

)

f

(

X

)

f

(

X

)T

S

o(

S

)

0無約束規(guī)劃的基本算法下降方向選擇方法——算法分類1.

最速下降法——梯度法Sk

f

(

X

k

)2.

共軛梯度法(包含多種方法)——梯度法的修正3.

牛頓法Sk

2

f

(

X

k

)1

f

(

X

k

)f

(

X

S

)

f

(

X

)

f

(

X

)T

S

ST

2

f

(

X

)S

o(

S

2

)

0牛頓法特點：二次函數(shù)1次收斂；單步迭代計算量大，且要求海森矩陣可逆。無約束規(guī)劃的基本算法擬牛頓法為克服牛頓法的缺點，同時保持較快收斂速度的優(yōu)點，利用第k

步和第k+1

步得到的X

k

，X

k

1

，f

(X

k

)，f

(X

k

1

)，構(gòu)造一個正定矩陣H

k

1

近似代替(2

f

(X

k

))1

，將牛頓方向改為：S

k

1

H

k

1f

(

xk

1

)從而得到下降方向.擬牛頓法特點：較梯度法收斂速度快速，較牛頓法穩(wěn)定且計算量小。信賴域算法——對大型問題穩(wěn)定性好，有成功的應(yīng)用無約束規(guī)劃的基本算法兩個著名的擬牛頓迭代公式:kH

k

1

H

k

X

k

(gk

)T

H

k

H

k

gk

(X

k

)T(gk

)T

X

k(gk

)T

xk

(gk

)T

X(gk

)T

H

k

gk

xk

(X

k

)T

1

H

H

(gk

)T

X

k

(gk

)T

H

k

gkX

k

(X

k

)T

H

k

gk

(gk

)T

H

kk

1

k其中：X

k

X

k

1

X

kgk

f

(

X

k

1

)

f

(

X

k

)

BFGS

DFPSk

1

H

k

1f

(

X

k

1

)Matlab求解無約束規(guī)劃問題類

型模

型基本函數(shù)名一元函數(shù)極小Min

F(x)s.t.x1<x<x2x=fminbnd(‘F’,x1,x2)多元無約束極小Min

F(X)X=fminunc(‘F’,X0)X=fminsearch(‘F’,X0)完整的調(diào)用格式：[X,FVAL,EXITFLAG,OUTPUT]

=fminbnd(FUN,x1,x2,OPTIONS,P1,P2,...)[X,FVAL,EXITFLAG,OUTPUT,GRAD,HESSIAN]

=fminunc(FUN,X0,OPTIONS,P1,P2,...)[X,FVAL,EXITFLAG,OUTPUT]

=fminsearch

(FUN,

X0,

OPTIONS,

P1,P2,...)輸出變量含義變量描

述x由優(yōu)化函數(shù)求得的值.若exitflag>0,則x為解;否則,x不是最終解,它只是迭代終止時優(yōu)化過程的值fval解x處的目標(biāo)函數(shù)值exitflag描述退出條件:exitflag>0,表目標(biāo)函數(shù)收斂于解x處exitflag=0,表已達到函數(shù)計算或迭代的最大次數(shù)exitflag<0,表目標(biāo)函數(shù)不收斂output包含優(yōu)化結(jié)果信息的輸出結(jié)構(gòu).Iterations:

迭代次數(shù)Algorithm:所采用的算法FuncCount:計算函數(shù)值次數(shù)AlgorithmsLarge-Scale

Optimization——

By

default

fminuncchooses

the

large-scale

algorithm

if

the

usersupplies

the

gradient

in

fun

(and

GradObj

is

'on'in

options).

This

algorithm

is

a

subspace

trustregion

method

and

is

based

on

the

interior-reflective

Newton

method.Medium-Scale

Optimization——fminunc

withoptions.LargeScale

set

to

'off'

uses

the

BFGSQuasi-Newton

method

with

a

mixed

quadratic

andcubic

line

search

procedure.

This

quasi-Newtonmethod

uses

the

BFGS

formula

for

updating

theapproximation

of

the

Hessian

matrix.

The

DFPformula,

which

approximates

the

inverse

Hessianmatrix is

selected

by

setting

optionsDisplay:顯示水平.取值為’off’時,不顯示輸出;取值為’iter’時,顯示每次迭代的信息;取值為’final’時,顯示最終結(jié)果.默認(rèn)值為’final’.MaxFunEvals:允許進行函數(shù)計算的最大次數(shù),取值為正整數(shù).MaxIter:

允許進行迭代的最大次數(shù),取值為正整數(shù).控制參數(shù)options可以通過函數(shù)optimset創(chuàng)建或修改.格式為options=optimset(‘param1’,value1,’param2’,value2,...)創(chuàng)建一個名稱為options的優(yōu)化選項參數(shù),其中指定的參數(shù)具有指定值,所有未指定的參數(shù)取默認(rèn)值.例：opts=optimset(‘Display’,’iter’,’TolFun’,1e-8)該語句創(chuàng)建一個稱為opts的優(yōu)化選項結(jié)構(gòu),其中顯示參數(shù)設(shè)為’iter’,TolFun參數(shù)設(shè)為1e-8.options中常用的幾個參數(shù)的名稱、含義、取值如下:用Matlab解無約束優(yōu)化問題1.一元函數(shù)無約束優(yōu)化問題:常用格式如下：min

f（x）x1

x

x2x=

fminbnd(fun,x1,x2)x=

fminbnd

(fun,x1,x2

,

options)(3)[x，fval]=

fminbnd(...)(4)[x，fval，exitflag]=

fminbnd(...)(5)[x，fval，exitflag，output]=

fminbnd(...)函數(shù)fminbnd的算法基于0.618算法和二次插值法，它要求目標(biāo)函數(shù)必須是連續(xù)函數(shù)，并可能只給出局部最優(yōu)解。例

1

求 f

=

2

e

x

sin

x

在

0<x<8

中的最小值與最大值主程序為test.m:f='2*exp(-x).*sin(x)';f1='-2*exp(-x).*sin(x)';fplot(f,[0,8],'*-');

%作圖語句hold

on,fplot(f1,[0,8],

'^-');

%作圖語句

[xmin,ymin]=fminbnd

(f,0,8)[xmax,ymax]=fminbnd

(f1,

0,8)運行結(jié)果：xmin

=

3.9270xmax

=

0.7854ymin

=

-0.0279ymax

=

0.64482、多元函數(shù)無約束優(yōu)化問題標(biāo)準(zhǔn)型為：min

F(X)命令格式為:x=fminunc(fun,X0

)；或x=fminsearch(fun,X0

)x=

fminunc(fun,X0

,

options)；或x=fminsearch(fun,X0

,options)(3)[x,fval]=fminunc(...)；或[x,fval]=fminsearch(...)(4)[x,fval,exitflag]=fminunc(...)；或[x,fval,exitflag]=

fminsearch(5)[x,fval,exitflag,output]=

fminunc(...)；或[x,fval,exitflag,output]=fminsearch(...)fminsearch是用單純形法尋優(yōu).fminunc的算法見以下幾點說明：fminunc為無約束優(yōu)化提供了大型優(yōu)化和中型優(yōu)化算法。由

options中的參數(shù)LargeScale控制：LargeScale=’on’(默認(rèn)值),使用大型算法(信賴域算法)LargeScale=’off’(默認(rèn)值),使用中型算法fminunc為中型優(yōu)化算法的搜索方向提供了4種算法，由

options中的參數(shù)HessUpdate控制a：HessUpdate=’bfgs’(默認(rèn)值),擬牛頓法的BFGS公式；HessUpdate=’dfp’，擬牛頓法的DFP公式；

HessUpdate=’steepdesc’，最速下降法fminunc為中型優(yōu)化算法的步長一維搜索提供了兩種算法，由options中參數(shù)LineSearchType控制：

LineSearchType=’quadcubic’(缺省值)混合的二次和三次多項式插值；LineSearchType=’cubicpoly’，三次多項式插使用fminunc和fminsearch可能會得到局部最優(yōu)解.例3

minf(x)=(4x1

+2x2

+4x1x2+2x2+1)*exp(x1)2

21、編寫M-文件fun1.m:function

f=fun1

(x)f

=

exp(x(1))*(4*x(1)^2+2*x(2)^2+4*x(1)*x(2)+2*x(2)+1);2、輸入M文件test.m如下:x0

=[-1,

1];x=fminunc(‘fun1’,x0);y=fun1(x)3、運行結(jié)果:-1.0000x=

0.5000y

=1.3029e-10例4 Rosenbrock函數(shù)

f(x1，x2)=100(x2-x12)2+(1-x1)2

的最優(yōu)解(極小)為x*=(1,1)，極小值為f*=0.試用不同算法(搜索方向和步長搜索)求數(shù)值最優(yōu)解.

初值選為x0=(-1.2

,

2).為獲得直觀認(rèn)識,先畫出Rosenbrock函數(shù)的三維圖形,輸入以下命令:[x,y]=meshgrid(-2:0.1:2,-1:0.1:3);z=100*(y-x.^2).^2+(1-x).^2;mesh(x,y,z)畫出Rosenbrock

函數(shù)的等高線圖,輸入命令：contour(x,y,z,20)hold

onplot(-1.2,2,'

o

');text(-1.2,2,'start

point')plot(1,1,'o')text(1,1,'solution')3.用fminsearch函數(shù)求解輸入命令:f='100*(x(2)-x(1)^2)^2+(1-x(1))^2';[x,fval,exitflag,output]=fminsearch(f,

[-1.2

2])運行結(jié)果:x

=1.0000

1.0000fval

=1.9151e-010exitflag

=

1output

=iterations:

108funcCount:

202algorithm:

'Nelder-Mead

simplex

direct

search'使用fminunc函數(shù)見Matlab演示！問題：增加生產(chǎn)、發(fā)展經(jīng)濟所依靠的主要因素有增加投資、增加勞動力以及技術(shù)革新等，試建立模型討論究國民經(jīng)濟產(chǎn)值與這些因素的數(shù)量關(guān)系。簡化：由于技術(shù)水平不像資金、勞動力那樣容易定量化,初步認(rèn)為技術(shù)水平不變,只討論產(chǎn)值和資金、勞動力之間的關(guān)系(在技術(shù)發(fā)展不快的時期,該簡化是有意義的.)分析及建模：用Q,K,L分別表示產(chǎn)值、資金和勞動力，該模型希望建立合適的函數(shù)Q(K,L)來描述三個量間的關(guān)系。假設(shè)1)產(chǎn)值依賴于每個勞動力的投資強度，并且與勞動力數(shù)示例:經(jīng)濟增長模型——最小二乘問題量成正比，即有(G表示某一函數(shù))：Q(

K

,

L)

G(

y)L,

y

LK假設(shè)2)

產(chǎn)值隨資金、勞動力的增加而增加，但增長得越來越慢.

據(jù)此選擇G函數(shù)的形式為G(

y)

ayb

,

a

0,

0

b

1簡化得:Q(

K

,

L)

aK

b

L1b——這是經(jīng)濟學(xué)中著名的柯布-道格拉斯(Cobb-Douglas)生產(chǎn)函數(shù)，其更一般的形式為:Q(

K

,

L)

aK

b

Lc

,

0

b,

c

1其中a,b,c由統(tǒng)計數(shù)據(jù)確定——最小二乘問題!現(xiàn)有統(tǒng)計數(shù)據(jù)(Qi,Ki,Li),i＝1,2,...,n.代入上式分別可得n個方程:b

ci

i

i

iQ

aK

L

0f

(a,

b,

c)i

1,2,,

n由于統(tǒng)計特性，一般來說，這些等式不可能完全成立，記:b

ci

i

i

iQ

aK

L最小二乘問題就是使得該誤差項盡可能小，于是極小化：b

ci

i

iQ

aK

L

ni

1i2ni

12

mini

1,2,,

n這是非線性最小二乘問題！ni

1Q(

K

,

L)

aK

b

Lc

,

0

b,

c

1對該式兩端取對數(shù)，可得ln

Q

ln

a

b

ln

K

c

ln

L

a

b

ln

K

c

ln

L這樣對統(tǒng)計數(shù)據(jù)(Qi,Ki,Li),i＝1,2,...,n.代入上式分別可得n個線性方程:fi

(a,

b,

c)

lnQi

a

b

ln

Ki

c

ln

Li

0i

1,2,,

n使得以上等式誤差項盡可能小，于是極小化：i

i

i2

c

ln

Lln

Q

a

b

ln

K

min這樣就轉(zhuǎn)化為線性最小二乘問題！——這更容易求解模型驗證美國馬薩諸賽州1890－1926年統(tǒng)計數(shù)據(jù)(以1899年歸1)tQKLtQKLtQKL18900.720.950.7819031.301.221.2219162.093.611.8618910.780.960.8119041.301.271.1719171.964.101.9318920.840.990.8519051.421.371.3019182.204.361.9618930.730.960.7719061.501.441.3919192.124.771.9518940.720.930.7219071.521.531.4719202.164.751.9018950.830.860.8419081.461.571.3119212.084.541