Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Phương pháp phân nhánh và cắt không gian cho bài toán QCQP không lồi với biến phức bị ràng buộc
Tóm tắt
Chúng tôi phát triển một phương pháp phân nhánh và cắt không gian cho các bài toán lập phương trình bậc hai không lồi với ràng buộc bậc hai đối với các biến phức (CQCQP). Các bất đẳng thức tuyến tính hợp lệ được thêm vào ở mỗi nút của cây tìm kiếm để củng cố sự thư giãn lập trình nửa xác định của CQCQP. Các bất đẳng thức hợp lệ này được suy diễn từ mô tả đa diện lồi của một tập không lồi các ma trận Hermitian nửa xác định dương $$2 \times 2$$ chịu ràng buộc bậc một. Chúng tôi đề xuất các quy tắc phân nhánh dựa trên một lựa chọn thay thế cho ràng buộc bậc một cho phép đo lường vi phạm ràng buộc một cách cục bộ. Các quy trình thắt chặt giới hạn dạng đóng được sử dụng để giảm miền của bài toán. Chúng tôi áp dụng thuật toán để giải quyết bài toán dòng điện xoay chiều tối ưu với các biến phức cũng như bài toán lập trình bậc hai có ràng buộc hộp với các biến thực.
Từ khóa
#QCQP #phương pháp phân nhánh và cắt #biến phức #ràng buộc bậc một #lập trình nửa xác địnhTài liệu tham khảo
Achterberg, T., Koch, T., Martin, A.: Branching rules revisited. Oper. Res. Lett. 33, 42–54 (2005)
Andersen, E.D., Andersen, K.D.: The MOSEK interior point optimizer for linear programming: an implementation of the homogeneous algorithm. High Perform. Optim. 33, 197–232 (2000)
Anstreicher, K.M.: Semidefinite programming versus the reformulation-linearization technique for nonconvex quadratically constrained quadratic programming. J. Global Optim. 43, 471–484 (2009)
Anstreicher, K.M., Burer, S.: Computable representations for convex hulls of low-dimensional quadratic forms. Math. Program. 124, 33–43 (2010)
Bai, X., Wei, H.: A semidefinite programming method with graph partitioning technique for optimal power flow problems. Int. J. Electr. Power Energy Syst. 33, 1309–1314 (2011)
Bai, X., Wei, H., Fujisawa, K., Wang, Y.: Semidefinite programming for optimal power flow problems. Int. J. Electr. Power Energy Syst. 30, 383–392 (2008)
Bao, X., Sahinidis, N.V., Tawarmalani, M.: Multiterm polyhedral relaxations for nonconvex, quadratically constrained quadratic programs. Optim. Methods Softw. 24, 485–504 (2009)
Beck, A., Eldar, Y.C.: Strong duality in nonconvex quadratic optimization with two quadratic constraints. SIAM J. Optim. 17, 844–860 (2006)
Belotti, P., Kirches, C., Leyffer, S., Linderoth, J., Luedtke, J., Mahajan, A.: Mixed-integer nonlinear optimization. Acta Numer. 22, 1–131 (2013)
Belotti, P., Lee, J., Liberti, L., Margot, F., Wächter, A.: Branching and bounds tightening techniques for non-convex MINLP. Optim. Methods Softw. 24, 597–634 (2009)
Ben-Tal, A., Nemirovski, A., Roos, C.: Extended matrix cube theorems with applications to \(\mu \)-theory in control. Math. Oper. Res. 28, 497–523 (2003)
Bienstock, D.: Electrical Transmission System Cascades and Vulnerability: An Operations Research Viewpoint, vol. 22. SIAM, Philadelphia (2016)
Bienstock, D., Munoz, G.: LP Approximations to Mixed-Integer Polynomial Optimization Problems. arXiv:1501.00288 (2015)
Blair, J.R.S., Peyton, B.: An introduction to chordal graphs and clique trees. In: George, A., Gilbert, J.R., Liu, J.W.H. (eds.) Graph Theory and Sparse Matrix Computation, pp. 1–29. Springer, New York (1993)
Burer, S.: Optimizing a polyhedral-semidefinite relaxation of completely positive programs. Math. Program. Comput. 2, 1–19 (2010)
Burer, S., Vandenbussche, D.: Globally solving box-constrained nonconvex quadratic programs with semidefinite-based finite branch-and-bound. Comput. Optim. Appl. 43, 181–195 (2009)
Chen, C., Atamtürk, A., Oren, S.S.: Bound tightening for the alternating current optimal power flow problem. IEEE Trans. Power Syst. (2015). doi:10.1109/TPWRS.2015.2497160
Chen, J., Burer, S.: Globally solving nonconvex quadratic programming problems via completely positive programming. Math. Program. Comput. 4, 33–52 (2012)
Coffrin, C., Gordon, D., Scott, P.: NESTA, The NICTA Energy System Test Case Archive. arXiv:1411.0359 (2014)
De Maio, A., Huang, Y., Piezzo, M., Zhang, S., Farina, A.: Design of optimized radar codes with a peak to average power ratio constraint. IEEE Trans. Signal Proces. 59, 2683–2697 (2011)
Fukuda, M., Kojima, M., Murota, K., Nakata, K.: Exploiting sparsity in semidefinite programming via matrix completion I: general framework. SIAM J. Optim. 11, 647–674 (2001)
Gopalakrishnan, A., Raghunathan, A.U., Nikovski, D., Biegler, L.T.: Global optimization of optimal power flow using a branch & bound algorithm. In: IEEE 50th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pp. 609–616 (2012)
Grone, R., Johnson, C.R., Sá, E.M., Wolkowicz, H.: Positive definite completions of partial Hermitian matrices. Linear Algebra Appl. 58, 109–124 (1984)
Huang, Y., Palomar, D.P.: Randomized algorithms for optimal solutions of double-sided QCQP with applications in signal processing. IEEE Trans. Signal Process. 62, 1093–1108 (2014)
Huang, Y., Zhang, S.: Complex matrix decomposition and quadratic programming. Math. Oper. Res. 32, 758–768 (2007)
Jabr, R.A.: Optimal power flow using an extended conic quadratic formulation. IEEE Trans. Power Syst. 23, 1000–1008 (2008)
Jabr, R.A.: Exploiting sparsity in SDP relaxations of the OPF problem. IEEE Trans. Power Syst. 27, 1138–1139 (2012)
Jiang, B., Li, Z., Zhang, S.: Approximation methods for complex polynomial optimization. Comput. Optim. Appl. 59, 219–248 (2014)
Josz, C., Molzahn, D.K.: Moment/Sum-of-Squares Hierarchy for Complex Polynomial Optimization. arXiv:1508.02068 (2015)
Kocuk, B., Dey, S.S., Sun, X.A.: Inexactness of SDP relaxation and valid inequalities for optimal power flow. IEEE Trans. Power Syst. 31, 642–651 (2016)
Lavaei, J., Low, S.H.: Zero duality gap in optimal power flow problem. IEEE Trans. Power Syst. 27, 92–107 (2012)
Linderoth, J.: A simplicial branch-and-bound algorithm for solving quadratically constrained quadratic programs. Math. Program. 103, 251–282 (2005)
Lofberg, J.: YALMIP: a toolbox for modeling and optimization in MATLAB. In: IEEE International Symposium on Computer Aided Control Systems Design, pp. 284–289 (2004)
Lovász, L., Schrijver, A.: Cones of matrices and set-functions and 0–1 optimization. SIAM J. Optim. 1, 166–190 (1991)
McCormick, G.P.: Computability of global solutions to factorable nonconvex programs: part 1 convex underestimating problems. Math. Program. 10, 147–175 (1976)
Misener, R., Floudas, C.A.: GloMIQO: global mixed-integer quadratic optimizer. J. Global Optim. 57, 3–50 (2013)
Misener, R., Smadbeck, J.B., Floudas, C.A.: Dynamically generated cutting planes for mixed-integer quadratically constrained quadratic programs and their incorporation into GloMIQO 2. Optim. Methods Softw. 30, 215–249 (2015)
Molzahn, D.K., Holzer, J.T., Lesieutre, B.C., DeMarco, C.L.: Implementation of a large-scale optimal power flow solver based on semidefinite programming. IEEE Trans. Power Syst. 28, 1–12 (2013)
Petriu, D.C., Shen, H.: Applying the UML performance profile: graph grammar-based derivation of LQN models from UML specifications. In: Field, T., Harrison, P.G., Bradley, J., Harder, U. (eds.) Computer Performance Evaluation: Modelling Techniques and Tools, vol. 2324, pp. 159–177. Springer, Berlin (2002)
Phan, D.T.: Lagrangian duality-based branch and bound algorithms for optimal power flow. Oper. Res. 60, 275–285 (2012)
Raber, U.: A simplicial branch-and-bound method for solving nonconvex all-quadratic programs. J. Global Optim. 13, 417–432 (1998)
Sahinidis, N.V.: BARON: a general purpose global optimization software package. J. Global Optim. 8, 201–205 (1996)
Sherali, H.D., Tuncbilek, C.H.: A global optimization algorithm for polynomial programming problems using a reformulation-linearization technique. J. Global Optim. 2, 101–112 (1992)
Shor, N.Z.: Quadratic optimization problems. Soviet J. Circuits Syst. Sci. 25, 6 (1987)
Sun, D.I., Ashley, B., Brewer, B., Hughes, A., Tinney, W.F.: Optimal power flow by Newton approach. IEEE Trans. Power Appar. Syst. 10, 2864–2880 (1984)
Tao, T.: Topics in Random Matrix Theory, vol. 132. American Mathematical Society, Providence (2012)
The MathWorks. MATLAB User’s Guide (1998)
Wächter, A., Biegler, L.T.: On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming. Math. Program. 106, 25–57 (2006)
Waldspurger, I., D’Aspremont, A., Mallat, S.: Phase recovery, maxcut and complex semidefinite programming. Math. Program. 149, 47–81 (2015)
Zimmerman, R.D., Murillo-Sánchez, C.E., Thomas, R.J.: MATPOWER: steady-state operations, planning, and analysis tools for power systems research and education. IEEE Trans. Power Syst. 26, 12–19 (2011)