André L. Tits

Addressing rank degeneracy in constraint-reduced interior-point methods for linear optimization

  • Pierre-Antoine Absil
  • Luke Winternitz
  • André L. Tits
    • Categories Linear Programming Tags , , ,

    In earlier work (Tits et al., SIAM J. Optim., 17(1):119–146, 2006; Winternitz et al., COAP, doi=10.1007/s10589-010-9389-4, 2011), the present authors and their collaborators proposed primal-dual interior-point (PDIP) algorithms for linear optimization that, at each iteration, use only a subset of the (dual) inequality constraints in constructing the search direction. For problems with many more constraints … Read more

    Constraint Reduction with Exact Penalization for Model-Predictive Rotorcraft Control

  • Aaron L. Greenfield
  • Meiyun Y. He
  • Vineet Sahasrabudhe
  • André L. Tits
    • Categories Applications - Science and Engineering, Control Applications, Quadratic Programming Tags , , , , , , , , ,

    Model Predictive Control (also known as Receding Horizon Control (RHC)) has been highly successful in process control applications. Its use for aerospace applications has been hindered by its high computational requirements. In the present paper, we propose using enhanced primal-dual interior-point optimization techniques in the convex-quadratic-program-based RHC control of a rotorcraft. Our enhancements include a … Read more

    Infeasible Constraint-Reduced Interior-Point Methods for Linear Optimization

  • Meiyun Y. He
  • André L. Tits
    • Categories Linear Programming

    Constraint-reduction schemes have been proposed for the solution by means of interior-point methods of linear programs with many more inequality constraints than variables in standard dual form. Such schemes have been shown to be provably convergent and highly efficient in practice. A critical requirement of these schemes is the availability of an initial dual-feasible point. … 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

    Convex duality and entropy-based moment closure: Characterizing degenerate densities

  • Cory D. Hauck
  • C. David Levermore
  • André L. Tits
    • Categories Convex Optimization, Infinite Dimensional Optimization Tags , , , , , ,

    A common method for constructing a function from a finite set of moments is to solve a constrained minimization problem. The idea is to find, among all functions with the given moments, that function which minimizes a physically motivated, strictly convex functional. In the kinetic theory of gases, this functional is the kinetic entropy; the … Read more

    Constraint Reduction for Linear Programs with Many Inequality Constraints

  • Pierre-Antoine Absil
  • André L. Tits
  • William P. Woessner
    • Categories Linear Programming Tags , , , , ,

    Consider solving a linear program in standard form, where the constraint matrix $A$ is $m \times n$, with $n \gg m \gg 1$. Such problems arise, for example, as the result of finely discretizing a semi-infinite program. The cost per iteration of typical primal-dual interior-point methods on such problems is $O(m^2n)$. We propose to reduce … Read more

    Newton-KKT Interior-Point Methods for Indefinite Quadratic Programming

  • Pierre-Antoine Absil
  • André L. Tits
    • Categories Constrained Nonlinear Optimization, Quadratic Programming Tags , , ,

    Two interior-point algorithms are proposed and analyzed, for the (local) solution of (possibly) indefinite quadratic programming problems. They are of the Newton-KKT variety in that (much like in the case of primal-dual algorithms for linear programming) search directions for the `primal´ variables and the Karush-Kuhn-Tucker (KKT) multiplier estimates are components of the Newton (or quasi-Newton) … Read more