本书为中法卓越工程师培养工程系列教材之一。全书共五章，主要内容包括：凸分析基础、线性规划、拉格朗日对偶理论、KKT 性条件等。此外，本书还介绍了MATLAB 和 CPLEX 优化建模软件的使用。书中对相关定理给出了详细的证明过程，且每章都配有例题和习题供读者参阅和练习。书中某些重要例题除给出传统计算或证明外，还结合优化建模软件进行了数值验算或图像说明，方便读者学习和理解。阅读本书需要数学分析、拓扑、线性代数和微分计算的基础知识，在本书章中简要回顾了上述知识。书末附有法 / 英 / 汉三语关键词索引，方便读者检索。本书可作为具有一定法语基础的高年级本科生或研究生的化理论课程教材，也可供相关研究人员阅读参考。
上海交大－巴黎高科卓越工程师学院（以下简称交大巴黎高科学院）创立于 2012年，由上海交通大学与法国巴黎高科工程师集团（以下简称巴黎高科集团）为响应教育部提出的卓越工程师教育培养计划而合作创办的，旨在借鉴法国高等工程师学校的教育体系和先进理念，致力于培养符合当代社会发展需要的高水平工程师人才。法国高等工程师教育属于精英教育体系，具有规模小、专业化程度高、重视实习实践等特色。法国工程师学校实行多次严格的选拔，筛选优秀高中毕业生通过 2 年预科基础阶段进入工程师学校就读。此类学校通过教学紧密结合实际的全方位培养模式，使其毕业生具备精良的工程技术能力，优秀的实践、管理能力与宽广的国际视野、强烈的创新意识，为社会输送了大批实用型、专家型的人才，包括许多国家领导人、学者、企业高层管理人员。巴黎高科集团汇集了全法富声誉的 12 所工程师学校。上海交通大学是我国历史悠久、享誉海内外的高等学府之一，经过 120 余年的不断历练开拓，已然成为集综合性、研究性、国际化于一体的国内一流、国际知名大学。此次与巴黎高科集团强强联手，创立了独特的预科基础阶段 工程师阶段人才培养计划，交大巴黎高科学院学制为4 年本科 2.5 年硕士研究生。其中初三年的预科基础阶段不分专业，课程以数学、计算机和物理、化学为主，目的是让学生具备扎实的数理化基础，构建全面完整的知识体系，具备独立思考和解决问题的实践能力等。预科基础教育阶段对于学生而言，是随后工程师专业阶段乃至日后整个职业生涯的基础，其重要性显而易见。
交大巴黎高科学院引进法国工程师预科教育阶段的大平台教学制度，即在基础教育阶段不分专业，强调打下坚实的数理基础。首先，学院注重系统性的学习，每周设有与理论课配套的习题课、实验课，加强知识巩固和实践。再者，学院注重跨学科及理论在现实生活中的应用。所有课程均由同一位教师或一个教学团队连贯地完成，这为实现跨学科教育奠定了关键性的基础。一些重要的数理课程会周期性地循环出现，且难度逐渐上升，帮助学生数往知来并学会触类旁通、举一反三。后，学院注重系统性的考核方式，定期有口试、家庭作业和阶段考试，以便时时掌握学生的学习情况。
交大巴黎高科学院创办至今，已有将近 8 个年头，预科基础阶段也已经过 9 届学生的不断探索实践。学院积累了一定的教育培养经验，归纳、沉淀、推广这些办学经验都适逢其时。因此交大巴黎高科学院与上海交通大学出版社联合策划出版中法卓越工程师培养工程系列图书。
刘增路
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
牛一帅，男，上海人，现任上海交通大学巴黎高科卓越工程师学院和数学科学学院教授，博士生导师。2001年赴法国留学就读法国国家应用科学院，分别于2006年获工程数学、理论和应用数学双硕士学位，并于2010年获该校数学博士学位，并荣获法国博士论文荣誉奖，师从DC规划之父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
书单推荐
