Other Topics

Integral Global Optimality Conditions and an Algorithm for Multiobjective Problems

  • Everton Silva
  • Elizabeth Wegner Karas
  • Lucelina Santos
    • Categories Multi-Criteria Optimization, Nonlinear Optimization, Nonsmooth Optimization Tags , , , ,

    In this work, we propose integral global optimality conditions for multiobjective problems not necessarily differentiable. The integral characterization, already known for single objective problems, are extended to multiobjective problems by weighted sum and Chebyshev weighted scalarizations. Using this last scalarization, we propose an algorithm for obtaining an approximation of the weak Pareto front whose effectiveness … Read more

    Duality assertions in vector optimization w.r.t. relatively solid convex cones in real linear spaces

  • Christian Günther
  • Bahareh Khazayel
  • Christiane Tammer
    • Categories Constrained Nonlinear Optimization, Multi-Criteria Optimization Tags , , , , , , ,

    We derive duality assertions for vector optimization problems in real linear spaces based on a scalarization using recent results concerning the concept of relative solidness for convex cones (i.e., convex cones with nonempty intrinsic cores). In our paper, we consider an abstract vector optimization problem with generalized inequality constraints and investigate Lagrangian type duality assertions … Read more

    CliSAT: a SAT-based exact algorithm for hard maximum clique problems

  • Pablo San Segundo
  • Fabio Furini
  • David Alvarez
  • Panos M. Pardalos
    • Categories Combinatorial Optimization, Game Theory Tags , , ,

    Given a graph, the maximum clique problem (MCP) asks for determining a complete subgraph with the largest possible number of vertices. We propose a new exact algorithm, called CliSAT, to solve the MCP to proven optimality. This problem is of fundamental importance in graph theory and combinatorial optimization due to its practical relevance for a … Read more

    Advancements in the computation of enclosures for multi-objective optimization problems

  • Gabriele Eichfelder
  • Leo Warnow
    • Categories (Mixed) Integer Nonlinear Programming, Multi-Criteria Optimization, Nonlinear Optimization Tags , , , ,

    A central goal for multi-objective optimization problems is to compute their nondominated sets. In most cases these sets consist of infinitely many points and it is not a practical approach to compute them exactly. One solution to overcome this problem is to compute an enclosure, a special kind of coverage, of the nondominated set. One … Read more

    Handling of constraints in multiobjective blackbox optimization

  • Jean Bigeon
  • Sébastien Le Digabel
  • Ludovic Salomon
    • Categories Multi-Criteria Optimization, Nonlinear Optimization Tags , , , ,

    This work proposes the integration of two new constraint-handling approaches into the blackbox constrained multiobjective optimization algorithm DMulti-MADS, an extension of the Mesh Adaptive Direct Search (MADS) algorithm for single-objective constrained optimization. The constraints are aggregated into a single constraint violation function which is used either in a two-phase approach, where research of a feasible … Read more

    Randomized Policy Optimization for Optimal Stopping

  • Xinyi Guan
  • Velibor Mišić
    • Categories Dynamic Programming, Finance and Economics, Unconstrained Optimization Tags , , , ,

    Optimal stopping is the problem of determining when to stop a stochastic system in order to maximize reward, which is of practical importance in domains such as finance, operations management and healthcare. Existing methods for high-dimensional optimal stopping that are popular in practice produce deterministic linear policies — policies that deterministically stop based on the … Read more

    A branch-and-prune algorithm for discrete Nash equilibrium problems

  • Stefan Schwarze
  • Oliver Stein
    • Categories (Mixed) Integer Nonlinear Programming, Game Theory Tags , , ,

    We present a branch-and-prune procedure for discrete Nash equilibrium problems with a convex description of each player’s strategy set. The derived pruning criterion does not require player convexity, but only strict convexity of some player’s objective function in a single variable. If satisfied, it prunes choices for this variable by stating activity of certain constraints. … Read more

    Convergence rates of the stochastic alternating algorithm for bi-objective optimization

  • Suyun Liu
  • Luis Nunes Vicente
    • Categories Convex and Nonsmooth Optimization, Multi-Criteria Optimization, Nonlinear Optimization Tags , , ,

    Stochastic alternating algorithms for bi-objective optimization are considered when optimizing two conflicting functions for which optimization steps have to be applied separately for each function. Such algorithms consist of applying a certain number of steps of gradient or subgradient descent on each single objective at each iteration. In this paper, we show that stochastic alternating … Read more

    Parallel Dual Dynamic Integer Programming for Large-Scale Hydrothermal Unit-Commitment

  • Bruno Colonetti
  • Erlon Finardi
  • Victor M. Zavala
  • Samuel Brito
    • Categories Dynamic Programming, Parallel Algorithms, Scheduling Tags , , ,

    Unit commitment has been at the center of power system operation for well over 50 years. Yet, this problem cannot be considered solved due to its size and complexity. Today, operators rely on off-the-shelf optimization solvers to tackle this challenging problem, and often resort to simplifications to make the problem more tractable and solvable in … Read more

    Discrete Optimal Transport with Independent Marginals is #P-Hard

  • Bahar Tașkesen
  • Soroosh Shafieezadeh-Abadeh
  • Daniel Kuhn
  • Karthik Natarajan
    • Categories Dynamic Programming, Linear Programming, Stochastic Programming

    We study the computational complexity of the optimal transport problem that evaluates the Wasserstein distance between the distributions of two K-dimensional discrete random vectors. The best known algorithms for this problem run in polynomial time in the maximum of the number of atoms of the two distributions. However, if the components of either random vector … Read more