Heuristic optimization

Heuristic optimization seeks useful feasible solutions without necessarily providing a universal approximation ratio or a polynomial worst-case guarantee. Examples are local search, simulated annealing and tabu search. A claimed approximation algorithm needs a separate proved performance guarantee.

Tabu search keeps a short-term memory of recently reversed moves or visited attributes and prohibits them temporarily, reducing cycling in local search. It can select the best admissible neighbor even when that neighbor worsens the objective; an aspiration rule permits a tabu move when it improves the best known solution. For allocations, transfers and exchanges maintain feasibility and recent reverse transfers can be tabu.

For a maximization objective, simulated annealing accepts every improving proposed neighbor and accepts a worsening move of loss $\Delta$ with probability $\exp (-\Delta /T)$ at temperature $T>0$. Decreasing the temperature reduces exploratory moves. Retain the best feasible solution seen. Finite practical cooling schedules carry no general global-optimality guarantee.

To maximize a log-likelihood, use energy $-\ell$ and Boltzmann distribution proportional to $e^{\ell /T}=L^{1/T}$ at temperature $T>0$. Reversing this sign favors likelihood minima and can make the probability density function nonnormalizable. For Poisson observations with total $s$ and sample size $m$, with respect to $d\lambda$ the normalized probability density function isIts mean is $(s+T)/m$ and variance $(sT+T^2)/m^2$, so it concentrates at the maximum-likelihood estimate $s/m$ as $T\downarrow 0$. Cooling of equilibrium laws and convergence of a particular changing-temperature chain are different statements; the latter requires mixing or a direct chain argument.

For $m$ independent binomial distribution observations with fixed trial count $n$ and total successes $s$, the likelihood-power probability density function relative to $dp$ is $p^{s/T}(1-p{)}^{(mn-s)/T}$. Its normalized law is the displayed beta distribution. Its mean tends to $s/(mn)$ and its variance tends to zero as $T\downarrow 0$, including endpoint maxima. Energy for maximizing a log-likelihood is its negative; the opposite sign reverses the optimization.

Let $\bar{x}=m^{-1}{\sum }_i{x}_i$ and $S={\sum }_i(x_i-\bar{x}{)}^2>0$. With Lebesgue base measure $d\mu dv$ for $v={\sigma }^2$, the likelihood-power law has conditionalsThe joint law is proper for $T<m/3$, since its marginal $v$ is inverse-gamma distribution with shape $m/(2T)-3/2$ and scale $S/(2T)$. There is also a direct convergence proof for successive Gibbs sampling updates with deterministic $0<T_n\le m/10$ and $T_n\to 0$. Update ${\mu }_n$ from $v_{n-1}$, then $v_n$ from ${\mu }_n$. Inverse-gamma distribution moments and conditional normal moments giveThe coefficients of the preceding moments are bounded by $1/6$ and $1/8$, so these moments stay bounded from a finite deterministic initial variance. Letting $T_n\to 0$ gives $\mathbb{E}{v}_n\to S/m$ and $\mathbb{E}{v}_n^2\to (S/m{)}^2$. Also $\mathbb{E}({\mu }_n-\bar{x}{)}^2=T_n\mathbb{E}{v}_{n-1}/m\to 0$. Thus the iterates converge in mean square to the normal maximum-likelihood estimate.

Local search repeatedly improves a feasible solution within a specified neighborhood until no improving move remains. For an allocation, neighbors can transfer an item or exchange items between bidders while preserving the partition. A local optimum need not be a global optimum; restarting from several initial solutions can explore different basins.