非綫性規劃（第3版）/清華版雙語教學用書 pdf epub mobi txt 電子書 下載 2025

簡體網頁||繁體網頁

☆☆☆☆☆

Dimitri，P.，Bertsekas 著

圖書標籤:

• 非綫性規劃
• 優化算法
• 數學規劃
• 運籌學
• 清華大學齣版社
• 雙語教學
• 高等教育
• 工程數學
• 數值優化
• 約束優化

齣版社： 清華大學齣版社

ISBN：9787302482345

版次：1

商品編碼：12350861

包裝：平裝

開本：16開

齣版時間：2018-04-01

用紙：膠版紙

頁數：861

字數：1208000

內容簡介

本書涵蓋非綫性規劃的主要內容，包括無約束優化、凸優化、拉格朗日乘子理論和算法、對偶理論及方法等，包含瞭大量的實際應用案例. 本書從無約束優化問題入手，通過直觀分析和嚴格證明給齣瞭無約束優化問題的*優性條件，並討論瞭梯度法、牛頓法、共軛方嚮法等基本實用算法. 進而本書將無約束優化問題的*優性條件和算法推廣到具有凸集約束的優化問題中，進一步討論瞭處理約束問題的可行方嚮法、條件梯度法、梯度投影法、雙度量投影法、近似算法、流形次優化方法、坐標塊下降法等. 拉格朗日乘子理論和算法是非綫性規劃的核心內容之一，也是本書的重點.

精彩書摘

Optimization over a Convex Set

Contents

3.1.ConstrainedOptimizationProblems.........p.2363.1.1.NecessaryandSu.cientConditionsforOptimality.p.2363.1.2.ExistenceofOptimalSolutions.........p.246

3.2.FeasibleDirections-ConditionalGradientMethod..p.2573.2.1.DescentDirectionsandStepsizeRules......p.2573.2.2.TheConditionalGradientMethod........p.262

3.3.GradientProjectionMethods............p.2723.3.1.FeasibleDirectionsandStepsizeRulesBasedon.....Projection..................p.2723.3.2.ConvergenceAnalysis..............p.283

3.4.Two-MetricProjectionMethods..........p.292

3.5.ManifoldSuboptimizationMethods.........p.298

3.6.ProximalAlgorithms...............p.3073.6.1.RateofConvergence..............p.3123.6.2.VariantsoftheProximalAlgorithm.......p.318

3.7.BlockCoordinateDescentMethods.........p.3233.7.1.VariantsofCoordinateDescent.........p.327

3.8.NetworkOptimizationAlgorithms..........p.331

3.9.NotesandSources................p.338

Inthischapterweconsidertheconstrainedoptimizationproblem

minimizef(x)subjecttox∈X,

where,intheabsenceofanexplicitstatementtothecontrary,weassumethroughoutthat:

(a)

Xisanonemptyandconvexsubsetofn .Whendealingwithalgo-rithms,weassumeinadditionthatXisclosed.

(b)

The function f : n →iscontinuouslydi.erentiableoveranopensetthatcontainsX.

Thisproblemgeneralizestheunconstrainedoptimizationproblemoftheprecedingchapters,whereX=n .Wewillseethatthemainalgorithmicideasforsolvingtheunconstrainedandtheconstrainedproblemsarequitesimilar.

UsuallythesetXhasstructurespeci.edbyequationsandinequal-ities.Ifwetakeintoaccountthisstructure,somenewalgorithmicideas,basedonLagrangemultipliersanddualitytheory,comeintoplay.Theseideaswillnotbediscussedinthepresentchapter,buttheywillbethefocusofsubsequentchapters.

Similartotheunconstrainedcase,themethodsofthischapterarebasedoniterativedescentalongsuitablyobtaineddirections.However,thesedirectionsmusthavetheadditionalpropertythattheymaintainfea-sibilityoftheiterates.Suchdirectionsarecalledfeasible,andaswewillseelater,theyareusuallyobtainedbysolvingcertainoptimizationsubprob-lems.Wewillconsidervariouswaystoconstructfeasibledescentdirectionsfollowingthediscussionofoptimalityconditionsinthenextsection.

3.1 CONSTRAINEDOPTIMIZATIONPROBLEMS

Inthissectionweconsiderthemainanalyticaltechniquesforourproblem,andweprovidesomeexamplesoftheirapplication.

3.1.1 NecessaryandSu.cientConditionsforOptimality

We.rstexpandtheunconstrainedoptimalityconditionsofSection1.1fortheproblemofminimizingthecontinuouslydi.erentiablefunctionfovertheconvexsetX.Recallingthede.nitionsofSection1.1,avectorx∈Xisreferredtoasafeasiblevector,andavectorx. ∈XisalocalminimumoffoverXifitisnoworsethanitsfeasibleneighbors;thatis,ifthereexistsan>0suchthat

f(x.)≤f(x),.x∈Xwithx.x.<.

A vector x . ∈XisaglobalminimumoffoverXifitisnoworsethanallotherfeasiblevectors,i.e.,

f (x .)≤f(x),.x∈X.

前言/序言

Preface to the Third Edition

The third edition of the book is a thoroughly rewritten version of the 1999

second edition. New material was included, some of the old material was

discarded, and a large portion of the remainder was reorganized or revised.

The total number of pages has increased by about 10 percent.

Aside from incremental improvements, the changes aim to bring the

book up-to-date with recent research progress, and in harmony with the major

developments in convex optimization theory and algorithms that have

occurred in the meantime. These developments were documented in three

of my books: the 2015 book “Convex Optimization Algorithms,” the 2009

book “Convex Optimization Theory,” and the 2003 book “Convex Analysis

and Optimization” (coauthored with Angelia Nedi′c and Asuman Ozdaglar).

A major difference is that these books have dealt primarily with convex, possibly

nondifferentiable, optimization problems and rely on convex analysis,

while the present book focuses primarily on algorithms for possibly nonconvex

differentiable problems, and relies on calculus and variational analysis.

Having written several interrelated optimization books, I have come to

see nonlinear programming and its associated duality theory as the lynchpin

that holds together deterministic optimization. I have consequently set as an

objective for the present book to integrate the contents of my books, together

with internet-accessible material, so that they complement each other and

form a unified whole. I have thus provided bridges to my other works with

extensive references to generalizations, discussions, and elaborations of the

analysis given here, and I have used throughout fairly consistent notation and

mathematical level.

Another connecting link of my books is that they all share the same style:

they rely on rigorous analysis, but they also aim at an intuitive exposition that

makes use of geometric visualization. This stems from my belief that success

in the practice of optimization strongly depends on the intuitive (as well as

the analytical) understanding of the underlying theory and algorithms.

Some of the more prominent new features of the present edition are:

(a) An expanded coverage of incremental methods and their connections to

stochastic gradient methods, based in part on my 2000 joint work with

Angelia Nedi′c; see Section 2.4 and Section 7.3.2.

(b) A discussion of asynchronous distributed algorithms based in large part

on my 1989 “Parallel and Distributed Computation” book (coauthored

xvii

xviii Preface to the Third Edition

with John Tsitsiklis); see Section 2.5.

(c) A discussion of the proximal algorithm and its variations in Section 3.6,

and the relation with the method of multipliers in Section 7.3.

(d) A substantial coverage of the alternating direction method of multipliers

(ADMM) in Section 7.4, with a discussion of its many applications and

variations, as well as references to my 1989 “Parallel and Distributed

Computation” and 2015 “Convex Optimization Algorithms” books.

(e) A fairly detailed treatment of conic programming problems in Section

6.4.1.

(f) A discussion of the question of existence of solutions in constrained optimization,

based on my 2007 joint work with Paul Tseng [BeT07], which

contains further analysis; see Section 3.1.2.

(g) Additional material on network flow problems in Section 3.8 and 6.4.3,

and their extensions to monotropic programming in Section 6.4.2, with

references to my 1998 “Network Optimization” book.

(h) An expansion of the material of Chapter 4 on Lagrangemultiplier theory,

using a strengthened version of the Fritz John conditions, and the notion

of pseudonormality, based on my 2002 joint work with Asuman Ozdaglar.

(i) An expansion of the material of Chapter 5 on Lagrange multiplier algorithms,

with references to my 1982 “Constrained Optimization and

Lagrange Multiplier Methods” book.

The book contains a few new exercises. As in the second edition, many

of the theoretical exercises have been solved in detail and their solutions have

been posted in the book’s internet site

http://www.athenasc.com/nonlinbook.html

These exercises have been marked with the symbolsWWW. Many other exercises

contain detailed hints and/or references to internet-accessible sources.

The book’s internet site also contains links to additional resources, such as

many additional solved exercises from my convex optimization books, computer

codes, my lecture slides from MIT Nonlinear Programming classes, and

full course contents from the MIT OpenCourseWare (OCW) site.

I would like to express my thanks to the many colleagues who contributed

suggestions for improvement of the third edition. In particular, let

me note with appreciation my principal collaborators on nonlinear programming

topics since the 1999 second edition: Angelia Nedi′c, Asuman Ozdaglar,

Paul Tseng, Mengdi Wang, and Huizhen (Janey) Yu.

Dimitri P. Bertsekas

June, 2016

內容概要 本書緻力於深入淺齣地介紹非綫性規劃這一重要的優化理論與方法。作為一本雙語教學用書，它旨在為國內外不同背景的讀者提供一個係統、嚴謹的學習平颱。全書圍繞非綫性規劃的核心概念、基本理論、經典算法以及實際應用展開，力求在理論深度和工程實踐之間找到最佳平衡點。 第一部分：理論基礎 在非綫性規劃領域，理解其基本框架至關重要。本部分首先會從最基礎的數學模型入手，闡述非綫性規劃問題的一般形式，包括目標函數和約束條件的非綫性特性。我們會詳細探討凸集和凸函數等核心概念，因為它們是保證許多非綫性規劃算法能夠找到全局最優解的關鍵。對於非凸問題，我們將分析其固有難度，並介紹一些局部最優的概念。 接著，我們會深入講解非綫性規劃的理論基石——Kuhn-Tucker（KKT）條件。這部分內容將是本書的重中之重，我們將從幾何角度和代數角度詳細推導KKT條件，並分析其充要條件。我們會詳細介紹拉格朗日乘子法、對偶理論等，以及它們在非綫性規劃中的作用。特彆是，我們將探討對偶問題的結構，以及弱對偶、強對偶等重要概念，並給齣相應的證明。 為瞭更好地理解KKT條件，我們還會介紹一些重要的數學工具，例如凸集分離定理、 Farkas 引理等，並展示它們如何在理論證明中發揮關鍵作用。此外，對於涉及不等式約束的非綫性規劃，我們會詳細介紹約束規範（Constraint Qualifications），如 Slater 條件、綫性獨立約束規範（LICQ）等，並解釋它們為何對於KKT條件成立至關重要。 第二部分：經典算法 理論的構建離不開實際的計算方法。本部分將係統介紹求解非綫性規劃問題的各類經典算法，並詳細分析它們的原理、收斂性以及適用範圍。 首先，我們會從最基礎的迭代法開始，例如梯度下降法。我們將詳細講解其原理，包括最速下降方嚮的選取，並分析其優缺點，例如在某些情況下收斂速度較慢的問題。接著，我們會介紹共軛梯度法，重點闡述其如何剋服梯度下降法的缺點，以及其在大型稀疏問題中的優勢。 之後，我們將深入探討牛頓法及其變種。牛頓法以其二階收斂的性質而著稱，我們將詳細介紹其原理，包括海森矩陣的計算和逆運算。然而，由於牛頓法在計算海森矩陣及其逆方麵存在挑戰，我們還會介紹擬牛頓法，例如DFP法和BFGS法。我們會詳細推導這些方法的迭代公式，並分析它們在保證算法穩定性和計算效率方麵的貢獻。 對於不等式約束問題，我們將重點介紹序列二次規劃（SQP）方法。SQP方法通過將原非綫性規劃問題轉化為一係列二次規劃子問題來求解，是一種非常強大且應用廣泛的算法。我們將詳細講解SQP方法的框架，包括二次規劃子問題的構建（例如利用Hessian矩陣的近似）以及如何處理約束。我們還會討論SQP方法的收斂性分析，並介紹一些提高其魯棒性的技巧。 除瞭上述經典方法，我們還會介紹一些其他重要的算法，例如內點法。內點法以其在大規模綫性規劃和某些非綫性規劃問題上的優異錶現而聞名，我們將介紹其基本思想，例如通過引入障礙函數或中心路徑來處理約束。 在算法介紹的各個部分，我們都會穿插實際的算例，通過具體的數值計算過程來加深讀者對算法的理解。同時，我們會討論算法的實現細節，例如步長選擇策略、終止條件等，並分析不同算法在麵對不同類型問題時的性能錶現。 第三部分：特殊類型與高級主題 在掌握瞭非綫性規劃的基礎理論和經典算法之後，本部分將進一步拓展視野，探討一些特殊類型的非綫性規劃問題和更高級的主題。 我們會首先關注二次規劃（Quadratic Programming, QP）。盡管二次規劃是綫性規劃的一個特例，但其目標函數為二次，約束為綫性的形式，使得它成為許多更復雜優化問題的基礎。我們會介紹求解二次規劃的專用算法，例如Lemke-Howton算法，並分析其在理論和實踐中的意義。 接著，我們會討論凸優化問題。凸優化因其能夠保證找到全局最優解而備受關注。我們將詳細闡述凸優化的定義，包括凸函數、凸集以及凸優化問題的標準形式。我們會介紹求解凸優化問題的各種高效算法，例如梯度下降法、牛頓法、內點法等在凸優化問題上的應用，並重點分析它們的收斂性保證。 對於非凸優化問題，雖然全局最優解難以保證，但局部最優解仍然具有重要意義。本部分將探討如何識彆和查找局部最優解，並討論一些旨在避免陷入“糟糕”局部最優的啓發式方法或全局優化技術。 此外，我們還將介紹一些高級主題，例如求解非綫性規劃的全局優化方法，包括模擬退火、遺傳算法等啓發式方法，以及一些確定性的全局優化方法（如分支定界法）。我們會探討這些方法的原理、優缺點以及適用場景。 我們還會觸及大規模非綫性規劃的求解，討論在處理維度極高或問題規模巨大的情況下，需要采取的特殊策略，例如降維技術、並行計算方法等。 第四部分：實際應用 理論與算法的最終目的是解決實際問題。本部分將通過一係列來自不同工程和科學領域的實際案例，展示非綫性規劃的強大應用能力。 在工程設計領域，我們將展示如何利用非綫性規劃來優化結構設計、電路布局、工藝參數等。例如，在機械工程中，可能需要最小化材料用量同時保證結構強度，這就可能轉化為一個非綫性規劃問題。 在金融工程領域，非綫性規劃被廣泛應用於投資組閤優化、風險管理、期權定價等方麵。我們會介紹如何將這些金融問題建模為非綫性規劃問題，並討論相應的求解方法。 在機器學習領域，許多模型的訓練過程本質上就是求解一個非綫性優化問題。例如，訓練神經網絡中的損失函數最小化問題，常常需要藉助非綫性規劃算法。我們會介紹梯度下降及其變種在機器學習中的應用。 在運營研究領域，非綫性規劃也扮演著重要角色，例如在生産調度、資源分配、供應鏈管理等方麵。我們會通過具體案例展示如何建立非綫性規劃模型來解決這些實際問題。 在每個應用案例中，我們都會詳細介紹問題的背景、數學建模的過程、所選用的求解算法以及結果的解釋。通過這些生動的實例，讀者將深刻體會到非綫性規劃作為一種強大的數學工具，在解決現實世界復雜問題中的價值。 學習資源與方法 本書作為一本雙語教學用書，提供瞭中英文對照的術語和解釋，方便不同語言背景的學習者。每章末尾都附有習題，涵蓋瞭理論推導、算法分析和問題建模等多個方麵，旨在幫助讀者鞏固所學知識。對於有誌於深入研究的讀者，我們還會提供進一步閱讀的參考書目和相關文獻。 本書的編寫風格力求清晰、嚴謹，同時注重概念的直觀性和方法的實用性。我們希望通過本書的學習，讀者不僅能掌握非綫性規劃的理論精髓，更能靈活運用各種算法來解決實際問題，為他們在各自的領域發展奠定堅實的數學基礎。 緻謝 （此處可根據實際情況添加緻謝內容，例如感謝提供資料、審閱意見的專傢，或對本書編寫做齣貢獻的個人等。） （本內容旨在介紹本書的整體結構和涵蓋的知識點，並非本書的實際內容。）

評分☆☆☆☆☆

這本書的封麵，簡單到極緻，卻又蘊含著某種哲思。那不是隨便一個設計師就能做齣來的，它似乎在無聲地訴說著非綫性規劃的精髓——那些蜿蜒麯摺、難以捉摸卻又最終指嚮最優解的路徑。我之前接觸過一些關於綫性規劃的書籍，覺得它們相對來說比較“直白”，問題和解法都比較容易理解。但非綫性規劃，正如其名，總給我一種“深不可測”的感覺。它的目標函數和約束條件可能包含平方項、指數項，甚至更復雜的函數，這使得求解的難度呈幾何級數增長。我一直好奇，那些在工業生産、金融投資、人工智能等領域看似“神奇”的優化決策，背後究竟隱藏著怎樣的數學原理？這本書，以其“雙語教學用書”的身份，承諾瞭內容上的嚴謹性和國際視野，這讓我對它充滿瞭期待。我希望能在這本書中找到解答，理解那些非綫性的約束如何被巧妙地處理，那些復雜的算法是如何被設計齣來以應對挑戰的。

評分☆☆☆☆☆

書的紙張質感非常棒，拿在手裏有一種踏實的感覺，不是那種廉價的、容易泛黃的紙。封麵設計低調而富有內涵，沒有那些花裏鬍哨的圖案，卻能精準地傳達齣“非綫性規劃”這個主題的學術氣質。作為一個對量化分析充滿興趣的金融從業者，我深知非綫性關係在金融市場中無處不在。比如，資産的風險和收益之間可能存在非綫性關係，投資組閤的優化也常常需要考慮這些復雜的交互作用。我之前嘗試過閱讀一些關於金融優化的書籍，但很多都直接跳到瞭模型和算法，而缺乏對非綫性規劃基礎理論的深入講解。這本《非綫性規劃（第3版）》以“雙語教學用書”的麵貌齣現，讓我看到瞭它係統性、嚴謹性以及國際化的視野，我希望它能幫助我搭建起堅實的理論基礎，從而更好地理解和應用非綫性規劃在金融領域中的各種模型和方法。

評分☆☆☆☆☆

拿到這本書的那一刻，我就被它沉甸甸的重量和精美的裝幀所吸引。清華齣品，本身就意味著品質的保證，而“雙語教學用書”更是讓我看到瞭它在教學和科研領域的專業定位。我一直認為，學習非綫性規劃，不僅僅是掌握一套算法，更重要的是理解其背後的思想和方法論。很多現實世界的問題，都無法用簡單的綫性模型來描述，這時候就需要非綫性規劃的工具來捕捉更精細的規律。我之前在一些行業應用的文章中看到過非綫性規劃的身影，比如在資源分配、生産調度、投資組閤優化等方麵，它都能發揮巨大的作用。然而，對於其中的具體細節，我總是感到有些模糊。這本書的齣現，對我來說，就像是一盞明燈，指引著我深入瞭解非綫性規劃的理論體係和實際應用。我尤其期待它在算法介紹和案例分析方麵的深度，希望能從中獲得解決實際問題的靈感和方法。

評分☆☆☆☆☆

一本厚重的書，沉甸甸地躺在書桌上，翻開它，撲麵而來的是嚴謹的學術氣息，紙張的觸感很舒服，散發著淡淡的書香。封麵設計簡潔大氣，幾個簡單的幾何圖形和文字，卻恰恰點明瞭這本書的主題。作為一個對數學建模和優化問題略有涉獵的業餘愛好者，我一直對非綫性規劃這個領域充滿好奇，但又苦於難以找到係統深入的學習資料。市麵上的一些書籍要麼過於理論化，讓初學者望而卻步，要麼過於簡化，無法觸及問題的本質。而這本《非綫性規劃（第3版）》的齣現，似乎正是我一直在尋找的那一本。從書本的裝幀和排版來看，它都顯得十分專業，雙語教學用書的定位更是讓人眼前一亮，這對於我這樣希望接觸國際前沿知識，同時又希望能夠理解透徹的讀者來說，無疑是巨大的福音。我期待著這本書能帶我領略非綫性規劃的魅力，解決那些看似復雜卻又充滿規律的優化難題。

評分☆☆☆☆☆

當這本書靜靜地躺在桌麵上時，我仿佛能感受到其中蘊含的強大力量。它的厚度，不僅是紙張的堆疊，更是知識的積纍和智慧的沉澱。作為一名對計算科學和人工智能領域有著濃厚興趣的學生，我經常在論文和研究報告中遇到“非綫性規劃”這個詞。它就像是解決復雜優化問題的一把瑞士軍刀，在機器學習模型的訓練、機器人路徑規劃、資源調度優化等眾多領域都有著舉足輕重的地位。然而，對於非綫性規劃的深入理解，我一直覺得有所欠缺。這本書，以“第3版”的更新和“雙語教學用書”的定位，讓我看到瞭它在理論深度和教學實用性上的雙重追求。我非常期待這本書能夠帶領我穿越非綫性規劃的迷宮，理解那些看似復雜但又遵循一定規律的數學模型，掌握那些強大的求解算法，並最終能夠將這些知識融會貫通，應用於我所熱愛的計算科學研究中。