nonconvex optimization

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

    Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming

  • Saeed Ghadimi
  • Guanghui Lan
    • Categories Convex and Nonsmooth Optimization, Stochastic Programming, Unconstrained Optimization Tags , , , ,

    In this paper, we introduce a new stochastic approximation (SA) type algorithm, namely the randomized stochastic gradient (RSG) method, for solving an important class of nonlinear (possibly nonconvex) stochastic programming (SP) problems. We establish the complexity of this method for computing an approximate stationary point of a nonlinear programming problem. We also show that this … Read more

    Smoothing and Worst Case Complexity for Direct-Search Methods in Non-Smooth Optimization

  • R. Garmanjani
  • Luis Nunes Vicente
    • Categories Nonsmooth Optimization, Unconstrained Optimization Tags , , , , ,

    For smooth objective functions it has been shown that the worst case cost of direct-search methods is of the same order as the one of steepest descent, when measured in number of iterations to achieve a certain threshold of stationarity. Motivated by the lack of such a result in the non-smooth case, we propose, analyze, … Read more

    Strong formulations for convex functions over nonconvex sets

  • Daniel Bienstock
  • Alexander Michalka
    • Categories Global Optimization, Nonsmooth Optimization, Second-Order Cone Programming Tags , ,

    In this paper we derive strong linear inequalities for sets of the form {(x, q) ∈ R^d × R : q ≥ Q(x), x ∈ R^d − int(P ) }, where Q(x) : R^d → R is a quadratic function, P ⊂ R^d and “int” denotes interior. Of particular but not exclusive interest is the … Read more

    An Adaptive Gradient Sampling Algorithm for Nonsmooth Optimization

  • Frank E. Curtis
  • Xiaocun Que
    • Categories Nonsmooth Optimization Tags , , , , , ,

    We present an algorithm for the minimization of f : Rn → R, assumed to be locally Lipschitz and continuously differentiable in an open dense subset D of Rn. The objective f may be non-smooth and/or non-convex. The method is based on the gradient sampling (GS) algorithm of Burke et al. [A robust gradient sampling … Read more