高等數(shù)學(xué)規(guī)劃預(yù)備知識

1、第1章 預(yù)備知識§1.1 基本概念與術(shù)語 數(shù)學(xué)規(guī)劃問題舉例例1 食譜（配食）問題l 假設(shè)市場上有n種不同的食物，第j種食物每個單位的銷售價為。l 人體在正常生命活動過程中需要m種基本的營養(yǎng)成分。為了保證人體的健康，一個人每天至少需要攝入第i種營養(yǎng)成分個單位。l 第j種食物的每個單位包含第i種營養(yǎng)成分個單位。食譜（配食）問題就是要求在滿足人體基本營養(yǎng)需求的前提下，尋找最經(jīng)濟(jì)的配食方案（食譜）。建立食譜的數(shù)學(xué)模型引入決策變量 ：食譜中第i種食物的單位數(shù)量s.t. 例2 選址與運(yùn)輸問題l 假設(shè)某大型建筑公司有m個項(xiàng)目在不同的地點(diǎn)同時開工建設(shè).記工地的位置分別為.l 第i個工地對某種建筑材料

2、的日用量是已知的（比如水泥的日用量（單位：t）為）l 該公司準(zhǔn)備分別在和兩個地點(diǎn)建造臨時料場，并且保證臨時料場對材料的日儲量（單位：t）分別為和如何為該公司確定臨時料場的位置，并且制訂每天的材料供應(yīng)計(jì)劃，使建筑材料的總體運(yùn)輸負(fù)擔(dān)最?。拷⑦x址與運(yùn)輸問題的數(shù)學(xué)模型引入決策變量：位置變量,從臨時料場向各工地運(yùn)送的材料數(shù)量.s.t. 例3 生產(chǎn)計(jì)劃問題l 某企業(yè)向客戶提供一種機(jī)器，第1季度末需要交貨臺，第2季度末需要交貨臺，第3季度末需要交貨臺l 該企業(yè)最大生產(chǎn)能力是每季度生產(chǎn)b 臺.l 若用x表示該企業(yè)在某季度生產(chǎn)的機(jī)器臺數(shù)，則生產(chǎn)費(fèi)用（單位：元）可以用函數(shù)來描述.l 企業(yè)需為每臺機(jī)器在每個季度多

3、支付p元的存儲費(fèi)l 假設(shè)在第一個季度開始時無存貨，不允許缺貨.如何制訂生產(chǎn)計(jì)劃，確定在每個季度應(yīng)該生產(chǎn)多少臺機(jī)器，才能既履行交貨合同，又使企業(yè)總體費(fèi)用最少？建立生產(chǎn)計(jì)劃的數(shù)學(xué)模型決策變量：用表示企業(yè)在第i個季度生產(chǎn)的機(jī)器數(shù)量合同規(guī)定的總數(shù)量：每個季度生產(chǎn)數(shù)量要求：每個季度生產(chǎn)數(shù)量不大于最大生產(chǎn)能力b ，不少于該季度末的交貨量與該季度初的庫存量之差.第j個季度初庫存量： （=0）變量隱含要求：，并且取整數(shù)企業(yè)總費(fèi)用：所有季度生產(chǎn)與存儲費(fèi)用之和s.t. (Z表示所有整數(shù)的集合) 數(shù)學(xué)規(guī)劃問題的模型與分類l 形成一個最優(yōu)化問題的數(shù)學(xué)模型n 首先需要辨識目標(biāo)，確定優(yōu)化標(biāo)準(zhǔn)，即待研究系統(tǒng)的性能定量描述，

4、如成本、數(shù)量、利潤、時間、能量等；n 其次用合適的決策變量描述系統(tǒng)的特征量，并將目標(biāo)表示成決策變量的函數(shù)（目標(biāo)函數(shù)，objective function )；n 此外需確定變量所受的范圍限制，由若干個函數(shù)的等式或者不等式來定義（約束函數(shù)，constraint functions)l 最優(yōu)化問題指在決策變量所受限制范圍內(nèi)，對相關(guān)的目標(biāo)函數(shù)進(jìn)行極小化或者極大化.s.t. 滿足約束條件的點(diǎn)稱為可行點(diǎn)（feasible point ) ，所有可行點(diǎn)的集合稱為可行域（feasible region) ，記為S.- 當(dāng)，無約束優(yōu)化問題;否則,約束優(yōu)化問題- 和都是線性函數(shù)，為線性規(guī)劃（linear pro

5、gramming，LP);否則為非線性規(guī)劃（nonlinear programming, NLP）.- 所有變量取整數(shù)，稱為整數(shù)規(guī)劃（integer programming);允許一部分變量取整數(shù)，另一部分變量取實(shí)數(shù)，為混合整數(shù)規(guī)劃（mixed integer programming, MIP）.- 從一個連通無限集合（可行域）中尋找最優(yōu)解, 稱為連續(xù)優(yōu)化(continuous optimization)問題；從一個有限的集合或者離散的集合中尋找最優(yōu)解，稱為組合優(yōu)化（combinatorial optimization)，或者離散優(yōu)化（discrete optimization）- 存在多個目

6、標(biāo)，即目標(biāo)函數(shù)取一個向量值函數(shù)，稱多目標(biāo)規(guī)劃（multi-objective programming)，或多目標(biāo)優(yōu)化- 最優(yōu)化問題中出現(xiàn)的參數(shù)是完全確定的，稱為確定型優(yōu)化（deterministic optimization）問題;否則稱為非確定型優(yōu)化（uncertain optimization) 問題，包括了隨機(jī)規(guī)劃（stochastic programming）、模糊規(guī)劃（fuzzy programming ) 等特殊情形 最優(yōu)解的概念定義: 設(shè)為目標(biāo)函數(shù)，為可行域，若對每個，成立，則稱為在上的全局極小點(diǎn)。定義: 設(shè)為目標(biāo)函數(shù)，為可行域，若存在的鄰域，使得對每個成立，則稱為在上的局部極小

7、點(diǎn)。l 全局極小點(diǎn)也是局部極小點(diǎn)，而局部極小點(diǎn)不一定是全局極小點(diǎn).l 大多數(shù)的優(yōu)化算法通常只是尋找局部最優(yōu)解.l 對于某些特殊情形，如凸規(guī)劃，局部極小點(diǎn)也是全局極小點(diǎn).§1.2 多元函數(shù)分析 梯度及Hesse矩陣函數(shù)在x處的梯度為n維列向量：函數(shù)在x處的Hesse矩陣為矩陣：二次函數(shù)A是n階對稱矩陣，b是n維列向量，c是常數(shù)梯度：Hesse矩陣: 對向量值函數(shù),每個分量為n元實(shí)值函數(shù).h在點(diǎn)x的Jacobi矩陣為該矩陣稱為h在x的導(dǎo)數(shù),記作或, 其中例 向量值函數(shù)在任一點(diǎn)的Jacobi矩陣,即導(dǎo)數(shù)為 多元函數(shù)的Taylor展式假設(shè)在開集S上連續(xù)可微,給定點(diǎn)，則f在點(diǎn)的一階Taylor

8、展開式為當(dāng)時,關(guān)于是高階無窮小量假設(shè)在開集S上二次連續(xù)可微,則f在點(diǎn)的二階Taylor展開式為當(dāng)時,關(guān)于是高階無窮小量 方向?qū)c最速下降方向在點(diǎn)處沿方向d的變化率用方向?qū)?shù)表示.在處沿方向d的方向?qū)?shù)定義為極限:對于可微函數(shù),方向?qū)?shù)等于梯度與方向的內(nèi)積,即在點(diǎn)處下降最快的方向,稱為最速下降方向,它是在點(diǎn)處的負(fù)梯度方向:§1.3 凸分析初步 凸集的定義、舉例(常見凸集)及性質(zhì)定義：設(shè)S為n維歐氏空間中一個集合若對S中任意兩點(diǎn)，聯(lián)結(jié)它們的線段仍屬于S；換言之，對S中任意兩點(diǎn),及每個實(shí)數(shù)，都有則稱S為凸集常見凸集： 集合為凸集（p為n維列向量，為實(shí)數(shù)）集合H稱為中的超平面，故超平面為凸集

9、 集合為凸集集合稱為半空間，故半空間為凸集 集合為凸集（d是給定的非零向量，是定點(diǎn)）集合稱為射線,故射線為凸集.證明：對任意兩點(diǎn)及每一個，必有 以及由于，因此有凸集的性質(zhì):設(shè)和為中的兩個凸集, 是實(shí)數(shù),則(1) 為凸集;(2) 為凸集;(3) 為凸集;(4) 為凸集.凸錐和多面集定義: 設(shè)有集合，若對C中每一點(diǎn)x，當(dāng)取任何非負(fù)數(shù)時，都有,則稱C為錐.又若C為凸集，則稱C為凸錐例 向量集的所有非負(fù)線性組合構(gòu)成的集合為凸錐定義 有限個半空間的交稱為多面集例: 集合為多面集若b=0，則多面集也是凸錐，稱為多面錐極點(diǎn)和極方向定義: 設(shè)S為非空凸集，若x不能表示成S中兩個不同點(diǎn)的凸組合；換言之，若假設(shè),

10、 必推得，則稱x是凸集S的極點(diǎn)定義: 設(shè)S為非空凸集，d為非零向量，如果對S中的每一個x，都有射線,則稱向量d為S的方向又設(shè)和是S的兩個方向，若對任何正數(shù)，有, 則稱和是兩個不同的方向若S的方向d不能表示成該集合的兩個不同方向的正的線性組合，則稱d為S的極方向注意:有界集不存在方向，因而也不存在極方向?qū)τ跓o界集才有方向的概念多面集的一個重要性質(zhì)表示定理：設(shè)為非空多面集，則有：(l)極點(diǎn)集非空，且存在有限個極點(diǎn).(2)極方向集合為空集的充要條件是S有界若S無界，則存在有限個極方向.(3) 的充要條件是: ，. 凸集分離定理及其應(yīng)用(擇一定理)凸集的另一個重要性質(zhì)分離定理集合的分離：指對于兩個集合

11、和，存在一個超平面H，使在H的一邊，在H的另一邊如果超平面的方程為，那么對位于H某一邊的點(diǎn)x，必有，而對位于H另一邊的點(diǎn)x，必有.S1S2H定義:設(shè)和是兩個非空集合，為超平面如對每個,有，對每個，有(或情形恰好相反），則稱H分離集合和.定理(凸集分離定理)：設(shè)和是兩個非空凸集，Æ，則存在超平面H，使得，.凸集分離定理的另一種表述方法：設(shè)和是兩個非空凸集，Æ，則存在非零向量p，使凸集分離定理在最優(yōu)化理論中很有用。著名的應(yīng)用是所謂的擇一定理。擇一定理(the theorem of the alternative)指對于兩個相關(guān)的線性系統(tǒng)（等式或不等式組）I和II來說，或者系統(tǒng)I

12、有解，或者系統(tǒng)II有解，但兩者不可能同時有解.擇一定理有多種不同的形式: Farkas定理,Gordan定理,Motzkin定理等.定理(Farkas定理):設(shè)A為矩陣,c為n維向量,則線性系統(tǒng)(I) , 有解,當(dāng)且僅當(dāng)(II) , 無解.定理(Gordan定理):設(shè)A為矩陣,那么的充要條件是不存在非零向量,使. 凸函數(shù)的定義、性質(zhì)及判別方法定義: 設(shè)S為非空凸集，f是定義在S上的實(shí)函數(shù)如果對任意的,及每個數(shù),都有則稱f為S上的凸函數(shù)如果對任意互不相同,及每一個數(shù)，都有,則稱f為S上的嚴(yán)格凸函數(shù) 如果-f 為S上的凸函數(shù)，則稱f為S上的凹函數(shù)凸函數(shù)的幾何解釋：連接函數(shù)曲線上任意兩點(diǎn)的弦不在曲線

13、的下方凸函數(shù)的一些性質(zhì)： f是定義在凸集S上的凸函數(shù)，實(shí)數(shù)，則也是定義在S上的凸函數(shù) 和是定義在凸集S上的凸函數(shù)，則也是定義在S上的凸函數(shù) 是定義在凸集S上的凸函數(shù)，實(shí)數(shù)，則也是定義在S上的凸函數(shù). S是非空凸集，f是定義在S上的凸函數(shù)，是一個實(shí)數(shù)，則水平集是凸集 S是非空凸集，f是定義在S上的凸函數(shù)，則f在S上局部極小點(diǎn)是全局極小點(diǎn)，且極小點(diǎn)的集合為凸集 證明: 設(shè)是f在S上的局部極小點(diǎn)，即存在的的鄰域，使得對每一點(diǎn)，成立.假設(shè)不是全局極小點(diǎn)，則存在，使由于S 是凸集，因此對每一個數(shù),有由于與是不同的兩點(diǎn)，可取,又由于f 是S 上的凸函數(shù),因此有當(dāng)取得充分小時，可使這與為局部極小點(diǎn)矛盾故是f

14、在S上的全局極小點(diǎn) 由以上證明可知，f在S上的極小值也是它在S上的最小值設(shè)極小值為，則極小點(diǎn)的集合可以寫作根據(jù)性質(zhì), 為凸集凸函數(shù)判別的一階條件定理: 設(shè)S 是非空開凸集，是定義在S上的可微函數(shù)，則為凸函數(shù)的充要條件是對任意兩點(diǎn)，都有而為嚴(yán)格凸函數(shù)的充要條件是對任意的互不相同的，成立推論: 設(shè)S是中的凸集, ,是定義在上的凸函數(shù)，且在點(diǎn)可微,則對任意的,有凸函數(shù)判別的二階條件定理: 設(shè)S 是中非空開凸集，是定義在S上的二次可微函數(shù)，則為凸函數(shù)的充要條件是在每一點(diǎn)處Hesse矩陣半正定 Hesse矩陣半正定, 即對于任意的和, 有定理: 設(shè)S 是中非空開凸集，是定義在S上的二次可微函數(shù)，如果在每一點(diǎn),Hesse矩陣正定,則為嚴(yán)格凸函數(shù)注意: 逆定理并不成立若是定義在S上的嚴(yán)格凸函數(shù)，則在每一點(diǎn)處，Hesse矩陣是半正定的(而不是正定的)例: 給定二次函數(shù)由于在每一點(diǎn)處,是正定的，因此是嚴(yán)格凸函數(shù) 凸規(guī)劃及其性質(zhì)考慮極小化問題：s.t. 設(shè)是凸函數(shù)，是凹函數(shù)，是線性函數(shù)問題的可行域由于是凹函數(shù)，因此滿足,即滿足的點(diǎn)的集合是凸集.根據(jù)凸函數(shù)和凹函數(shù)的定義，線性函數(shù)既是凸函數(shù)也是凹函數(shù)