# Global Optimization of a well-defined function with gradient information

I try to minimize the function $$f(x_1, …x_n)=\sum\limits_{i}^n-a_i\cos(4(x_i-b_i)) +\sum\limits_{ij}^\text{edge}- \cos(4(x_i-x_j)), \quad x_i,b_i\in (-\pi, \pi)$$ where $\sum\limits_{ij}^{edge}$ only sums over predefined edges (the edges are sparse, typical there are 4 edges for each $i$). The variables $a_i, b_i$ are constants, $a_i \in (0,1)$; many $a_i$s are 0. The gradient at each iteration can be directly computed. I observe that Gradient Descent converges very fast, but produces very bad results (very easily falls into local optimal). I have no idea whether Conjugate Gradient Algorithm or BFGS algorithm will make a significant difference. While general optimization such as simulated annealing and GA do not use the gradient information (they seem powerful but blind to local derivative), thus I am looking for techniques making good use of gradient information.

Another approach is to continue using gradient descent, but make some adjustments. One simple thing you can try is to apply it many times, each time with a different random starting point. Also there are various tuning knobs you can tweak, such as adjusting the step size or using momentum. A third possibility could be to try to make a "smarter" choice of starting point for gradient descent: you can approximate each cosine by a quadratic function (using the Taylor series expansion at a particular point), obtain a function $f^*$ that is a quadratic approximation to $f$, and then find the exact minimum for $f^*$ using least-squares method. This basically amounts to applying one step of Newton's method and then continuing with gradient descent from there.
Thank D.W! I would like to try various Newton methods in near future. But I found my function here has a special structure that can be formulated as a quadric form. Today I tried quadratic programming with Java and it works! First, the energy function is defined as (a little bit from the original one): $$f(x_1, …x_n)=\sum\limits_{i}^n(x_i-m_i)^2 +\sum\limits_{ij}^{edge}(x_i-y_i)^2$$ Let $x=\{ x_1, …x_n \}$ we get a quadratic form: $$f(x_1, …x_n)= \frac{1}{2}x^TAx-b^Tx$$ Which can be solved by Ax=b, by one shot instead of iterative process! I programmed it in Java and it gives the results in the following image(the red points are $m_i$). Here $n=2156$, so matrix $A$ is $2156\times2156$. It takes several seconds to compute its inverse to solve the system. while, the 'sharp' peak at each $m_i$ is not desirable, I guess modifying the energy function would change the curvature at the peaks.