Steepest Descent with constraints

[matts0611]

Hi, I am working on a project for my research and am need of some advice.
My background is in computer engineering / programming so I'm in need of some help from some math people :)

I need to use steepest descent to solve a problem, a function that needs to be minimized.

The function has 5 variables that each have a constant range, min1 < X1 < max1 etc

I am writing this program in C.

The function that needs to be minimized is complex enough that I do not know how to calculate the partial derivatives by hand.Some questions.

1. As far as I understand steepest descent (or gradient search) works without constraints. However, my variables do have constraints. Is there a way to modify steepest descent that works with constraints?

I have used the MS Excel solver to solve my problem and it solves it pretty fast (less than one second). From what I understand Excel uses something called Generalized Reduced Gradient method. Which from what I understand is based off Steepest Descent but can be used on problems with constraints. I have found some information on this algorithm but it seems so complex. Do i need to use this algorithm or can I get away with using something simpler since the constrains in my problem are simple?

2. If I don't know the partial derivatives of my function is it ok to estimate the derivatives by taking the difference of two points close together? Is there a better way?

3. On steepest descent, from what I understand, you first find the negative gradient vector and then find the step size in that direction. How do you find the best step size? There seems to be so many different methods for this?The more things I read about this stuff on my own the more confused and the more questions I seem to have. I guess I'm just looking for some guidance from someone more knowledgeable than I in this area.

Any help or advice would be greatly appreciated.

 

[Stephen Tashi]

Hi, I am working on a project for my research

I need to use steepest descent to solve a problem, a function that needs to be minimized.

I can't resist asking why the research requires that you use a particular algorithm.

The function that needs to be minimized is complex enough that I do not know how to calculate the partial derivatives by hand.

Don't neglect trying computer algebra software if knowing the symbolic form of the partial derivatives would be useful.

.
Is there a way to modify steepest descent that works with constraints?

Do you mean some very simple way? I don't know of any. There might be particular things about the function you are dealing with that made some simple way possible.

If I don't know the partial derivatives of my function is it ok to estimate the derivatives by taking the difference of two points close together? Is there a better way?

There is probably a better way. The better techniques for estimating the derivative of a function involve computing estimates at several different points and adding them together so that the errors in the estimates tend to cancel. There are so-called "two point", "three point", etc. methods.

3. On steepest descent, from what I understand, you first find the negative gradient vector and then find the step size in that direction. How do you find the best step size? There seems to be so many different methods for this?

Strictly speaking, I don't know of any way to find "the best" step size. For particular sets of similar problems, you can find step sizes that usually work if the functions doesn't have lots of local minima.

The more things I read about this stuff on my own the more confused and the more questions I seem to have.

That's natural. Few numerical methods work "in general". That's one reason there are so many of them. If the Excel version of the "generalized gradient" method works on your function, we can probably figure out how to code that algorithm. I've not studied that algorithm, but glancing at versions on the web, it looks like the typical ordeal that one must endure to get numerical answers.