complexity

On the Convergence Properties of Non-Euclidean Extragradient Methods for Variational Inequalities with Generalized Monotone Operators

  • Cong D. Dang
  • Guanghui Lan
    • Categories Complementarity and Variational Inequalities, Convex and Nonsmooth Optimization, Nonlinear Optimization Tags , , , , ,

    In this paper, we study a class of generalized monotone variational inequality (GMVI) problems whose operators are not necessarily monotone (e.g., pseudo-monotone). We present non-Euclidean extragradient (N-EG) methods for computing an approximate strong solution of these problems, and demonstrate how their iteration complexities depend on the global Lipschitz or H\”{o}lder continuity properties for their operators … Read more

    Complexity of Bilevel Coherent Risk Programming

  • Jonathan Eckstein
    • Categories Stochastic Programming Tags , ,

    This paper considers a bilevel programming approach to applying coherent risk measures to extended two-stage stochastic programming problems. This formulation technique avoids the time-inconsistency issues plaguing naive models and the incomposability issues which cause time-consistent formulations to have complicated, hard-to-explain objective functions. Unfortunately, the analysis here shows that such bilevel formulations, when using the standard … Read more

    Bilevel Programming and the Separation Problem

  • Andrea Lodi
  • Ted K. Ralphs
  • Gerhard J. Woeginger
    • Categories Cutting Plane Approaches, Integer Programming Tags , , ,

    In recent years, branch-and-cut algorithms have become firmly established as the most effective method for solving generic mixed integer linear programs (MILPs). Methods for automatically generating inequalities valid for the convex hull of solutions to such MILPs are a critical element of branch-and-cut. This paper examines the nature of the so-called separation problem, which is … Read more

    Smoothing SQP Algorithm for Non-Lipschitz Optimization with Complexity Analysis

  • Wei Bian
  • Xiaojun Chen
    • Categories Nonsmooth Optimization, Statistics, Unconstrained Optimization Tags , ,

    In this paper, we propose a smoothing sequential quadratic programming (SSQP) algorithm for solving a class of nonsmooth nonconvex, perhaps even non-Lipschitz minimization problems, which has wide applications in statistics and sparse reconstruction. At each step, the SSQP algorithm solves a strongly convex quadratic minimization problem with a diagonal Hessian matrix, which has a simple … Read more

    Subgradient methods for huge-scale optimization problems

  • Yurii Nesterov
    • Categories Nonsmooth Optimization Tags , , , ,

    We consider a new class of huge-scale problems, the problems with {\em sparse subgradients}. The most important functions of this type are piece-wise linear. For optimization problems with uniform sparsity of corresponding linear operators, we suggest a very efficient implementation of subgradient iterations, which total cost depends {\em logarithmically} in the dimension. This technique is … Read more

    Stochastic first order methods in smooth convex optimization.

  • Olivier Devolder
    • Categories Convex Optimization, Stochastic Programming Tags , , , , , ,

    In this paper, we are interested in the development of efficient first-order methods for convex optimization problems in the simultaneous presence of smoothness of the objective function and stochasticity in the first-order information. First, we consider the Stochastic Primal Gradient method, which is nothing else but the Mirror Descent SA method applied to a smooth … Read more

    Algebraic Relaxations and Hardness Results in Polynomial Optimization and Lyapunov Analysis

  • Amir Ali Ahmadi
    • Categories Control Applications, Convex Optimization, Semi-definite Programming Tags , , , , ,

    The contributions of the first half of this thesis are on the computational and algebraic aspects of convexity in polynomial optimization. We show that unless P=NP, there exists no polynomial time (or even pseudo-polynomial time) algorithm that can decide whether a multivariate polynomial of degree four (or higher even degree) is globally convex. This solves … Read more

    On the Difficulty of Deciding Asymptotic Stability of Cubic Homogeneous Vector Fields

  • Amir Ali Ahmadi
    • Categories Control Applications, Semi-definite Programming, Systems governed by Differential Equations Optimization Tags , ,

    It is well-known that asymptotic stability (AS) of homogeneous polynomial vector fields of degree one (i.e., linear systems) can be decided in polynomial time e.g. by searching for a quadratic Lyapunov function. Since homogeneous vector fields of even degree can never be AS, the next interesting degree to consider is equal to three. In this … Read more

    Complexity and Exact Solution Approaches to the Minimum Changeover Cost Arborescence Problem

  • Frank Baumann
  • Stefano Gualandi
  • Giulia Galbiati
  • Emiliano Traversi
    • Categories Combinatorial Optimization, Integer Programming, Network Optimization Tags , , , ,

    We are given a digraph G = (N, A), where each arc is colored with one among k given colors. We look for a spanning arborescence T of G rooted at a given node and having minimum changeover cost. We call this the Minimum Changeover Cost Arborescence problem. To the authors’ knowledge, it is a … Read more

    Removing critical nodes from a graph: complexity results and polynomial algorithms for the case of bounded treewidth

  • Bernardetta Addis
  • Marco Di Summa
  • Andrea Grosso
    • Categories Combinatorial Optimization Tags , , ,

    We consider the problem of deleting a limited number of nodes from a graph in order to minimize a connectivity measure between the surviving nodes. We prove that the problem is $NP$-complete even on quite particular types of graph, and define a dynamic programming recursion that solves the problem in polynomial time when the graph … Read more