Sự hội tụ toàn cầu của một lớp phương pháp hình phạt mượt cho lập trình nửa vô hạn

Journal of Systems Science and Complexity - Tập 24 - Trang 769-783 - 2011
Changyu Wang1, Haiyan Zhang2, Fang Liu2
1Institute of Operations Research, Qufu Normal University, Qufu, China
2The First Middle School of Juancheng, Heze, China

Tóm tắt

Đối với bài toán lập trình nửa vô hạn (SIP), các tác giả đầu tiên chuyển đổi bài toán này thành một bài toán lập trình phi tuyến tương đương với chỉ một ràng buộc bất đẳng thức bằng cách sử dụng một hàm tích phân, và sau đó đề xuất một phương pháp hình phạt mượt dựa trên một lớp các hàm mượt. Đặc điểm chính của phương pháp này là nghiệm toàn cục của hàm hình phạt không nhất thiết phải được tìm ra trong mỗi vòng lặp, và dưới những giả định nhẹ nhàng, phương pháp này luôn khả thi và hiệu quả khi việc đánh giá hàm tích phân không tốn kém nhiều. Tính chất hội tụ toàn cầu được chứng minh mà không cần bất kỳ điều kiện ràng buộc nào, tức là bất kỳ điểm tích lũy nào của chuỗi được tạo ra bởi thuật toán đều là nghiệm của SIP. Hơn nữa, các tác giả đã chỉ ra một định lý nhiễu của phương pháp và thu được một số kết quả thú vị. Thêm vào đó, các tác giả chỉ ra rằng tất cả các điểm lặp vẫn khả thi sau một số vòng lặp hữu hạn dưới điều kiện ràng buộc Mangasarian-Fromovitz. Cuối cùng, kết quả số được cung cấp.

Từ khóa

#lập trình nửa vô hạn #phương pháp hình phạt mượt #hội tụ toàn cầu #điều kiện ràng buộc Mangasarian-Fromovitz

Tài liệu tham khảo

A. Ben-Tal and M. Teboulle, A smoothing technique for non-differentiable optimization problem, Lecture Notes in Mathematics, Springer Verlag, Berlin, 1989, 1405: 1–11. J. V. Burke and M. C. Ferris, Weak sharp minima in mathematical programming, SIAM J. Control Optim, 1993, 31: 1340–1359. C. Chen and O. L. Mangasarian, Smoothing method for convex inequalities and linear complementarity problems, Math. Program., 1995, 71: 51–69. C. Price, Non-linear semi-infinite programming, Ph. D. Thesis, University of Canterbury, New Zealand, 1992. K. Roleff, A Stable Multiple Exchange Algorithm for Linear SIP, Hettich R. (eds.), Semi-Infinite Programming, Springer-Verlag, 1979: 83–96. A. Auslender, R. Cominetti, and M. Haddou, Asymptotic analysis for penalty and barrier methods in convex and linear programming, Math. Oper. Res., 1997, 22: 43–62. R. Hettich and G. Gramlich, A note on an implementation of a method for quadratic semi-infinite programming, Math. Program., 1990, 46: 249–254. D. H. Li, L. Qi, J. Tam, and S. Y. Wu, A smoothing newton method for semi-infinite programming, J. Glob. Optim., 2004, 30: 169–194. C. Ling, L. Qi, G. Zhou, and S. Y. Wu, Global convergence of a robust smoothing SQP method for semi-infinite programming, J. Optim. Theory Appl., 2006, 129: 147–164. M. H. Wang and Y. E. Kuo, A perturbation method for solving linear semi-infinite programming problems, Comput. Math. Appl., 1999, 37: 181–198. A. Auslender, Penalty and barrier methods: A unified framework, SIAM J. Optim., 1999, 10: 211–230. C. Price and I. Coope, Numerical experiments in semi-infinite programming, Comput. Optim. Appl., 1996, 6: 169–189. A. Vaz, E. Fernandes, and M. Gomes, Discretization methods for semi-infinite programnfing, Investigacão Oper, 2001, 21: 37–46. G. Watson, Globally convergent methods for semi-infinite programming, BIT., 1981, 21: 362–373. J. Kaliski, D. Haglin, C. Roos, and T. Terlaky, Logarithmic barrier decomposition methods for semi-infinite programming, International Transactions in Oper. Res., 1997, 4: 285–303. M. Pinar and S. Zenios, On smoothing exact penalty functions for convex constrained opimization, SIAM J. Optim., 1994, 4: 486–511. S. Y. Wu and S. C. Fang, Solving convex programs with infinitely many constraints by a relaxed cutting plane method, Comput. Math. Appl., 1999, 38: 23–33. C. C. Gonzaga and R. A. Castillo, A nonlinear programming algorithm based on non-coercive penalty functions, Math. Program. Ser. A, 2003, 96: 87–101. W. I. Zangwill, Non-linear programming via penalty functions, Manage. Sci., 1967, 13: 344–358. L. Qi, S. Y. Wu, and G. Zhou, Semismooth newton methods for solving semi-infinite programming problems, J. Glob. Optim., 2003, 27: 215–232. T. Ledn, S. Sanrnatfas, and E. Vercher, On the numerical treatment of linearly constrained semiinfinite optimization problems, European J. Oper. Res., 2000, 121: 78–91. R. Reemtsen, Discretization methods for the solution of semi-infinite programming problems, J. Optim. Theory Appl., 1991, 71: 85–103. S. Y. Wu, D. H. Li, L. Qi, and G. Zhou, An iterative method for solving the kkt system of semi-infinite programming, Optim. Methods and Softw., 2005, 20: 629–643.