Square root in objective function must appear as nonlinear constraints for optimization?

The title already described my question. Let me give a specific example:

If I have in my objective function for fmincon to optimize. During the iterations, may be smaller than 0.

Therefore, do I need to write as nonlinear constraints or does Matlab already take account of the problem?

Thank you very much!

Answer 1

[Matt J]

You should omit square roots, because they introduce both unneccesary additional computation and non-differentiability into the cost function, which breaks the theoretical assumptions of fmincon. In your example, the problem could be equivalently posed without square roots as

min x^2
s.t. x^2>=100

[Frank]

Matt, thanks for your answer! I gave an over-simplified example in the my question above.

In my real project, the objective function is too complicated to omit square roots in function f: I frequently have to evaluate the function f=a+b^2+sqrt(c) and put the function into use for the objective function. f has very a specific physical meaning and f^2 can't be use for the objective function.

Therefore, I now believe I have to take the advice of Sandeep.

[Matt J]

Sandeep's advice won't work reliably, unfortunately, because fmincon does not obey the nonlinear constraints at all iterations. Even if you specify constraints, it can still attempt to evaluate your objective in regions where the square root argument is negative.

Also, even if the nonlinear constraints were obeyed at all iterations, the non-differentiability issue still remains.

You have to avoid the square roots... As for how to do that, I recommend you repost your question with an example more representative of your actual problem.

[John D'Errico]

@Frank - you have decided to take Sandeep's advice here, because you think it makes your solution easy. In the end, Matt is giving you the advice you need, whether or not you like the consequence. The easy solution is not always the best one.

[Frank]

Thank you all for adding further information here. Please allow me to provide further illustrations of my problem above. I am doing a tomography problem with velocity function as f=a+b^2+sqrt(-x^3+2*x+99), which requires calculating time as distance divided by velocity f directly. The objective function is |t(f)-data|, where t is time that depends on velocity f complicately (I have to do ray tracing here, ray tracing requires evaluating velocity function f directly and you can't use f^2 for ray tracing). The objective function |t(f)-data| is the standard objective function in tomography, I have seen many many people use it.

Lastly, Matt, could you please kindly tell me what is the non-differentiability issue? I can differentiate my objective function and nonlinear constraints easily.

[Matt J]

Lastly, Matt, could you please kindly tell me what is the non-differentiability issue? I can differentiate my objective function and nonlinear constraints easily.

The function sqrt(z) has no derivative at z=0. In your case, the function f and hence also t(f) is non-differentiable wherever -x^3+2*x+99=0. So, if the optimal solution lies near such a point, fmincon will not be able to use gradients to find its way there.

What is |t(f)-data|? Is it a least squares objective or is it the L1 norm error between t(f) and |data|? The L1 norm also has differentiability issues.

[Frank]

Thanks! I can understand your answer. It is a least square.

Answer 2

[Matt J]

One general way to get rid of sqrt expressions in the objective is to replace them with an additional nonlinearly constrained variable, e.g., instead of

f=a+b^2+sqrt(-x^3+2*x+99)

have instead,

f=a+b^2+c
s.t. c^2=-x^3+2*x+99
     c>=0;

All of the above expressions, both in the objective and the constraints, are now differentiable everywhere.

[Pedro Luis Camuñas]

Thanks, this canswer helped me a lot

Answer 3

[SandeepKumar R]

Yes, you need to specify that constraint as ignoring this will lead infeasibilty. This is true for any optimizer

Answer 4

[Walter Roberson]

if you have fractional power of a polynomial (not a multinomial) then manually solve for the bounds and express them as bounds constraints . Bounds constraints are respected in most situations .

You might end up with discontinuous ranges. If so it can often be more efficient to run the ranges as separate problems and take the best solution afterwards . Nonlinear constraints are much less efficient to deal with .