給定兩個$n$元二次函數$f(x)=x^{T}Ax+2a^{T}x+a_{0}$和$g(x)=x^{T}Bx+2b^{T}x+b_{0}$，二次曲面相交問題研究超曲面${x|f(x)=0}$和${x|g(x)=0}$是否相交。這個問題在文獻中被稱為「二次曲面交線問題」，縮寫為(QSIC)。Levin在1970年代末嘗試通過直接求解二次方程組來處理(QSIC)問題，但即使在三維實空間中也遇到了巨大的困難。後來1990年代的一些嘗試將空間升級到了$mathbb{P}_{3}(mathbb{R})$（三維實射影空間），但也沒有解決這個問題。因此，2007年，Pólik和Terlaky在SIAM Review中提出了二次曲面相交問題作為一個開放性問題。直到2020年，Nguyen、Sheu和Xia提出了通過計算一個四次多項式的最優值，並要求檢查一些拓撲性質來解決(QSIC)問題，即判斷${x|f(x)=0}$和${x|g(x)=0}$這兩個等高集是否相互切割。在本文中，我們通過僅需檢查四個帶有單一二次約束的二次規劃問題之無界性和不可達性來改進了Nguyen、Sheu和Xia在2020年提出的方法。我們的新方法節省了大量的計算步驟。實作方面，我們提供透過計算正半定矩陣對${lambda|A+lambda Bsucceq 0}$的數值測試。數值測試結果驗證我們的方法的正確性和效率。

Given two $n$-variate quadratic functions $f(x)=x^{T}Ax+2a^{T}x+a_{0},g(x)=x^{T}Bx+2b^{T}x+b_{0}$, the quadratic surfaces intersection problem asks whether the hypersurfaces ${x|f(x)=0}$ and ${x|g(x)=0}$ intersect with each other. In literature, it is known as the the decision version of ``quadratic surfaces intersection curve problem,'' usually abbreviated as (QSIC). Levin (c. late 1970) tried to handle the (QSIC) problem by directly solving the system of quadratic equations, but has encountered enormous difficulty even just in 3D real spaces. Later attempts in 1990 did not resolve the problem by raising the space to $mathbb{P}_{3}(mathbb{R})$ (3D real projective spaces). As such, in 2007 Pólik and Terlaky posed the quadratic surfaces intersection problem as an open problem in SIAM Review. The problem remained open until a preprint by Nguyen, Sheu, and Xia in 2020, in which they proposed to resolve the (QSIC) problem by computing the optimal value of a polynomial of degree $4$ and by requiring to check some topological property that whether the two level sets ${x|f(x)=0}$ and ${x|g(x)=0}$ separate one by the other. In this thesis, we improve the method by Nguyen, Sheu, and Xia in 2020 by only having to check the unboundedness and the unattainability of four quadratic programs with a single quadratic constraint. Our new approach thus saves a lot of computational steps. Implementation through computing the positive-semidefinite matrix pencil ${lambda|A+lambda Bsucceq0}$ as well as the numerical testing results are also provided. The numerical results confirm both the correctness and the efficiency of our method.

[1] Satoru Adachi and Yuji Nakatsukasa. Eigenvalue-based algorithm and analysis for nonconvex QCQP with one constraint. Mathematical Programming, 173:79–116, 2019.
[2] Stephen Boyd and Lieven Vandenberghe. Convex Optimization. IEEE Transactions on Automatic Control, 51:1859–1859, 2004.
[3] Eugenio Calabi. Linear systems of real quadratic forms. ii. Proceedings of the American Mathematical Society, 84(3):331–334, 1964.
[4] Richard J. Caron and Nicholas I. M. Gould. Finding a positive semidefinite interval for a parametric matrix. Linear Algebra and its Applications, 76:19–29, 1986.
[5] Arnold Dresden. Solid Analytical Geometry And Determinants. Dover Publications, 1964.
[6] Laurent Dupont, Daniel Lazard, Sylvain Lazard, and Sylvain Petitjean. Near-optimal parameterization of the intersection of quadrics. Journal of Symbolic Computation, 43:168–191, 2003.
[7] Rida T. Farouki, C. Andrew Neff, and M. A. O’Conner. Automatic parsing of degenerate quadric-surface intersections. ACM Transactions on Graphics, 8:174–203, 1989.
[8] Joe-Mei Feng, Gang-Xuan Lin, Ruey-Lin Sheu, and Yong Xia. Duality and solutions for quadratic programming over single non-homogeneous quadratic constraint. Journal of Global Optimization, 54:275–293, 2012.
[9] Paul Finsler. Über das vorkommen definiter und semidefiniter formen in scharen quadratischer formen. Commentarii Mathematici Helvetici, 9:188–192, 1936.
[10] Michael Grant and Stephen Boyd. Graph implementations for nonsmooth convex programs. In V. Blondel, S. Boyd, and H. Kimura, editors, Recent Advances in Learning and Control, Lecture Notes in Control and Information Sciences, pages 95–110. Springer-Verlag Limited, 2008. http://stanford.edu/~boyd/graph_dcp.html.
[11] Michael Grant and Stephen Boyd. CVX: Matlab software for disciplined convex programming, version 2.1. http://cvxr.com/cvx, March 2014.
[12] Chun-Hua Guo, Nicholas John Higham, and Françoise Tisseur. An improved arc algorithm for detecting definite hermitian pairs. SIAM Journal on Matrix Analysis and Applications, 31(3):1131–1151, 2009.
[13] Christoph Helmberg. Semidefinite programming. European Journal of Operational Research, 137:461–482, 2002.
[14] Jean-Baptiste Hiriart-Urruty and Mounir Torki. Permanently going back and forth between the “quadratic world” and the “convexity world” in optimization. Applied Mathematics and Optimization, 45:169–184, 2002.
[15] Yong Hsia, Gang-Xuan Lin, and Ruey-Lin Sheu. A revisit to quadratic programming with one inequality quadratic constraint via matrix pencil. Pacific Journal of Optimization, 10:461–481, 2014.
[16] Joshua Z. Levin. A parametric algorithm for drawing pictures of solid objects composed of quadric surfaces. Communications of the ACM, 19:555–563, 1976.
[17] Joshua Z. Levin. Mathematical models for determining the intersections of quadric surfaces. Computer Graphics and Image Processing, 11:73–87, 1979.
[18] Zhi-Quan Tom Luo, Wing-Kin Ma, Anthony Man-Cho So, Yinyu Ye, and Shuzhong Zhang. Semidefinite relaxation of quadratic optimization problems. IEEE Signal Processing Magazine, 27:20–34, 2010.
[19] Jorge J. Moré. Generalizations of the trust region problem. Optimization Methods and Software, 2:189–209, 1993.
[20] Huu-Quang Nguyen, Ya-Chi Chu, and Ruey-Lin Sheu. On the convexity for the range set of two quadratic functions. Journal of Industrial and Management Optimization, 2020.
[21] Huu-Quang Nguyen and Ruey-Lin Sheu. Geometric properties for level sets of quadratic functions. Journal of Global Optimization, 73:349–369, 2019.
[22] Huu-Quang Nguyen, Ruey-Lin Sheu, and Yong Xia. Deciding whether two quadratic surfaces actually intersect. arXiv:2012.10318, 2020.
[23] Imre Pólik and Tamás Terlaky. A survey of the s-lemma. SIAM Review, 49:371–418, 2007.
[24] Huiming Song. Positive semidefinite intervals for matrix pencils. Master’s thesis, University of Windsor, 2004.
[25] Jos F. Sturm and Shuzhong Zhang. On cones of nonnegative quadratic functions. Mathematics of Operations Research, 28:246–267, 2003.
[26] K.C. Toh, M.J. Todd, and R.H. Tutuncu. Sdpt3 - a matlab software package for semidefinite programming, optimization methods and software. Optimization Methods and Software, 11:545–581, 1999.
[27] Changhe Tu, Wenping Wang, Bernard Mourrain, and Jiaye Wang. Using signature sequences to classify intersection curves of two quadrics. Computer Aided Geometric Design, 26:317–335, 2009.
[28] R.H Tutuncu, K.C. Toh, and M.J. Todd. Solving semidefinite-quadratic-linear programs using sdpt3. Mathematical Programming Series B, 95:189–217, 2003.
[29] Lieven Vandenberghe and Stephen P. Boyd. Semidefinite programming. SIAM Review, 38:49–95, 1996.
[30] Wenping Wang, Ron Goldman, and Changhe Tu. Enhancing levin’s method for computing quadric-surface intersections. Computer Aided Geometric Design, 20:401–422, 2003.
[31] Itzhak Wilf and Yehuda Manor. Quadric-surface intersection curves: shape and structure. Computer Aided Design, 25:633–643, 1993.
[32] Yong Xia, Shu Wang, and Ruey-Lin Sheu. S-lemma with equality and its applications. Mathematical Programming, 156:513–547, 2016.
[33] Vladimir A Yakubovich. S-procedure in nolinear control theory. Vestnik Leninggradskogo Universiteta, Ser. Matematika, pages 62–77, 1971.