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

前言

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

內(nèi)容概要

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

圖書封面

圖書標簽Tags

無

評論、評分、閱讀與下載

---

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

---