本書為中法卓越工程師培養(yǎng)工程系列教材之一。全書共五章，主要內容包括：凸分析基礎、線性規(guī)劃、拉格朗日對偶理論、KKT 性條件等。此外，本書還介紹了MATLAB 和 CPLEX 優(yōu)化建模軟件的使用。書中對相關定理給出了詳細的證明過程，且每章都配有例題和習題供讀者參閱和練習。書中某些重要例題除給出傳統(tǒng)計算或證明外，還結合優(yōu)化建模軟件進行了數(shù)值驗算或圖像說明，方便讀者學習和理解。閱讀本書需要數(shù)學分析、拓撲、線性代數(shù)和微分計算的基礎知識，在本書章中簡要回顧了上述知識。書末附有法 / 英 / 漢三語關鍵詞索引，方便讀者檢索。本書可作為具有一定法語基礎的高年級本科生或研究生的化理論課程教材，也可供相關研究人員閱讀參考。
上海交大－巴黎高科卓越工程師學院（以下簡稱交大巴黎高科學院）創(chuàng)立于 2012年，由上海交通大學與法國巴黎高科工程師集團（以下簡稱巴黎高科集團）為響應教育部提出的卓越工程師教育培養(yǎng)計劃而合作創(chuàng)辦的，旨在借鑒法國高等工程師學校的教育體系和先進理念，致力于培養(yǎng)符合當代社會發(fā)展需要的高水平工程師人才。法國高等工程師教育屬于精英教育體系，具有規(guī)模小、專業(yè)化程度高、重視實習實踐等特色。法國工程師學校實行多次嚴格的選拔，篩選優(yōu)秀高中畢業(yè)生通過 2 年預科基礎階段進入工程師學校就讀。此類學校通過教學緊密結合實際的全方位培養(yǎng)模式，使其畢業(yè)生具備精良的工程技術能力，優(yōu)秀的實踐、管理能力與寬廣的國際視野、強烈的創(chuàng)新意識，為社會輸送了大批實用型、專家型的人才，包括許多國家領導人、學者、企業(yè)高層管理人員。巴黎高科集團匯集了全法富聲譽的 12 所工程師學校。上海交通大學是我國歷史悠久、享譽海內外的高等學府之一，經(jīng)過 120 余年的不斷歷練開拓，已然成為集綜合性、研究性、國際化于一體的國內一流、國際知名大學。此次與巴黎高科集團強強聯(lián)手，創(chuàng)立了獨特的預科基礎階段 工程師階段人才培養(yǎng)計劃，交大巴黎高科學院學制為4 年本科 2.5 年碩士研究生。其中初三年的預科基礎階段不分專業(yè)，課程以數(shù)學、計算機和物理、化學為主，目的是讓學生具備扎實的數(shù)理化基礎，構建全面完整的知識體系，具備獨立思考和解決問題的實踐能力等。預科基礎教育階段對于學生而言，是隨后工程師專業(yè)階段乃至日后整個職業(yè)生涯的基礎，其重要性顯而易見。
交大巴黎高科學院引進法國工程師預科教育階段的大平臺教學制度，即在基礎教育階段不分專業(yè)，強調打下堅實的數(shù)理基礎。首先，學院注重系統(tǒng)性的學習，每周設有與理論課配套的習題課、實驗課，加強知識鞏固和實踐。再者，學院注重跨學科及理論在現(xiàn)實生活中的應用。所有課程均由同一位教師或一個教學團隊連貫地完成，這為實現(xiàn)跨學科教育奠定了關鍵性的基礎。一些重要的數(shù)理課程會周期性地循環(huán)出現(xiàn)，且難度逐漸上升，幫助學生數(shù)往知來并學會觸類旁通、舉一反三。后，學院注重系統(tǒng)性的考核方式，定期有口試、家庭作業(yè)和階段考試，以便時時掌握學生的學習情況。
交大巴黎高科學院創(chuàng)辦至今，已有將近 8 個年頭，預科基礎階段也已經(jīng)過 9 屆學生的不斷探索實踐。學院積累了一定的教育培養(yǎng)經(jīng)驗，歸納、沉淀、推廣這些辦學經(jīng)驗都適逢其時。因此交大巴黎高科學院與上海交通大學出版社聯(lián)合策劃出版中法卓越工程師培養(yǎng)工程系列圖書。
劉增路
2020 年 9 月于
上海交通大學
Ce livre est à lorigine un polycopié du cours doptimisation depuis 2015 pourles étudiants en 3ème année à lÉcole dingénieur SJTU-Paritech (SPEIT), situéesur la campus Minhang de lUniversité Shanghai Jiao Tong en Chine. Cette école rassemble des 4 Grandes Écoles françaises de premier plan (École Polytechnique de Paris, Mines ParisTech, Télécom ParisTech et ENSTA ParisTech) et lUniversité Shanghai Jiao Tong pour apporter à des étudiants chinois et internationaux à fort potentiel une formation leur permettant de devenir des leaders industriels et des innovateurs possédant un large spectre de connaissances scientifiques, la
capacité dévoluer avec aisance dans un milieu professionnel multiculturel, et des connaissances approfondies dans une spécialité : Ingénierie mécanique, Ingénierie en énergie et puissance, Ingénierie de linformation.
Selon les besoins spécifiques des spécialisations concernées, ce cours est une in troduction en optimisation linéaire et non-linéaire, notamment sur des théories et algorithmes qui ont beaucoup dapplications en pratique dans lindustrie et lingé-nierie comme loptimisation linéaire et lalgorithme du simplexe, lanalyse convexe, et les outils fondamentaux pour loptimisation non-linéaire (par exemple, la théorie de dualité et les conditions doptimalité).
Ce livre est découpé en 5 chapitres :
Lintroduction sur loptimisation, la modélisation mathématique et les rap pels des notions mathématiques utiles en optimisation (norme vectorielle et matricielle, suite numérique dans Rn , topologie et calcul différentiel des fonctions de plusieurs variables) ;
Lanalyse convexe (ensemble convexe, combinaison linéaire, convexe, affffine et positive, théorème de Carathéodory, projection et séparation, point ex trémal et direction extrémale, théorème de représentation de lensemble convexe, lemme de Farkas et de Gordan, fonction convexe et extension sur la fonction D.C.) ;
Loptimisation linéaire et lalgorithme du simplexe (forme standard, solutionde base, lalgorithme du simplexe version tableau, méthode de deux phases, et règles danti-cyclage) ;
La théorie de dualité Lagrangienne (point-selle, problème min-max, et dua lité de Lagrange) ;
Les conditions doptimalité KKT (direction réalisable et direction de des cente, qualification de contrainte, conditions doptimalité dordre 1 et 2 pour les problèmes doptimisation sans contrainte et sous ontraintes) ;
Concernant la modélisation et loptimisation en informatique, nous utilisons le toolbox doptimisation de MATLAB et le logiciel CPLEX. Lapprentissage de ces logiciels et les réalisations sur les algorithmes classiques (par exemple, lalgorithme du simplexe et lalgorithme du gradient) font partie du cours de TP (travaux pratiques).Bien noté, lapprentissage par cur est, en général, une mauvaise technique dapprentissage pour les mathématiques. Nous conseillons une compréhension approfondie des théorèmes et des algorithmes afin de pouvoir utiliser correctement ces outils puissants pour résoudre des problèmes doptimisation en science et en
ingénierie.
Les volumes de ce livre sont en constante évolution, grce aux remarques et auxsuggestions des professeurs et élèves de linstitut. Je tiens à remercier mes collègues Alain Chillès, Marguerite Rossillon et Geoffrey Boutard pour la relecture du poly copié et leurs collaborations sur lenseignement dune partie des travaux pratiques. Je remercie également mes étudiants et en particulier mon doctorant Faouzi Moha med Benammour qui, par leur relecture et commentaires sur le matériel pendant lecours, ont conduit à de nombreuses améliorations dans la présentation. Je voudrais également exprimer ma profonde gratitude aux directeurs de linstitut et à tout
membre de léquipe de mathématiques au SPEIT, ce livre naurait pas pu voir le jour sans leurs encouragements et leurs soutiens.Enfin, je remercie tous les membres de ma famille pour leur compagnie et leur
amour éternel.
Université Shanghai Jiao Tong
Janvier 2021
Yi-Shuai Niu
牛一帥，男，上海人，現(xiàn)任上海交通大學巴黎高科卓越工程師學院和數(shù)學科學學院教授，博士生導師。2001年赴法國留學就讀法國國家應用科學院，分別于2006年獲工程數(shù)學、理論和應用數(shù)學雙碩士學位，并于2010年獲該校數(shù)學博士學位，并榮獲法國博士論文榮譽獎，師從DC規(guī)劃之父Pham Dinh Tao教授。
1 Introduction de loptimisation
1
1.1 Brève histoire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2
1.2 Définition du problème doptimisation . . . . . . . . . . . . . . . . .3
1.3 Classes des problèmes doptimisation . . . . . . . . . . . . . . . . . .4
1.4 Rappels mathématiques pour loptimisation . . . . . . . . . . . . . .5
1.4.1 Normes vectorielles et matricielles . . . . . . . . . . . . . . .5
1.4.2 Suite numérique dans Rn. . . . . . . . . . . . . . . . . . . . 12
1.4.3 Topologie dans Rn. . . . . . . . . . . . . . . . . . . . . . . . 13
1.4.4 Fonctions de plusieurs variables et calcul différentiel . . . . . 17
2 Analyse convexe
25
2.1 Ensemble convexe . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.1.1 Ensemble convexe . . . . . . . . . . . . . . . . . . . . . . . . 25
2.1.2 Combinaison linéaire, convexe, affffine et positive . . . . . . . . 30
2.1.3 Théorème de Carathéodory . . . . . . . . . . . . . . . . . . . 36
2.1.4 Projection et Séparation . . . . . . . . . . . . . . . . . . . . . 38
2.1.5 Point extrémal et Direction extrémale . . . . . . . . . . . . . 44
2.1.6 Théorème de représentation . . . . . . . . . . . . . . . . . . . 47
2.1.7 Lemme de Farkas et de Gordan . . . . . . . . . . . . . . . . . 49
2.2 Fonction convexe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
2.2.1 Fonction convexe . . . . . . . . . . . . . . . . . . . . . . . . . 52
2.2.2 Fonction D.C. . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
3 Optimisation Linéaire
65
3.1 Problème doptimisation linéaire . . . . . . . . . . . . . . . . . . . . 65
3.2 Solution doptimisation linéaire . . . . . . . . . . . . . . . . . . . . . 67
3.2.1 Théorème dexistence de solution optimale doptimisation linéaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
3.2.2 Solution de base . . . . . . . . . . . . . . . . . . . . . . . . . 69
3.3 Méthodes de résolution du problème (OL) . . . . . . . . . . . . . . . 75
3.3.1 Méthode graphique . . . . . . . . . . . . . . . . . . . . . . . . 75
3.3.2 Algorithme du simplexe . . . . . . . . . . . . . . . . . . . . . 76
3.3.3 Tableau du simplexe . . . . . . . . . . . . . . . . . . . . . . . 85
3.3.4 Méthode des deux phases . . . . . . . . . . . . . . . . . . . . 89
3.3.5 Règles danti-cyclage . . . . . . . . . . . . . . . . . . . . . . . 93
3.3.6 Logiciels pour loptimisation linéaire . . . . . . . . . . . . . . 97
4 Théorie de dualité
104
4.1 Problème dual et point-selle . . . . . . . . . . . . . . . . . . . . . . . 104
4.2 Dualité de Lagrange . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
5 Conditions doptimalité
114
5.1 Direction réalisable et Direction de descente . . . . . . . . . . . . . . 114
5.2 Conditions doptimalité du problème doptimisation sans contrainte . 116
5.3 Conditions doptimalité du problème doptimisation sous contraintesdinégalités et dégalités . . . . . . . . . . . . . . . . . . . . . . . . . 118
5.3.1 Contrainte active et qualification de contrainte . . . . . . . . 118
5.3.2 Qualifications des contraintes usuelles . . . . . . . . . . . . . 120
5.3.3 Conditions de Karush-Kuhn-Tucker . . . . . . . . . . . . . . 123
Bibliographie
134
Index des définitions
135
Index des théorèmes
139
書單推薦
