最優(yōu)化理論與算法(第八章)

1、第八章第八章約束優(yōu)化最優(yōu)性條件約束優(yōu)化最優(yōu)性條件8.18.1約束優(yōu)化問題約束優(yōu)化問題一、一、問題基本形式問題基本形式min()fx（8.1）1()01..()0ieiecximstcximm??????????特別地，當(dāng)為二次函數(shù)，而約束是線性約束時(shí)，稱為二次規(guī)劃。()fx記，稱之為可行域（約束域）。??1()0(1)()0ieieXxcximcximm????????，，??1eEm????1eImm?????()()0iIxicxi

2、I???稱是在處的積極約束的指標(biāo)集。積極約束也稱有效約束，起作用約束或緊約束()EIx?xX?（activeconstraintsbindingconstraints）。應(yīng)該指出的是，如果是（1）的局部最優(yōu)解，且有某個(gè)，使得x?0iI?0()0icx??則將此約束去掉，仍是余下問題的局部最優(yōu)解。x?事實(shí)上，若不是去掉此約束后所得問題的局部極小點(diǎn)，則意味著，存在，使得x?0???x?，且，這里滿足新問題的全部約束。注意到當(dāng)充分小時(shí)，由xx

3、?????()()fxfx???x??的連續(xù)性，必有，由此知是原問題的可行解，但，這與是局0()icx0()0icx??x?()()fxfx???x?部極小點(diǎn)矛盾。因此如果有某種方式，可以知道在最優(yōu)解處的積極約束指標(biāo)集，則問題x?()()AxEIx????可轉(zhuǎn)化為等式的約束問題：min()fx（8.2）..()0istcx?()iAx??一般地，這個(gè)問題較原問題（8.1）要簡單，但遺憾的是，我們無法預(yù)先知道。()Ax?在上兩式的左右兩端

4、除以，然后令趨于無窮，即得滿足k?kd()0Tidcx???iE?()0Tidcx???()iIx??因而，由的任意性，即知，證畢。()dLFDxX?d()()SFDxXLFDxX?二、一階最優(yōu)性條件二、一階最優(yōu)性條件引理引理8.58.5設(shè)是問題（8.1）的局部極小點(diǎn)，若和都在處可微，xX??()fx()icx(1)im??x?則必有，。()0Tdfx??()dSFDxX???證明：證明：對(duì)任何，存在序列和，使得()dSFDxX?(12

5、)kdk??0(12)kk????，且和。kkxdX????kdd?0k??由，而且是局部極小點(diǎn)，故對(duì)充分大的有：kkxdx?????x?k()()()()()Tkkkkkkfxfxdfxdfxod?????????????由上式可知，，引理于是證畢。()0Tdfx??引理8.5表明：在極小點(diǎn)處，所有的序列可行方向都不是下降方向。引理引理8.68.6（Farkas引理）線性方程組和不等式組001(8.6)01(8.7)0(8.8)TiT