Stochastic Item Descent Method for Large Scale Equal Circle Packing Problem

• URL: http://arxiv.org/abs/2001.08540v1
• Date: Wed, 22 Jan 2020 02:40:31 GMT
• Title: Stochastic Item Descent Method for Large Scale Equal Circle Packing Problem
• Authors: Kun He, Min Zhang, Jianrong Zhou, Yan Jin, and Chu-min Li
• Abstract summary: gradient descent (SGD) is a powerful method for large-scale optimization problems in the area of machine learning. We apply SGD with batch selection of samples to a classic optimization problem in decision version. Specifically, we propose a item descent method (SIDM) for ECPP in large scale, which randomly divides the unit circles into batches.
• Score: 22.230497408207594
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Stochastic gradient descent (SGD) is a powerful method for large-scale optimization problems in the area of machine learning, especially for a finite-sum formulation with numerous variables. In recent years, mini-batch SGD gains great success and has become a standard technique for training deep neural networks fed with big amount of data. Inspired by its success in deep learning, we apply the idea of SGD with batch selection of samples to a classic optimization problem in decision version. Given $n$ unit circles, the equal circle packing problem (ECPP) asks whether there exist a feasible packing that could put all the circles inside a circular container without overlapping. Specifically, we propose a stochastic item descent method (SIDM) for ECPP in large scale, which randomly divides the unit circles into batches and runs Broyden-Fletcher-Goldfarb-Shanno (BFGS) algorithm on the corresponding batch function iteratively to speedup the calculation. We also increase the batch size during the batch iterations to gain higher quality solution. Comparing to the current best packing algorithms, SIDM greatly speeds up the calculation of optimization process and guarantees the solution quality for large scale instances with up to 1500 circle items, while the baseline algorithms usually handle about 300 circle items. The results indicate the highly efficiency of SIDM for this classic optimization problem in large scale, and show potential for other large scale classic optimization problems in which gradient descent is used for optimization.

Related papers

• Optimizing Posterior Samples for Bayesian Optimization via Rootfinding [2.94944680995069]
  We introduce an efficient global optimization strategy for posterior samples based on global rootfinding. Remarkably, even with just one point from each set, the global optimum is discovered most of the time. Our approach also improves the performance of other posterior sample-based acquisition functions, such as variants of entropy search.
  arXiv  Detail & Related papers  (2024-10-29T17:57:16Z)
• A Multilevel Approach For Solving Large-Scale QUBO Problems With Noisy Hybrid Quantum Approximate Optimization [3.3493770627144004]
  We experimentally test how existing quantum processing units (QPUs) perform as subsolvers within a multilevel strategy. We find approximate solutions to $10$ instances of fully connected $82$-qubit Sherrington-Kirkpatrick graphs. We observe that quantum optimization results are competitive regarding the quality of solutions compared to classicals.
  arXiv  Detail & Related papers  (2024-08-14T20:06:32Z)
• A Particle-based Sparse Gaussian Process Optimizer [5.672919245950197]
  We present a new swarm-swarm-based framework utilizing the underlying dynamical process of descent. The biggest advantage of this approach is greater exploration around the current state before deciding descent descent.
  arXiv  Detail & Related papers  (2022-11-26T09:06:15Z)
• STORM+: Fully Adaptive SGD with Momentum for Nonconvex Optimization [74.1615979057429]
  We investigate non-batch optimization problems where the objective is an expectation over smooth loss functions. Our work builds on the STORM algorithm, in conjunction with a novel approach to adaptively set the learning rate and momentum parameters.
  arXiv  Detail & Related papers  (2021-11-01T15:43:36Z)
• Distributed stochastic optimization with large delays [59.95552973784946]
  One of the most widely used methods for solving large-scale optimization problems is distributed asynchronous gradient descent (DASGD) We show that DASGD converges to a global optimal implementation model under same delay assumptions.
  arXiv  Detail & Related papers  (2021-07-06T21:59:49Z)
• Local policy search with Bayesian optimization [73.0364959221845]
  Reinforcement learning aims to find an optimal policy by interaction with an environment. Policy gradients for local search are often obtained from random perturbations. We develop an algorithm utilizing a probabilistic model of the objective function and its gradient.
  arXiv  Detail & Related papers  (2021-06-22T16:07:02Z)
• Bayesian Algorithm Execution: Estimating Computable Properties of Black-box Functions Using Mutual Information [78.78486761923855]
  In many real world problems, we want to infer some property of an expensive black-box function f, given a budget of T function evaluations. We present a procedure, InfoBAX, that sequentially chooses queries that maximize mutual information with respect to the algorithm's output. On these problems, InfoBAX uses up to 500 times fewer queries to f than required by the original algorithm.
  arXiv  Detail & Related papers  (2021-04-19T17:22:11Z)
• Correcting Momentum with Second-order Information [50.992629498861724]
  We develop a new algorithm for non-critical optimization that finds an $O(epsilon)$epsilon point in the optimal product. We validate our results on a variety of large-scale deep learning benchmarks and architectures.
  arXiv  Detail & Related papers  (2021-03-04T19:01:20Z)
• Learning the Step-size Policy for the Limited-Memory Broyden-Fletcher-Goldfarb-Shanno Algorithm [3.7470451129384825]
  We consider the problem of how to learn a step-size policy for the Limited-Memory Broyden-Fletcher-Goldfarb-Shanno (L-BFGS) algorithm. We propose a neural network architecture with local information of the current gradient as the input. The step-length policy is learned from data of similar optimization problems, avoids additional evaluations of the objective function, and guarantees that the output step remains inside a pre-defined interval.
  arXiv  Detail & Related papers  (2020-10-03T09:34:03Z)
• A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Critic [142.1492359556374]
  Bilevel optimization is a class of problems which exhibit a two-level structure. We propose a two-timescale approximation (TTSA) algorithm for tackling such a bilevel problem. We show that a two-timescale natural actor-critic policy optimization algorithm can be viewed as a special case of our TTSA framework.
  arXiv  Detail & Related papers  (2020-07-10T05:20:02Z)
• Adaptive Large Neighborhood Search for Circle Bin Packing Problem [8.855116523397935]
  We address a new variant of packing problem called the circle bin packing problem (CBPP) CBPP is to find a dense packing of circle items to multiple square bins so as to minimize the number of used bins. We propose an adaptive large neighborhood search (ALNS) algorithm, which uses our Greedy Algorithm with Corner Occupying Action (GACOA) to construct an initial layout.
  arXiv  Detail & Related papers  (2020-01-20T10:14: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.