一類單線性約束二次規(guī)劃問題計算機(jī)快速算法的研究

1、一類單線性約束二次規(guī)劃問題計算機(jī)快速算法的研究第 1 章 緒 論1.1 本文主要研究內(nèi)容隨著計算機(jī)科學(xué)的高速發(fā)展，計算機(jī)技術(shù)對人們生活影響越來越大，特別是人工智能的火熱，deep learning1-5、neural networks6-8、support vector machine（SVM）9-10等等人工智能算法留下深刻印象，而這些算法都離不開數(shù)學(xué)理論基礎(chǔ)的支撐。我們在綜合研究了支持向量機(jī)、連續(xù)二次背包11-17、圖上快速馬爾科夫18-20、度量投影21-22等等問題的算法后，發(fā)現(xiàn)其在模型建立后都需要求解凸二次規(guī)劃問題。.1.2 課題研究的意義本文主體構(gòu)架由五個章節(jié)組成，每個章節(jié)具體內(nèi)容

2、如下：第一章緒論：此章節(jié)交代課題選定的初衷，在研究支持向量機(jī)、連續(xù)二次背包、度量投影等問題，歸納出一類單線性約束二次規(guī)劃問題標(biāo)準(zhǔn)形式，旨在給出一個標(biāo)準(zhǔn)模型和快速的通用算法，為機(jī)器學(xué)習(xí)研究者在二次規(guī)劃模型求解上給出一個可靠的解決方案。針對標(biāo)準(zhǔn)模型，本文給出具體的幾個應(yīng)用場景組，并分析了相關(guān)場景組的已有算法和研究現(xiàn)狀。第二章最優(yōu)化理論基礎(chǔ)知識：本文應(yīng)用的最優(yōu)化基礎(chǔ)理論主要包括有：凸集、凸函數(shù)的定義及判別分析，最優(yōu)性條件 KKT 判別，Lagrange 對偶問題與原問題的轉(zhuǎn)化，半光滑牛頓迭代優(yōu)化形式?；谏鲜鲋饕A(chǔ)優(yōu)化思想，結(jié)合提出的實際標(biāo)準(zhǔn)模型問題，即可推出模型的最優(yōu)解。本章詳細(xì)給出上述基礎(chǔ)優(yōu)化

3、理論的概念，且作有針對本文模型的展開和推廣。第三章封閉形式解的構(gòu)造：針對文章中所建立的標(biāo)準(zhǔn)模型，對于約束條件首先只考慮其中的類盒子約束，于是得到只有一種約束條件的二次規(guī)劃問題。那么，對于簡化后的模型，運(yùn)用互補(bǔ)松弛的 KKT 最優(yōu)性條件求得子問題的最優(yōu)解。并對求得的最優(yōu)解以分類討論的方式證明最優(yōu)解是存在且唯一的。子問題的封閉形式解得到后，通過引進(jìn)參數(shù)的方法來得到原問題的參數(shù)形式解。第四章 Lagrange 對偶問題及 Pssn 算法：針對原問題的參數(shù)形式最優(yōu)解，本文采用Lagrange 對偶方法得到標(biāo)準(zhǔn)二次規(guī)劃問題（1.1）的對偶問題，通過求解對偶問題的最優(yōu)解性質(zhì)來確定原問題參數(shù)最優(yōu)解中的參數(shù)取

4、值。針對原問題與對偶問題的等價性條件優(yōu)化，在分析了等價性函數(shù)的性質(zhì)后，本章節(jié)中運(yùn)用線搜索保障的半光滑牛頓迭代法來求得等價性函數(shù)的最優(yōu)解。第五章高效鳥群優(yōu)化算法：在這一章節(jié)我們介紹另外一種優(yōu)化算法-鳥群優(yōu)化算法，用來優(yōu)化原問題與對偶問題的等價性方程。第六章算法理論分析及數(shù)值實驗：對于本文設(shè)計的半光滑牛頓迭代算法，分析算法的收斂性和收斂速度，對于收斂速度主要用時間復(fù)雜度和收斂階來衡量，在理論上給出算法的性能指標(biāo)體現(xiàn)其優(yōu)越性。本文最后實現(xiàn)三個典型形式的隨機(jī)數(shù)值實驗，并與已有的最優(yōu)算法和最高水平優(yōu)化軟件作對比試驗，證實本文算法的高效性與準(zhǔn)確性。.第 2 章 最優(yōu)化相關(guān)理論及背景知識隨著人工智能時代的來

5、臨，機(jī)器學(xué)習(xí)28-32、深度學(xué)習(xí)33-38、強(qiáng)化學(xué)習(xí)39-42等各類人工智能領(lǐng)域逐漸被大家所熟知，更是學(xué)術(shù)研究者孜孜不倦的研究方向。人工智能算法被應(yīng)用到各個領(lǐng)域，最優(yōu)化理論在其中發(fā)揮著舉足輕重的作用，其優(yōu)化模型目標(biāo)函數(shù)對算法來說至關(guān)重要。本章來介紹有關(guān)最優(yōu)化的幾個基本知識和二次規(guī)劃算法的基本概念。2.1 凸集和凸函數(shù)凸集是一個擁有良好優(yōu)化特性的集合，凸函數(shù)是目前優(yōu)化算法最擅長處理的函數(shù)類型，凸集和凸函數(shù)在算法優(yōu)化里擔(dān)當(dāng)關(guān)鍵的角色。有關(guān)凸集和凸函數(shù)的很多重要定理在最優(yōu)化算法特別是二次規(guī)劃問題算法的理論證明和算法性質(zhì)分析中具有重要的作用。.2.2 本章小結(jié)本章主要介紹了最優(yōu)化相關(guān)基礎(chǔ)理論以及一些二

6、次規(guī)劃算法背景知識。首先介紹了優(yōu)化中最重要的凸集和凸函數(shù)，這是整個最優(yōu)化最基礎(chǔ)的也是最重要的只是部分，是整個優(yōu)化理論基石；然后介紹了最優(yōu)化問題的最優(yōu)性條件，這是判別一個最優(yōu)解的基本必要條件，互補(bǔ)松弛 KKT 條件對最優(yōu)解求解起著關(guān)鍵性作用；最后引入二次規(guī)劃問題的概念，并介紹相關(guān)經(jīng)典算法。.第 3 章 封閉形式解的構(gòu)造.163.1 子問題封閉性解的構(gòu)造 .163.2 參數(shù)方法 .20第 4 章 LAGRANGE 對偶問題及 PSSN 算法.224.1 拉格朗日對偶方法 .224.2 PSSN 算法 .24第 5 章 基于雙高斯函數(shù)的高效鳥群算法 .325.1 鳥群算法介紹 .325.2 基本鳥群

7、算法流程 .335.3 高效鳥群算法 .345.4 高效鳥群優(yōu)化算法步驟及時間復(fù)雜度分析 .375.5 測試結(jié)果及分析 .385.6 高效鳥群算法總結(jié) .39第 6 章 算法理論分析及數(shù)值實驗本章節(jié)主要討論算法的一些關(guān)鍵處理技術(shù)和給出收斂速度分析，并在理論的指導(dǎo)下設(shè)計三個典型的隨機(jī)數(shù)值實驗來驗證算法的高效性和實用性。6.1 等價性函數(shù)解析解存在的條件針對前章節(jié)提出來的算法，主要探索對偶方程的數(shù)值解，這里也探討算法的解析解存在的條件，由于一般解析解的條件比較嚴(yán)格，于是本章只作簡單介紹。值得注意的是，在半光滑算法中當(dāng)初始點(diǎn)遠(yuǎn)離極小點(diǎn)時，半光滑牛頓法可能不收斂，或者收斂速度非常慢。對此，在半光滑牛頓

8、算法開始之前采用對初始點(diǎn)不依賴的Barzilou-Borwein stepsize 方法來選取初始點(diǎn)。當(dāng)優(yōu)化目標(biāo)函數(shù)維度很大或很復(fù)雜的時候，精確線搜索的計算量很大，并且迭代點(diǎn)離最優(yōu)解很遠(yuǎn)的時候，作精確線搜索的作用就會大大降低。非精確線搜索沿搜索方向產(chǎn)生迭代點(diǎn)，總體希望算法的迭代收斂性快，每一步并不要達(dá)到精確的最小值，非精確線搜索雖然在每一次外循環(huán)迭代增加選擇步長的迭代次數(shù)，但是會使整個算法的迭代次數(shù)大大降低，從而達(dá)到加速收斂的速度。.結(jié) 論本文在總結(jié)大量機(jī)器學(xué)習(xí)算法原型的基礎(chǔ)上，根據(jù)其數(shù)學(xué)原理將問題模型歸納成一類單線性類盒子約束凸二次規(guī)劃標(biāo)準(zhǔn)形式。關(guān)于標(biāo)準(zhǔn)形式模型的最優(yōu)化解，通過最優(yōu)性條件和參數(shù)方法來構(gòu)造，并證明了其存在唯一性。在確定最優(yōu)解參數(shù)方面，引入拉格朗日對偶原理和費(fèi)馬定理得到最優(yōu)性函數(shù)，而且文中通過分析其函數(shù)性質(zhì)確定使用半光滑牛頓迭代方法得到最優(yōu)參數(shù)解。全文的主要工作內(nèi)容總結(jié)如下：1. 在學(xué)習(xí)研究支持向量機(jī)、馬爾科夫模型、條件隨機(jī)模型、EM 模型等算法原型的基礎(chǔ)上總結(jié)一類單線性類盒子約束標(biāo)準(zhǔn)凸二次規(guī)劃模型。在簡單的變量代換和變形后，上述算法模型蘊(yùn)含的最優(yōu)化問題都可以轉(zhuǎn)化為本文提出的標(biāo)準(zhǔn)形式。2. 本文不但提出了標(biāo)準(zhǔn)凸二次規(guī)劃模型，而且運(yùn)用互補(bǔ)松弛 KKT 條件和參數(shù)方法給出了標(biāo)準(zhǔn)二次規(guī)劃形式的帶參數(shù)解，并證明解的存在唯一性。在構(gòu)造解的過程中以分類討論的形式考