On the Exactness of Dantzig-Wolfe Relaxation for Rank Constrained Optimization Problems

  • Yongchun Li
  • Weijun Xie
    • Categories Integer Programming Tags , , , , , ,

    In the rank-constrained optimization problem (RCOP), it minimizes a linear objective function over a prespecified closed rank-constrained domain set and $m$ generic two-sided linear matrix inequalities. Motivated by the Dantzig-Wolfe (DW) decomposition, a popular approach of solving many nonconvex optimization problems, we investigate the strength of DW relaxation (DWR) of the RCOP, which admits the … Read more

    Finding Groups with Maximum Betweenness Centrality via Integer Programming with Random Path Sampling

  • Tomas Lagos
  • Oleg A. Prokopyev
  • Alexander Veremyev
    • Categories Approximation Algorithms, Graphs and Matroids, Stochastic Approaches Tags , , , ,

    One popular approach to access the importance/influence of a group of nodes in a network is based on the notion of centrality. For a given group, its group betweenness centrality is computed, first, by evaluating a ratio of shortest paths between each node pair in a network that are “covered” by at least one node … Read more

    Simple Alternating Minimization Provably Solves Complete Dictionary Learning

  • lianggy
  • Gavin Zhang
  • Salar Fattahi
  • Richard Y. Zhang
    • Categories Optimization in Data Science

    This paper focuses on complete dictionary learning problem, where the goal is to reparametrize a set of given signals as linear combinations of atoms from a learned dictionary. There are two main challenges faced by theoretical and practical studies of dictionary learning: the lack of theoretical guarantees for practically-used heuristic algorithms, and their poor scalability … Read more

    A Consensus-Based Alternating Direction Method for Mixed-Integer and PDE-Constrained Gas Transport Problems

  • Richard Krug
  • Günter Leugering
  • Alexander Martin
  • Martin Schmidt
  • Dieter Weninger
    • Categories (Mixed) Integer Nonlinear Programming, Network Optimization, Optimization of Systems modeled by PDEs Tags , , , ,

    We consider dynamic gas transport optimization problems, which lead to large-scale and nonconvex mixed-integer nonlinear optimization problems (MINLPs) on graphs. Usually, the resulting instances are too challenging to be solved by state-of-the-art MINLP solvers. In this paper, we use graph decompositions to obtain multiple optimization problems on smaller blocks, which can be solved in parallel … Read more

    Decentralized Stochastic Bilevel Optimization with Improved Per-Iteration Complexity

  • Xuxing Chen
  • Minhui Huang
  • Shiqian Ma
  • Krishnakumar Balasubramanian
    • Categories Nonlinear Optimization, Optimization in Data Science, Stochastic Programming

    Bilevel optimization recently has received tremendous attention due to its great success in solving important machine learning problems like meta learning, reinforcement learning, and hyperparameter optimization. Extending single-agent training on bilevel problems to the decentralized setting is a natural generalization, and there has been a flurry of work studying decentralized bilevel optimization algorithms. However, it … Read more

    Machine Learning for K-adaptability in Two-stage Robust Optimization

  • Esther Julien
  • Krzysztof Postek
  • Ş. İlker Birbil
    • Categories Robust Optimization Tags , , , , ,

    Two-stage robust optimization problems constitute one of the hardest optimization problem classes.One of the solution approaches to this class of problems is K-adaptability. This approach simultaneously seeks the best partitioning of the uncertainty set of scenarios into K subsets, and optimizesdecisions corresponding to each of these subsets. In general case, it is solved using the … Read more

    An Exact Method for Nonlinear Network Flow Interdiction Problems

  • Martin Schmidt
  • Johannes Thürauf
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization, Network Optimization Tags , , ,

    We study network flow interdiction problems with nonlinear and nonconvex flow models. The resulting model is a max-min bilevel optimization problem in which the follower’s problem is nonlinear and nonconvex. In this game, the leader attacks a limited number of arcs with the goal to maximize the load shed and the follower aims at minimizing … Read more

    Wasserstein Regularization for 0-1 Loss

  • Rui Gao
    • Categories Data Science Theory, Robust Optimization, Stochastic Programming

    Wasserstein distributionally robust optimization (DRO) finds robust solutions by hedging against data perturbation specified by distributions in a Wasserstein ball. The robustness is linked to the regularization effect, which has been studied for continuous losses in various settings. However, existing results cannot be simply applied to the 0-1 loss, which is frequently seen in uncertainty … Read more