Từ Tối ưu Lồi đến Tối ưu không Lồi

Giáo sư Phạm Đình Tảo, INSA‐Rouen, Pháp

Số tiết: 30 tiết

Thời gian học: 12/1/2009 – 18/1/2009 (một buổi / ngày)

Thời gian học để trang bị các kiến thức cơ bản: 3/1/2009 – 9/1/2009 (không học ngày chủ nhật) do giáo viên Nguyễn Thị Thu Vân phụ trách.

Tóm tắt môn học: Môn học này gồm có 2 phần A và B. Phần A: trình bày một số kiến thức cơ bản của Tối ưu lồi để làm nền tảng cho phần B. Phần B: mô hình hoá, tối ưu không lồi và tối ưu toàn cục. Các phương pháp trong Tối ưu không lồi trong phần B được áp dụng để giải các bài toán thực tế trình bày trong môn học của Giáo sư Lê Thị Hoài An.

Môn học này được giảng dạy bởi giáo sư Phạm Đình Tảo, một trong những chuyên gia đầu ngành trong lĩnh vực Tối ưu.

Đối tượng tham gia: tất cả các sinh viên đại học, học viên cao học.

Các môn học bắt buộc trước: không

Nội dung môn học:

A. CONVEX OPTIMIZATION : Basic tools of modern convex analysis

I. Convex sets and convex functions taking the infinity value

Operations preserving convexity

Generating functional operations of convex functions Epigraph of a convex function. Infimal convolution. Convex hull of a set and convex hull of a function.

II. Topological properties for sets and functions

Relative interior of a convex set. Lower semicontinuity (lsc) functional. Intérieur relatif d’un ensemble convexe. Semi-continuité inférieure (sci) d’une fonction convexe. Lsc- regularized and ≅- regularized of a convex function.

Asymptote cone of a convex set and characterization of a bounded convex set.

Function asymptote of a convex function. Continuity of a convex function.

III. Duality for sets and functions

Separation of convex sets. Conjugate of a convex function, support function of a convex set polar of a convex set.. Infimal -convolution and functional cnjugacy

IV. Subdifferential calculus for convex functions

Directional derivative and subgradient. Subdifferential and monotonicity. Derivability of convex functions.

V. Duality in convex optimization

Optimality for a convex program, Kuhn-Tucker conditions. Programme convexe Ordinairy convex programs and Lagrangianb multipliers . Lagrange duality and Fenchel duality.

VI. Some basic algorithms in convex optimization.

Reduced gradient algorithm, conjugate gradient algorithm and Lemke method for convex quadratic programs. Subgradient projection method, Kelley’s cutting plane method for nondifferentiable convex programs. Maximal monotone operators and proximal algorithms: Applications to decomposition in convex programming and Augmented Lagrangian methods.. Interior point methods in convex programming. Newton methods

Références bibliographiques

1. A. Auslender : Optimisation. Méthodes Numériques, Masson Paris (1976)

2. J. Cea : Optimisation, Théorie et Algorithmes, Dunod Paris (1971)

3. V.F. Demyanov, L.V. Vasilev : Optimization Software, Inc publications Division, New York (1985)

4. I. Ekeland, R. Temam: Analyse Convexe et Problèmes Variationnels, Dunod, Gauthier-Villars (1974)

5. P.J. Laurent : Approximation et Optimisation : Hermann, Paris (1971)

6. R.T. Rockafellar : Convex Analysis, Princeton University Press, N.J. (1970)

7. J.P. Aubin, P. Nepomiastchy: Méthodes Explicites de l’Optimisation , Dunod (1982)

8. L. Cesari : Optimization, Theory and Applications. Problems with Ordinary Differential Equations, Springer (1983)

9. P.G. Ciarlet: Introduction à l’Analyse Numérique et à l’Optimisation, Masson (1988)

10. M.R. Osborne : Finite Algorithms in Optimization and Data Analysis, Wiley Series (1985)

11. B. Polyak : Introduction to Optimization, Optimization Software, Inc., Publications (1987)

12. B. Pchenitchny, Y. Daniline: Méthodes numériques dans les problèmes d’extrémum. Editions MIR. Moscou (Traduction française 1977)

13. D. Luenberger : Linear and Nonlinear Programming (Second Edition). Addison-Wesley Publishing Company (1989)

14. D. Bertsekas: Constrained Optimization and Lagrange Multiplier Methods. Academic Press (1982)

15. Y. Nesterov, A. Nemiroski : Interior – Point Polynomial Algorithms in Convex Programming. SIAM, Studies in Applied Mathematics (1993)

16. D. Bertsekas: Nonlinear Programming, Athena Scientific, Belmont Massachusetts (1995)

17. R. J. Vanderbei : Linear Programming, Foundations and Extensions. Kluwer Academic

Publishers, 1997

18. D. Bertsekas : Constrained Optimization and lagrange Multiplier Methods, Academic Press (1982)

19. Jean Baptiste Hiriart-Urruty, Claude Lemaréchal: Convex Analysis and Minimization Algorithms, Parts I&II, Springer Verlag (1991)

20. Mokhtar S. Bazaraa, C.M. Shetty: Nonlinear Programming, Parts I&II, John Wiley & Sons, New York (1977)

B. MODELIZATION, OPTIMIZATION NON CONVEXE & GLOBAL OPTIMIZATION

I. Classification of nonconvex programs : Convex maximization , DC programs (minimization of a DC function on a convex set), minimization of a convex function on an intersection of a convex set and a complement of a convex set.

II. DC Programming and DCA

Structure of the space of DC functions. DC duality, DC programs primal and dual. Relations between primal and dual solutions. Local optimality and global optimality in DC programming. Regularization in DC programming. Exact penalty and reformulation in DC Programming.

III. DC Algorithms (DCA)

Description and interpretation of DCA. Choice of DC decompositions in DC programming.

Standard algorithms in convex (resp. nonconvex) programming as special cases of DCA

Modeling and solution of real‐world nonconvex programs by DCA 

IV. Algorithms for solving nonconvex programs 

 

Branch and Bound techniques (BB) for globally solving DC programs

Combination of DCA and BB : Applications to globally solving mixed 0-1 nonconvex quadratic programs and real-world nonconvex programs

Trust region methods for solving nonconvex programs.

V. Applications: modelling of different problems in various areas: (data mining, bioinformatic, signal and image processing, Computer security, Engineering structures, finance,

References

1. R. Horst & H. Tuy : Global Optimization, Deterministic Approaches,

Second, Revised Edition Springer Verlag, Berlin 1993

2. R. Horst, P.M. Pardalos , Nguyen van Thoai

Introduction to Global Optimization, 1995, Kluwer Academic Publishers

3. Le Thi Hoai An,

Contribution à l'optimisation non convexe et l'optimisation globale: Théorie, Algorithmes, Applications. Habilitation à Diriger des Recherches, Rouen, Juin 1997

4. J. F. Bonnans, J.C. Gilbert, C. Lemarechal, C. Sagastizabal

Optimisation Numérique , Aspects théoriques et pratiques, Mathématiques & Applications, SMAI, Springer-Verlag Berlin Heidelberg 1997

5. R.T. Rockafellar : Convex analysis, Princeton University Press, N.J. (1970)

6. J. B. Hiriart Urruty and C. Lemaréchal : Convex analysis and minimization algorithms I&II. Springer-Verlag, Berlin Heidelberg New York (1993)

7. H. Bréziz : Opérateurs maximaux monotones. Mathematics Studies 5, North Holland, (1973).

8. J. Cea: Optimisation, théorie et algorithmes. Dunod, Paris (1971)

9. V.F. Demyanov & L.V.Vasilev :

Nondifferentiable optimization, Optimization Sofware, Inc Publications Division, New-York(1985)

10. I. Ekeland & R.Temam: Analyse convexe et problèmes variationnels. Dunod, Gauthier-Villars (1974)

11. P.J. Laurent: Approximation et Optimisation. Hermann (1972)

12. P. Mahey, Pham Dinh Tao

Proximal decomposition on the graph of a maximal monotone operator.

SIAM Journal on Optimization, Vol. 5, (1995), pp. 454-4681.

13. Pham Dinh Tao, Le Thi Hoai An

Convex analysis approach to DC (Difference of Convex functions) Programming: Theory, Algorithms and Applications.  

Acta Mathematica Vietnamica, Vol. 22, No 1 (1997), pp. 289‐355 

14. Pham Dinh Tao, Le Thi Hoai An

D.C. Optimization Algorithm for Solving The Trust Region Problem.

SIAM Journal on Optimization, Vol. 8, Number 2 (1998) pp. 476-505

15. Le Thi Hoai An

An efficient algorithm for globally minimizing a quadratic function under quadratic constraints

Mathematical Programming, Ser. A, Vol. 87, No 3, (2000), pp. 401-426

16. Le Thi Hoai An, Pham Dinh Tao Large Scale Molecular Optimization From Distance Matrices by a D.C. Optimization Approach.

SIAM Journal on Optimization, Vol. 14, No 1 (2003), pp. 77-116

16. Le Thi Hoai An, Pham Dinh Tao: DC Programming: Theory, Algorithms and Applications. The State of the Art (28 pages) 

Proceedings (containing the refereed contributed papers) of The First International Workshop on Global Constrained Optimization and Constraint Satisfaction (Cocos' 02), Valbonne-Sophia Antipolis, France, October 2-4, 2002

17. Le Thi Hoai An, Pham Dinh Tao: The DC (difference of convex functions) Programming and DCA revisited with DC models of real world nonconvex optimization problems.

Annals of Operations Research, 133, pp. 23-46, 2005.