 Library Home /
 Search Collections /
 Open Collections /
 Browse Collections /
 UBC Theses and Dissertations /
 Quadratic programming : quantitative analysis and polynomial...
Open Collections
UBC Theses and Dissertations
UBC Theses and Dissertations
Quadratic programming : quantitative analysis and polynomial running time algorithms Boljunčić, Jadranka
Abstract
Many problems in economics, statistics and numerical analysis can be formulated as the optimization of a convex quadratic function over a polyhedral set. A polynomial algorithm for solving convex quadratic programming problems was first developed by Kozlov at al. (1979). Tardos (1986) was the first to present a polynomial algorithm for solving linear programming problems in which the number of arithmetic steps depends only on the size of the numbers in the constraint matrix and is independent of the size of the numbers in the right hand side and the cost coefficients. In the first part of the thesis we extended Tardos' results to strictly convex quadratic programming of the form max {cTx½xTDx : Ax ≤ b, x ≥0} with D being symmetric positive definite matrix. In our algorithm the number of arithmetic steps is independent of c and b but depends on the size of the entries of the matrices A and D. Another part of the thesis is concerned with proximity and sensitivity of integer and mixedinteger quadratic programs. We have shown that for any optimal solution z̅ for a given separable quadratic integer programming problem there exist an optimal solution x̅ for its continuous relaxation such that; z̅  x̅; ∞≤n∆(A) where n is the number of variables and ∆(A) is the largest absolute subdeterminant of the integer constraint matrix A . We have further shown that for any feasible solution z, which is not optimal for the separable quadratic integer programming problem, there exists a feasible solution z̅ having greater objective function value and with; z  z̅; ∞≤n∆(A). Under some additional assumptions the distance between a pair of optimal solutions to the integer quadratic programming problem with right hand side vectors b and b', respectively, depends linearly on; b — b'; ₁. The extension to the mixedinteger nonseparable quadratic case is also given. Some sensitivity analysis results for nonlinear integer programming problems are given. We assume that the nonlinear 0 — 1 problem was solved by implicit enumeration and that some small changes have been made in the right hand side or objective function coefficients. We then established what additional information to keep in the implicit enumeration tree, when solving the original problem, in order to provide us with bounds on the optimal value of a perturbed problem. Also, suppose that after solving the original problem to optimality the problem was enlarged by introducing a new 0 — 1 variable, say xn+1. We determined a lower bound on the added objective function coefficients for which the new integer variable xn+1 remains at zero level in the optimal solution for the modified integer nonlinear program. We discuss the extensions to the mixedinteger case as well as to the case when integer variables are not restricted to be 0 or 1. The computational results for an example with quadratic objective function, linear constraints and 0—1 variables are provided. Finally, we have shown how to replace the objective function of a quadratic program with 0—1 variables ( by an integer objective function whose size is polynomially bounded by the number of variables) without changing the set of optimal solutions. This was done by making use of the algorithm given by Frank and Tardos (1985) which in turn uses the simultaneous approximation algorithm of Lenstra, Lenstra and Lovász (1982).
Item Metadata
Title 
Quadratic programming : quantitative analysis and polynomial running time algorithms

Creator  
Publisher 
University of British Columbia

Date Issued 
1987

Description 
Many problems in economics, statistics and numerical analysis can be formulated as the optimization of a convex quadratic function over a polyhedral set. A polynomial algorithm for solving convex quadratic programming problems was first developed by Kozlov at al. (1979). Tardos (1986) was the first to present a polynomial
algorithm for solving linear programming problems in which the number of arithmetic steps depends only on the size of the numbers in the constraint matrix and is independent of the size of the numbers in the right hand side and the cost coefficients. In the first part of the thesis we extended Tardos' results to strictly convex quadratic programming of the form max {cTx½xTDx : Ax ≤ b, x ≥0} with D being symmetric positive definite matrix. In our algorithm the number of arithmetic steps is independent of c and b but depends on the size of the entries of the matrices A and D.
Another part of the thesis is concerned with proximity and sensitivity of integer and mixedinteger quadratic programs. We have shown that for any optimal solution z̅ for a given separable quadratic integer programming problem there exist an optimal solution x̅ for its continuous relaxation such that; z̅  x̅; ∞≤n∆(A) where n is the number of variables and ∆(A) is the largest absolute subdeterminant of the integer constraint matrix A . We have further shown that for any feasible solution z, which is not optimal for the separable quadratic integer programming problem, there exists a feasible solution z̅ having greater objective function value and with; z  z̅; ∞≤n∆(A). Under some additional assumptions the distance between a pair of optimal solutions to the integer quadratic programming
problem with right hand side vectors b and b', respectively, depends linearly on; b — b'; ₁. The extension to the mixedinteger nonseparable quadratic case is also given.
Some sensitivity analysis results for nonlinear integer programming problems are given. We assume that the nonlinear 0 — 1 problem was solved by implicit enumeration and that some small changes have been made in the right hand side or objective function coefficients. We then established what additional information to keep in the implicit enumeration tree, when solving the original problem, in order to provide us with bounds on the optimal value of a perturbed problem. Also, suppose that after solving the original problem to optimality the problem was enlarged by introducing a new 0 — 1 variable, say xn+1. We determined a lower bound on the added objective function coefficients for which the new integer variable xn+1 remains at zero level in the optimal solution for the modified integer nonlinear program. We discuss the extensions to the mixedinteger case as well as to the case when integer variables are not restricted to be 0 or 1. The computational results for an example with quadratic objective function, linear constraints and 0—1 variables are provided.
Finally, we have shown how to replace the objective function of a quadratic program
with 0—1 variables ( by an integer objective function whose size is polynomially bounded by the number of variables) without changing the set of optimal solutions. This was done by making use of the algorithm given by Frank and Tardos (1985) which in turn uses the simultaneous approximation algorithm of Lenstra, Lenstra and Lovász (1982).

Genre  
Type  
Language 
eng

Date Available 
20100818

Provider 
Vancouver : University of British Columbia Library

Rights 
For noncommercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use.

DOI 
10.14288/1.0097502

URI  
Degree  
Program  
Affiliation  
Degree Grantor 
University of British Columbia

Campus  
Scholarly Level 
Graduate

Aggregated Source Repository 
DSpace

Item Media
Item Citations and Data
Rights
For noncommercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use.