| Interior Point Methods for Linear Programming and Concave Quadratic Programming | |||||||||
| Funding: |
CONACyT, México (Grant for graduate studies) U. of Texas - Austin (Continuing Fellowship) |
||||||||
| Dates: | 1992 - 1994 | ||||||||
| People: |
Prof. Jon Bard (U. of Texas) Supervisor
Roger Z. Ríos (U. of Texas)
|
||||||||
| Summary: |
Before beginning my dissertation, I was involved in
a research project to develop efficient interior point algorithms
for linear programming. In this research, I developed and coded
(in FORTRAN) a primal-dual interior point algorithm for linear
optimization models. The aim was to solve large-scale instances.
This code uses an efficient data structure for sparse matrix
manipulation that greatly simplifies the computational load.
As part of the research, I investigated and compared several
of the existing state-of-the-art interior point method codes
such as LOQO (developed by Prof. Robert Vanderbei from
Princeton U.), HOPDM (developed by Prof. Anna Altman and
Prof. Jacek Gondzio from Polish Academy of Sciences), and OSL
(Optimization Subroutine Library from IBM). Although there was
not an unanimous dominance, I found LOQO better structured and
suitable for the second part of my research, which focused on
using these interior point techniques to solve nonconvex
quadratic optimization models. My approaches to this very
difficult problem were not fully successful. After I developed
an interior point algorithm for this problem, I faced several
difficulties such as a slow rate of convergence and inability
to efficiently escape from local optimum. As of today,
nonconvex quadratic optimization remains one of the most
challenging problems.
|
||||||||
| Publications: |
|
||||||||