nonconvex optimization

Copositive relaxation beats Lagrangian dual bounds in quadratically and linearly constrained QPs

  • Immanuel M. Bomze
    • Categories Global Optimization Theory, Linear, Cone and Semidefinite Programming, Quadratic Programming Tags , , , , ,

    We study non-convex quadratic minimization problems under (possibly non-convex) quadratic and linear constraints, and characterize both Lagrangian and Semi-Lagrangian dual bounds in terms of conic optimization. While the Lagrangian dual is equivalent to the SDP relaxation (which has been known for quite a while, although the presented form, incorporating explicitly linear constraints, seems to be … Read more

    Narrowing the difficulty gap for the Celis-Dennis-Tapia problem

  • Immanuel M. Bomze
  • Michael L. Overton
    • Categories Constrained Nonlinear Optimization, Global Optimization Theory, Quadratic Programming Tags , , , ,

    We study the {\em Celis-Dennis-Tapia (CDT) problem}: minimize a non-convex quadratic function over the intersection of two ellipsoids. In contrast to the well-studied trust region problem where the feasible set is just one ellipsoid, the CDT problem is not yet fully understood. Our main objective in this paper is to narrow the difficulty gap that … Read more

    Accelerated Gradient Methods for Nonconvex Nonlinear and Stochastic Programming

  • Saeed Ghadimi
  • Guanghui Lan
    • Categories Convex and Nonsmooth Optimization, Nonlinear Optimization Tags , , ,

    In this paper, we generalize the well-known Nesterov’s accelerated gradient (AG) method, originally designed for convex smooth optimization, to solve nonconvex and possibly stochastic optimization problems. We demonstrate that by properly specifying the stepsize policy, the AG method exhibits the best known rate of convergence for solving general nonconvex smooth optimization problems by using first-order … Read more

    A new and improved quantitative recovery analysis for iterative hard thresholding algorithms in compressed sensing

  • Coralia Cartis
  • Andrew Thompson
    • Categories Applications - Science and Engineering, Nonlinear Optimization Tags , ,

    We present a new recovery analysis for a standard compressed sensing algorithm, Iterative Hard Thresholding (IHT) (Blumensath and Davies, 2008), which considers the fixed points of the algorithm. In the context of arbitrary measurement matrices, we derive a sufficient condition for convergence of IHT to a fixed point and a necessary condition for the existence … Read more

    Mini-batch Stochastic Approximation Methods for Nonconvex Stochastic Composite Optimization

  • Saeed Ghadimi
  • Guanghui Lan
  • Hongchao Zhang
    • Categories Constrained Nonlinear Optimization, Convex and Nonsmooth Optimization Tags , , , , , ,

    This paper considers a class of constrained stochastic composite optimization problems whose objective function is given by the summation of a differentiable (possibly nonconvex) component, together with a certain non-differentiable (but convex) component. In order to solve these problems, we propose a randomized stochastic projected gradient (RSPG) algorithm, in which proper mini-batch of samples are … Read more

    Polynomial solvability of variants of the trust-region subproblem

  • Daniel Bienstock
  • Alexander Michalka
    • Categories Linear, Cone and Semidefinite Programming, Quadratic Programming Tags , ,

    The trust region subproblem concerns the minimization of a general quadratic over the unit ball in R^n. Extensions to this problem are of interest because of applications to, for example, combinatorial optimization. However the extension obtained by adding an arbitrary family of linear side constraints is NP-hard. In this paper we consider variants of the … Read more

    Branching and Bounding Improvements for Global Optimization Algorithms with Lipschitz Continuity Properties

  • Coralia Cartis
  • Nicholas I. M. Gould
  • Jaroslav M. Fowkes
    • Categories Global Optimization, Nonlinear Optimization Tags ,

    We present improvements to branch and bound techniques for globally optimizing functions with Lipschitz continuity properties by developing novel bounding procedures and parallelisation strategies. The bounding procedures involve nonconvex quadratic or cubic lower bounds on the objective and use estimates of the spectrum of the Hessian or derivative tensor, respectively. As the nonconvex lower bounds … Read more

    An Adaptive Augmented Lagrangian Method for Large-Scale Constrained Optimization

  • Frank E. Curtis
  • Daniel P. Robinson
  • Hao Jiang
    • Categories Nonlinear Optimization Tags , , , , ,

    We propose an augmented Lagrangian algorithm for solving large-scale constrained optimization problems. The novel feature of the algorithm is an adaptive update for the penalty parameter motivated by recently proposed techniques for exact penalty methods. This adaptive updating scheme greatly improves the overall performance of the algorithm without sacrificing the strengths of the core augmented … Read more

    Mixed-Integer Nonlinear Optimization

  • Pietro Belotti
  • Christian Kirches
  • Sven Leyffer
  • Jeff Linderoth
  • James R. Luedtke
  • Ashutosh Mahajan
    • Categories (Mixed) Integer Nonlinear Programming Tags , , ,

    Many optimal decision problems in scientific, engineering, and public sector applications involve both discrete decisions and nonlinear system dynamics that affect the quality of the final design or plan. These decision problems lead to mixed-integer nonlinear programming (MINLP) problems that combine the combinatorial difficulty of optimizing over discrete variable sets with the challenges of handling … Read more

    An Efficient Global Optimization Algorithm for Nonlinear Sum-of-Ratios Problems

  • Yun-Chol Jong
    • Categories Global Optimization Tags , , , ,

    This paper presents a practical method for finding the globally optimal solution to nonlinear sum-of-ratios problem arising in image processing, engineering and management. Unlike traditional methods which may get trapped in local minima due to the non-convex nature of this problem, our approach provides a theoretical guarantee of global optimality. Our algorithm is based on … Read more