A Newton-CG based augmented Lagrangian method for finding a second-order stationary point of nonconvex equality constrained optimization with complexity guarantees

  • Chuan He
  • Zhaosong Lu
  • Ting Kei Pong
    • Categories Constrained Nonlinear Optimization Tags , , , , ,

    In this paper we consider finding a second-order stationary point (SOSP) of nonconvex equality constrained optimization when a nearly feasible point is known. In particular, we first propose a new Newton-CG method for finding an approximate SOSP of unconstrained optimization and show that it enjoys a substantially better complexity than the Newton-CG method [56]. We … Read more

    Strengthening SONC Relaxations with Constraints Derived from Variable Bounds

  • Ksenia Bestuzheva
  • Ambros Gleixner
    • Categories Constrained Nonlinear Optimization, Global Optimization, Optimization Software Design Principles Tags , , ,

    Nonnegativity certificates can be used to obtain tight dual bounds for polynomial optimization problems. Hierarchies of certificate-based relaxations ensure convergence to the global optimum, but higher levels of such hierarchies can become very computationally expensive, and the well-known sums of squares hierarchies scale poorly with the degree of the polynomials. This has motivated research into … Read more

    A Levenberg-Marquardt Method for Nonsmooth Regularized Least Squares

  • Dominique Orban
  • Aleksandr Y. Aravkin
  • Robert Baraldi
    • Categories Data Science Algorithms, Nonlinear Systems and Least-Squares, Nonsmooth Optimization Tags , , , , ,

    We develop a Levenberg-Marquardt method for minimizing the sum of a smooth nonlinear least-squares term \(f(x) = \frac{1}{2} \|F(x)\|_2^2\) and a nonsmooth term \(h\). Both \(f\) and \(h\) may be nonconvex. Steps are computed by minimizing the sum of a regularized linear least-squares model and a model of \(h\) using a first-order method such as … Read more

    A first-order augmented Lagrangian method for constrained minimax optimization

  • Zhaosong Lu
  • Sanyou Mei
    • Categories Constrained Nonlinear Optimization, Robust Optimization Tags , , ,

    In this paper we study a class of constrained minimax problems. In particular, we propose a first-order augmented Lagrangian method for solving them, whose subproblems turn out to be a much simpler structured minimax problem and are suitably solved by a first-order method recently developed in [26] by the authors. Under some suitable assumptions, an … Read more

    Data-driven Prediction of Relevant Scenarios for Robust Combinatorial Optimization

  • Marc Goerigk
  • Jannis Kurtz
    • Categories Optimization in Data Science, Robust Optimization Tags , , ,

    We study iterative methods for (two-stage) robust combinatorial optimization problems with discrete uncertainty. We propose a machine-learning-based heuristic to determine starting scenarios that provide strong lower bounds. To this end, we design dimension-independent features and train a Random Forest Classifier on small-dimensional instances. Experiments show that our method improves the solution process for larger instances … Read more

    Solving Unsplittable Network Flow Problems with Decision Diagrams

  • Hosseinali Salemi
  • Danial Davarnia
    • Categories (Mixed) Integer Linear Programming, Network Optimization, Transportation Tags , , ,

    In unsplittable network flow problems, certain nodes must satisfy a combinatorial requirement that the incoming arc flows cannot be split or merged when routed through outgoing arcs. This so-called “no-split no-merge” requirement arises in unit train scheduling where train consists should remain intact at stations that lack necessary equipment and manpower to attach/detach them. Solving … Read more

    First-order penalty methods for bilevel optimization

  • Zhaosong Lu
  • Sanyou Mei
    • Categories Constrained Nonlinear Optimization Tags , , , ,

    In this paper we study a class of unconstrained and constrained bilevel optimization problems in which the lower-level part is a convex optimization problem, while the upper-level part is possibly a nonconvex optimization problem. In particular, we propose penalty methods for solving them, whose subproblems turn out to be a structured minimax problem and are … Read more

    The Hamiltonian p-median Problem: Polyhedral Results and Branch-and-Cut Algorithm

  • Michele Barbato
  • Luís Gouveia
    • Categories Branch and Cut Algorithms, Combinatorial Optimization, Polyhedra Tags , , , ,

    In this paper we study the Hamiltonian \(p\)-median problem, in which a weighted graph on \(n\) vertices is to be partitioned into \(p\) simple cycles of minimum total weight. We introduce two new families of valid inequalities for a formulation of the problem in the space of natural edge variables. Each one of the families … Read more

    Inexact reduced gradient methods in nonconvex optimization

  • Dat Tran
    • Categories Global Optimization Applications, Unconstrained Optimization

    This paper proposes and develops new linesearch methods with inexact gradient information for finding stationary points of nonconvex continuously differentiable functions on finite-dimensional spaces. Some abstract convergence results for a broad class of linesearch methods are established. A general scheme for inexact reduced gradient (IRG) methods is proposed, where the errors in the gradient approximation … Read more

    Strong Partitioning and a Machine Learning Approximation for Accelerating the Global Optimization of Nonconvex QCQPs

  • Rohit Kannan
  • Harsha Nagarajan
  • Deepjyoti Deka
    • Categories Global Optimization Tags , , , , , ,

    We learn optimal instance-specific heuristics for the global minimization of nonconvex quadratically-constrained quadratic programs (QCQPs). Specifically, we consider partitioning-based convex mixed-integer programming relaxations for nonconvex QCQPs and propose the novel problem of strong partitioning to optimally partition variable domains without sacrificing global optimality. Since solving this max-min strong partitioning problem exactly can be very challenging, … Read more