Unconstrained Optimization

An adaptive line-search-free multiobjective gradient method and its iteration-complexity analysis

  • Max L. N. Gonçalves
  • Geovani Nunes Grapiglia
  • Jefferson Gonçalves Melo
    • Categories Multi-Criteria Optimization, Unconstrained Optimization Tags , , ,

    This work introduces an Adaptive Line-Search-Free Multiobjective Gradient (AMG) method for solving smooth multiobjective optimization problems. The proposed approach automatically adjusts stepsizes based on steepest descent directions, promoting robustness with respect to stepsize choice while maintaining low computational cost. The method is specifically tailored to the multiobjective setting and does not rely on function evaluations, … Read more

    On Approximate Computation of Critical Points

  • Amir Ali Ahmadi
  • Georgina Hall
    • Categories Global Optimization, Unconstrained Optimization Tags , ,

    We show that computing even very coarse approximations of critical points is intractable for simple classes of nonconvex functions. More concretely, we prove that if there exists a polynomial-time algorithm that takes as input a polynomial in \(n\) variables of constant degree (as low as three) and outputs a point whose gradient has Euclidean norm … Read more

    Iteration complexity of the Difference-of-Convex Algorithm for unconstrained optimization: a simple proof

  • Serge Gratton
  • Philippe L. Toint
    • Categories Convex Optimization, Nonlinear Optimization, Unconstrained Optimization Tags , ,

    We propose a simple proof of the worst-case iteration complexity for the Difference of Convex functions Algorithm (DCA) for unconstrained minimization, showing that the global rate of convergence of the norm of the objective function’s gradients at the iterates converge to zero like $o(1/k)$. A small example is also provided indicating that the rate cannot … Read more

    A Majorization-Minimization approach for multiclass classification in a big data scenario

  • Giorgia Franchini
  • Federica Porta
  • Émilie Chouzenoux
  • Jean-Christophe Pesquet
  • Filippo Camellini
    • Categories Convex Optimization, Data Science Algorithms, Unconstrained Optimization Tags , , , , ,

    This work presents a novel optimization approach for training linear classifiers in multiclass classification tasks, when focusing on a regularized and smooth Weston-Watkins support vector machine (SVM) model. We propose a Majorization-Minimization (MM) algorithm to solve the resulting, Lipschitz-differentiable, optimization problem. To enhance scalability of the algorithm when tackling large datasets, we introduce an incremental … Read more

    Extended-Krylov-subspace methods for trust-region and norm-regularization subproblems

  • Hussam Al Daas
  • Nicholas I. M. Gould
    • Categories Constrained Nonlinear Optimization, Nonlinear Optimization, Unconstrained Optimization Tags , , ,

    We consider an effective new method for solving trust-region and norm-regularization problems that arise as subproblems in many optimization applications. We show that the solutions to such subproblems lie on a manifold of approximately very low rank as a function of their controlling parameters (trust-region radius or regularization weight). Based on this, we build a … Read more

    Accelerated proximal gradient algorithm for weakly convex function

  • Milan Barik
  • Suvendu Ranjan Pattanaik
    • Categories Nonlinear Optimization, Nonsmooth Optimization, Unconstrained Optimization Tags , , , ,

    In this work, we investigate the accelerated proximal gradient algorithm (APGα) for weakly convex composite optimization problems. Building upon the framework of B¨ohm and Wright, and additionally assuming that f is convex and coercive while g is bounded below, we establish an objective residual convergence rate of O(1⁄j²) for α≥3. Moreover, when α›3, this rate … Read more

    Optimization in Theory and Practice

  • Stephen Wright
    • Categories Convex Optimization, Linear Programming, Unconstrained Optimization Tags , ,

    Algorithms for continuous optimization problems have a rich history of design and innovation over the past several decades, in which mathematical analysis of their convergence and complexity properties plays a central role. Besides their theoretical properties, optimization algorithms are interesting also for their practical usefulness as computational tools for solving real-world problems. There are often … Read more

    Continuous-time Analysis of a Stochastic ADMM Method for Nonconvex Composite Optimization

  • Jiahong Guo
  • Xiao Wang
  • Xiantao Xiao
    • Categories Nonlinear Optimization, Unconstrained Optimization

    In this paper, we focus on nonconvex composite optimization, whose objective is the sum of a smooth but possibly nonconvex function and a composition of a weakly convex function coupled with a linear operator. By leveraging a smoothing technique based on Moreau envelope, we propose a stochastic proximal linearized ADMM algorithm (SPLA). To understand its … Read more

    Active-set Newton-MR methods for nonconvex optimization problems with bound constraints

  • Ernesto G. Birgin
  • Geovani Nunes Grapiglia
  • Diaulas S. Marcondes
    • Categories Bound-constrained Optimization, Nonlinear Optimization, Unconstrained Optimization Tags , , , ,

    This paper presents active-set methods for minimizing nonconvex twice-continuously differentiable functions subject to bound constraints. Within the faces of the feasible set, we employ descent methods with Armijo line search, utilizing approximated Newton directions obtained through the Minimum Residual (MINRES) method. To escape the faces, we investigate the use of the Spectral Projected Gradient (SPG) … Read more

    A linesearch-based derivative-free method for noisy black-box problems

  • Giampaolo Liuzzi
  • Stefano Lucidi
  • Alberto De Santis
    • Categories Nonlinear Optimization, Stochastic Programming, Unconstrained Optimization Tags , ,

    In this work we consider unconstrained optimization problems. The objective function is known through a zeroth order stochastic oracle that gives an estimate of the true objective function. To solve these problems, we propose a derivativefree algorithm based on extrapolation techniques. Under reasonable assumptions we are able to prove convergence properties for the proposed algorithms. … Read more