高等數(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)濟的配食方案（食譜）。建立食譜的數(shù)學(xué)模型引入決策變量 ：食譜中第i種食物的單位數(shù)量s.t. 例2 選址與運輸問題l 假設(shè)某大型建筑公司有m個項目在不同的地點同時開工建設(shè).記工地的位置分別為.l 第i個工地對某種建筑材料

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

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

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

5、gramming，LP);否則為非線性規(guī)劃（nonlinear programming, NLP）.- 所有變量取整數(shù)，稱為整數(shù)規(guī)劃（integer programming);允許一部分變量取整數(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、標，即目標函數(shù)取一個向量值函數(shù)，稱多目標規(guī)劃（multi-objective programming)，或多目標優(yōu)化- 最優(yōu)化問題中出現(xiàn)的參數(shù)是完全確定的，稱為確定型優(yōu)化（deterministic optimization）問題;否則稱為非確定型優(yōu)化（uncertain optimization) 問題，包括了隨機規(guī)劃（stochastic programming）、模糊規(guī)劃（fuzzy programming ) 等特殊情形 最優(yōu)解的概念定義: 設(shè)為目標函數(shù)，為可行域，若對每個，成立，則稱為在上的全局極小點。定義: 設(shè)為目標函數(shù)，為可行域，若存在的鄰域，使得對每個成立，則稱為在上的局部極小

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

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

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

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

11、和，存在一個超平面H，使在H的一邊，在H的另一邊如果超平面的方程為，那么對位于H某一邊的點x，必有，而對位于H另一邊的點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) , 有解,當且僅當(II) , 無解.定理(Gordan定理):設(shè)A為矩陣,那么的充要條件是不存在非零向量,使. 凸函數(shù)的定義、性質(zhì)及判別方法定義: 設(shè)S為非空凸集，f是定義在S上的實函數(shù)如果對任意的,及每個數(shù),都有則稱f為S上的凸函數(shù)如果對任意互不相同,及每一個數(shù)，都有,則稱f為S上的嚴格凸函數(shù) 如果-f 為S上的凸函數(shù)，則稱f為S上的凹函數(shù)凸函數(shù)的幾何解釋：連接函數(shù)曲線上任意兩點的弦不在曲線

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

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