Nonlinear Optimization

Model Construction for Convex-Constrained Derivative-Free Optimization

  • Lindon Roberts
    • Categories Bound-constrained Optimization, Constrained Nonlinear Optimization, Nonlinear Optimization Tags , ,

    We develop a new approximation theory for linear and quadratic interpolation models, suitable for use in convex-constrained derivative-free optimization (DFO). Most existing model-based DFO methods for constrained problems assume the ability to construct sufficiently accurate approximations via interpolation, but the standard notions of accuracy (designed for unconstrained problems) may not be achievable by only sampling … Read more

    A Unified Approach for Maximizing Continuous $\gamma$-weakly DR-submodular Functions

  • Mohammad Pedramfar
  • Christopher Quinn
  • Vaneet Aggarwal
    • Categories Constrained Nonlinear Optimization, Stochastic Programming Tags , ,

    This paper presents a unified approach for maximizing continuous \(\gamma\)-weakly DR-submodular functions that encompasses a range of settings and oracle access types. Our approach includes a Frank-Wolfe type offline algorithm for both monotone and non-monotone functions, with different restrictions on the convex feasible region. We consider settings where the oracle provides access to either the … Read more

    The stochastic Ravine accelerated gradient method with general extrapolation coefficients

  • Hédy Attouch
  • Jalal Fadili
  • Vyacheslav Kungurtsev
    • Categories Convex Optimization, Nonlinear Optimization Tags ,

    Abstract: In a real Hilbert space domain setting, we study the convergence properties of the stochastic Ravine accelerated gradient method for convex differentiable optimization. We consider the general form of this algorithm where the extrapolation coefficients can vary with each iteration, and where the evaluation of the gradient is subject to random errors. This general … Read more

    A Jacobi-type Newton method for Nash equilibrium problems with descent guarantees

  • Oliver Kolossoski
  • Luís Felipe Bueno
  • Gabriel Haeser
    • Categories Game Theory, Nonlinear Optimization, Other Topics Tags , , , ,

    A common strategy for solving an unconstrained two-player Nash equilibrium problem with continuous variables is applying Newton’s method to the system obtained by the corresponding first-order necessary optimality conditions. However, when taking into account the game dynamics, it is not clear what is the goal of each player when considering they are taking their current … Read more

    A Polyhedral Characterization of Linearizable Quadratic Combinatorial Optimization Problems

  • Lucas Waddell
    • Categories 0-1 Programming, Combinatorial Optimization, Quadratic Programming Tags , , ,

    We introduce a polyhedral framework for characterizing instances of quadratic combinatorial optimization programs (QCOPs) that are linearizable, meaning that the quadratic objective can be equivalently rewritten as linear in such a manner that preserves the objective function value at all feasible solutions. In particular, we show that an instance is linearizable if and only if … Read more

    Uncertainty Quantification for Multiobjective Stochastic Convex Quadratic Programs

  • Ziyu Liu
  • Susan R. Hunter
  • Nan Kong
  • Raghu Pasupathy
    • Categories Multi-Criteria Optimization, Quadratic Programming, Stochastic Programming

    A multiobjective stochastic convex quadratic program (MOSCQP) is a multiobjective optimization problem with convex quadratic objectives that are observed with stochastic error. MOSCQP is a useful problem formulation arising, for example, in model calibration and nonlinear system identification when a single regression model combines data from multiple distinct sources, resulting in a multiobjective least squares … Read more

    Problem-Parameter-Free Decentralized Nonconvex Stochastic Optimization

  • Jiaxiang Li
  • Xuxing Chen
  • Shiqian Ma
  • Mingyi Hong
    • Categories Nonlinear Optimization, Stochastic Programming

    Existing decentralized algorithms usually require knowledge of problem parameters for updating local iterates. For example, the hyperparameters (such as learning rate) usually require the knowledge of Lipschitz constant of the global gradient or topological information of the communication networks, which are usually not accessible in practice. In this paper, we propose D-NASA, the first algorithm … Read more

    A new proximal gradient algorithm for solving mixed variational inequality problems with a novel explicit stepsize and applications

  • Pham Thi Hoai
    • Categories Complementarity and Variational Inequalities, Convex Optimization, Nonlinear Optimization Tags , , , ,

    In this paper, we propose a new algorithm for solving monotone mixed variational inequality problems in real Hilbert spaces based on proximal gradient method. Our new algorithm uses a novel explicit stepsize which is proved to be increasing to a positive value. This property plays an important role in improving the speed of the algorithm. … Read more

    Riemannian trust-region methods for strict saddle functions with complexity guarantees

  • Florentin Goyens
  • Clément W. Royer
    • Categories Nonlinear Optimization Tags , , ,

    The difficulty of minimizing a nonconvex function is in part explained by the presence of saddle points. This slows down optimization algorithms and impacts worst-case complexity guarantees. However, many nonconvex problems of interest possess a favorable structure for optimization, in the sense that saddle points can be escaped efficiently by appropriate algorithms. This strict saddle … Read more

    Extending the Reach of First-Order Algorithms for Nonconvex Min-Max Problems with Cohypomonotonicity

  • Ahmet Alacaoglu
  • Donghwan Kim
  • Stephen Wright
    • Categories Complementarity and Variational Inequalities, Generalized Convexity/Monoticity, Nonlinear Optimization, Stochastic Programming

    We focus on constrained, \(L\)-smooth, nonconvex-nonconcave min-max problems either satisfying \(\rho\)-cohypomonotonicity or admitting a solution to the \(\rho\)-weakly Minty Variational Inequality (MVI), where larger values of the parameter \(\rho>0\) correspond to a greater degree of nonconvexity. These problem classes include examples in two player reinforcement learning, interaction dominant min-max problems, and certain synthetic test problems on … Read more