Nonlinear Optimization

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

    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

    New convergence results for the inexact variable metric forward-backward method

  • Silvia Bonettini
  • Marco Prato
  • Simone Rebegoldi
    • Categories Nonlinear Optimization Tags , ,

    Forward–backward methods are valid tools to solve a variety of optimization problems where the objective function is the sum of a smooth, possibly nonconvex term plus a convex, possibly nonsmooth function. The corresponding iteration is built on two main ingredients: the computation of the gradient of the smooth part and the evaluation of the proximity … Read more

    A general branch-and-bound framework for continuous global multiobjective optimization

  • Gabriele Eichfelder
  • Peter Kirst
  • Oliver Stein
  • Laura Meng
    • Categories Global Optimization, Multi-Criteria Optimization, Nonlinear Optimization

    Current generalizations of the central ideas of single-objective branch-and-bound to the multiobjective setting do not seem to follow their train of thought all the way. The present paper complements the various suggestions for generalizations of partial lower bounds and of overall upper bounds by general constructions for overall lower bounds from partial lower bounds, and … Read more

    Sequential Quadratic Optimization for Nonlinear Equality Constrained Stochastic Optimization

  • Albert S. Berahas
  • Frank E. Curtis
  • Daniel P. Robinson
  • Baoyu Zhou
    • Categories Nonlinear Optimization Tags , ,

    Sequential quadratic optimization algorithms are proposed for solving smooth nonlinear optimization problems with equality constraints. The main focus is an algorithm proposed for the case when the constraint functions are deterministic, and constraint function and derivative values can be computed explicitly, but the objective function is stochastic. It is assumed in this setting that it … Read more

    Exact Penalty Function for L21 Norm Minimization over the Stiefel Manifold

  • Nachuan Xiao
  • Xin Liu
  • Ya-xiang Yuan
    • Categories Constrained Nonlinear Optimization, Statistics Tags , , ,

    L21 norm minimization with orthogonality constraints, feasible region of which is called Stiefel manifold, has wide applications in statistics and data science. The state-of-the-art approaches adopt proximal gradient technique on either Stiefel manifold or its tangent spaces. The consequent subproblem does not have closed-form solution and hence requires an iterative procedure to solve which is … Read more

    A DISCUSSION ON ELECTRICITY PRICES, OR THE TWO SIDES OF THE COIN

  • Juan Pablo Luna
  • Claudia Sagastizábal
  • Paulo J. S. Silva
    • Categories Applications - OR and Management Sciences, Nonlinear Optimization Tags , , ,

    We examine how different pricing frameworks deal with nonconvex features typical of day-ahead energy prices when the power system is hydro-dominated, like in Brazil. For the system operator, requirements of minimum generation translate into feasibility issues that are fundamental to carry the generated power through the network. When utilities are remunerated at a price depending … Read more