Algorithms for Block Tridiagonal Systems: Foundations and New Results for Generalized Kalman Smoothing

  • Aleksandr Y. Aravkin
  • James V. Burke
  • Bradley Bell
  • Gianluigi Pillonetto
    • Categories Control Applications, Convex Optimization

    Block tridiagonal systems appear in classic Kalman smoothing problems, as well in generalized Kalman smoothing, where problems may have nonsmooth terms, singular covariance, constraints, nonlinear models, and unknown parameters. In this paper, first we interpret all the classic smoothing algorithms as different approaches to solve positive definite block tridiagonal linear systems. Then, we obtain new … Read more

    On the Linear Convergence to Weak/Standard D-stationary Points of DCA-based Algorithms for Structured Nonsmooth DC Programming

  • Dong Hongbo
  • Tao Min
    • Categories Nonlinear Optimization

    We consider a class of structured nonsmooth difference-of-convex minimization. We allow nonsmoothness in both the convex and concave components in the objective function, with a finite max structure in the concave part. Our focus is on algorithms that compute a (weak or standard) d(irectional)-stationary point as advocated in a recent work of Pang et al. … Read more

    A New Dual Face Algorithm Using LU Factorization for Linear Programming

  • Ping-Qi Pan
    • Categories Linear, Cone and Semidefinite Programming Tags , , , ,

    The dual face algorithm for linear programming (LP) was proposed by the author in 2014. Using QR factorization, it proceeds from dual face to dual face, until reaching an optimal dual face along with dual and primal optimal solutions, unless detecting infeasibility of the problem. On the other hand, a variant of the algorithm using … Read more

    Residuals-based distributionally robust optimization with covariate information

  • Rohit Kannan
  • Güzin Bayraksan
  • James R. Luedtke
    • Categories Robust Optimization, Stochastic Programming Tags , , , , , , ,

    We consider data-driven approaches that integrate a machine learning prediction model within distributionally robust optimization (DRO) given limited joint observations of uncertain parameters and covariates. Our framework is flexible in the sense that it can accommodate a variety of regression setups and DRO ambiguity sets. We investigate asymptotic and finite sample properties of solutions obtained … Read more

    Time-Domain Decomposition for Optimal Control Problems Governed by Semilinear Hyperbolic Systems

  • Richard Krug
  • Günter Leugering
  • Martin Schmidt
  • Dieter Weninger
  • Alexander Martin
    • Categories Systems governed by Differential Equations Optimization Tags , , , ,

    In this article, we extend the time-domain decomposition method described by Lagnese and Leugering (2003) to semilinear optimal control problems for hyperbolic balance laws with spatio-temporal varying coefficients. We provide the design of the iterative method applied to the global first-order optimality system, prove its convergence, and derive an a posteriori error estimate. The analysis … Read more

    EFIX: Exact Fixed Point Methods for Distributed Optimization

  • Dušan Jakovetić
  • Nataša Krejić
  • Nataša Krklec Jerinkić
    • Categories Convex Optimization, Global Optimization Theory, Quadratic Programming Tags , , ,

    We consider strongly convex distributed consensus optimization over connected networks. EFIX, the proposed method, is derived using quadratic penalty approach. In more detail, we use the standard reformulation – transforming the original problem into a constrained problem in a higher dimensional space – to define a sequence of suitable quadratic penalty subproblems with increasing penalty … Read more

    Multipliers Correction Methods for Optimization Problems over the Stiefel Manifold

  • Bin Gao
  • Xin Liu
  • Lei Wang
    • Categories Constrained Nonlinear Optimization Tags , , ,

    We propose a class of multipliers correction methods to minimize a differentiable function over the Stiefel manifold. The proposed methods combine a function value reduction step with a proximal correction step. The former one searches along an arbitrary descent direction in the Euclidean space instead of a vector in the tangent space of the Stiefel … Read more

    On Recognizing Staircase Compatibility

  • Andreas Bärmann
  • Maximilian Merkert
  • Patrick Gemander
  • Alexander Martin
    • Categories 0-1 Programming, Graphs and Matroids, Scheduling Tags , , ,

    For the problem to find an m-clique in an m-partite graph, staircase compatibility has recently been introduced as a polynomial-time solvable special case. It is a property of a graph together with an m-partition of the vertex set and total orders on each subset of the partition. In optimization problems involving m-cliques in m-partite graphs … Read more

    User manual of NewtBracket: “A Newton-Bracketing method for a simple conic optimization problem” with applications to QOPs in binary variables

  • Sunyoung Kim
  • Masakazu Kojima
  • Kim-Chuan Toh
    • Categories Linear, Cone and Semidefinite Programming Tags , , , ,

    We describe the Matlab package NewtBracket for solving a simple conic optimization problem that minimizes a linear objective function subject to a single linear equality constraint and a convex cone constraint. The problem is converted into the problem of finding the largest zero $y^*$ of a continuously differentiable (except at $y^*$) convex function $g : … Read more

    Safely Learning Dynamical Systems from Short Trajectories

  • Amir Ali Ahmadi
  • Abraar Chaudhry
  • Vikas Sindhwani
  • Stephen Tu
    • Categories Control Applications, Linear, Cone and Semidefinite Programming, Robust Optimization Tags , , , ,

    A fundamental challenge in learning to control an unknown dynamical system is to reduce model uncertainty by making measurements while maintaining safety. In this work, we formulate a mathematical definition of what it means to safely learn a dynamical system by sequentially deciding where to initialize the next trajectory. In our framework, the state of … Read more