Nonlinear Optimization

A Stochastic Sequential Quadratic Optimization Algorithm for Nonlinear Equality Constrained Optimization with Rank-Deficient Jacobians

  • Albert S. Berahas
  • Frank E. Curtis
  • Michael J. O'Neill
  • Daniel P. Robinson
    • Categories Constrained Nonlinear Optimization, Statistics Tags , , , ,

    A sequential quadratic optimization algorithm is proposed for solving smooth nonlinear equality constrained optimization problems in which the objective function is defined by an expectation of a stochastic function. The algorithmic structure of the proposed method is based on a step decomposition strategy that is known in the literature to be widely effective in practice, … Read more

    A stochastic first-order trust-region method with inexact restoration for finite-sum minimization

  • Stefania Bellavia
  • Nataša Krejić
  • Benedetta Morini
  • Simone Rebegoldi
    • Categories Nonlinear Optimization Tags , , , ,

    We propose a stochastic first-order trust-region method with inexact function and gradient evaluations for solving finite-sum minimization problems. At each iteration, the function and the gradient are approximated by sampling. The sample size in gradient approximations is smaller than the sample size in function approximations and the latter is determined using a deterministic rule inspired … Read more

    Frank-Wolfe and friends: a journey into projection-free first-order optimization methods

  • Immanuel M. Bomze
  • Francesco Rinaldi
  • Damiano Zeffiro
    • Categories Convex Optimization, Nonlinear Optimization Tags , , , ,

    Invented some 65 years ago in a seminal paper by Marguerite Straus-Frank and Philip Wolfe, the Frank-Wolfe method recently enjoys a remarkable revival, fuelled by the need of fast and reliable first-order optimization methods in Data Science and other relevant application areas. This review tries to explain the success of this approach by illustrating versatility … Read more

    Cardinality Minimization, Constraints, and Regularization: A Survey

  • Daniel Bienstock
  • Andrea Lodi
  • Andreas M. Tillmann
  • Alexandra Schwartz
    • Categories (Mixed) Integer Linear Programming, (Mixed) Integer Nonlinear Programming, Constrained Nonlinear Optimization Tags , , , , , , ,

    We survey optimization problems that involve the cardinality of variable vectors in constraints or the objective function. We provide a unified viewpoint on the general problem classes and models, and give concrete examples from diverse application fields such as signal and image processing, portfolio selection, or machine learning. The paper discusses general-purpose modeling techniques and … Read more

    Inductive Linearization for Binary Quadratic Programs with Linear Constraints: A Computational Study

  • Sven Mallach
    • Categories (Mixed) Integer Nonlinear Programming, 0-1 Programming, Quadratic Programming Tags , , ,

    The computational performance of inductive linearizations for binary quadratic programs in combination with a mixed-integer programming solver is investigated for several combinatorial optimization problems and established benchmark instances. Apparently, a few of these are solved to optimality for the first time. Citationpreprint (no internal series / number): University of Bonn, Germany June 11, 2021ArticleDownload View … Read more

    LSOS: Line-search Second-Order Stochastic optimization methods for nonconvex finite sums

  • Daniela di Serafino
  • Nataša Krejić
  • Nataša Krklec Jerinkić
  • Marco Viola
    • Categories Nonlinear Optimization, Stochastic Programming Tags , , , ,

    We develop a line-search second-order algorithmic framework for minimizing finite sums. We do not make any convexity assumptions, but require the terms of the sum to be continuously differentiable and have Lipschitz-continuous gradients. The methods fitting into this framework combine line searches and suitably decaying step lengths. A key issue is a two-step sampling at … Read more

    MatQapNB User Guide: A branch-and-bound program for QAPs in Matlab with the Newton-Bracketing method

  • Koichi Fujii
  • Naoki Ito
  • Sunyoung Kim
  • Masakazu Kojima
  • Hans D Mittelmann
  • Kim-Chuan Toh
  • Yuji Shinano
    • Categories Global Optimization Applications, Optimization Software Design Principles, Quadratic Programming Tags , , ,

    MatQapNB is a MATLAB toolbox that implements a parallel branch-and-bound method using NewtBracket (the Newton bracketing method [4]) for its lower bounding procedure. It can solve small to medium scale Quadratic Assignment Problem (QAP) instances with dimension up to 30. MatQapNB was used in the numerical experiments on QAPs in the recent article “Solving challenging … Read more

    A stochastic alternating balance k-means algorithm for fair clustering

  • Suyun Liu
  • Luis Nunes Vicente
    • Categories Convex and Nonsmooth Optimization, Data-Mining, Nonlinear Optimization Tags , , , , ,

    In the application of data clustering to human-centric decision-making systems, such as loan applications and advertisement recommendations, the clustering outcome might discriminate against people across different demographic groups, leading to unfairness. A natural conflict occurs between the cost of clustering (in terms of distance to cluster centers) and the balance representation of all demographic groups … Read more

    Sequential Domain Adaptation by Synthesizing Distributionally Robust Experts

  • Jose Blanchet
  • Daniel Kuhn
  • Viet Anh Nguyen
  • Bahar Tașkesen
  • Man-Chung Yue
    • Categories Nonlinear Systems and Least-Squares, Robust Optimization, Stochastic Programming

    Least squares estimators, when trained on a few target domain samples, may predict poorly. Supervised domain adaptation aims to improve the predictive accuracy by exploiting additional labeled training samples from a source distribution that is close to the target distribution. Given available data, we investigate novel strategies to synthesize a family of least squares estimator … Read more

    Lifting convex inequalities for bipartite bilinear programs

  • Santanu S. Dey
  • Jean-Philippe P. Richard
  • Xiaoyi Gu
    • Categories Cutting Plane Approaches, Global Optimization Theory, Nonlinear Optimization Tags

    The goal of this paper is to derive new classes of valid convex inequalities for quadratically constrained quadratic programs (QCQPs) through the technique of lifting. Our first main result shows that, for sets described by one bipartite bilinear constraint together with bounds, it is always possible to sequentially lift a seed inequality that is valid … Read more