《最優(yōu)化計(jì)算方法》：
　　第1章 引論
　　本章首先介紹最優(yōu)化問(wèn)題的數(shù)學(xué)模型?基本概念及其分類(lèi)， 然后介紹凸集和凸函數(shù)的概念及相關(guān)性質(zhì)， 最后介紹線搜索迭代算法的一般框架?線搜索準(zhǔn)則及其算法收斂性判別.
　　1.1 最優(yōu)化問(wèn)題概述
　　在現(xiàn)實(shí)社會(huì)中， 人們經(jīng)常遇到這樣一類(lèi)問(wèn)題： 判別在一個(gè)問(wèn)題的眾多解決方案中什么樣的方案最佳， 以及如何找出最佳方案. 例如， 在資源分配中， 如何分配有限資源， 使得分配方案既能滿足各方面的需求， 又能獲得好的經(jīng)濟(jì)效益； 在工程設(shè)計(jì)中， 如何選擇設(shè)計(jì)參數(shù)， 使得設(shè)計(jì)方案既能滿足設(shè)計(jì)要求， 又能降低成本等. 這類(lèi)問(wèn)題就是在一定的限制條件下使得所關(guān)心的指標(biāo)達(dá)到最優(yōu). 最優(yōu)化就是為解決這類(lèi)問(wèn)題提供理論基礎(chǔ)和求解方法的一門(mén)數(shù)學(xué)學(xué)科.
　　最優(yōu)化問(wèn)題的基本數(shù)學(xué)模型為
　　min f（x）
　　s.t. ci（x） > 0； 8i 2 I ：= f1； 2； ￠ ￠ ￠ ； pg；
　　ci（x） = 0； 8i 2 E ：= fp + 1； p + 2； ￠ ￠ ￠ ；mg； （1.1.1）
　　其中， min 是 minimize 的縮寫(xiě)， s.t. 是 subject to 的縮寫(xiě)， x 2 Rn 稱(chēng)為決策向量，函數(shù) f ： Rn ! R 稱(chēng)為目標(biāo)函數(shù)， 函數(shù) ci（￠） （i 2 I） 稱(chēng)為不等式約束函數(shù)， 函數(shù)ci（￠） （i 2 E） 稱(chēng)為等式約束函數(shù)， 不等式 ci（x） > 0 （i 2 I） 稱(chēng)為不等式約束， 方程ci（x） = 0 （i 2 E） 稱(chēng)為等式約束， I 稱(chēng)為不等式約束的指標(biāo)集， E 稱(chēng)為等式約束的指標(biāo)集. 記
　　F ：=8<：
　　x 2 Rnˉˉˉˉˉˉ
　　ci（x） > 0； 8i 2 I = f1； 2； ￠ ￠ ￠ ； pg ；
　　ci（x） = 0； 8i 2 E = fp + 1； p + 2； ￠ ￠ ￠ ；mg9=；： （1.1.2）
　　那么， 稱(chēng)集合 F 為最優(yōu)化問(wèn)題 （1.1.1） 的可行域， F 中的每個(gè)點(diǎn) x 稱(chēng)為最優(yōu)化問(wèn)題（1.1.1） 的一個(gè)可行點(diǎn). 若 F = ?， 則稱(chēng)問(wèn)題 （1.1.1） 是不可行的； 否則稱(chēng)問(wèn)題 （1.1.1）是可行的. 因此， 最優(yōu)化問(wèn)題 （1.1.1） 就是在可行域 F 中尋找一點(diǎn) x 使得它對(duì)應(yīng)的目標(biāo)函數(shù)值 f（x） 不大于 F 中其他任何點(diǎn)所對(duì)應(yīng)的目標(biāo)函數(shù)值.
　　定義 1.1.1 假設(shè)可行域 F 由 （1.1.2） 式給出.
　�。╥） 若 x¤ 2 F， 且對(duì)所有的 x 2 F 恒有 f（x¤） 6 f（x）， 則稱(chēng) x¤ 為最優(yōu)化問(wèn)題（1.1.1） 的一個(gè)全局最優(yōu)解.
　　（ii） 若 x¤ 2 F， 且對(duì)所有的 x 2 F n fx¤g 恒有 f（x¤） < f（x）， 則稱(chēng) x¤ 為最優(yōu)化問(wèn)題 （1.1.1） 的嚴(yán)格全局最優(yōu)解.
　�。╥ii） 若 x¤ 2 F， 且存在 x¤ 的某個(gè)鄰域
　　N"（x¤） ：= fx 2 Rn j kx . x¤k < "g； "為正實(shí)數(shù)且k ￠ k表示某種范數(shù)；
　　使得對(duì)所有的 x 2 F \N"（x¤） 恒有 f（x¤） 6 f（x）， 那么稱(chēng) x¤ 為最優(yōu)化問(wèn)題 （1.1.1）的一個(gè)局部最優(yōu)解.
　�。╥v） 若 x¤ 2F， 且存在 x¤ 的某個(gè)鄰域 N"（x¤）， 使得對(duì)所有的 x 2 F \ N"（x¤）n fx¤g 恒有 f（x¤） < f（x）， 那么稱(chēng) x¤ 為最優(yōu)化問(wèn)題 （1.1.1） 的一個(gè)嚴(yán)格局部最優(yōu)解.
　　顯然， 全局最優(yōu)解一定是局部最優(yōu)解； 而局部最優(yōu)解不一定是全局最優(yōu)解. 求解最優(yōu)化問(wèn)題 （1.1.1） 就是在可行域 F 上尋找問(wèn)題 （1.1.1） 的全局最優(yōu)解. 但是， 在一般情況下， 不容易求得全局最優(yōu)解， 往往只能求出局部最優(yōu)解. 以下若不做特別聲明， 全局最優(yōu)解簡(jiǎn)稱(chēng)最優(yōu)解.
　　定義 1.1.2 對(duì)于最優(yōu)化問(wèn)題 （1.1.1）， 稱(chēng)其最優(yōu)解 x¤ 對(duì)應(yīng)的目標(biāo)函數(shù)值 f（x¤）為此優(yōu)化問(wèn)題的最優(yōu)值.
　　對(duì)于最優(yōu)化問(wèn)題 （1.1.1）， 最優(yōu)解不一定存在， 即使存在也不一定唯一； 但是， 若最優(yōu)解存在， 則最優(yōu)值必唯一. 以下用 S 表示最優(yōu)化問(wèn)題 （1.1.1） 的最優(yōu)解集. 如果S = ?， 那么最優(yōu)化問(wèn)題 （1.1.1） 無(wú)最優(yōu)解； 否則最優(yōu)化問(wèn)題 （1.1.1） 有最優(yōu)解. 顯然，若最優(yōu)化問(wèn)題 （1.1.1） 不可行； 或者該問(wèn)題可行但它的目標(biāo)函數(shù)值在可行域上無(wú)下界， 則最優(yōu)化問(wèn)題 （1.1.1） 都無(wú)最優(yōu)解. 另外需要提到的一點(diǎn)是： 在實(shí)際中， 若需要極大化目標(biāo)函數(shù)， 那么通過(guò)將目標(biāo)函數(shù)前加負(fù)號(hào)可轉(zhuǎn)化為極小化問(wèn)題求解. 因此，不失一般性， 本書(shū)中只考慮極小化問(wèn)題.
　　最優(yōu)化問(wèn)題 （1.1.1） 也常被寫(xiě)成
　　min8<：
　　f（x)ˉˉˉˉˉˉ
　　ci（x） > 0； 8i 2 I ：= f1； 2； ￠ ￠ ￠ ； pg；
　　ci（x） = 0； 8i 2 E ：= fp + 1； p + 2； ￠ ￠ ￠ ；mg
　　9=；
　　或者 minff（x） j x 2 Fg； 或者 minx2F f（x）； 或者 x¤ = arg minx2F f（x） 等， 其中arg min 為 the argument of the minimum 的縮寫(xiě).
　　最優(yōu)化問(wèn)題形形色色， 對(duì)應(yīng)的最優(yōu)化模型多種多樣， 不同的優(yōu)化模型， 其求解方法有很大的差異. 因此， 為了有效地求解最優(yōu)化問(wèn)題， 人們首先應(yīng)能區(qū)分優(yōu)化問(wèn)題的類(lèi)型. 下面從不同的角度對(duì)優(yōu)化問(wèn)題進(jìn)行分類(lèi).
　�。�1） 根據(jù)有無(wú)約束條件分為無(wú)約束優(yōu)化和約束優(yōu)化 若 F = Rn， 則稱(chēng)問(wèn)題 （1.1.1） 為無(wú)約束優(yōu)化問(wèn)題； 若 F μ Rn 且 F 6= Rn， 則稱(chēng)問(wèn)題 （1.1.1） 為約束優(yōu)化問(wèn)題.
　�。�2） 根據(jù)所涉及的函數(shù)是否線性分為線性規(guī)劃和非線性規(guī)劃 若目標(biāo)函數(shù)和約束函數(shù)都是線性的， 則稱(chēng)問(wèn)題 （1.1.1） 為線性規(guī)劃問(wèn)題； 若目標(biāo)函數(shù)和約束函數(shù)中至少有一個(gè)是非線性的， 則稱(chēng)問(wèn)題 （1.1.1） 為非線性規(guī)劃問(wèn)題. 若目標(biāo)函數(shù)是二次函數(shù)且所有約束函數(shù)都是線性函數(shù)， 則稱(chēng)問(wèn)題 （1.1.1） 為二次規(guī)劃問(wèn)題. 二次規(guī)劃是一 類(lèi)簡(jiǎn)單?特殊的非線性規(guī)劃問(wèn)題.
　　（3） 根據(jù)目標(biāo)函數(shù)分為單目標(biāo)規(guī)劃和多目標(biāo)規(guī)劃 若目標(biāo)函數(shù) f 是一個(gè)實(shí)值函數(shù)， 則稱(chēng)問(wèn)題 （1.1.1） 為單目標(biāo)規(guī)劃問(wèn)題； 若目標(biāo)函數(shù) f 是一個(gè)向量值函數(shù)， 則稱(chēng)問(wèn)題 （1.1.1） 為多目標(biāo)規(guī)劃問(wèn)題.
　�。�4） 根據(jù)涉及函數(shù)的可微性質(zhì)分為光滑優(yōu)化和非光滑優(yōu)化 若目標(biāo)函數(shù)和約束函數(shù)都是連續(xù)可微的， 則稱(chēng)問(wèn)題 （1.1.1） 為光滑優(yōu)化問(wèn)題； 否則稱(chēng)為非光滑優(yōu)化問(wèn)題.
　�。�5） 根據(jù)涉及函數(shù)的凸性分為凸規(guī)劃和非凸規(guī)劃 若可行域 F 是凸集且目標(biāo)函數(shù) f 是凸函數(shù)， 則稱(chēng)問(wèn)題 （1.1.1） 為凸規(guī)劃問(wèn)題； 否則稱(chēng)為非凸規(guī)劃問(wèn)題. 1.3節(jié)將詳細(xì)介紹凸規(guī)劃.
　　（6） 根據(jù)可行點(diǎn)的個(gè)數(shù)情況分為連續(xù)優(yōu)化和離散優(yōu)化 若可行域 F 中含有無(wú)窮多個(gè)點(diǎn)且可行域中的點(diǎn)連續(xù)變化， 則稱(chēng)問(wèn)題 （1.1.1） 為連續(xù)優(yōu)化問(wèn)題. 若可行域F 中含有有限個(gè)點(diǎn)或可數(shù)個(gè)點(diǎn)， 則稱(chēng)問(wèn)題 （1.1.1） 為離散優(yōu)化問(wèn)題. 若所有決策變量取整數(shù)， 則稱(chēng)問(wèn)題 （1.1.1） 為整數(shù)規(guī)劃問(wèn)題； 若部分決策變量取整數(shù)且其他決策變量連續(xù)變化， 則稱(chēng)問(wèn)題 （1.1.1） 為混合整數(shù)規(guī)劃問(wèn)題. 在整數(shù)規(guī)劃中， 如果決策變量只能取 0 和 1， 那么對(duì)應(yīng)的優(yōu)化問(wèn)題稱(chēng)為 0-1 整數(shù)規(guī)劃問(wèn)題.需要指出兩點(diǎn)：第一， 部分不同優(yōu)化問(wèn)題在某些情況下可以相互轉(zhuǎn)化； 第二， 這里只是給出一些基本的分類(lèi)， 最優(yōu)化問(wèn)題還有其他的一些分類(lèi).本書(shū)主要討論光滑的單目標(biāo)無(wú)約束優(yōu)化和約束優(yōu)化問(wèn)題的理論與求解算法， 對(duì)多目標(biāo)規(guī)劃只做簡(jiǎn)單的介紹.
　　1.2 預(yù) 備 知 識(shí)
　　本節(jié)介紹在最優(yōu)化理論與方法中經(jīng)常使用的數(shù)學(xué)基礎(chǔ)知識(shí)， 包括向量范數(shù)?矩陣范數(shù)?函數(shù)的梯度與 Hesse 陣?Taylor 展開(kāi)式等.
　　1.2.1 向量范數(shù)與矩陣范數(shù)
　　本小節(jié)介紹向量范數(shù)與矩陣范數(shù)的定義以及幾個(gè)重要不等式.
　　在本書(shū)中， 約定向量取列向量形式， 即 x 2 Rn 是指 x 具有如下形式：
　　其中， x1； x2； ￠ ￠ ￠ ； xn 分別是向量 x 的分量， 記號(hào) \：=" 表示 \定義". 此外， 對(duì)任意的 x； y 2 Rn， 常用的內(nèi)積 hx； yi 定義為
　　定義 1.2.1 稱(chēng)映射 k ￠ kRn !R 為 Rn 上的范數(shù)， 當(dāng)且僅當(dāng)它具有下列性質(zhì)：
　　（i） 對(duì)任意的 x 2 Rn， 有 kxk > 0， 且 kxk = 0 當(dāng)且僅當(dāng) x = 0；
　�。╥i） 對(duì)任意的 x 2 Rn 和任意的 . 2 R， 有 k.xk = j.jkxk；
　　（iii） 對(duì)任意的 x； y 2 Rn， 有 kx + yk 6 kxk + kyk.
　　對(duì)任意的 x 2 Rn， 常用的向量范數(shù)如下.
　�。�1） l1-范數(shù)： kxk1 =
　　注 在本書(shū)中， 向量范數(shù) k ￠ k2 廣為使用， 為了簡(jiǎn)便， 簡(jiǎn)寫(xiě)為 k ￠ k.
　　由上述各種范數(shù)的定義，容易驗(yàn)證： 對(duì)任意的 x 2 Rn， 有向量范數(shù)等價(jià)性的定義如下.
　　命題 1.2.1 假設(shè) k ￠ k. 和 k ￠ kˉ 是定義在 Rn 上的任意兩種范數(shù). 那么總存在兩個(gè)正數(shù) .1 和 .2， 使得對(duì)任意的 x 2 Rn， 有 .1kxk. 6 kxkˉ 6 .2kxk
　　因此，以上定義在 Rn 上的向量范數(shù)是等價(jià)的. 在最優(yōu)化方法中， 常需要考察某個(gè)點(diǎn)列 fxkg 趨向于 x¤ 的速率， 利用命題 1.2.1， 只需要按某種范數(shù) k ￠ k 考察kxk . x¤k 趨向于 0 的速率即可.
　　另外，假設(shè) A 2 Rn￡n 是對(duì)稱(chēng)正定矩陣. 那么向量的橢球范數(shù) k￠kA 定義如下： kxkA ：= pxTAx； 8x 2 Rn：
　　1.2 預(yù) 備 知 識(shí)
　　類(lèi)似于向量范數(shù)， 可以定義矩陣范數(shù).
　　定義 1.2.2 稱(chēng)映射 k ￠ k ： Rn￡n ! R 為 Rn￡n 上的范數(shù)， 當(dāng)且僅當(dāng)它具有下列性質(zhì)：
　�。╥） 對(duì)任意的 A 2 Rn￡n， 有 kAk > 0， 且 kAk = 0 當(dāng)且僅當(dāng) A = 0；
　�。╥i） 對(duì)任意的 A 2 Rn￡n 和任意的 . 2 R， 有 k.Ak = j.jkAk；
　　（iii） 對(duì)任意的 A；B 2 Rn￡n， 有 kA + Bk 6 kAk + kBk.
　　對(duì)任意的 A = （aij）n￡n 2 Rn￡n， 最常用的矩陣范數(shù)是 Frobenius 范數(shù)， 其定義為
　　其中， Tr（ATA） 表示矩陣 ATA 的跡， 即 ATA 的所有主對(duì)角線元素之和， 也等于ATA 的所有特征值之和. 另一個(gè)常用的矩陣范數(shù)是由向量所誘導(dǎo)的矩陣范數(shù)， 也稱(chēng)為算子范數(shù)， 其定義為
　　其中， k ￠ k 是某種向量范數(shù). 特別地， 對(duì)任意的 A 2 Rn￡n， 有
　　（1） 由向量 l1- 范數(shù)誘導(dǎo)的矩陣范數(shù) （列范數(shù)） 為 kAk1 = max . n Xi=1jaij jˉj 2 f1； 2； ￠ ￠ ￠ ； nga；
　�。�2） 由向量 l1- 范數(shù)誘導(dǎo)的矩陣范數(shù) （行范數(shù)） 為 kAk1 = max . n Xj=1jaij jˉˉi 2 f1； 2； ￠ ￠ ￠ ； nga；
　　（3） 由向量 l2- 范數(shù)誘導(dǎo)的矩陣范數(shù) （譜范數(shù)） 為 kAk2 = p.max（ATA）， 其中.max（ATA） 表示矩陣 ATA 的最大特征值.
　　假設(shè) k ￠ k 表示上述定義四種矩陣范數(shù)中的任意一種范數(shù)， 那么它滿足相容性件， 即對(duì)任意的 A；B 2 Rn￡n， 有 kABk 6 kAkkBk； 并且它與相應(yīng)的向量范數(shù)是 相容的， 即對(duì)任意的 A 2 Rn￡n 和 x 2 Rn 有 kAxk 6 kAkkxk.
　　下面介紹五個(gè)常用的不等式.
　　……