Skip to Main Content
 

Global Search Box

 
 
 
 

Files

File List


case1056644216.pdf (3.69 MB)

ETD Abstract Container

Abstract Header

Using linear programming to solve convex quadratic programming problems

Ilyes, Amy Louise
http://rave.ohiolink.edu/etdc/view?acc_num=case1056644216

Abstract Details

1993, Doctor of Philosophy, Case Western Reserve University, Operations Research.
Convex quadratic programming is a very important topic in mathematical programming because of its numerous applications in such diverse fields as economics, statistics and engineering. This thesis presents a finite improvement algorithm that solves the Linear Complementarity Problem (LCP) obtained from the Kuhn-Tucker conditions of the quadratic programming problem. The major advantage of the proposed algorithm is that any existing linear programming package may be used without modification to solve a convex quadratic programming problem. The algorithm attempts to solve the LCP by generating a finite sequence of points, each of which satisfies two of the three LCP conditions. It starts with a solution to the linearity constraints of the LCP, if one exists, and all subsequent points generated by the algorithm also satisfy these linearity constraints. At each step of the algorithm, an overall objective function is improved and acts as a measure of progress toward a solution to the LCP. It is shown that when the quadratic program is convex, the M matrix in the associated LCP is positive semidefinite and, in this case, the algorithm obtains a solution to the quadratic program in a finite number of steps. The thesis also addresses computational issues involving general LCP's with positive semidefinite matri ces. Applications involving both convex quadratic problems and linear programming problems are investigated, and computational results are reported for both the finite improvement algorithm and Lemke's algorithm. Specifically, it is shown that when bound constraints are added to the general convex quadratic program, and an initial basic feasible solution is available, the performance of the algorithm on small problems is nearly equivalent to that of Lemke's algorithm. However, as the problem size increases the algorithm becomes less efficient. In fact, it is apparent from computational testing that the algorithm is very dependent on the availability of an initial basic feasible solution, and as a result, its efficiency is strongly correlated to the Phase I procedure used to find such a starting solution. An efficient Phase I procedure is presented in which only one artificial variable is added, and it is shown that under certain circumstances this Phase I procedure follows the same path as Lemke's algorithm, thus yielding the same computational efficiencies.
Daniel Solow (Advisor)
185 p.
Using linear programming solve convex quadratic programming problems

Recommended Citations

Citations

  • Ilyes, A. L. (1993). Using linear programming to solve convex quadratic programming problems [Doctoral dissertation, Case Western Reserve University]. OhioLINK Electronic Theses and Dissertations Center. http://rave.ohiolink.edu/etdc/view?acc_num=case1056644216

    APA Style (7th edition)

  • Ilyes, Amy. Using linear programming to solve convex quadratic programming problems. 1993. Case Western Reserve University, Doctoral dissertation. OhioLINK Electronic Theses and Dissertations Center, http://rave.ohiolink.edu/etdc/view?acc_num=case1056644216.

    MLA Style (8th edition)

  • Ilyes, Amy. "Using linear programming to solve convex quadratic programming problems." Doctoral dissertation, Case Western Reserve University, 1993. http://rave.ohiolink.edu/etdc/view?acc_num=case1056644216

    Chicago Manual of Style (17th edition)

case1056644216
873
© 1993, all rights reserved.
This open access ETD is published by Case Western Reserve University School of Graduate Studies and OhioLINK.