การแสดงถึงความไม่มีคำตอบและความไม่มีขอบเขตของปัญหาหลัก - ปัญหาคู่ควบโดยใช้วิธีการตามเส้นทางจุดภายใน
Infeasibility and Unboundedness of Primal-Dual Problems Using Interior-point Methods
Keywords:
วิธีจุดภายใน , ความไม่มีคำตอบ , หลัก-คู่ควบAbstract
บทความนี้ศึกษาการใช้วิธีจุดภายในในการหาตัวบ่งบอกถึงความไม่มีคำตอบและความไม่มีขอบเขตของปัญหาหลัก - ปัญหาคู่ควบและได้ทำการศึกษากรณีที่ใช้ ขั้นตอนวิธีการตามเส้นทางคู่ควบ (Dual) และพบว่าพฤติกรรมทางทฤษฎีมีความแตกต่างไปจากขั้นตอนวิธีการตามเส้นทางหลัก-คู่ควบ (Primal-Dual) เนื่องจากฟังก์ชันขวางกั้นมาตรฐานมีความซับซ้อนน้อยกว่า We apply interior-point method to find infeasibility and unboundedness certifies. We study dual path-following interior-point method and compare it to primal-dual method. Both methods are able to find certifies. However, there are differences in the theories due the less of complexity of the universal barrier function.References
Adler, I., Resende, M.G.C., Veiga, G., Karmarkar, N.K. (1989). An implementation of Karmarkar’s Algorithms for linear programming. Mathematical Programming. 44(3), 297-335.
Benson, SJ., Ye, Y., Zhang, X., (2000). Solving large-scale sparse semidefinite programs for combinatorial optimization, SIAM Journal of Optimization. 10(2), 443-461.
Gonzaga, C.C. (1992). Path following methods for linear programming. SIAM Review. 34(2), 167-224.
Guler, O. (1992). Barrier functions in interior point methods. Mathematics of Operations Research. 21, 860-885.
Nesterov, Y.E., Nemirovskii, A.S. (1993). Interior Point Polynomial Method in Convex Programming: Theory and Algorithms. SIAM, Philadelphia.
Renegar, J. (1988). A polynomial-time algorithms based on Newton’s method for linear programming. Mathematical Programming. 40, 59-93.
Todd, M.J. (2004). Detecting infeasibility in infeasibleinterior- point methods for optimization. In: Cucker, F., DeVore, R., Olver, P., Süli, E. (eds.) Foundations of Computational Mathematics, Minneapolis 2002, pp. 157-192. Cambridge University Press, Cambridge.
Ye, Y. (1997). Interior Point Algorithms: Theory and Analysis. Wiley, New York.
