Nonlinear Optimization

Computational advances in polynomial optimization: RAPOSa, a freely available global solver

  • Julio González-Díaz
  • Joaquín Ossorio-Castillo
  • Brais González-Rodríguez
  • Ángel M. González-Rueda
  • David R. Penas
  • Diego Rodríguez-Martínez
    • Categories Nonlinear Optimization Tags , ,

    In this paper we introduce RAPOSa, a global optimization solver specifically designed for (continuous) polynomial programming problems with box-constrained variables. Written entirely in C++, RAPOSa is based on the Reformulation-Linearization Technique developed by Sherali and Tuncbilek (1992) and subsequently improved in Sherali et al. (2012a), Sherali et al. (2012b) and Dalkiran and Sherali (2013). We … Read more

    An Orthogonalization-free Parallelizable Framework for All-electron Calculations in Density Functional Theory

  • Bin Gao
  • Xin Liu
  • Guanghui Hu
  • Yang Kuang
    • Categories Applications - Science and Engineering, Nonlinear Optimization Tags , , ,

    All-electron calculations play an important role in density functional theory, in which improving computational efficiency is one of the most needed and challenging tasks. In the model formulations, both nonlinear eigenvalue problem and total energy minimization problem pursue orthogonal solutions. Most existing algorithms for solving these two models invoke orthogonalization process either explicitly or implicitly … Read more

    A Subspace Acceleration Method for Minimization Involving a Group Sparsity-Inducing Regularizer

  • Frank E. Curtis
  • Daniel P. Robinson
  • Yutong Dai
    • Categories Nonsmooth Optimization, Unconstrained Optimization Tags , , , , , , ,

    We consider the problem of minimizing an objective function that is the sum of a convex function and a group sparsity-inducing regularizer. Problems that integrate such regularizers arise in modern machine learning applications, often for the purpose of obtaining models that are easier to interpret and that have higher predictive accuracy. We present a new … Read more

    On the best achievable quality of limit points of augmented Lagrangian schemes

  • Roberto Andreani
  • Gabriel Haeser
  • Alberto Ramos
  • Leonardo M. Mito
  • Leonardo D. Secchin
    • Categories Constrained Nonlinear Optimization, Nonlinear Optimization Tags , ,

    The optimization literature is vast in papers dealing with improvements on the global convergence of augmented Lagrangian schemes. Usually, the results are based on weak constraint qualifications, or, more recently, on sequential optimality conditions obtained via penalization techniques. In this paper we propose a somewhat different approach, in the sense that the algorithm itself is … Read more

    On the abs-polynomial expansion of piecewise smooth functions

  • Andreas Griewank
  • Caren Tischendorf
  • Tom Streubel
    • Categories Nonlinear Systems and Least-Squares, Nonsmooth Optimization

    Tom Streubel has observed that for functions in abs-normal form, generalized Taylor expansions of arbitrary order $\bd \!- \!1$ can be generated by algorithmic piecewise differentiation. Abs-normal form means that the real or vector valued function is defined by an evaluation procedure that involves the absolute value function $|\cdot|$ apart from arithmetic operations and $\bd$ … Read more

    Manifold Proximal Point Algorithms for Dual Principal Component Pursuit and Orthogonal Dictionary Learning

  • Shixiang Chen
  • Shiqian Ma
  • Anthony Man-Cho So
  • Zengde Deng
    • Categories Nonlinear Optimization

    We consider the problem of maximizing the $\ell_1$ norm of a linear map over the sphere, which arises in various machine learning applications such as orthogonal dictionary learning (ODL) and robust subspace recovery (RSR). The problem is numerically challenging due to its nonsmooth objective and nonconvex constraint, and its algorithmic aspects have not been well … Read more

    Riemannian Stochastic Proximal Gradient Methods for Nonsmooth Optimization over the Stiefel Manifold

  • Shiqian Ma
  • Bokun Wang
  • Lingzhou Xue
    • Categories Nonlinear Optimization

    Riemannian optimization has drawn a lot of attention due to its wide applications in practice. Riemannian stochastic first-order algorithms have been studied in the literature to solve large-scale machine learning problems over Riemannian manifolds. However, most of the existing Riemannian stochastic algorithms require the objective function to be differentiable, and they do not apply to … Read more

    A Manifold Proximal Linear Method for Sparse Spectral Clustering with Application to Single-Cell RNA Sequencing Data Analysis

  • Shixiang Chen
  • Shiqian Ma
  • Bingyuan Liu
  • Zhongruo Wang
  • Lingzhou Xue
  • Hongyu Zhao
    • Categories Nonlinear Optimization

    Spectral clustering is one of the fundamental unsupervised learning methods widely used in data analysis. Sparse spectral clustering (SSC) imposes sparsity to the spectral clustering and it improves the interpretability of the model. This paper considers a widely adopted model for SSC, which can be formulated as an optimization problem over the Stiefel manifold with … Read more

    Stochastic Zeroth-order Riemannian Derivative Estimation and Optimization

  • Krishnakumar Balasubramanian
  • Shiqian Ma
  • Jiaxiang Li
    • Categories Nonlinear Optimization

    We consider stochastic zeroth-order optimization over Riemannian submanifolds embedded in Euclidean space, where the task is to solve Riemannian optimization problem with only noisy objective function evaluations. Towards this, our main contribution is to propose estimators of the Riemannian gradient and Hessian from noisy objective function evaluations, based on a Riemannian version of the Gaussian … Read more

    Zeroth-Order Algorithms for Nonconvex Minimax Problems with Improved Complexities

  • Krishnakumar Balasubramanian
  • Shiqian Ma
  • Meisam Razaviyayn
  • Zhongruo Wang
    • Categories Nonlinear Optimization

    In this paper, we study zeroth-order algorithms for minimax optimization problems that are nonconvex in one variable and strongly-concave in the other variable. Such minimax optimization problems have attracted significant attention lately due to their applications in modern machine learning tasks. We first design and analyze the Zeroth-Order Gradient Descent Ascent (ZO-GDA) algorithm, and provide … Read more