本書為中法卓越工程師培養(yǎng)工程系列教材之一。全書共五章，主要內(nèi)容包括：凸分析基礎(chǔ)、線性規(guī)劃、拉格朗日對偶理論、KKT 性條件等。此外，本書還介紹了MATLAB 和 CPLEX 優(yōu)化建模軟件的使用。書中對相關(guān)定理給出了詳細(xì)的證明過程，且每章都配有例題和習(xí)題供讀者參閱和練習(xí)。書中某些重要例題除給出傳統(tǒng)計(jì)算或證明外，還結(jié)合優(yōu)化建模軟件進(jìn)行了數(shù)值驗(yàn)算或圖像說明，方便讀者學(xué)習(xí)和理解。閱讀本書需要數(shù)學(xué)分析、拓?fù)洹⒕�性代數(shù)和微分計(jì)算的基礎(chǔ)知識，在本書章中簡要回顧了上述知識。書末附有法 / 英 / 漢三語關(guān)鍵詞索引，方便讀者檢索。本書可作為具有一定法語基礎(chǔ)的高年級本科生或研究生的化理論課程教材，也可供相關(guān)研究人員閱讀參考。
上海交大－巴黎高科卓越工程師學(xué)院（以下簡稱交大巴黎高科學(xué)院）創(chuàng)立于 2012年，由上海交通大學(xué)與法國巴黎高科工程師集團(tuán)（以下簡稱巴黎高科集團(tuán)）為響應(yīng)教育部提出的卓越工程師教育培養(yǎng)計(jì)劃而合作創(chuàng)辦的，旨在借鑒法國高等工程師學(xué)校的教育體系和先進(jìn)理念，致力于培養(yǎng)符合當(dāng)代社會(huì)發(fā)展需要的高水平工程師人才。法國高等工程師教育屬于精英教育體系，具有規(guī)模小、專業(yè)化程度高、重視實(shí)習(xí)實(shí)踐等特色。法國工程師學(xué)校實(shí)行多次嚴(yán)格的選拔，篩選優(yōu)秀高中畢業(yè)生通過 2 年預(yù)科基礎(chǔ)階段進(jìn)入工程師學(xué)校就讀。此類學(xué)校通過教學(xué)緊密結(jié)合實(shí)際的全方位培養(yǎng)模式，使其畢業(yè)生具備精良的工程技術(shù)能力，優(yōu)秀的實(shí)踐、管理能力與寬廣的國際視野、強(qiáng)烈的創(chuàng)新意識，為社會(huì)輸送了大批實(shí)用型、專家型的人才，包括許多國家領(lǐng)導(dǎo)人、學(xué)者、企業(yè)高層管理人員。巴黎高科集團(tuán)匯集了全法富聲譽(yù)的 12 所工程師學(xué)校。上海交通大學(xué)是我國歷史悠久、享譽(yù)海內(nèi)外的高等學(xué)府之一，經(jīng)過 120 余年的不斷歷練開拓，已然成為集綜合性、研究性、國際化于一體的國內(nèi)一流、國際知名大學(xué)。此次與巴黎高科集團(tuán)強(qiáng)強(qiáng)聯(lián)手，創(chuàng)立了獨(dú)特的預(yù)科基礎(chǔ)階段 工程師階段人才培養(yǎng)計(jì)劃，交大巴黎高科學(xué)院學(xué)制為4 年本科 2.5 年碩士研究生。其中初三年的預(yù)科基礎(chǔ)階段不分專業(yè)，課程以數(shù)學(xué)、計(jì)算機(jī)和物理、化學(xué)為主，目的是讓學(xué)生具備扎實(shí)的數(shù)理化基礎(chǔ)，構(gòu)建全面完整的知識體系，具備獨(dú)立思考和解決問題的實(shí)踐能力等。預(yù)科基礎(chǔ)教育階段對于學(xué)生而言，是隨后工程師專業(yè)階段乃至日后整個(gè)職業(yè)生涯的基礎(chǔ)，其重要性顯而易見。
交大巴黎高科學(xué)院引進(jìn)法國工程師預(yù)科教育階段的大平臺(tái)教學(xué)制度，即在基礎(chǔ)教育階段不分專業(yè)，強(qiáng)調(diào)打下堅(jiān)實(shí)的數(shù)理基礎(chǔ)。首先，學(xué)院注重系統(tǒng)性的學(xué)習(xí)，每周設(shè)有與理論課配套的習(xí)題課、實(shí)驗(yàn)課，加強(qiáng)知識鞏固和實(shí)踐。再者，學(xué)院注重跨學(xué)科及理論在現(xiàn)實(shí)生活中的應(yīng)用。所有課程均由同一位教師或一個(gè)教學(xué)團(tuán)隊(duì)連貫地完成，這為實(shí)現(xiàn)跨學(xué)科教育奠定了關(guān)鍵性的基礎(chǔ)。一些重要的數(shù)理課程會(huì)周期性地循環(huán)出現(xiàn)，且難度逐漸上升，幫助學(xué)生數(shù)往知來并學(xué)會(huì)觸類旁通、舉一反三。后，學(xué)院注重系統(tǒng)性的考核方式，定期有口試、家庭作業(yè)和階段考試，以便時(shí)時(shí)掌握學(xué)生的學(xué)習(xí)情況。
交大巴黎高科學(xué)院創(chuàng)辦至今，已有將近 8 個(gè)年頭，預(yù)科基礎(chǔ)階段也已經(jīng)過 9 屆學(xué)生的不斷探索實(shí)踐。學(xué)院積累了一定的教育培養(yǎng)經(jīng)驗(yàn)，歸納、沉淀、推廣這些辦學(xué)經(jīng)驗(yàn)都適逢其時(shí)。因此交大巴黎高科學(xué)院與上海交通大學(xué)出版社聯(lián)合策劃出版中法卓越工程師培養(yǎng)工程系列圖書。
劉增路
2020 年 9 月于
上海交通大學(xué)
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)任上海交通大學(xué)巴黎高科卓越工程師學(xué)院和數(shù)學(xué)科學(xué)學(xué)院教授，博士生導(dǎo)師。2001年赴法國留學(xué)就讀法國國家應(yīng)用科學(xué)院，分別于2006年獲工程數(shù)學(xué)、理論和應(yīng)用數(shù)學(xué)雙碩士學(xué)位，并于2010年獲該校數(shù)學(xué)博士學(xué)位，并榮獲法國博士論文榮譽(yù)獎(jiǎng)，師從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
書單推薦
