Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Thắt chặt một phép làm mềm copositif cho các vấn đề tối ưu hóa bậc hai chuẩn
Tóm tắt
Chúng tôi tập trung vào vấn đề cải thiện các phép làm mềm lập phương bán định (SDP) cho bài toán tối ưu bậc hai chuẩn (viết tắt là QP chuẩn) liên quan đến việc tối thiểu hóa một dạng thức bậc hai trên một khối đơn hình. Trước tiên, chúng tôi phân tích khoảng cách đối ngẫu giữa QP chuẩn và một trong các phép làm mềm SDP của nó được biết đến với tên gọi “phép làm mềm Shor được củng cố”. Để ước lượng khoảng cách đối ngẫu, chúng tôi sử dụng thông tin đối ngẫu từ phép làm mềm SDP để xây dựng một đồ thị G∗. Việc ước lượng này có thể được giảm xuống thành một bài toán hai giai đoạn, đầu tiên là liệt kê tất cả các tập đỉnh tối thiểu của G∗ và sau đó giải quyết một họ các bài toán lập phương hình nón bậc hai. Khi có một khoảng cách đối ngẫu khác không, việc ước lượng khoảng cách đối ngẫu này có thể dẫn đến một giới hạn dưới chặt chẽ hơn so với giới hạn SDP được củng cố của Shor. Với kế hoạch cải thiện ước lượng khoảng cách đối ngẫu, chúng tôi phát triển thêm một thuật toánheuristic để thu được một nghiệm gần đúng tốt cho QP chuẩn.
Từ khóa
#tối ưu hóa bậc hai #phép làm mềm lập phương bán định #khoảng cách đối ngẫu #thuật toán heuristic #đồ thị.Tài liệu tham khảo
Anstreicher, K.M., Burer, S.: D. C. versus copositive bounds for standard QP. J. Glob. Optim. 33, 299–312 (2005)
Anstreicher, K.M., Burer, S.: Computable representations for convex hulls of low-dimensional quadratic forms. Math. Program. 124, 33–43 (2010)
Bomze, I.M.: On standard quadratic optimization problems. J. Glob. Optim. 13, 369–387 (1998)
Bomze, I.M., De Klerk, E.: Solving standard quadratic optimization problems via linear, semidefinite and copositive programming. J. Glob. Optim. 24(2), 163–185 (2002)
Bomze, I.M., Dür, M., De Klerk, E., Roos, C., Quist, A.J., Terlaky, T.: On copositive programming and standard quadratic optimization problems. J. Glob. Optim. 18, 301–320 (2000)
Bomze, I.M., Locatelli, M., Tardella, F.: New and old bounds for standard quadratic optimization: dominance, equivalence and incomparability. Math. Program. 115, 31–64 (2008)
Dukanovic, I., Rendl, F.: Copositive programming motivated bounds on the stability and the chromatic numbers. Math. Program. 121, 249–268 (2010)
Grant, M., Boyd, S.C.V.: Matlab software for disciplined convex programming, version 1. 21 (2010). http://cvxr.com/cvx
Grötschel, M., Lovász, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization. Springer, Berlin (1988)
Laurent, M., Rendl, F.: Semidefinite programming and integer programming. In: Weismantel, R., Aardal, K., Nemhauser, G. (eds.) Handbook on Discrete Optimization, pp. 393–514. Elsevier, Amsterdam (2005)
Lovász, L.: On the Shannon capacity of a graph. IEEE Trans. Inf. Theory 25, 1–7 (1979)
Luz, C., Schrijver, A.: A convex quadratic characterization of the Lovász theta number. SIAM J. Discrete Math. 19(2), 382–387 (2005)
Maxfield, J.E., Minc, H.: On the matrix equation X′X=A. Proc. Edinb. Math. Soc. 13, 125–129 (1963)
McEliece, R.J., Rodemich, E.R., Rumsey, H.C.: The Lovász’ bound and some generalizations. J. Comb. Inf. Syst. Sci. 3, 134–152 (1978)
Meyer, C.D.: Matrix Analysis and Applied Linear Algebra. SIAM, Philadelphia (2000)
Motzkin, T.S., Straus, E.G.: Maxima for graphs and a new proof of a theorem of Turán. Can. J. Math. 17, 533–540 (1965)
Nesterov, Y., Nemirovsky, A.: Interior-Point Polynomial Methods in Convex Programming. SIAM, Philadelphia (1994)
Parrilo, P.A.: Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization. Ph.D. thesis, California Institute of Technology, CA (2000)
Rosgen, B., Stewart, L.: Complexity results on graphs with few cliques. Discrete Math. Theor. Comput. Sci. 9, 127–136 (2007)
Schrijver, A.: A comparison of the Delsarte and Lovász bounds. IEEE Trans. Inf. Theory 25, 425–429 (1979)
Sun, X.L., Liu, C.L., Li, D., Gao, J.J.: On duality gap in binary quadratic programming. J. Glob. Optim. 53, 255–269 (2012)
Tsukiyama, S., Ide, M., Ariyoshi, H., Shirakawa, I.: A new algorithm for generating all the maximal independent sets. SIAM J. Comput. 6, 505–517 (1977)
Vandenberghe, L., Boyd, S.: Semidefinite programming. SIAM Rev. 38, 49–95 (1996)
Xia, Y., Sun, X.L., Li, D., Zheng, X.J.: On the reduction of duality gap in box constrained nonconvex quadratic program. SIAM J. Optim. 21, 706–729 (2011)
Zheng, X.J., Sun, X.L., Li, D., Xia, Y.: Duality gap estimation of linear equality constrained binary quadratic programming. Math. Oper. Res. 35, 864–880 (2010)