1. 非線性規(guī)劃

1.1 示例以及定義

如果目標函數(shù)或約束條件中包含非線性函數(shù)贬养，就稱這種規(guī)劃問題為非線性規(guī)劃問 題昼捍。一般說來识虚，解非線性規(guī)劃要比解線性規(guī)劃問題困難得多。而且妒茬，也不象線性規(guī)劃有單純形法這一通用方法担锤，非線性規(guī)劃目前還沒有適于各種問題的一般算法，各個方法都有自己特定的適用范圍乍钻。

1.2 線性規(guī)劃與非線性規(guī)劃的區(qū)別

如果線性規(guī)劃的優(yōu)解存在肛循，其優(yōu)解只能在其可行域的邊界上達到（特別是可行 域的頂點上達到）；而非線性規(guī)劃的優(yōu)解（如果優(yōu)解存在）則可能在其可行域的任意一點達到团赁。

1.3非線性規(guī)劃的Matlab 解法

Matlab 中非線性規(guī)劃的數(shù)學模型寫成以下形式

其中是非線性函數(shù)
Matlab 中的命令是
X=FMINCON(FUN,X0,A,B,Aeq,Beq,LB,UB,NONLCON,OPTIONS)
NONLCON 是用 M 文件定義的非線性向量函數(shù)
給出例子如下

function f=fun1(x); %定義目標函數(shù)
f=sum(x.^2)+8;

function [g,h]=fun2(x);
g=[-x(1)^2+x(2)-x(3)^2
x(1)+x(2)^2+x(3)^3-20];  %非線性不等式約束
h=[-x(1)-x(2)^2+2
x(2)+2*x(3)^2-3]; %非線性等式約束

求解程序：

[x,y]=fmincon('fun1',rand(3,1),[],[],[],[],zeros(3,1),[],'fun2')
>>
x =

    0.5522
    1.2033
    0.9478


y =

   10.6511

2.無約束問題

2.1 一維搜索方法

當用迭代法求函數(shù)的極小點時育拨，常常用到一維搜索，即沿某一已知方向求目標函數(shù)的極小點欢摄。一維搜索的方法很多熬丧，常用的有：

1. 試探法（“成功—失敗”，斐波那契法怀挠，0.618 法等）
2. 插值法（拋物線插值法析蝴，三次插值法等）
3. 微積分中的求根法（切線法，二分法等）

下面有兩個通過不斷地縮短區(qū)間[a,b]的長度绿淋，來搜索得到近似優(yōu)解的兩個方法闷畸。

2.1.1 斐波那契法

2.1.2 0.618法

2.2 無約束極值問題的解法

迭代法大體上分為兩點：一是用到函數(shù)的一階導數(shù)或二階導數(shù)， 稱為解析法吞滞。另一是僅用到函數(shù)值佑菩，稱為直接法。

2.3.1 解析法

1. 梯度法
   
   
   
   
   其中為步長裁赠，通過求在這點去最小函數(shù)值時的
   給出一個例子如下：
   【例】
   用最速下降法求解
   要求初始點為

function [f,df] = detaf(x);
f = x(1)^2+25*x(2)^2;
df = [2*x(1)
    50*x(2)];%函數(shù)的梯度

clc
x = [2,2];
[f0,g] = detaf(x);
while norm(g)>0.000001
    p = -g/norm(g);
    t = 1.0;
    f = detaf(x+t*p);
    while f>f0   %尋找讓函數(shù)值最小的t
        t = t/2;
        f = detaf(x+t*p);
    end
    x = x+t*p;
    [f0,g] = detaf(x);
end
x,f0

2. 牛頓法
   考慮目標函數(shù)在點的二次逼近
   
   假定海塞矩陣正定：
   
   

2.4 matlab求解無約束極值

3. 約束極值問題

帶有約束條件的極值問題稱為約束極值問題殿漠，也叫規(guī)劃問題。 求解約束極值問題要比求解無約束極值問題困難得多佩捞。為了簡化其優(yōu)化工作绞幌，可采用以下方法：將約束問題化為無約束問題；將非線性規(guī)劃問題化為線性規(guī)劃問題一忱，以及能將復雜問題變換為較簡單問題的其它方法莲蜘。 庫恩—塔克條件是非線性規(guī)劃領(lǐng)域中重要的理論成果之一，是確定某點為優(yōu)點的必要條件帘营，但一般說它并不是充分條件（對于凸規(guī)劃票渠，它既是優(yōu)點存在的必要條件， 同時也是充分條件）芬迄。

3.1 二次規(guī)劃

若某非線性規(guī)劃的目標函數(shù)為自變量 x的二次函數(shù)庄新，約束條件又全是線性的，就稱 這種規(guī)劃為二次規(guī)劃薯鼠。


【例】求解如下的例子

【注意】要提出

h=[4,-4;-4,8]; 
f=[-6;-3]; 
a=[1,1;4,1]; 
b=[3;9]; 
[x,value]=quadprog(h,f,a,b,[],[],zeros(2,1)) 
>>
x =

    1.9500
    1.0500


value =

  -11.0250

3.2 罰函數(shù)法

利用罰函數(shù)法择诈，可將非線性規(guī)劃問題的求解，轉(zhuǎn)化為求解一系列無約束極值問題出皇， 因而也稱這種方法為序列無約束小化技術(shù)
罰函數(shù)法求解非線性規(guī)劃問題的思想是羞芍，利用問題中的約束函數(shù)作出適當?shù)牧P函數(shù)，由此構(gòu)造出帶參數(shù)的增廣目標函數(shù)郊艘，把問題轉(zhuǎn)化為無約束非線性規(guī)劃問題荷科。主要有 兩種形式，一種叫外罰函數(shù)法纱注，另一種叫內(nèi)罰函數(shù)法畏浆，下面介紹外罰函數(shù)法。

取一個充分大的數(shù)M>0狞贱，構(gòu)造函數(shù)如下：

直觀上可以理解為若則給這個目標函數(shù)一個很大的懲罰刻获，而如果則對該目標函數(shù)無影響.
或者寫成：

【例】

function g=test1(x);
M=50000;
f=x(1)^2+x(2)^2+8;
g=f-M*min(x(1),0)-M*min(x(2),0)-M*min(x(1)^2-x(2),0)+M*abs(-x(1)-x(2)^2+2);

或者寫成矩陣形式：

function g=test2(x);
M=50000;
f=x(1)^2+x(2)^2+8;
g=f-M*sum(min([x';zeros(1,2)]))-M*min(x(1)^2-x(2),0)+M*abs(-x(1)-x(2)^2+2);

其中的min([x';zeros(1,2)])表示都大于0
再在命令行中輸入

[x,y]=fminunc('test1',rand(2,1)) 
>>
x =

    1.3118
    0.8296


y =

   10.4090

[x,y] = fminunc('test2',rand(2,1))
>>
x =

    1.1810
    0.9050


y =

   10.2140

可以看出兩次的效果略有偏差氧枣。但是我們不滿足于此沐兵，由于問題的規(guī)模較小，嘗試使用fmincon求得精確得最優(yōu)解

function f = fun1(x)
f = sum(x.^2)+8;

function [g,h] = fun2(x)
g = x(1)^2-x(2); %非線性的不等式約束
h = -x(1)-x(2)^2 + 2 %非線性等式約束

[x,y] = fmincon('fun1',rand(2,1),[],[],[],[],zeros(3,1),[],'fun2',options)
>>
x =

    0.5000
    1.2247


y =

    9.7500

可以看出罰函數(shù)法雖然收斂速度快便监，但是精確度不是很高扎谎。當問題規(guī)模較大，不好求解時烧董，可以考慮使用毁靶。

3.3 使用梯度法求解約束線性規(guī)劃

其中約束條件為：

當使用梯度求解上述問題時，效率更高并且結(jié)果更準確解藻。 題目中目標函數(shù)的梯度為（對分別求偏導數(shù)）：

1. 編寫fun10定義目標函數(shù)和梯度函數(shù)：

function [f,df]=fun10(x);
f=exp(x(1))*(4*x(1)^2+2*x(2)^2+4*x(1)*x(2)+2*x(2)+1);
df=[exp(x(1))*(4*x(1)^2+2*x(2)^2+4*x(1)*x(2)+8*x(1)+6*x(2)+1);exp(x(1))*(4*x(2)+4*x(1)+2)];

2. 編寫fun11定義約束條件老充，以及約束條件的梯度函數(shù)

function [c,ceq,dc,dceq]=fun11(x);
c=[x(1)*x(2)-x(1)-x(2)+1.5;-x(1)*x(2)-10];
dc=[x(2)-1,-x(2);x(1)-1,-x(1)];
ceq=[];dceq=[];

3. 調(diào)用fincon()

options=optimset('GradObj','on','GradConstr','on');%采用梯度
[x,y]=fmincon(@fun10,rand(2,1),[],[],[],[],[],[],@fun11,options)
>>
x =

   -9.5473
    1.0474


y =

    0.0236

3.5 optimtool工具箱的使用

在命令行中輸入optimtool可以打開圖形界面

對于上一個問題，只要選擇方法（solver）后螟左，在相應位置輸入@fun10啡浊，@fun11，點擊start就可以