New results on subgradient methods for strongly convex optimization problems with a unified analysis

  • Masaru Ito
    • Categories Constrained Nonlinear Optimization, Convex Optimization, Nonsmooth Optimization Tags , , , , , ,

    We develop subgradient- and gradient-based methods for minimizing strongly convex functions under a notion which generalizes the standard Euclidean strong convexity. We propose a unifying framework for subgradient methods which yields two kinds of methods, namely, the Proximal Gradient Method (PGM) and the Conditional Gradient Method (CGM), unifying several existing methods. The unifying framework provides … Read more

    Lower Bounds on Complexity of Lyapunov Functions for Switched Linear Systems

  • Amir Ali Ahmadi
  • Raphaël Jungers
    • Categories Convex Optimization, Semi-definite Programming, Systems governed by Differential Equations Optimization Tags , , ,

    We show that for any positive integer $d$, there are families of switched linear systems—in fixed dimension and defined by two matrices only—that are stable under arbitrary switching but do not admit (i) a polynomial Lyapunov function of degree $\leq d$, or (ii) a polytopic Lyapunov function with $\leq d$ facets, or (iii) a piecewise … Read more

    An MILP-MINLP decomposition method for the global optimization of a source based model of the multiperiod blending problem

  • Myun-Seok Cheon
  • Ignacio E. Grossmann
  • Irene Lotero
  • Dimitri J. Papageorgiou
  • Francisco Trespalacios
    • Categories Chemical Engineering, Scheduling

    The multiperiod blending problem involves binary variables and bilinear terms, yielding a nonconvex MINLP. In this work we present two major contributions for the global solution of the problem. The rst one is an alternative formulation of the problem. This formulation makes use of redundant constraints that improve the MILP relaxation of the MINLP. The … Read more

    Exactly solving packing problems with fragmentation

  • Marco Casazza
  • Alberto Ceselli
    • Categories Applications - Science and Engineering, Combinatorial Optimization, Integer Programming Tags , , ,

    In packing problems with fragmentation a set of items of known weight is given, together with a set of bins of limited capacity; the task is to find an assignment of items to bins such that the sum of items assigned to the same bin does not exceed its capacity. As a distinctive feature, items … Read more

    Iteration Complexity Analysis of Multi-Block ADMM for a Family of Convex Minimization without Strong Convexity

  • Tianyi Lin
  • Shiqian Ma
  • Shuzhong Zhang
    • Categories Convex and Nonsmooth Optimization Tags , ,

    The alternating direction method of multipliers (ADMM) is widely used in solving structured convex optimization problems due to its superior practical performance. On the theoretical side however, a counterexample was shown in [7] indicating that the multi-block ADMM for minimizing the sum of $N$ $(N\geq 3)$ convex functions with $N$ block variables linked by linear … Read more

    Sparse optimization for inverse problems in atmospheric modelling

  • Lukáš Adam
  • Martin Branda
    • Categories 0-1 Programming, Civil and Environmental Engineering Tags , , , , ,

    We consider inverse problems in atmospheric modelling. Instead of using the ordinary least squares, we add a weighting matrix based on the topology of measurement points and show the connection with Bayesian modelling. Since the source–receptor sensitivity matrix is usually ill-conditioned, the problem is often regularized, either by perturbing the objective function or by modifying … Read more

    On an adaptive regularization for ill-posed nonlinear systems and its trust-region implementation

  • Stefania Bellavia
  • Benedetta Morini
  • Elisa Riccietti
    • Categories Nonlinear Optimization Tags , , ,

    In this paper we address the stable numerical solution of nonlinear ill-posed systems by a trust-region method. We show that an appropriate choice of the trust-region radius gives rise to a procedure that has the potential to approach a solution of the unperturbed system. This regularizing property is shown theoretically and validated numerically. CitationDipartimento di … Read more

    Convergence rates for forward-backward dynamical systems associated with strongly monotone inclusions

  • Radu Ioan Bot
  • Ernö Robert Csetnek
    • Categories Convex Optimization, Nonsmooth Optimization, Systems governed by Differential Equations Optimization Tags , , , ,

    We investigate the convergence rates of the trajectories generated by implicit first and second order dynamical systems associated to the determination of the zeros of the sum of a maximally monotone operator and a monotone and Lipschitz continuous one in a real Hilbert space. We show that these trajectories strongly converge with exponential rate to … Read more

    An implementation of the steepest descent method using retractions on riemannian manifolds

  • Ever Cruzado
  • Erik Alex Papa Quiroz
    • Categories Global Optimization Tags , , ,

    In 2008 Absil et al. published a book with optimization methods in Riemannian manifolds. The authors developed steepest descent, Newton, trust-region and conjugate gradients methods using an approximation of the geodesic called retraction. In this paper we present implementations of the of steepest descent method of Absil et al. using Matlab software. We show the … Read more

    An extension of the projected gradient method to a Banach space setting with application in structural topology optimization

  • Luise Blank
  • Christoph Rupprecht
    • Categories Constrained Nonlinear Optimization, Control Applications, Systems governed by Differential Equations Optimization Tags , , , ,

    For the minimization of a nonlinear cost functional under convex constraints the relaxed projected gradient process is a well known method. The analysis is classically performed in a Hilbert space. We generalize this method to functionals which are differentiable in a Banach space. The search direction is calculated by a quadratic approximation of the cost … Read more