Môn Tối ưu mở trong tháng 1/2009 (cập nhật lịch học)
31/12/2008
Vào đầu tháng 1/2009 sẽ có 2 môn tự chọn cho bậc đại học được mở.
  • Tối ưu Tổ hợp: Mô hình, Phương pháp và Phần mềm. Giáo viên: Giáo sư Lê Thị Hoài An, Đại học Paul Verlaine – Metz, Pháp.

  • Từ Tối ưu Lồi đến Tối ưu không Lồi. Giáo viên: Giáo sư Phạm Đình Tảo, INSA-Rouen, Pháp.

Lịch  dạy để trang bị các kiến thức cơ bản: do giáo viên Nguyễn Thị Thu Vân phụ trách.
Thứ tư 7/1/2009: 8g30--11g và 2g-4g tại phòng I34.
Thứ năm 8/1/2009: 8g30--11g và 2g-4g tại phòng I30.
Thứ sáu 9/1/2009: 8g30--11g tại phòng I30.

Lịch dạy của GS Lê Thị Hoài An và GS Phạm Đình Tảo:
Thứ hai 12/1/2009: 8g--11g
1g30--4g30, phòng I44.
Thứ ba đến thứ bảy 17/1/2009: 8g--11g
1g30--4g30, phòng I30.

Chi tiết như sau:  

Học phần mới

 Tối ưu Tổ hợp: Mô hình, Phương pháp và Phần mềm

 Giáo sư Lê Thị Hoài An, Đại học Paul Verlaine – Metz, 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)

Tóm tắt môn học: Môn học này nhằm cung cấp cho sinh viên một cái nhìn đầy đủ nhất có thể về lý thuyết, thuật toán và ứng dụng của Tối ưu tổ hợp trong các lĩnh vực khoa học ứng dụng.

Môn học này được giảng dạy bởi giáo sư Lê Thị Hoài An, một trong những chuyên gia đầu ngành trong lĩnh vực ứng dụng, sẽ giúp cho sinh viên tiếp cận các bài toán thực tế trên thế giới và làm quen với các phần mềm tính toán (CPLEX, XPRESS, …) .

Đối tượng tham gia: tất cả các sinh viên đại học, học viên cao học. Đặc biệt rất hữu ích cho sinh viên ngành tin học.

Tham khảo thêm tại website:

http://lita.sciences.univ-metz.fr/~lethi

Yêu cầu sinh viên biết trước: các ký hiệu cơ bản về đồ thị

Nội dung môn học:

Chapter 1: Introduction to optimization

  • Basic notations

  • Classification of optimization problems

  • Two facets of the optimization: modelling & algorithms

  • A review on existing techniques of optimization and software

  • What can do optimization?

 

Chapter 2: Applications and software of Linear Programming (LP)

  • Basic notations of LP

  • Software CPLEX, XPRESS for LP

  • Using LP for modelling and solving various problems in Management science (transport, Production Planning and Scheduling, Resource Allocation, Supply Chain Management …)

 

Chapter 3: Mixed Integer Linear Programming (MILP)

  • Principal methods for MILP (Branch and Bound, Cutting plane)

  • Software CPLEX, XPRESS for MILP

  • Using MILP for modelling and solving various problems in Management science and Computer science

 

Chapter 4: Another point of view: Network optimization 

  • Classification of network optimization problems

  • Using the graphs to modelling the applied problems studied in chapters 2 and 3 in terms of network optimization problems

 Tài liệu tham khảo:

1. Optimisation Combinatoires (2 tomes) - M. Sakarovitch - Herman 1984

2. Algorithmes de Graphe, Chritian PRINS, Edition Eyrolle, 1994.

3. Exercices et problèmes résolus de recherche opérationnelle, ROSEAUX- MASSON 2e Edition 1993

tome 1: graphes: leurs usages, leurs algorithmes

tome 3: programmation linéaire et extensions; problèmes classiques

4. Recherche Opérationnelle. Exercices corrigés - J.M. Herlary, R. Pedrono, Herman 1983.

Graphes et algorithmes, Michel Gondran, Michel Minoux, Editions Eyrolles, 3e édition, 1995.

5. Théorie des graphes et ses applications, Claude BERGE - DUNOD Paris 1958.

6. Flow in Networks - L.R. FORD & D.R. FULKERSON, Princeton University 1962.

7. Network Flows: theory, algorithms & Applications, Ahuja, Magnanti & Orlin, Prentice Hall 1993.

 




Học phần mới

 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

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

18. 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.

 

 

 

 

 

 

 
Khoa Toán - Tin học, Trường Đại học Khoa học Tự nhiên, Đại học Quốc gia TP Hồ Chí Minh.
Phòng F.009, cơ sở 227 Nguyễn Văn Cừ, Quận 5, TP HCM.