Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Cách làm cho giao của một hội tụ bậc hai và một bậc hai không lồi trở thành lồi
Tóm tắt
Một loạt các bài báo gần đây đã xem xét việc mở rộng kỹ thuật lập trình phân tách sang lập trình nón bậc hai với số nguyên hỗn hợp. Ví dụ, đã có nhiều tác giả sử dụng các kỹ thuật khác nhau chứng minh rằng mê cung lồi của giao điểm giữa một elip, $$\mathcal {E}$$, và một sự phân tách bị tách rời, $$(l - x_j)(x_j - u) \le 0$$ với $$l < u$$, bằng với giao của $$\mathcal {E}$$ với một tập hợp có thể đại diện bởi nón bậc hai (SOCr) bổ sung. Trong bài báo này, chúng tôi nghiên cứu các giao điểm tổng quát hơn ở dạng $$\mathcal {K}\cap \mathcal {Q}$$ và $$\mathcal {K}\cap \mathcal {Q}\cap H$$, trong đó $$\mathcal {K}$$ là một nón SOCr, $$\mathcal {Q}$$ là một nón không lồi được xác định bởi một phương trình bậc hai đồng nhất duy nhất, và H là một mặt phẳng affine. Dưới một số điều kiện dễ xác minh, chúng tôi suy ra các giãn cách lồi đơn giản, có thể tính toán $$\mathcal {K}\cap \mathcal {S}$$ và $$\mathcal {K}\cap \mathcal {S}\cap H$$, trong đó $$\mathcal {S}$$ là một nón SOCr. Dưới các điều kiện bổ sung, chúng tôi chứng minh rằng hai tập hợp này chính xác tái hiện các nón/lồi tương ứng. Phương pháp của chúng tôi thống nhất và mở rộng các kết quả trước đây, và chúng tôi minh họa tính áp dụng và tổng quát của nó với nhiều ví dụ.
Từ khóa
#Lập trình phân tách #lập trình nón bậc hai #tối ưu hóa #lồi #hàm bậc haiTài liệu tham khảo
Adjiman, C., Dallwig, S., Floudas, C., Neumaier, A.: A global optimization method, \(\alpha \)-BB, for general twice-differentiable constrained NLPs—I. Theoretical advances. Comput. Chem. Eng. 22(9), 1137–1158 (1998)
Andersen, K., Jensen, A.N.: Intersection cuts for mixed integerconic quadratic sets. In: Proceedings of IPCO 2013, volume7801 of Lecture Notes in Computer Science, pp. 37–48.Valparaiso, Chile (March 2013)
Androulakis, I.P., Maranas, C.D., Floudas, C.A.: \(\alpha {{\rm BB}}\): a global optimization method for general constrained nonconvex problems. J. Glob. Optim. 7(4), 337–363 (1995). State of the art in global optimization: computational methods and applications (Princeton, NJ, 1995)
Anstreicher, K.M., Burer, S.: Computable representations for convex hulls of low-dimensional quadratic forms. Math. Program. 124(1–2), 33–43 (2010)
Atamtürk, A., Narayanan, V.: Conic mixed-integer rounding cuts. Math. Program. 122(1), 1–20 (2010)
Balas, E.: Intersection cuts—a new type of cutting planes for integer programming. Oper. Res. 19, 19–39 (1971)
Balas, E.: Disjunctive programming. Ann. Discret. Math. 5, 3–51 (1979)
Balas, E., Ceria, S., Cornuéjols, G.: A lift-and-project cutting plane algorithm for mixed 0–1 programs. Math. Program. 58, 295–324 (1993)
Bao, X., Sahinidis, N.V., Tawarmalani, M.: Semidefinite relaxations for quadratically constrained quadratic programming: a review and comparisons. Math. Program. 129(1), 129–157 (2011)
Barvinok, A.: A Course in Convexity, vol. 54. American Mathematical Society, Providence (2002)
Belotti, P.: Disjunctive cuts for nonconvex MINLP. In: Lee, J., Leyffer, S. (eds.) Mixed Integer Nonlinear Programming, volume 154 of The IMA Volumes in Mathematics and its Applications, pp. 117–144. Springer, New York, NY (2012)
Belotti, P., Góez, J., Pólik, I., Ralphs, T., Terlaky, T.: On families of quadratic surfaces having fixed intersections with two hyperplanes. Discret. Appl. Math. 161(16), 2778–2793 (2013)
Belotti, P., Goez, J.C., Polik, I., Ralphs, T.K., Terlaky, T.: A conic representation of the convex hull of disjunctive sets and conic cuts for integer second order cone optimization. In: Al-Baali, M., Grandinetti, L., Purnama, A. (eds.) Numerical Analysis and Optimization, volume 134 of Springer Proceedings in Mathematics and Statistics, pp. 1–35. Springer (2014)
Bienstock, D., Michalka, A.: Cutting-planes for optimization of convex functions over nonconvex sets. SIAM J. Optim. 24(2), 643–677 (2014)
Bonami, P.: Lift-and-project cuts for mixed integer convex programs. In: Gunluk, O., Woeginger, G.J. (eds.) Proceedings of the 15th IPCO Conference, volume 6655 of Lecture Notes in Computer Science, pp. 52–64. Springer, New York, NY (2011)
Burer, S., Anstreicher, K.M.: Second-order-cone constraints for extended trust-region subproblems. SIAM J. Optim. 23(1), 432–451 (2013)
Burer, S., Saxena, A.: The MILP road to MIQCP. In: Mixed Integer Nonlinear Programming, pp. 373–405. Springer (2012)
Cadoux, F.: Computing deep facet-defining disjunctive cuts for mixed-integer programming. Math. Program. 122(2), 197–223 (2010)
Çezik, M., Iyengar, G.: Cuts for mixed 0–1 conic programming. Math. Program. 104(1), 179–202 (2005)
Ceria, S., Soares, J.: Convex programming for disjunctive convex optimization. Math. Program. 86(3), 595–614 (1999)
Conn, A.R., Gould, N.I.M., Toint, P.L.: Trust-RegionMethods. MPS/SIAM Series on Optimization. SIAM, Philadelphia, PA (2000)
Cornuéjols, G., Lemaréchal, C.: A convex-analysis perspective on disjunctive cuts. Math. Program. 106(3), 567–586 (2006)
Dadush, D., Dey, S.S., Vielma, J.P.: The split closure of a strictly convex body. Oper. Res. Lett. 39, 121–126 (2011)
Drewes, S.: Mixed Integer Second Order Cone Programming. Ph.D. thesis, Technische Universität Darmstadt (2009)
Drewes, S., Pokutta, S.: Cutting-planes for weakly-coupled 0/1 second order cone programs. Electron. Notes in Discrete Math. 36, 735–742 (2010)
Gould, N.I.M., Lucidi, S., Roma, M., Toint, P.L.: Solving the trust-region subproblem using the Lanczos method. SIAM J. Optim. 9(2), 504–525 (1999)
Günlük, O., Linderoth, J.: Perspective reformulations of mixed integer nonlinear programs with indicator variables. Math. Program. 124(1–2), 183–205 (2010)
Horn, R.A., Johnson, C.R.: Matrix Analysis. Cambridge University Press, Cambridge (2013)
Hu, J., Mitchell, J.E., Pang, J.-S., Bennett, K.P., Kunapuli, G.: On the global solution of linear programs with linear complementarity constraints. SIAM J. Optim. 19(1), 445–471 (2008)
Jeyakumar, V., Li, G.Y.: Trust-region problems with linear inequality constraints: exact SDP relaxation, global optimality and robust optimization. Math. Program. 147(1), 171–206 (2013)
Júdice, J.J., Sherali, H., Ribeiro, I.M., Faustino, A.M.: A complementarity-based partitioning and disjunctive cut algorithm for mathematical programming problems with equilibrium constraints. J. Glob. Optim. 136, 89–114 (2006)
Kato, T.: Perturbation Theory for Linear Operators, second edn. Springer, Berlin-New York (1976). Grundlehren der Mathematischen Wissenschaften, Band 132
Kılınç, M., Linderoth, J., Luedtke, J.: Effective separation of disjunctive cuts for convex mixed integer nonlinear programs. Technical report. http://www.optimization-online.org/DB_FILE/2010/11/2808.pdf (2010)
Kılınç-Karzan, F.: On minimal inequalities for mixed integer conic programs. Math. Oper. Res. 41(2), 477–510 (2016)
Kılınç-Karzan, F., Yıldız, S.: Two-term disjunctions on the second-order cone. In: Lee, J., Vygen, J. (eds.) IPCO, volume 8494 of Lecture Notes in Computer Science, pp. 345–356. Springer (2014)
Kılınç-Karzan, F., Yıldız, S.: Two-term disjunctions on the second-order cone. Math. Program. 154(1), 463–491 (2015)
Kim, S., Kojima, M.: Second order cone programming relaxation of nonconvex quadratic optimization problems. Optim. Methods Softw. 15(3–4), 201–224 (2001)
Mahajan, A., Munson, T.: Exploiting second-order cone structure for global optimization. Technical report. ANL/MCS-P1801-1010, Argonne National Laboratory, http://www.optimization-online.org/DB_HTML/2010/10/2780.html (October 2010)
Modaresi, S., Kılınç, M.R., Vielma, J.P.: Split cuts and extended formulations for mixed integer conic quadratic programming. Oper. Res. Lett. 43(1), 10–15 (2015)
Modaresi, S., Kılınç, M.R., Vielma, J.P.: Intersection cuts for nonlinear integer programming: convexification techniques for structured sets. Math. Program. 155(1), 575–611 (2016)
Modaresi, S., Vielma, J.: Convex hull of two quadratic or a conic quadratic and a quadratic inequality. Technical report. http://www.optimization-online.org/DB_HTML/2014/11/4641.html (November 2014)
Moré, J.J., Sorensen, D.C.: Computing a trust region step. SIAM J. Sci. Stat. Comput. 4(3), 553–572 (1983)
Nguyen, T.T., Tawarmalani, M., Richard, J.-P.P.: Convexification techniques for linear complementarity constraints. In: Günlük, O., Woeginger, G.J. (eds.) IPCO, volume 6655 of Lecture Notes in Computer Science, pp. 336–348. Springer (2011)
Pataki, G.: On the rank of extreme matrices in semidefinite programs and the multiplicity of optimal eigenvalues. Math. Oper. Res. 23(2), 339–358 (1998)
Pólik, I., Terlaky, T.: A survey of the S-lemma. SIAM Rev. 49(3), 371–418 (2007). (electronic)
Rellich, F.: Perturbation theory of eigenvalue problems. Assisted by J. Berkowitz. With a preface by Jacob T. Schwartz. Gordon and Breach Science Publishers, New York-London-Paris (1969)
Rendl, F., Wolkowicz, H.: A semidefinite framework for trust region subproblems with applications to large scale minimization. Math. Program. 77(2), 273–299 (1997)
Saxena, A., Bonami, P., Lee, J.: Disjunctive cuts for non-convex mixed integer quadratically constrained programs. In: Lodi, A., Panconesi, A., Rinaldi, G. (eds.) IPCO, volume 5035 of Lecture Notes in Computer Science, pp. 17–33. Springer (2008)
Sherali, H., Shetty, C.: Optimization with disjunctive constraints. Lectures on Econ. Math. Systems, 181 (1980)
Stubbs, R.A., Mehrotra, S.: A branch-and-cut method for 0–1 mixed convex programming. Math. Program. 86(3), 515–532 (1999)
Tawarmalani, M., Richard, J., Chung, K.: Strong valid inequalities for orthogonal disjunctions and bilinear covering sets. Math. Program. 124(1–2), 481–512 (2010)
Tawarmalani, M., Richard, J.-P.P., Xiong, C.: Explicit convex and concave envelopes through polyhedral subdivisions. Math. Program. 138(1–2), 531–577 (2013)
Vielma, J.P., Ahmed, S., Nemhauser, G.L.: A lifted linear programming branch-and-bound algorithm for mixed-integer conic quadratic programs. INFORMS J. Comput. 20(3), 438–450 (2008)
Yıldıran, U.: Convex hull of two quadratic constraints is an LMI set. IMA J. Math. Control Inf. 26, 417–450 (2009)
Yıldız, S., Cornuéjols, G.: Disjunctive cuts for cross-sections of the second-order cone. Oper. Res. Lett. 43(4), 432–437 (2015)