Convergence rate and iteration complexity on the alternating direction method of multipliers with a substitution procedure for separable convex programming

  • Bingsheng He
  • Tao Min
  • Xiao-Ming Yuan
    • Categories Convex Optimization Tags , , , ,

    Recently, in [17] we have showed the first possibility of combining the Douglas-Rachford alternating direction method of multipliers (ADMM) with a Gaussian back substitution procedure for solving a convex minimization model with a general separable structure. This paper is a further study on theoretical aspects of this theme. We first derive a general algorithmic framework … Read more

    Alternating Proximal Gradient Method for Convex Minimization

  • Shiqian Ma
    • Categories Convex Optimization Tags , , ,

    In this paper, we propose an alternating proximal gradient method that solves convex minimization problems with three or more separable blocks in the objective function. Our method is based on the framework of alternating direction method of multipliers. The main computational effort in each iteration of the proposed method is to compute the proximal mappings … Read more

    Threshold Boolean Form for Joint Probabilistic Constraints with Random Technology Matrix

  • Alexander Kogan
  • Miguel A. Lejeune
    • Categories (Mixed) Integer Nonlinear Programming, Data-Mining, Stochastic Programming Tags , , , , ,

    We develop a new modeling and exact solution method for stochastic programming problems that include a joint probabilistic constraint in which the multirow random technology matrix is discretely distributed. We binarize the probability distribution of the random variables in such a way that we can extract a threshold partially defined Boolean function (pdBf) representing the … Read more

    Compressed Sensing Off the Grid

  • Badri Narayan Bhaskar
  • Benjamin Recht
  • Parikshit Shah
  • Gongguo Tang
    • Categories Convex Optimization, Data-Mining, Semi-definite Programming Tags , , , , , , ,

    We consider the problem of estimating the frequency components of a mixture of s complex sinusoids from a random subset of n regularly spaced samples. Unlike previous work in compressed sensing, the frequencies are not assumed to lie on a grid, but can assume any values in the normalized frequency domain [0, 1]. We propose … Read more

    Equilibria on the Day-Ahead Electricity Market

  • Margarida Carvalho
  • João Pedro Pedroso
    • Categories Finance and Economics, Game Theory

    In the energy sector, there has been a transition from monopolistic to oligopolistic situations (pool markets); each time more companies’ optimization revenues depend on the strategies of their competitors. The market rules vary from country to country. In this work, we model the Iberian Day-Ahead Duopoly Market and find exactly which are the outcomes (Nash … Read more

    On the complexity of the steepest-descent with exact linesearches

  • Coralia Cartis
  • Nicholas I. M. Gould
  • Philippe L. Toint
    • Categories Nonlinear Systems and Least-Squares, Unconstrained Optimization Tags , ,

    The worst-case complexity of the steepest-descent algorithm with exact linesearches for unconstrained smooth optimization is analyzed, and it is shown that the number of iterations of this algorithm which may be necessary to find an iterate at which the norm of the objective function’s gradient is less that a prescribed $\epsilon$ is, essentially, a multiple … Read more

    Linearizing the Method of Conjugate Gradients

  • Serge Gratton
  • David Titley-Peloquin
  • Philippe L. Toint
  • Jean Tshimanga Ilunga
    • Categories Basic Sciences Applications, Unconstrained Optimization Tags , , , ,

    The method of conjugate gradients (CG) is widely used for the iterative solution of large sparse systems of equations $Ax=b$, where $A\in\Re^{n\times n}$ is symmetric positive definite. Let $x_k$ denote the $k$–th iterate of CG. In this paper we obtain an expression for $J_k$, the Jacobian matrix of $x_k$ with respect to $b$. We use … Read more

    Conjugate-gradients versus multigrid solvers for diffusion-based correlation models in data assimilation

  • Serge Gratton
  • Philippe L. Toint
  • Jean Tshimanga Ilunga
    • Categories Nonlinear Systems and Least-Squares, Optimization of Systems modeled by PDEs

    This paper provides a theoretical and experimental comparison between conjugate-gradients and multigrid, two iterative schemes for solving linear systems, in the context of applying diffusion-based correlation models in data assimilation. In this context, a large number of such systems has to be (approximately) solved if the implicit mode is chosen for integrating the involved diffusion … Read more

    How much patience do you have? A worst-case perspective on smooth nonconvex optimization

  • Coralia Cartis
  • Nicholas I. M. Gould
  • Philippe L. Toint
    • Categories Constrained Nonlinear Optimization, Nonlinear Systems and Least-Squares, Unconstrained Optimization Tags , ,

    The paper presents a survey of recent results in the field of worst-case complexity of algorithms for nonlinear (and possibly nonconvex) smooth optimization. Both constrained and unconstrained case are considered. ArticleDownload View PDF

    Gradient consistency for integral-convolution smoothing functions

  • James V. Burke
  • Tim Hoheisel
  • Christian Kanzow
    • Categories Convex and Nonsmooth Optimization, Nonlinear Optimization Tags , , ,

    Chen and Mangasarian (1995) developed smoothing approximations to the plus function built on integral-convolution with density functions. X. Chen (2012) has recently picked up this idea constructing a large class of smoothing functions for nonsmooth minimization through composition with smooth mappings. In this paper, we generalize this idea by substituting the plus function for an … Read more