Nonlinear Optimization

Iteration-complexity of an inner accelerated inexact proximal augmented Lagrangian method based on the classical Lagrangian function and a full Lagrange multiplier update

  • Jefferson Gonçalves Melo
  • Renato D.C. Monteiro
    • Categories Convex and Nonsmooth Optimization, Nonlinear Optimization, Nonsmooth Optimization Tags , , ,

    This paper establishes the iteration-complexity of an inner accelerated inexact proximal augmented Lagrangian (IAPIAL) method for solving linearly constrained smooth nonconvex composite optimization problems which is based on the classical Lagrangian function and, most importantly, performs a full Lagrangian multiplier update, i.e., no shrinking factor is incorporated on it. More specifically, each IAPIAL iteration consists … Read more

    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

    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

    Accelerated Inexact Composite Gradient Methods for Nonconvex Spectral Optimization Problems

  • Weiwei Kong
  • Renato D.C. Monteiro
    • Categories Convex and Nonsmooth Optimization, Nonlinear Optimization Tags , , , , ,

    This paper presents two inexact composite gradient methods, one inner accelerated and another doubly accelerated, for solving a class of nonconvex spectral composite optimization problems. More specifically, the objective function for these problems is of the form f_1 + f_2 + h where f_1 and f_2 are differentiable nonconvex matrix functions with Lipschitz continuous gradients, … 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