A Matrix-free Algorithm for Equality Constrained Optimization Problems with Rank-deficient Jacobians

  • Frank E. Curtis
  • Jorge Nocedal
  • Andreas Wächter
    • Categories Constrained Nonlinear Optimization, Infinite Dimensional Optimization Tags , , , , ,

    We present a line search algorithm for large-scale constrained optimization that is robust and efficient even for problems with (nearly) rank-deficient Jacobian matrices. The method is matrix-free (i.e., it does not require explicit storage or factorizations of derivative matrices), allows for inexact step computations, and is applicable for nonconvex problems. The main components of the … Read more

    Large-Scale Parallel Multibody Dynamics with Frictional Contact on the Graphical Processing Unit

  • Mihai Anitescu
  • Dan Negrut
  • Alessandro Tasora
    • Categories Complementarity and Variational Inequalities, Mechanical Engineering, Second-Order Cone Programming Tags , ,

    In the context of simulating the frictional contact dynamics of large systems of rigid bodies, this paper reviews a novel method for solving large cone complementarity problems by means of a fixed-point iteration algorithm. The method is an extension of the Gauss-Seidel and Gauss-Jacobimethods with overrelaxation for symmetric convex linear complementarity problems. Convergent under fairly … Read more

    A computational study of the use of an optimization-based method for simulating large multibody systems

  • Mihai Anitescu
  • Florian A. Potra
  • Bogdan Gavrea
  • Cosmin G. Petra
    • Categories Mechanical Engineering, Quadratic Programming

    The present work aims at comparing the performance of several quadratic programming (QP) solvers for simulating large-scale frictional rigid-body systems. Traditional time-stepping schemes for simulation of multibody systems are formulated as linear complementarity problems (LCPs) with copositive matrices. Such LCPs are generally solved by means of Lemketype algorithms and solvers such as the PATH solver … Read more

    An Improved Algorithm for the Generalized Quadratic Assignment Problem

  • Monique Guignard
  • Peter M. Hahn
  • Artur Alves Pessoa
  • Yi-Rong Zhu
    • Categories 0-1 Programming, Combinatorial Optimization Tags , ,

    In the Generalized Quadratic Assignment Problem (GQAP), given M facilities and N locations, one must assign each facility to one location so as to satisfy the given facility space requirements, minimizing the sum of installation and facility interaction costs. In this paper, we propose a new Lagrangean relaxation and a lower bounding procedure for the … Read more

    Asymptotic convergence to the optimal value of diagonal proximal iterations in convex minimization

  • Juan Peypouquet
    • Categories Convex Optimization Tags ,

    Given an approximation $\{f_n\}$ of a given objective function $f$, we provide simple and fairly general conditions under which a diagonal proximal point algorithm approximates the value $\inf f$ at a reasonable rate. We also perform some numerical tests and present a short survey on finite convergence. CitationTo appear in Journal of Convex Analysis, 16 … Read more

    Estimating Bounds for Quadratic Assignment Problems Associated with Hamming and Manhattan Distance Matrices based on Semidefinite Programming

  • Hans D Mittelmann
  • Jiming Peng
    • Categories Applications - OR and Management Sciences, Semi-definite Programming Tags , , ,

    Quadratic assignment problems (QAPs) with a Hamming distance matrix of a hypercube or a Manhattan distance matrix of rectangular grids arise frequently from communications and facility locations and are known to be among the hardest discrete optimization problems. In this paper we consider the issue of how to obtain lower bounds for those two classes … Read more

    Strong asymptotic convergence of evolution equations governed by maximal monotone operators

  • Roberto Cominetti
  • Juan Peypouquet
  • S Sorin
    • Categories Applications - Science and Engineering, Convex and Nonsmooth Optimization Tags , ,

    We consider the Tikhonov-like dynamics $-\dot u(t)\in A(u(t))+\varepsilon(t)u(t)$ where $A$ is a maximal monotone operator and the parameter function $\eps(t)$ tends to 0 for $t\to\infty$ with $\int_0^\infty\eps(t)dt=\infty$. When $A$ is the subdifferential of a closed proper convex function $f$, we establish strong convergence of $u(t)$ towards the least-norm minimizer of $f$. In the general case … Read more

    Asymptotic almost-equivalence of abstract evolution systems

  • Felipe Álvarez
  • Juan Peypouquet
    • Categories Basic Sciences Applications, Convex and Nonsmooth Optimization Tags , ,

    We study the asymptotic behavior of almost-orbits of abstract evolution systems in Banach spaces with or without a Lipschitz assumption. In particular, we establish convergence, convergence in average and almost-convergence of almost-orbits both for the weak and the strong topologies based on the behavior of the orbits. We also analyze the set of almost-stationary points. … Read more

    Asymptotic equivalence and Kobayashi-type estimates for nonautonomous monotone operators in Banach spaces

  • Felipe Álvarez
  • Juan Peypouquet
    • Categories Basic Sciences Applications Tags , ,

    We provide a sharp generalization to the nonautonomous case of the well-known Ko\-ba\-yashi estimate for proximal iterates associated with maximal monotone operators. We then derive a bound for the distance between a continuous-in-time trajectory, namely the solution to the differential inclusion $\dot{x} + A(t)x\ni 0$, and the corresponding proximal iterations. We also establish continuity properties … Read more

    Algorithms for stochastic lot-sizing problems with backlogging

  • Yongpei Guan
    • Categories (Mixed) Integer Linear Programming, Stochastic Programming Tags , ,

    As a traditional model in the operations research and management science domain, lot-sizing problem is embedded in many application problems such as production and inventory planning and has been consistently drawing attentions from researchers. There is significant research progress on polynomial time algorithm developments for deterministic uncapacitated lot-sizing problems based on Wagner-and-Whitin property. However, in … Read more