最优化理论和算法（法文版）

上海交大－巴黎高科卓越工程师学院（以下简称交大巴黎高科学院）创立于 2012年，由上海交通大学与法国巴黎高科工程师集团（以下简称巴黎高科集团）为响应*提出的“卓越工程师教育培养计划”而合作创办的，旨在借鉴法国高等工程师学校的教育体系和先进理念，致力于培养符合当代社会发展需要的高水平工程师人才。法国高等工程师教育属于精英教育体系，具有规模小、专业化程度高、重视实习实践等特色。法国工程师学校实行多次严格的选拔，筛选优秀高中毕业生通过 2 年预科基础阶段进入工程师学校就读。此类学校通过教学紧密结合实际的全方位培养模式，使其毕业生具备精良的工程技术能力，优秀的实践、管理能力与宽广的国际视野、强烈的创新意识，为社会输送了大批实用型、专家型的人才，包括许多国家领导人、学者、企业高层管理人员。巴黎高科集团汇集了全法富声誉的 12 所工程师学校。上海交通大学是我国历史悠久、享誉海内外的高等学府之一，经过 120 余年的不断历练开拓，已然成为集“综合性、研究性、国际化”于一体的国内一流、国际知名大学。此次与巴黎高科集团强强联手，创立了独特的“预科基础阶段 工程师阶段”人才培养计划，交大巴黎高科学院学制为“4 年本科 2.5 年硕士研究生”。其中初三年的“预科基础阶段”不分专业，课程以数学、计算机和物理、化学为主，目的是让学生具备扎实的数理化基础，构建全面完整的知识体系，具备独立思考和解决问题的实践能力等。预科基础教育阶段对于学生而言，是随后工程师专业阶段乃至日后整个职业生涯的基础，其重要性显而易见。

交大巴黎高科学院引进法国工程师预科教育阶段的大平台教学制度，即在基础教育阶段不分专业，强调打下坚实的数理基础。首先，学院注重系统性的学习，每周设有与理论课配套的习题课、实验课，加强知识巩固和实践。再者，学院注重跨学科及理论在现实生活中的应用。所有课程均由同一位教师或一个教学团队连贯地完成，这为实现跨学科教育奠定了关键性的基础。一些重要的数理课程会周期性地循环出现，且难度逐渐上升，帮助学生数往知来并学会触类旁通、举一反三。后，学院注重系统性的考核方式，定期有口试、家庭作业和阶段考试，以便时时掌握学生的学习情况。

交大巴黎高科学院创办至今，已有将近 8 个年头，预科基础阶段也已经过 9 届学生的不断探索实践。学院积累了一定的教育培养经验，归纳、沉淀、推广这些办学经验都适逢其时。因此交大巴黎高科学院与上海交通大学出版社联合策划出版“中法卓越工程师培养工程”系列图书。

刘增路

2020 年 9 月于

上海交通大学

Ce livre est à l’origine un polycopié du cours d’optimisation depuis 2015 pourles étudiants en 3ème année à l’École d’ingénieur SJTU-Paritech (SPEIT), situéesur la campus Minhang de l’Université 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 l’Université 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 l’information.

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 d’applications en pratique dans l’industrie et l’ingé-nierie comme l’optimisation linéaire et l’algorithme du simplexe, l’analyse convexe, et les outils fondamentaux pour l’optimisation non-linéaire (par exemple, la théorie de dualité et les conditions d’optimalité).

Ce livre est découpé en 5 chapitres :

— L’introduction sur l’optimisation, 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) ;

— L’analyse 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 l’ensemble convexe, lemme de Farkas et de Gordan, fonction convexe et extension sur la fonction D.C.) ;

— L’optimisation linéaire et l’algorithme du simplexe (forme standard, solutionde base, l’algorithme du simplexe version tableau, méthode de deux phases, et règles d’anti-cyclage) ;

— La théorie de dualité Lagrangienne (point-selle, problème min-max, et dua lité de Lagrange) ;

— Les conditions d’optimalité KKT (direction réalisable et direction de des cente, qualification de contrainte, conditions d’optimalité d’ordre 1 et 2 pour les problèmes d’optimisation sans contrainte et sous ontraintes) ;

Concernant la modélisation et l’optimisation en informatique, nous utilisons le toolbox d’optimisation de MATLAB et le logiciel CPLEX. L’apprentissage de ces logiciels et les réalisations sur les algorithmes classiques (par exemple, l’algorithme du simplexe et l’algorithme du gradient) font partie du cours de TP (travaux pratiques).Bien noté, l’apprentissage par cœur est, en général, une mauvaise technique d’apprentissage 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 d’optimisation en science et en

ingénierie.

Les volumes de ce livre sont en constante évolution, grâce aux remarques et auxsuggestions des professeurs et élèves de l’institut. Je tiens à remercier mes collègues Alain Chillès, Marguerite Rossillon et Geoffrey Boutard pour la relecture du poly copié et leurs collaborations sur l’enseignement d’une 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 l’institut et à tout

membre de l’équipe de mathématiques au SPEIT, ce livre n’aurait 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

本书为“中法卓越工程师培养工程”系列教材之一。全书共五章，主要内容包括：凸分析基础、线性规划、拉格朗日对偶理论、KKT 性条件等。此外，本书还介绍了MATLAB 和 CPLEX 优化建模软件的使用。书中对相关定理给出了详细的证明过程，且每章都配有例题和习题供读者参阅和练习。书中某些重要例题除给出传统计算或证明外，还结合优化建模软件进行了数值验算或图像说明，方便读者学习和理解。阅读本书需要数学分析、拓扑、线性代数和微分计算的基础知识，在本书章中简要回顾了上述知识。书末附有法 / 英 / 汉三语关键词索引，方便读者检索。本书可作为具有一定法语基础的高年级本科生或研究生的化理论课程教材，也可供相关研究人员阅读参考。

牛一帅，男，上海人，现任上海交通大学巴黎高科卓越工程师学院和数学科学学院教授，博士生导师。2001年赴法国留学就读法国国家应用科学院，分别于2006年获工程数学、理论和应用数学双硕士学位，并于2010年获该校数学博士学位，并荣获法国博士论文“荣誉奖”，师从DC规划之父Pham Dinh Tao教授。

1 Introduction de l’optimisation

1

1.1 Brève histoire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2

1.2 Définition du problème d’optimisation . . . . . . . . . . . . . . . . .3

1.3 Classes des problèmes d’optimisation . . . . . . . . . . . . . . . . . .4

1.4 Rappels mathématiques pour l’optimisation . . . . . . . . . . . . . .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 d’optimisation linéaire . . . . . . . . . . . . . . . . . . . . 65

3.2 Solution d’optimisation linéaire . . . . . . . . . . . . . . . . . . . . . 67

3.2.1 Théorème d’existence de solution optimale d’optimisation 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 d’anti-cyclage . . . . . . . . . . . . . . . . . . . . . . . 93

3.3.6 Logiciels pour l’optimisation 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 d’optimalité

114

5.1 Direction réalisable et Direction de descente . . . . . . . . . . . . . . 114

5.2 Conditions d’optimalité du problème d’optimisation sans contrainte . 116

5.3 Conditions d’optimalité du problème d’optimisation sous contraintesd’iné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