selecting units for (1) scaling of variable and (2) condition number minimization

In gradient-based optimization problem, selecting units can influence the condition number of the gradient. A smaller condition number is generally good for optimization.

At the same time, selecting untis can also make the variable unblanced. For example, one variable maybe of the scale of 10^10, while another variable maybe of the scale of 0.0001.

My experience is if I make the variable of similar scale, the optimization problem generally finishes good.

Sometimes, the the two objectives are contradictory to each other.

How to balance these two contradictions? Thank you very much!

[Matt J]

selecting units can influence the condition number of the gradient

The condition number of the Hessian, I think you mean.

Answer 1

[Matt J]

You are free to translate as well as scale your optimization variables (or make any other nonlinear 1-1 transformation that might be useful).

For example, this quadratic objective is well-conditioned, wih condition number = 1, and doesn't require a change of units,

but has solutions at very large x and very small y. I'm not sure why you consider this a problem, but you could remedy it by making the change of variables , and rewriting the problem as,

[Frank]

You didn't understand my question. If the unit of x is meter, you have the above equation. Then if the unit of x is centermeter, and unit of y is kept the same, you will have the following equation:

This is ill-conditioned compare to your original equation, which shows the importance of selecting units. Also, I talked about scale of 10^10 and 0.0001, you talked about the solution at 10^10 and 0.0001.

[Matt J]

Also, I talked about scale of 10^10 and 0.0001, you talked about the solution at 10^10 and 0.0001.

I don't see the difference. If the solution in your problem is not located at values of very different magnitude, in what way do the variables have different scales? An illustration of the conflict you're encountering might help to clarify things.

In any case, my remarks apply equally well to your revised example. If you make the change of variables you obtain the same well-conditioned problem,

and the solutions for X and Y are of comparable magnitudes.

[Frank]

In optimization, you can't make the change of variables to obtain the well-conditioned problem because you don't know the solution or the units for change. In my problem, I have to try different units to know the best units. Your suggested change of variables assume you know the solution and the best units.

[Matt J]

But every time you try different units, you are making a change of variables. If your original function is f(x), the new function after changing units is g(z)=f(S*z) where S is a diagonal scaling matrix.

As for the toy examples, they are idealizations. It is true that you may not be able to know the ideal best transformation beforehand, but the closer to the ideal transformation that you can guess, the greater improvement in conditioning you will achieve.

[Frank]

I am doing a highly sophistcated optimizaiton. I agree completely with what you said in the last post. In fact, I can do another optimization search to obtain the best transformation with the best conditioning. However, as I said in the original post, running my optimization with the best conditioning often does NOT produce good results. What I tried is try to make the initial input parameters of similar scale, which often produce good results. "make the initial input parameters of similar scale” often obtain a good conditioning.

Could you please give some comments on this? Maybe some bugs in my code? Thank you!

[Bruno Luong]

@Frank "unning my optimization with the best conditioning often does NOT produce good results. "

Please explain

• how do you estimate the conditioning of the Hessian? and
• what do you do to "running your optimization with the best conditioning"?

In other words what leads you to draw such conclusion?

I agree with Matt in the sense that if the problem is linear least squares, by doing "best" conditioning, meaning H = eye(length(x)) the mimimizer should converge in one iteration. So something else is going on and you need to explain what is "highly sophistcated optimizaiton" or when you claimed "best" is not really best.

You haven't elaborate in your question at all your math model what you did. it's just a vain disussion on the air if you don't provide us with more details.

[Frank]

Thanks for your comments.

I am not talking about the conditioning of the Hessian. I am talking about the conditioning of the gradient. I do SVD to compute the gradient of the objective function, whose largest singular value to smallest singular value is defined as condition number. This condition number is dependant on selection of units. For example, by doing a grid search for all units I can obtain the smallest condition number, which is what I meant "best conditioning". I have seen power of this method in many publications and my own experiences.

It is a tomography model. Sorry I can't disclose more of my model since I have been working on this model for years and don't want my competitor to know all my calculation details.

[Bruno Luong]

"I am not talking about the conditioning of the Hessian. I am talking about the conditioning of the gradient."

AFAIK condition number applied on matrix. It's defined as

norm(A)*norm(inv(A)) https://en.wikipedia.org/wiki/Condition_number

There is no such thing as conditioning of the gradient which is a vector and NOT a matrix.

To describe your problem you must start to use correctly math terminology.

I do SVD to compute the gradient of the objective function, whose largest singular value to smallest singular value is defined as condition number"

I don't know what SVD you are talking about (what is the matrix, is it the Jacobian of the model (?)), but if that is the case please explain this process.

What you call conditioning might be something entirely different than what WE think (the matrix is the Hessian) and may be that's explain why you get confusing result.

Note that for non-linear case the Hessian is NOT J'*J, where J is the Jacobian of the model (at the considered point).

And the Jacobian change wrt the point. Do you take the Jacobian at the first guess? At the solution of the preceding optimisation? Something else?

"This condition number is dependant on selection of units."

Of course this we all know, but you did not explain:

• when normalizing the unit and it converges faster; does the conditiong improve or degrade?

Also the conditiong is just a partial view of the whole picture. May be you have in your model somesort of null-space (space of the decision variables that is NOT observable by your data), or you have some constrained problem and active constraints and you need to evalute the conditioning of the Hessian projected on the tangent space (*), in this case the condition number of the full Hessian does NOT reflect the convergence rate.

Manything that can lead you to a wrong conclusion. If you are not able to show with a MWE the disussion is just vain.

At least show us the figure of normalization process, the problem dimension, the condition number you estimate - at the initial point and at the convergence point -, the number of iterations for convergence, the number of active constraints at the solution; etc...

I'll stop here, without more details the discussion is a waste of time.

(*) Acutually the curvature of the constraints also matter.

[Frank]

Thanks for your thought-provoking reply. Sorry I wasn't clear enough and made some wrong statements.

I am doing a tomography problem, which has the main physical parameter traveltime. When I said gradient, I meant the gradeint of each ray traveltime with regard to the velocity. Since there are m traveltimes and n velocity parameters, we have a gradient matrix. I did Singular Value Decomposition of this matrix and obtain its condition number.

What you said is NOT in vain to me, they are very helpful!!! Thank you very much!!!