在這篇論文中，我們估計了帶有方塊限制的二次規劃和它的半正定規劃鬆弛問題的對偶間隙。此問題有著二元整數規劃問題作為特例，因此一般來說是NP-hard。利用馬鞍點定理，我們證明了這個對偶間隙可以用一個距離函數$delta_{W}( heta)$估計，而此距離函數計算的是仿射空間$C^*$和參數化的盒子$Lambda^{*}( heta)$之間的距離。
此外，我們結合一個離散幾何中稱作超平面安排的技巧，和使用各種對於權重$W$和參數$ heta$的選擇，來找到對於間隙更好的下界。
最終，提供了幾個例子來驗證定理和說明計算的執行，並嘗試了一些啟發式的策略，來找到更好的權重$W$以便得到更好的間隙估計。

In this thesis, we estimate the gap between a box constrained quadratic program and its SDP relaxation. The problem includes the binary quadratic program as a special case and is thus in general NP-hard. Applying the saddle point theorem, we show that the duality gap can be estimated by a function $delta_{W}( heta)$ measuring a weighted distance between an affine subspace $C^*$ and some parametrized box $Lambda^{*}( heta)$. Incorporating a technique called the hyperplane arrangement in discrete geometry with various choices of parameters and weights, we are able to tighten the bound for the gap. Illustrative examples based on heuristic strategies show how a better bound can be chosen.

Reference
[1] C. Baiocchi, V. Comincioli, E. Magenes, and G.A. Pozzi. Free boundary problems in the theory of fluid flow through porous media: existence and uniqueness theorems. Annali di Matematica Pura ed Applicata, 97(1):1–82, 1973.
[2] M.S. Bazaraa, H.D. Sherali, and C.M. Shetty. Nonlinear programming: theory and algorithms. John Wiley & Sons, 2013.
[3] W. Ben-Ameur and J. Neto. Spectral bounds for the maximum cut problem.Networks, 52(1):8–13, 2008.
[4] A. Ben-Tal. Conic and robust optimization. Lecture Notes, Universita di Roma La Sapienzia, Rome, Italy, 2002.
[5] S. Boyd and L. Vandenberghe. Convex optimization. Cambridge university press, 2009.
[6] J. Céa and R. Glowinski. Sur des méthodes d’optimisation par relaxation. ESAIM: Mathematical Modelling and Numerical Analysis-Modélisation Mathématique et Analyse Numérique, 7(R3):5–31, 1973.
[7] P.G. Ciarlet. The finite element method for elliptic problems. Elsevier, 1978.
[8] C.W. Cryer. The method of christopherson for solving free boundary problems for infinite journal bearings by means of finite differences. Mathematics of computation, 25(115):435–443, 1971.
[9] P.L. De Angelis, P.M. Pardalos, and G. Toraldo. Quadratic programming with box constraints. In Developments in global optimization, pages 73–93. Springer, 1997.
[10] R.S. Dembo and U. Tulowitzki. On the minimization of quadratic functions subject to box constraints. Yale University, Department of Computer Science, 1984.
[11] F. Glineur. Conic optimization: an elegant framework for convex optimization. Belgian Journal of Operations Research, Statistics and Computer Science, 41(1-2): 5–28, 2001.
[12] M.X. Goemans and D.P. Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of the ACM (JACM), 42(6):1115–1145, 1995.
[13] M. Grant and S. Boyd. Cvx: Matlab software for disciplined convex programming, version 1.21 (2011). Available: cvxr. com/cvx, 2010.
[14] L. Lovász and A. Schrijver. Cones of matrices and set-functions and 0-1 optimization. SIAM Journal on Optimization, 1(2):166–190, 1991.
[15] U. Malik, I.M. Jaimoukha, G.D. Halikias, and S.K. Gungah. On the gap between the quadratic integer programming problem and its semidefinite relaxation. Mathematical programming, 107(3):505–515, 2006.
[16] R.G. Michael and S.J. David. Computers and intractability: a guide to the theory of np-completeness. WH Freeman & Co., San Francisco, 1979.
[17] A. Nemirovski. Advances in convex optimization: Conic programming. Proceedings on the International Congress of Mathematicians, 1(21):413–444, 2006.
[18] I.U.E. Nesterov. Quality of semidefinite relaxation for nonconvex quadratic optimization. Center for Operations Research & Econometrics. Université catholique de Louvain, 1997.
[19] E. Polak. Computational methods in optimization: a unified approach, volume 77. Academic press, 1971.
[20] I.G. Rosenberg. Brèves communications. 0-1 optimization and non-linear programming. RAIRO-Operations Research-Recherche Opérationnelle, 6(V2):95–97, 1972.
[21] N.Z. Shor. Quadratic optimization problems. Soviet Journal of Computer and Systems Sciences, 25(6):1–11, 1987.
[22] N.H. Sleumer. Output-sensitive cell enumeration in hyperplane arrangements. Nordic journal of computing, 6(2):137–147, 1999.
[23] S.S. Syam. A dual ascent method for the portfolio selection problem with multiple constraints and linked proposals. European journal of operational research, 108(1): 196–207, 1998.
[24] Y. Vardi, L.A. Shepp, and L. Kaufman. A statistical model for positron emission tomography. Journal of the American Statistical Association, 80(389):8–20, 1985.
[25] Y. Xia, R.L. Sheu, X.L. Sun, and D. Li. Improved estimation of duality gap in binary quadratic programming using a weighted distance measure. European Journal of Operational Research, 218(2):351–357, 2012.
[26] Y. Xia, X.L. Sun, D. Li, and X.J. Zheng. On the reduction of duality gap in box constrained nonconvex quadratic program. SIAM Journal on Optimization, 21(3): 706–729, 2011.
[27] Y. Ye. Approximating quadratic programming with bound and quadratic constraints. Mathematical Programming, 84(2):219–226, 1999.
[28] T. Zaslavsky. Facing up to arrangements: face-count formulas for partitions of space by hyperplanes, volume 1. American Mathematical Society, 1975.