Dianne P. O'Leary

A Polynomial Time Constraint-Reduced Algorithm for Semidefinite Optimization Problems, with Convergence Proofs

  • Dianne P. O'Leary
  • Sungwoo Park
    • Categories Semi-definite Programming Tags , , , , , , , , ,

    We present an infeasible primal-dual interior point method for semidefinite optimization problems, making use of constraint reduction. We show that the algorithm is globally convergent and has polynomial complexity, the first such complexity result for primal-dual constraint reduction algorithms for any class of problems. Our algorithm is a modification of one with no constraint reduction … Read more

    Euclidean Distance Matrix Completion Problems

  • Haw-ren Fang
  • Dianne P. O'Leary
    • Categories Chemical Engineering, Global Optimization Applications Tags , , , , ,

    A Euclidean distance matrix is one in which the $(i,j)$ entry specifies the squared distance between particle $i$ and particle $j$. Given a partially-specified symmetric matrix $A$ with zero diagonal, the Euclidean distance matrix completion problem (EDMCP) is to determine the unspecified entries to make $A$ a Euclidean distance matrix. We survey three different approaches … Read more

    Adaptive Constraint Reduction for Convex Quadratic Programming

  • Jin Hyuk Jung
  • Dianne P. O'Leary
  • André L. Tits
    • Categories Quadratic Programming Tags , , ,

    We propose an adaptive, constraint-reduced, primal-dual interior-point algorithm for convex quadratic programming with many more inequality constraints than variables. We reduce the computational e ort by assembling, instead of the exact normal-equation matrix, an approximate matrix from a well chosen index set which includes indices of constraints that seem to be most critical. Starting with a … Read more

    Adaptive Constraint Reduction for Training Support Vector Machines

  • Jin Hyuk Jung
  • Dianne P. O'Leary
  • André L. Tits
    • Categories Data-Mining, Quadratic Programming Tags , , ,

    A support vector machine (SVM) determines whether a given observed pattern lies in a particular class. The decision is based on prior training of the SVM on a set of patterns with known classification, and training is achieved by solving a convex quadratic programming problem. Since there are typically a large number of training patterns, … Read more

    A Constraint-Reduced Variant of Mehrotra’s Predictor-Corrector Algorithm

  • Stacey Nicholls
  • Dianne P. O'Leary
  • Luke Winternitz
  • André L. Tits
    • Categories Linear Programming Tags , , ,

    Consider linear programs in dual standard form with n constraints and m variables. When typical interior-point algorithms are used for the solution of such problems, updating the iterates, using direct methods for solving the linear systems and assuming a dense constraint matrix A, requires O(nm^2) operations. When n>>m it is often the case that at … Read more

    A polynomial-time interior-point method for conic optimization, with inexact barrier evaluations

  • Dianne P. O'Leary
  • Simon P. Schurr
  • André L. Tits
    • Categories Convex and Nonsmooth Optimization, Linear, Cone and Semidefinite Programming Tags , , , ,

    In this work we develop a primal-dual short-step interior point method for conic convex optimization problems for which exact evaluation of the gradient and Hessian of the barrier function is either impossible or too expensive. As our main contribution, we show that if approximate gradients and Hessians can be computed, and the relative errors in … Read more

    Modified Cholesky Algorithms: A Catalog with New Approaches

  • Haw-ren Fang
  • Dianne P. O'Leary
    • Categories Nonlinear Optimization Tags , ,

    Given an n by n symmetric possibly indefinite matrix A, a modified Cholesky algorithm computes a factorization of the positive definite matrix A+E, where E is a correction matrix. Since the factorization is often used to compute a Newton-like downhill search direction for an optimization problem, the goals are to compute the modification without much … Read more

    Universal Duality in Conic Convex Optimization

  • Dianne P. O'Leary
  • Simon P. Schurr
  • André L. Tits
    • Categories Linear, Cone and Semidefinite Programming Tags , , , ,

    Given a primal-dual pair of linear programs, it is well known that if their optimal values are viewed as lying on the extended real line, then the duality gap is zero, unless both problems are infeasible, in which case the optimal values are +infinity and -infinity. In contrast, for optimization problems over nonpolyhedral convex cones, … Read more