Runtime Analysis of Single- and Multi-Objective Evolutionary Algorithms for Chance Constrained Optimization Problems with Normally Distributed Random Variables

• URL: http://arxiv.org/abs/2109.05799v2
• Date: Wed, 10 Aug 2022 01:20:47 GMT
• Title: Runtime Analysis of Single- and Multi-Objective Evolutionary Algorithms for Chance Constrained Optimization Problems with Normally Distributed Random Variables
• Authors: Frank Neumann and Carsten Witt
• Abstract summary: We study the scenario of components that are independent and Normally distributed. We show that imposing an additional uniform constraint already leads to local optima. We prove that this approach can also be used to compute a set of optimal solutions for the chance constrained minimum spanning tree problem.
• Score: 13.264683014487376
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Chance constrained optimization problems allow to model problems where constraints involving stochastic components should only be violated with a small probability. Evolutionary algorithms have been applied to this scenario and shown to achieve high quality results. With this paper, we contribute to the theoretical understanding of evolutionary algorithms for chance constrained optimization. We study the scenario of stochastic components that are independent and Normally distributed. Considering the simple single-objective (1+1)~EA, we show that imposing an additional uniform constraint already leads to local optima for very restricted scenarios and an exponential optimization time. We therefore introduce a multi-objective formulation of the problem which trades off the expected cost and its variance. We show that multi-objective evolutionary algorithms are highly effective when using this formulation and obtain a set of solutions that contains an optimal solution for any possible confidence level imposed on the constraint. Furthermore, we prove that this approach can also be used to compute a set of optimal solutions for the chance constrained minimum spanning tree problem. In order to deal with potentially exponentially many trade-offs in the multi-objective formulation, we propose and analyze improved convex multi-objective approaches. Experimental investigations on instances of the NP-hard stochastic minimum weight dominating set problem confirm the benefit of the multi-objective and the improved convex multi-objective approach in practice.

Related papers

• Generalization Bounds of Surrogate Policies for Combinatorial Optimization Problems [61.580419063416734]
  A recent stream of structured learning approaches has improved the practical state of the art for a range of optimization problems. The key idea is to exploit the statistical distribution over instances instead of dealing with instances separately. In this article, we investigate methods that smooth the risk by perturbing the policy, which eases optimization and improves the generalization error.
  arXiv  Detail & Related papers  (2024-07-24T12:00:30Z)
• Optimizing Chance-Constrained Submodular Problems with Variable Uncertainties [12.095075636344536]
  We study chance-constrained submodular optimization problems, which capture a wide range of problems with constraints. We present greedy algorithms that can obtain a high-quality solution, i.e., a constant approximation ratio to the given optimal solution.
  arXiv  Detail & Related papers  (2023-09-23T04:48:49Z)
• Backpropagation of Unrolled Solvers with Folded Optimization [55.04219793298687]
  The integration of constrained optimization models as components in deep networks has led to promising advances on many specialized learning tasks. One typical strategy is algorithm unrolling, which relies on automatic differentiation through the operations of an iterative solver. This paper provides theoretical insights into the backward pass of unrolled optimization, leading to a system for generating efficiently solvable analytical models of backpropagation.
  arXiv  Detail & Related papers  (2023-01-28T01:50:42Z)
• End-to-End Pareto Set Prediction with Graph Neural Networks for Multi-objective Facility Location [10.130342722193204]
  Facility location problems (FLPs) are a typical class of NP-hard optimization problems, which are widely seen in the supply chain and logistics. In this paper, we consider the multi-objective facility location problem (MO-FLP) that simultaneously minimizes the overall cost and maximizes the system reliability. Two graph neural networks are constructed to learn the implicit graph representation on nodes and edges.
  arXiv  Detail & Related papers  (2022-10-27T07:15:55Z)
• Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
  We present an end-to-end method to learn the proximal operator across non-family problems. We show that for weakly-ized objectives and under mild conditions, the method converges globally.
  arXiv  Detail & Related papers  (2022-01-28T05:53:28Z)
• Integrated Conditional Estimation-Optimization [6.037383467521294]
  Many real-world optimization problems uncertain parameters with probability can be estimated using contextual feature information. In contrast to the standard approach of estimating the distribution of uncertain parameters, we propose an integrated conditional estimation approach. We show that our ICEO approach is theally consistent under moderate conditions.
  arXiv  Detail & Related papers  (2021-10-24T04:49:35Z)
• Outlier-Robust Sparse Estimation via Non-Convex Optimization [73.18654719887205]
  We explore the connection between high-dimensional statistics and non-robust optimization in the presence of sparsity constraints. We develop novel and simple optimization formulations for these problems. As a corollary, we obtain that any first-order method that efficiently converges to station yields an efficient algorithm for these tasks.
  arXiv  Detail & Related papers  (2021-09-23T17:38:24Z)
• Modeling the Second Player in Distributionally Robust Optimization [90.25995710696425]
  We argue for the use of neural generative models to characterize the worst-case distribution. This approach poses a number of implementation and optimization challenges. We find that the proposed approach yields models that are more robust than comparable baselines.
  arXiv  Detail & Related papers  (2021-03-18T14:26:26Z)
• Offline Model-Based Optimization via Normalized Maximum Likelihood Estimation [101.22379613810881]
  We consider data-driven optimization problems where one must maximize a function given only queries at a fixed set of points. This problem setting emerges in many domains where function evaluation is a complex and expensive process. We propose a tractable approximation that allows us to scale our method to high-capacity neural network models.
  arXiv  Detail & Related papers  (2021-02-16T06:04:27Z)
• Adaptive Sampling of Pareto Frontiers with Binary Constraints Using Regression and Classification [0.0]
  We present a novel adaptive optimization algorithm for black-box multi-objective optimization problems with binary constraints. Our method is based on probabilistic regression and classification models, which act as a surrogate for the optimization goals. We also present a novel ellipsoid truncation method to speed up the expected hypervolume calculation.
  arXiv  Detail & Related papers  (2020-08-27T09:15:02Z)
• Evolutionary Bi-objective Optimization for the Dynamic Chance-Constrained Knapsack Problem Based on Tail Bound Objectives [12.634782111072585]
  We consider the dynamic chance-constrained knapsack problem where the weight of each item is the subject of a capacity constraint. The objective is to maximize the total profit subject to the probability that total weight exceeds the capacity. We introduce an additional objective which estimates the minimal capacity bound for a given solution that still meets the chance constraint.
  arXiv  Detail & Related papers  (2020-02-17T04:36:15Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.