The purpose of this dissertation was to provide a review of the theory of Optimization, in particular quadratic programming, and the algorithms suitable for solving both convex and non-convex quadratic programming problems. Optimization problems arise in a wide variety of fields and many can be effectively modeled with linear equations. However, there are problems for which linear models are not sufficient thus creating a need for non-linear systems. This dissertation includes a literature study of the formal theory necessary for understanding optimization and an investigation of the algorithms available for solving a special class of the non-linear programming problem, namely the quadratic programming problem. It was not the intention of this dissertation to discuss all possible algorithms for solving the quadratic programming problem, therefore certain algorithms for convex and non-convex quadratic programming problems were selected for a detailed discussion in the dissertation. Some of the algorithms were selected arbitrarily, because limited information was available comparing the efficiency of the various algorithms. Algorithms available for solving general non-linear programming problems were also included and briefly discussed as they can be used to solve quadratic programming problems. A number of algorithms were then selected for evaluation, depending on the frequency of use in practice and the availability of software implementing these algorithms. The evaluation included a theoretical and quantitative comparison of the algorithms. The quantitative results were analyzed and discussed and it was shown that the results supported the theoretical comparison. It was also shown that it is difficult to conclude that one algorithm is better than another as the efficiency of an algorithm greatly depends on the size of the problem, the complexity of an algorithm and many other implementation issues. Optimization problems arise continuously in a wide range of fields and thus create the need for effective methods of solving them. This dissertation provides the fundamental theory necessary for the understanding of optimization problems, with particular reference to quadratic programming problems and the algorithms that solve such problems. Keywords: Quadratic Programming, Quadratic Programming Algorithms, Optimization, Non-linear Programming, Convex, Non-convex.

The purpose of this thesis is to discuss Markoff Numbers, their associated binary quadratic forms, together with the units in the associated real quadratic field. Relations betweeen the Markoff Numbers, the explicit structure of the automorph group of the forms, generators of the Commutator Subgroup Γ’ of SL₂(Z) = Γ and the lengths of geodesies on certain Riemann Surfaces are conveyed. A conjecture combining these relations is formulated and expressed at the end of this paper. / Science, Faculty of / Mathematics, Department of / Graduate

In this thesis I will outline the impact of Pell's equation on various branches of number theory, as well as some of the history. I will also discuss some recently discovered properties of the solutions of Pell's equation.

No description available.

Two important topics in the study of Quadratically Constrained Quadratic Programming (QCQP) are how to exactly solve a QCQP with few constraints in polynomial time and how to find an inexpensive and strong relaxation bound for a QCQP with many constraints. In this thesis, we first review some important results on QCQP, like the S-Procedure, and the strength of Lagrangian Relaxation and the semidefinite relaxation. Then we focus on two special classes of QCQP, whose objective and constraint functions take the form trace(X^TQX + 2C^T X) + β, and trace(X^TQX + XPX^T + 2C^T X)+ β respectively, where X is an n by r real matrix. For each class of problems, we proposed different semidefinite relaxation formulations and compared their strength. The theoretical results obtained in this thesis have found interesting applications, e.g., solving the Quadratic Assignment Problem.

Two important topics in the study of Quadratically Constrained Quadratic Programming (QCQP) are how to exactly solve a QCQP with few constraints in polynomial time and how to find an inexpensive and strong relaxation bound for a QCQP with many constraints. In this thesis, we first review some important results on QCQP, like the S-Procedure, and the strength of Lagrangian Relaxation and the semidefinite relaxation. Then we focus on two special classes of QCQP, whose objective and constraint functions take the form trace(X^TQX + 2C^T X) + β, and trace(X^TQX + XPX^T + 2C^T X)+ β respectively, where X is an n by r real matrix. For each class of problems, we proposed different semidefinite relaxation formulations and compared their strength. The theoretical results obtained in this thesis have found interesting applications, e.g., solving the Quadratic Assignment Problem.

Doctor of Philosophy / Department of Mathematics / Todd E. Cochrane / Let $m$ be a positive integer, $p$ be an odd prime, and $\mathbb{Z}_{p^m } = \mathbb{Z}/(p^m )$ be the ring of integers modulo $p^m $. Let $$Q({\mathbf{x}}) = Q(x_1 ,x_2 ,...,x_n ) = \sum\limits_{1 \leqslant i \leqslant j \leqslant n} {a_{ij} x_i x_j } ,$$ be a quadratic form with integer coefficients. Suppose that $n$ is even and $\det A_Q \not \equiv 0\;(\bmod p)$. Set $\Delta = (( - 1)^{n/2} \det A_Q /p)$, where $( \cdot /p)$ is the Legendre symbol and $\left\| {\mathbf{x}} \right\| = \max \left| {x_i } \right|$. Let $V$ be the set of solutions the congruence $ $Q({\mathbf{x}})\, \equiv \;0\quad (\bmod p^m ) \quad(1)$$, contained in $\mathbb{Z}^n $ and let $B$ be any box of points in $\mathbb{Z}^n $of the type $$B = \left\{ {{\mathbf{x}} \in \mathbb{Z}^n \left| {\,a_i \leqslant x_i < a_i + m_i ,\;\,1 \leqslant i \leqslant n} \right.} \right\},$$ where $a_i ,m_i \in \mathbb{Z},\;1 \leqslant m_i \leqslant p^m $. In this dissertation we use the method of exponential sums to investigate how large the cardinality of the box $B$ must be in order to guarantee that there exists a solution ${\mathbf{x}}$of (1) in $ B$. In particular we will focus on cubes (all $m_i $equal) centered at the origin in order to obtain primitive solutions with $\left\| {\mathbf{x}} \right\|$ small. For $m = 2$ and $n \geqslant 4$ we obtain a primitive solution with $\left\| {\mathbf{x}} \right\| \leqslant \max \left\{ {2^5 p,2^{18} } \right\}$. For $m = 3$, $n \geqslant 6$, and $\Delta = + 1$, we get $\left\| {\mathbf{x}} \right\| \leqslant \max \left\{ {2^{2/n} p^{(3/2) + (3/n)} ,2^{(2n + 4)/(n - 2)} } \right\}$. Finally for any $m \geqslant 2$, $n \geqslant m,$ and any nonsingular quadratic form we obtain $\left\| {\mathbf{x}} \right\| \leqslant \max \{ 6^{1/n} p^{m[(1/2) + (1/n)]} ,2^{2(n + 1)/(n - 2)} 3^{2/(n - 2)} \} $. Others results are obtained for boxes $B$ with sides of arbitrary lengths.

In my thesis I deal with quadratic equation, inequality and quadratic function and their teaching with using computer and interactive whiteboard. The thesis is devided into two parts, theoretical one and practical one. In the theoretical part I deal with motivation to learning, constructivism, rating the teaching materials and interactivity in the school surrounding. I state my conclusions from lessons, where I used the prepaired worksheets with secondary vocational school students. The practical part includes my own created worksheets for teaching with interactive whiteboard and their use in teaching on a secondary vocational school.

Liu Shubao. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2005. / Includes bibliographical references (leaves 90-98). / Abstracts in English and Chinese. / Abstract --- p.i / 摘要 --- p.iii / Acknowledgement --- p.iv / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Time-Varying Quadratic Optimization --- p.1 / Chapter 1.2 --- Recurrent Neural Networks --- p.3 / Chapter 1.2.1 --- From Feedforward to Recurrent Networks --- p.3 / Chapter 1.2.2 --- Computational Power and Complexity --- p.6 / Chapter 1.2.3 --- Implementation Issues --- p.7 / Chapter 1.3 --- Thesis Organization --- p.9 / Chapter I --- Theory and Models --- p.11 / Chapter 2 --- Linearly Constrained QP --- p.13 / Chapter 2.1 --- Model Description --- p.14 / Chapter 2.2 --- Convergence Analysis --- p.17 / Chapter 3 --- Quadratically Constrained QP --- p.26 / Chapter 3.1 --- Problem Formulation --- p.26 / Chapter 3.2 --- Model Description --- p.27 / Chapter 3.2.1 --- Model 1 (Dual Model) --- p.28 / Chapter 3.2.2 --- Model 2 (Improved Dual Model) --- p.28 / Chapter II --- Engineering Applications --- p.29 / Chapter 4 --- KWTA Network Circuit Design --- p.31 / Chapter 4.1 --- Introduction --- p.31 / Chapter 4.2 --- Equivalent Reformulation --- p.32 / Chapter 4.3 --- KWTA Network Model --- p.36 / Chapter 4.4 --- Simulation Results --- p.40 / Chapter 4.5 --- Conclusions --- p.40 / Chapter 5 --- Dynamic Control of Manipulators --- p.43 / Chapter 5.1 --- Introduction --- p.43 / Chapter 5.2 --- Problem Formulation --- p.44 / Chapter 5.3 --- Simplified Dual Neural Network --- p.47 / Chapter 5.4 --- Simulation Results --- p.51 / Chapter 5.5 --- Concluding Remarks --- p.55 / Chapter 6 --- Robot Arm Obstacle Avoidance --- p.56 / Chapter 6.1 --- Introduction --- p.56 / Chapter 6.2 --- Obstacle Avoidance Scheme --- p.58 / Chapter 6.2.1 --- Equality Constrained Formulation --- p.58 / Chapter 6.2.2 --- Inequality Constrained Formulation --- p.60 / Chapter 6.3 --- Simplified Dual Neural Network Model --- p.64 / Chapter 6.3.1 --- Existing Approaches --- p.64 / Chapter 6.3.2 --- Model Derivation --- p.65 / Chapter 6.3.3 --- Convergence Analysis --- p.67 / Chapter 6.3.4 --- Model Comparision --- p.69 / Chapter 6.4 --- Simulation Results --- p.70 / Chapter 6.5 --- Concluding Remarks --- p.71 / Chapter 7 --- Multiuser Detection --- p.77 / Chapter 7.1 --- Introduction --- p.77 / Chapter 7.2 --- Problem Formulation --- p.78 / Chapter 7.3 --- Neural Network Architecture --- p.82 / Chapter 7.4 --- Simulation Results --- p.84 / Chapter 8 --- Conclusions and Future Works --- p.88 / Chapter 8.1 --- Concluding Remarks --- p.88 / Chapter 8.2 --- Future Prospects --- p.88 / Bibliography --- p.89

In part I of this dissertation, certain rich geometric properties hidden behind quadratic 0-1 programming are investigated. Especially, we derive new lower bounding methods and variable fixation techniques for quadratic 0-1 optimization problems by investigating geometric features of the ellipse contour of a (perturbed) convex quadratic function. These findings further lead to some new optimality conditions for quadratic 0-1 programming. Integrating these novel solution schemes into a proposed solution algorithm of a branch-and-bound type, we obtain promising preliminary computational results. / In part II of this dissertation, we present new results of the duality gap between the binary quadratic optimization problem and its Lagrangian dual. We first derive a necessary and sufficient condition for the zero duality gap and discuss its relationship with the polynomial solvability of the problem. We then characterize the zeroness of duality gap by the distance, delta, between the binary set and certain affine space C. Finally, we discuss a computational procedure of the distance delta. These results provide new insights into the duality gap and polynomial solvability of binary quadratic optimization problems. / The unconstraint quadratic binary problem (UBQP), as a classical combinatorial problem, finds wide applications in broad field and human activities including engineering, science, finance, etc. The NP-hardness of the combinatorial problems makes a great challenge to solve the ( UBQP). The main purpose of this research is to develop high performance solution method for solving (UBQP) via the geometric properties of the objective ellipse contour and the optimal solution. This research makes several contributions to advance the state-of-the-art of geometric approach of (UBQP). These contributions include both theoretical and numerical aspects as stated below. / Liu, Chunli. / Adviser: Duan Li. / Source: Dissertation Abstracts International, Volume: 70-06, Section: B, page: 3764. / Thesis (Ph.D.)--Chinese University of Hong Kong, 2008. / Includes bibliographical references (leaves 140-153). / Electronic reproduction. Hong Kong : Chinese University of Hong Kong, [2012] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Electronic reproduction. [Ann Arbor, MI] : ProQuest Information and Learning, [200-] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Abstracts in English and Chinese. / School code: 1307.