5
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

One alternative is to use Newton's method. Newton's method uses information from the first and second derivative (i.e., the Hessian matrix), so it can converge in fewer steps than gradient descent (which uses only information from the first derivative) -- but the cost is that each single step is slower, because it requires more complex computations.

If Newton's method is too slow, there are faster variants, such as BFGS and other quasi-Newton methods or the conjugate gradient method.

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.

Trying several different methods shouldn't be too hard if you use the right software, as there are many software packages that let you specify the function and then make it easy to try multiple different optimization methods.

$\endgroup$
0
$\begingroup$

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. enter image description here

while, the 'sharp' peak at each $m_i$ is not desirable, I guess modifying the energy function would change the curvature at the peaks.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.