3
$\begingroup$

I am using a stable version of SQP algorithm from a lib. Parameters setting is left to the developer, althought default values are at hands. I launch solver on very simple optimization problems s.a.

$\min{( p_{1} * \exp^{ (p_{2} * x)})}$

$s.t. 0 \leq p_{1}, p_{2} \leq 10$

I feed optimization with a well chosen initial point, using Monte Carlo sampling in the allowed space.

It appears that optimization output is very sensitive to initial point. I tried to play with some parameters such as precision on gradient calculation (using finite difference scheme)... but still: even on simple examples like this one, it does not converge at all time.

I also would like optimization to be possible on any function such as elementary functions of matlab optimization toolbox, and their linear combination (exp, power, gaussian, sin, cos, fourier, polynomial, linear, rational as a start).

If somebody has some experience with tuning such algorithms, I would be glad that he shares that knowledge. Also, would you have good hint at literature where tuning strategies are unveiled?

regards.

$\endgroup$
3
$\begingroup$

The right thing is to scale your variables before calling the solver. Then you can probably use the default version.

Good scaling is often problem-dependent and therefore difficut to do automatically. This is why most solvers leave it to the user.

Your variables are well-scaled if the Hessian divided by its absolutely largest entry has small entries only where the corresponding interactions are truly negligible. This may give you an idea how to scale even if you cannot calculate an explicit Hessian.

In your example, it means to use $p_2x$ or even $e^{p_2x}$ as variable in place of $p_2$.

In general, there are no fixed rules for scaling; it is an art and depends on the details of your objective function and your constraints. One way to find out which variables need scaling is to compute the Hessian at the starting point, equilibrate it using a scaling method for symmetric matrices, and check all variables that were scaled heavily. (If the Hessian is positive definite, you may simply divide the variables by the square root of the Hessian diagonal elements, or their order of magnitude; but if the Hessian is indefinite, this may be dangerous!) This gives you also scaling factors for linear scaling. If this is not sufficient, you either need nonlinear scaling (inspect your function to find out what is natural), or you need to use the solver iteratively, restarting with the previous output and a new scale determined at the new starting point.

If you still need to tune, the standard recipe is to prepare a set of test problems typical for the application (but simpler if the application functions are expensive to evaluate), run all examples with the solver, and compute from the results a performance measure of interest. Then systematically change the tuning parameters to improve the performance. This is itself a black-box optimization problem, for which you can use solvers such as SNOBFIT (a solver developed by my group, works for continuous tuning parameters only) or NOMAD (also accepts discrete tuning parameters).

$\endgroup$
  • $\begingroup$ thanks! you explain with words what makes a good scaling. but do you have some recipe, some rules for scaling with hessian calculation and test ? (a rule statement s a (preposterous) 'if hessian divided by largest entry < tol, divide data by n') what you say about difficult automation let me think there isnt, i am asking anyway. $\endgroup$ – kiriloff Oct 2 '12 at 8:30
  • $\begingroup$ BTW, the solver i am integrating in my code is providing scaling already $\endgroup$ – kiriloff Oct 2 '12 at 8:33
  • $\begingroup$ @fonjibe: I added to my ansewer some remarks on how to scale. - Which solver has such a poor scaling behavior? I cannot understand why your solver doesn't solve the problem when $x=1$. When $x$ is very different from 1, well-designed scaling routine (assuming the solver has one) should produce a reasonable scale corresponding to $x\approx 1$. $\endgroup$ – Arnold Neumaier Oct 2 '12 at 10:13

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.