Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userUsing Entropy-Based Methods to Study General Constrained Parameter Optimization Problems
56
0
0.0
(
0
)
Added by
Marcio Argollo de Menezes
Publication date
2001
fields
Physics
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
In this letter we propose the use of physics techniques for entropy determination on constrained parameter optimization problems. The main feature of such techniques, the construction of an unbiased walk on energy space, suggests their use on the quest for optimal solutions of an optimization problem. Moreover, the entropy, and its associated density of states, give us information concerning the feasibility of solutions.
rate research
Read More
Optimization is fundamental in many areas of science, from computer science and information theory to engineering and statistical physics, as well as to biology or social sciences. It typically involves a large number of variables and a cost function depending on these variables. Optimization problems in the NP-complete class are particularly difficult, it is believed that the number of operations required to minimize the cost function is in the most difficult cases exponential in the system size. However, even in an NP-complete problem the practically arising instances might, in fact, be easy to solve. The principal question we address in this thesis is: How to recognize if an NP-complete constraint satisfaction problem is typically hard and what are the main reasons for this? We adopt approaches from the statistical physics of disordered systems, in particular the cavity method developed originally to describe glassy systems. We describe new properties of the space of solutions in two of the most studied constraint satisfaction problems - random satisfiability and random graph coloring. We suggest a relation between the existence of the so-called frozen variables and the algorithmic hardness of a problem. Based on these insights, we introduce a new class of problems which we named locked constraint satisfaction, where the statistical description is easily solvable, but from the algorithmic point of view they are even more challenging than the canonical satisfiability.
A two parameter percolation model with nucleation and growth of finite clusters is developed taking the initial seed concentration rho and a growth parameter g as two tunable parameters. Percolation transition is determined by the final static configuration of spanning clusters. A finite size scaling theory for such transition is developed and numerically verified. The scaling functions are found to depend on both g and rho. The singularities at the critical growth probability gc of a given rho are described by appropriate critical exponents. The values of the critical exponents are found to be same as that of the original percolation at all values of rho at the respective gc . The model then belongs to the same universality class of percolation for the whole range of rho.
We use a neural network ansatz originally designed for the variational optimization of quantum systems to study dynamical large deviations in classical ones. We obtain the scaled cumulant-generating function for the dynamical activity of the Fredrickson-Andersen model, a prototypical kinetically constrained model, in one and two dimensions, and present the first size-scaling analysis of the dynamical activity in two dimensions. These results provide a new route to the study of dynamical large-deviation functions, and highlight the broad applicability of the neural-network state ansatz across domains in physics.
The inverse problem for a disordered system involves determining the interparticle interaction parameters consistent with a given set of experimental data. Recently, Rutledge has shown (Phys. Rev. E63, 021111 (2001)) that such problems can be generally expressed in terms of a grand canonical ensemble of polydisperse particles. Within this framework, one identifies a polydisperse attribute (`pseudo-species) $sigma$ corresponding to some appropriate generalized coordinate of the system to hand. Associated with this attribute is a composition distribution $barrho(sigma)$ measuring the number of particles of each species. Its form is controlled by a conjugate chemical potential distribution $mu(sigma)$ which plays the role of the requisite interparticle interaction potential. Simulation approaches to the inverse problem involve determining the form of $mu(sigma)$ for which $barrho(sigma)$ matches the available experimental data. The difficulty in doing so is that $mu(sigma)$ is (in general) an unknown {em functional} of $barrho(sigma)$ and must therefore be found by iteration. At high particle densities and for high degrees of polydispersity, strong cross coupling between $mu(sigma)$ and $barrho(sigma)$ renders this process computationally problematic and laborious. Here we describe an efficient and robust {em non-equilibrium} simulation scheme for finding the equilibrium form of $mu[barrho(sigma)]$. The utility of the method is demonstrated by calculating the chemical potential distribution conjugate to a specific log-normal distribution of particle sizes in a polydisperse fluid.
We introduce and study the random locked constraint satisfaction problems. When increasing the density of constraints, they display a broad clustered phase in which the space of solutions is divided into many isolated points. While the phase diagram can be found easily, these problems, in their clustered phase, are extremely hard from the algorithmic point of view: the best known algorithms all fail to find solutions. We thus propose new benchmarks of really hard optimization problems and provide insight into the origin of their typical hardness.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
