錐優(yōu)化的基于核函數(shù)的內(nèi)點(diǎn)算法

前言

　　錐優(yōu)化問(wèn)題是一個(gè)凸規(guī)劃問(wèn)題，它的目標(biāo)函數(shù)是線性函數(shù)，約束集是仿射空間和一個(gè)錐的交集，它從優(yōu)化問(wèn)題可行域的結(jié)構(gòu)推廣了線性規(guī)劃問(wèn)題，為求解非線性最優(yōu)化問(wèn)題提供了一種新的框架，錐優(yōu)化有凸結(jié)構(gòu)和豐富的對(duì)偶理論，對(duì)偶問(wèn)題具有對(duì)稱的簡(jiǎn)潔結(jié)構(gòu)，同時(shí)，又有廣泛應(yīng)用背景，除了在傳統(tǒng)學(xué)科，在經(jīng)濟(jì)、金融、管理和工程技術(shù)等領(lǐng)域亦有廣泛的應(yīng)用，近年來(lái)，錐優(yōu)化與新興學(xué)科有了廣泛交叉和應(yīng)用，如在無(wú)線傳感網(wǎng)絡(luò)、信息理論、編碼理論等信息學(xué)科找到了豐富的應(yīng)用，20世紀(jì)80年代出現(xiàn)的內(nèi)點(diǎn)算法推動(dòng)了算法計(jì)算復(fù)雜性研究的發(fā)展，也成為求解錐優(yōu)化問(wèn)題的強(qiáng)大工具，迄今為止，錐優(yōu)化和內(nèi)點(diǎn)算法已成為數(shù)學(xué)規(guī)劃和優(yōu)化領(lǐng)域最活躍的研究課題之一?！　”緯鶕?jù)作者和其合作者Roos教授、Ghami博士、王國(guó)強(qiáng)博士近年來(lái)的研究工作，全面介紹求解線性規(guī)劃、P（K）線性互補(bǔ)問(wèn)題、半正定優(yōu)化、二階錐優(yōu)化基于核函數(shù)的內(nèi)點(diǎn)算法，核函數(shù)的重要性體現(xiàn)在它有簡(jiǎn)單的解析表達(dá)式、容易計(jì)算的高階導(dǎo)數(shù)等良好性質(zhì)。

內(nèi)容概要

本書根據(jù)作者和其合作者Roos教授、Ghami博士、王國(guó)強(qiáng)博士近年來(lái)的研究工作，全面介紹求解線性規(guī)劃、P*(k)線性互補(bǔ)問(wèn)題、半正定優(yōu)化、二階錐優(yōu)化基于核函數(shù)的內(nèi)點(diǎn)算法。核函數(shù)的重要性體現(xiàn)在它有簡(jiǎn)單的解析表達(dá)式、容易計(jì)算的高階導(dǎo)數(shù)等良好性質(zhì)。由核函數(shù)確定的障礙函數(shù)繼承了這些良好性質(zhì)，準(zhǔn)確刻畫了錐優(yōu)化問(wèn)題的中心路徑，基于障礙函數(shù)設(shè)計(jì)的原始對(duì)偶內(nèi)點(diǎn)算法，并有程序化的分析方法，使得內(nèi)點(diǎn)算法的計(jì)算復(fù)雜性分析變得十分容易。

書籍目錄

PrefaceChapter 1  Introduction  1.1  Conic optimization problems  1.2  Conic duality  1.3  From the dual cone to the dual problem  1.4  Development of the interior-point methods  1.5  Scope of the bookChapter 2  Kernel Functions  2.1  Definition of kernel functions and basic properties  2.2  The further conditions of kernel functions  2.3  Properties of kernel functions  2.4  Examples of kernel functions  2.5  Barrier functions based on kernel functions  2.6  Generalization of kernel function    2.6.1  Finite kernel function    2.6.2  Parametric kernel functionChapter 3  Kernel Function-based Interior-point Algorithm for LO  3.1  The central path for LO  3.2  The search directions for LO  3.3  The generic primal-dual interior-point algorithm for LO  3.4  Analysis of the algorithm    3.4.1  Decrease of the barrier function during an inner iteration    3.4.2  Choice of the step size  3.5  Iteration bounds  3.6  Summary of computation for complexity bound  3.7  Complexity analysis based on kernel functions  3.8  Summary of resultsChapter 4  Kernel Function-based Interior-point Algorithm for P*(k) LCP  4.1  The P*(k)-LCP  4.2  The central path for P*(k)-LCP  4.3  The new search directions for P*(k)-LCP  4.4  The generic primal-dual interior-point algorithm for P*(k)-LCP...  4.5  The properties of the barrier function  4.6  Analysis of the algorithm    4.6.1  Growth behavior of the barrier function    4.6.2  Determining the default step size  4.7  Decrease of the barrier function during an inner iteration  4.8  Complexity of the algorithm    4.8.1  Iteration bound for the large-update methods    4.8.2  Iteration bound for the small-update methodsChapter 5  Kernel Function-based Interior-point Algorithm for SDO  5.1  Special matrix functions  5.2  The central path for SDO  5.3  The new search directions for SDO  5.4  The generic primal-dual interior-point algorithm for SDO  5.5  The properties of the barrier function  5.6  Analysis of the algorithm    5.6.1  Decrease of the barrier function during an inner iteration    5.6.2  Choice of the step size  5.7  Iteration bounds  5.8  Kernel function-based schemes  5.9  The example  5.10  Numerical resultsChapter 6  Kernel Function-based Interior-point Algorithm for SOCO  6.1  Algebraic properties of second-order cones  6.2  Barrier functions defined on second-order cone  6.3  Rescaling the cone  6.4  The central path for SOCO  6.5  The new search directions for SOCO  6.6  The generic primal-dual interior-point algorithm for SOCO  6.7  Analysis of the algorithm  6.8  The crucial inequality  6.9  Decrease of the barrier function during an inner iteration  6.10  Increase of the barrier function during a μ-update  6.11  Iteration-bounds  6.12  Numerical results  6.13  Some technical lemmasAppendix  Three Technical LemmasReference

章節(jié)摘錄

　　A linear optimization problem is the minimization of a linear function over a polyhedral set which can be viewed as the intersection of an affine space and the coneof nonnegative orthant. Many problems can be formulated as, or approximated bya linear optimization problem. There are many versions of interior-point methodsfor linear optimization. But the basic scheme of these methods is to remove theconstraint set and add a multiple of the barrier function to the objective function.Therefore, the barrier-based scheme reduces the constrained problem into a seriesof unconstrained problems, then to "trace" the path formed by the optimal solutions of unconstrained problems. "Trace" means that the optimal solutions ofunconstrained problems can be replaced by a good enough approximation of theoptimal solutions of unconstrained problems. The procedure of the scheme canbe gone on with updating the barrier parameter until the optimal set of linearoptimization problem is reached.

圖書封面

圖書標(biāo)簽Tags

無(wú)

評(píng)論、評(píng)分、閱讀與下載

---

    錐優(yōu)化的基于核函數(shù)的內(nèi)點(diǎn)算法 PDF格式下載

---