Nonlinear Optimization

Vector Transport-Free SVRG with General Retraction for Riemannian Optimization: Complexity Analysis and Practical Implementation

  • Bo Jiang
  • Shiqian Ma
  • Anthony Man-Cho So
  • Shuzhong Zhang
    • Categories Constrained Nonlinear Optimization, Stochastic Programming Tags , , , ,

    In this paper, we propose a vector transport-free stochastic variance reduced gradient (SVRG) method with general retraction for empirical risk minimization over Riemannian manifold. Existing SVRG methods on manifold usually consider a specific retraction operation, and involve additional computational costs such as parallel transport or vector transport. The vector transport-free SVRG with general retraction we … Read more

    A New Use of Douglas-Rachford Splitting and ADMM for Identifying Infeasible, Unbounded, and Pathological Conic Programs

  • Yanli Liu
  • Ernest K. Ryu
  • Wotao Yin
    • Categories Convex and Nonsmooth Optimization, Linear, Cone and Semidefinite Programming, Nonlinear Optimization Tags , , , ,

    In this paper, we present a method for identifying infeasible, unbounded, and pathological conic programs based on Douglas-Rachford splitting, or equivalently ADMM. When an optimization program is infeasible, unbounded, or pathological, the iterates of Douglas-Rachford splitting diverge.Somewhat surprisingly, such divergent iterates still provide useful information, which our method uses for identification. In addition, for strongly … Read more

    Oracle Complexity of Second-Order Methods for Smooth Convex Optimization

  • Ohad Shamir
  • Ron Shiff
    • Categories Convex Optimization, Nonlinear Optimization Tags , ,

    Second-order methods, which utilize gradients as well as Hessians to optimize a given function, are of major importance in mathematical optimization. In this work, we study the oracle complexity of such methods, or equivalently, the number of iterations required to optimize a function to a given accuracy. Focusing on smooth and convex functions, we derive … Read more

    An Inexact Newton-like conditional gradient method for constrained nonlinear systems

  • Max L. N. Gonçalves
  • F.R. Oliveira
    • Categories Constrained Nonlinear Optimization, Nonlinear Optimization

    In this paper, we propose an inexact Newton-like conditional gradient method for solving constrained systems of nonlinear equations. The local convergence of the new method as well as results on its rate are established by using a general majorant condition. Two applications of such condition are provided: one is for functions whose the derivative satisfies … Read more

    Optimality of orders one to three and beyond: characterization and evaluation complexity in constrained nonconvex optimization

  • Coralia Cartis
  • Nicholas I. M. Gould
  • Philippe L. Toint
    • Categories Bound-constrained Optimization, Constrained Nonlinear Optimization, Nonlinear Systems and Least-Squares Tags , ,

    Necessary conditions for high-order optimality in smooth nonlinear constrained optimization are explored and their inherent intricacy discussed. A two-phase minimization algorithm is proposed which can achieve approximate first-, second- and third-order criticality and its evaluation complexity is analyzed as a function of the choice (among existing methods) of an inner algorithm for solving subproblems in … Read more

    A pattern search and implicit filtering algorithm for solving linearly constrained minimization problems with noisy objective functions

  • Maria A. Diniz-Ehrhardt
  • Sandra Augusta Santos
  • D. G. Ferreira
    • Categories Constrained Nonlinear Optimization

    PSIFA -Pattern Search and Implicit Filtering Algorithm- is a derivative-free algorithm that has been designed for linearly constrained problems with noise in the objective function. It combines some elements of the pattern search approach of Lewis and Torczon (2000) with ideas from the method of implicit filtering of Kelley (2011) enhanced with a further analysis … Read more

    The New Butterfly Relaxation Methods for Mathematical Program with Complementarity Constraints

  • Jean-Pierre Dussault
  • Tangi Migot
  • Mounir Haddou
    • Categories Complementarity and Variational Inequalities, Constrained Nonlinear Optimization Tags

    We propose a new family of relaxation schemes for mathematical program with complementarity constraints that extends the relaxations of Kadrani, Dussault, Bechakroun from 2009 and the one of Kanzow \& Schwartz from 2011. We discuss the properties of the sequence of relaxed non-linear program as well as stationarity properties of limiting points. A sub-family of … Read more

    How to Compute a M-stationary point of the MPCC

  • Jean-Pierre Dussault
  • Tangi Migot
  • Mounir Haddou
  • Abdeslam Kadrani
    • Categories Complementarity and Variational Inequalities, Constrained Nonlinear Optimization

    We discuss here the convergence of relaxation methods for MPCC with approximate sequence of stationary points by presenting a general framework to study these methods. It has been pointed out in the literature, \cite{kanzow2015}, that relaxation methods with approximate stationary points fail to give guarantee of convergence. We show that by defining a new strong … Read more

    Extending the Scope of Robust Quadratic Optimization

  • Aharon Ben-Tal
  • Dick den Hertog
  • Ahmadreza Marandi
  • Bertrand Melenberg
    • Categories Quadratic Programming, Robust Optimization Tags , , ,

    We derive computationally tractable formulations of the robust counterparts of convex quadratic and conic quadratic constraints that are concave in matrix-valued uncertain parameters. We do this for a broad range of uncertainty sets. In particular, we show how to reformulate the support functions of uncertainty sets represented in terms of matrix norms and cones. Our … Read more

    Bad semidefinite programs with short proofs, and the closedness of the linear image of the semidefinite cone

  • Gabor Pataki
    • Categories Convex Optimization, Nonlinear Optimization, Semi-definite Programming

    Semidefinite programs (SDPs) — some of the most useful and pervasive optimization problems of the last few decades — often behave pathologically: the optimal values of the primal and dual problems may differ and may not be attained. Such SDPs are theoretically interesting and often impossible to solve. Yet, the pathological SDPs in the literature … Read more