Optimization

Optimization problems arising from partial differential equations can lead to linear programming [C02], quadratic programming [J02], [J08], or more general optimization problem [J03].

I developed the discrete Newton method [J12], today called the truncated Newton method, for use when derivatives are not easy to calculate.

Other work concerned understanding quasi-Newton methods [J41] and making them more efficient [J47].

[J54] is a survey of the impact of numerical linear algebra on optimization.

Efficient adaptive use of conjugate gradient algorithms for computing the search directions in interior point methods was studied in [J55].

In [J83], Haw-ren Fang and I reviewed modified Newton methods based on the Cholesky factorization, determining the properties of existing methods and deriving new methods that perform better.

Jin Hyuk Jung and I proposed efficient algorithms for solving linear programming problems on inexpensive parallel computers GPUs [J89], for training support vector machines [J90], and for solving convex quadratic programming problems with many constraints [J97].

Simon Schurr, Andre' Tits, and I have posed two problems related to conic convex optimization. First [J79] we studied conditions under which such problems are well posed, in the sense that solutions can be constructed for arbitrary specifications of the data values. Second, we studied the accuracy necessary to evaluate the functions in order to preserve polynomial complexity in the solution algorithms [J93].

Many important optimization problems have many more constraints than variables, and, for efficiency, it very useful to identify and neglect the ones that are irrelevant to the solution. In a series of papers with Andre' Tits and collaborators, we showed how this can be done for primal-dual interior point methods, with or without a feasible starting point [J90], [J97], [J101]; see also the recent dissertation of Sungwoo Park.

Advances in solving a very important optimization problem, used, for example, in determining the structure of proteins, were made in collaboration with Haw-ren Fang [J104].

[C02]

Dianne P. O'Leary, ``Linear programming problems arising from partial differential equations,'' in Sparse Matrix Proceedings 1978, Iain S. Duff and G. W. Stewart (Eds.) SIAM Press, Philadelphia (1979) 25-40.

[J02]

Dianne P. O'Leary and Wei H. Yang, ``Elasto-plastic torsion by quadratic programming,'' Computer Methods in Applied Mechanics and Engineering 16 (1978) 361-368.

[J03]

Dianne P. O'Leary, ``Conjugate gradient algorithms in the solution of optimization problems for nonlinear elliptic partial differential equations,'' Computing 22 (1979) 59-77.

[J08]

Dianne P. O'Leary, ``A generalized conjugate gradient algorithm for solving a class of quadratic programming problems,'' Linear Algebra and Its Applications Special Issue on Large Scale Matrix Problems 34 (1980) 371-399. Also in Large Scale Matrix Problems, A. Bjorck, R. J. Plemmons and H. Schneider, eds. North Holland Pub. Co. NY (1981) 391-399.

[J12]

Dianne P. O'Leary, ``A discrete Newton algorithm for minimizing a function of many variables,'' Mathematical Programming 23 (1982) 20-33.

[J41]

Dianne P. O'Leary, ``Why Broyden's nonsymmetric method terminates on linear equations,'' SIAM Journal on Optimization, 5 (1995) 231-235.

[J47]

Tamara Kolda, Dianne P. O'Leary, and Larry Nazareth, ``BFGS with Update Skipping and Varying Memory," SIAM Journal on Optimization, 8 (1998) 1060-1083. http://epubs.siam.org/sam-bin/dbq/article/30645

[J54]

Dianne P. O'Leary, ``Symbiosis between Linear Algebra and Optimization," invited paper, J. of Computational and Applied Math. 123 (2000) 447-465; reprinted in a book Numerical Analysis 2000.

[J55]

Weichung Wang and Dianne P. O'Leary, ``Adaptive Use of Iterative Methods in Predictor-Corrector Interior Point Methods for Linear Programming," Numerical Algorithms, (special issue honoring Richard Varga), 25 (2000) 387-406.

[J79]

Simon P. Schurr, Andre' L. Tits, and Dianne P. O'Leary, ``Universal Duality in Conic Convex Optimization," Mathematical Programming A, (2006) DOI: 10.1007/s10107-005-0690-4 http://dx.doi.org/10.1007/s10107-005-0690-4

[J83]

Haw-ren Fang and Dianne P. O'Leary, ``Modified Cholesky Algorithms: A Catalog with New Approaches," Mathematical Programming A, 2007. DOI:10.1007/s10107-007-0177-6

[J89]

Jin Hyuk Jung and Dianne P. O'Leary, ``Implementing an Interior Point Method for Linear Programs on a CPU-GPU System," Electronic Transactions on Numerical Analysis, 28 (2008) 174-189. http://etna.mcs.kent.edu/vol.28.2007-2008/pp174-189.dir/pp174-189.pdf

[J90]

Jin Hyuk Jung, Dianne P. O'Leary, and Andre' L. Tits, ``Adaptive Constraint Reduction for Training Support Vector Machines," Electronic Transactions on Numerical Analysis, 31 (2008) 156-177. http://etna.mcs.kent.edu/vol.31.2008/pp156-177.dir/pp156-177.pdf

[J93]

Simon P. Schurr, Dianne P. O'Leary, and Andre L. Tits, ``A Polynomial-Time Interior-Point Method for Conic Optimization, with Inexact Barrier Evaluations," SIAM Journal on Optimization, 20 (2009) 548-571. DOI: 10.1137/080722825

[J97]

Jin Hyuk Jung, Dianne P. O'Leary, and André L. Tits, ``Adaptive Constraint Reduction for Convex Quadratic Programming," Computational Optimization and Applications, (March 2010) 33 pages. (Online First) 51(1) (2012) 125-157. DOI:10.1007/s10589-010-9324-8

[J101]

Luke B. Winternitz, Stacey O. Nicholls, André Tits, and Dianne P. O'Leary, ``A Constraint-Reduced Variant of Mehrotra's Predictor-Corrector Algorithm" Computational Optimization and Applications, 19 January 2011, 36 pages. DOI: 10.1007/s10589-010-9389-4

[J104]

Haw-ren Fang and Dianne P. O'Leary, ``Euclidean Distance Matrix Completion Problems," Optimization Methods and Software, Available on-line: December 2011 DOI: 10.1080/10556788.2011.643888

[J104]

Haw-ren Fang and Dianne P. O'Leary, ``Euclidean Distance Matrix Completion Problems," Optimization Methods and Software, Available on-line: December 2011 DOI: 10.1080/10556788.2011.643888