Nonlinear Optimization

An Alternating Manifold Proximal Gradient Method for Sparse PCA and Sparse CCA

  • Shixiang Chen
  • Shiqian Ma
  • Lingzhou Xue
  • Hui Zou
    • Categories Constrained Nonlinear Optimization, Statistics

    Sparse principal component analysis (PCA) and sparse canonical correlation analysis (CCA) are two essential techniques from high-dimensional statistics and machine learning for analyzing large-scale data. Both problems can be formulated as an optimization problem with nonsmooth objective and nonconvex constraints. Since non-smoothness and nonconvexity bring numerical difficulties, most algorithms suggested in the literature either solve … Read more

    Line search and convergence in bound-constrained optimization

  • Behzad Azmi
  • Arnold Neumaier
    • Categories Bound-constrained Optimization Tags , , , ,

    The first part of this paper discusses convergence properties of a new line search method for the optimization of continuously differentiable functions with Lipschitz continuous gradient. The line search uses (apart from the gradient at the current best point) function values only. After deriving properties of the new, in general curved, line search, global convergence … Read more

    An Augmented Lagrangian algorithm for nonlinear semidefinite programming applied to the covering problem

  • Ernesto G. Birgin
  • Walter Gómez
  • Gabriel Haeser
  • Leonardo M. Mito
  • Daiana O. Santos
    • Categories Constrained Nonlinear Optimization, Convex Optimization, Semi-definite Programming Tags , , ,

    In this work we present an Augmented Lagrangian algorithm for nonlinear semidefinite problems (NLSDPs), which is a natural extension of its consolidated counterpart in nonlinear programming. This method works with two levels of constraints; one that is penalized and other that is kept within the subproblems. This is done in order to allow exploiting the … Read more

    Planning for Dynamics under Uncertainty

  • Dicong Qiu
  • Karsh Tharyani
    • Categories Dynamic Programming, Systems governed by Differential Equations Optimization, Unconstrained Optimization Tags , ,

    Planning under uncertainty is a frequently encountered problem. Noisy observation is a typical situation that introduces uncertainty. Such a problem can be formulated as a Partially Observable Markov Decision Process (POMDP). However, solving a POMDP is nontrivial and can be computationally expensive in continuous state, action, observation and latent state space. Through this work, we … Read more

    Using two-dimensional Projections for Stronger Separation and Propagation of Bilinear Terms

  • Ambros Gleixner
  • Felipe Serrano
  • Benjamin Müller
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization, Nonlinear Optimization Tags , , , , , ,

    One of the most fundamental ingredients in mixed-integer nonlinear programming solvers is the well- known McCormick relaxation for a product of two variables x and y over a box-constrained domain. The starting point of this paper is the fact that the convex hull of the graph of xy can be much tighter when computed over … Read more

    Inertial Block Mirror Descent Method for Non-Convex Non-Smooth Optimization

  • Nicolas Gillis
  • Le Thi Khanh Hien
  • Panagiotis Patrinos
    • Categories Constrained Nonlinear Optimization Tags , , , , ,

    In this paper, we propose inertial versions of block coordinate descent methods for solving non-convex non-smooth composite optimization problems. We use the general framework of Bregman distance functions to compute the proximal maps. Our method not only allows using two different extrapolation points to evaluate gradients and adding the inertial force, but also takes advantage … Read more

    An Enhanced Logical Benders Approach for Linear Programs with Complementarity

  • Francisco Jara-Moroni
  • John E. Mitchell
  • Jong-Shi Pang
    • Categories Complementarity and Variational Inequalities, Global Optimization, Nonlinear Optimization Tags , ,

    This work extends the ones of Hu et al. (2008) and Bai et al. (2013) of a logical Benders approach for globally solving Linear Programs with Complementarity Constraints. By interpreting the logical Benders method as a reversed branch-and-bound method, where the whole exploration procedure starts from the leaf nodes in an enumeration tree, we provide … Read more

    On Electricity Market Equilibria with Storage: Modeling, Uniqueness, and a Distributed ADMM

  • Julia Grübel
  • Thomas Kleinert
  • Vanessa Krebs
  • Lars Schewe
  • Martin Schmidt
  • Johannes Thürauf
  • Galina Orlinskaya
    • Categories Convex Optimization, Parallel Algorithms, Quadratic Programming Tags , , , , , ,

    We consider spot-market trading of electricity including storage operators as additional agents besides producers and consumers. Storages allow for shifting produced electricity from one time period to a later one. Due to this, multiple market equilibria may occur even if classical uniqueness assumptions for the case without storages are satisfied. For models containing storage operators, … Read more

    Limited-Memory BFGS with Displacement Aggregation

  • Albert S. Berahas
  • Frank E. Curtis
  • Baoyu Zhou
    • Categories Nonlinear Optimization, Unconstrained Optimization Tags , , , ,

    A displacement aggregation strategy is proposed for the curvature pairs stored in a limited-memory BFGS (a.k.a. L-BFGS) method such that the resulting (inverse) Hessian approximations are equal to those that would be derived from a full-memory BFGS method. This means that, if a sufficiently large number of pairs are stored, then an optimization algorithm employing … Read more

    Iteration and evaluation complexity for the minimization of functions whose computation is intrinsically inexact

  • Ernesto G. Birgin
  • Nataša Krejić
  • José Mario Martínez
    • Categories Nonlinear Optimization Tags , ,

    In many cases in which one wishes to minimize a complicated or expensive function, it is convenient to employ cheap approximations, at least when the current approximation to the solution is poor. Adequate strategies for deciding the accuracy desired at each stage of optimization are crucial for the global convergence and overall efficiency of the … Read more