Creating function for implementing steepest descent algorithm

Question

I am trying to implement steepest descent algorithm for minimization of 2D function. Let me explain with example.

I have function f1(x1,x2) = 2*x1^2 + x2^2 - 5*x1*x2 and starting with initial guess point p0 = [1,0].

Step 1: Initial guess point p0 = [1,0], convergence parameter e=0.1

Step 2: calculate gradient c1 of f1 at p0. c1=[4,-5] I am using central difference method for that.

Step 3: If norm of c1>e, go to step 4, otherwise stop.

Step 4: Our direction of search is d1 = - c1. So, d1 = [-4,5].

Step 5: Find step size a to minimize f1(a) = f1(p0 + a*d1) = f1(1-4a,5a)

Step 6: Update p0 to p1 as p1 = p0 + a * d1 and to to step 2.

I am trying to implement this example in matlab and do not know how to implement step 5. I know that ant 1D search algorithm, such as bisection method can work. But, problem is to 'converting' f1(1-4a,5a) to a function, that is, substituting (1-4a,5a) into f1. I encounter symbolic constant a here, which I do not know how to deal with. If I write a minimization function, I can pass values to it, but not sure about symbolic variable a. I do not want to use special features of matlab, such as symbolics and trying to keep code at general level, so I can convert it into other programming languages without any problems. Your suggestions are welcome.

Please show us the code you have so far.

Dev-iL
– Dev-iL

2017-03-22 20:39:28 +00:00
Commented Mar 22, 2017 at 20:39 — Dev-iL
– Dev-iL, Commented Mar 22, 2017 at 20:39

user6655984 · Accepted Answer · 2017-03-22 22:16:03Z

0

You probably want to use fminbnd to place some bounds on the line search (-1 to 1 below), since searching the entire line is an ill-defined task. There is no need for a symbolic variable. Step size is determined by minimizing an anonymous function below:

a = fminbnd(@(a) f1(p(1) + a*d(1), p(2) + a*d(2)), -1, 1);

Here p is the current point and d is the direction of search. (I wouldn't want to call them p1 and d1 as in your description, as if they are something used for the 1st step only.)

The example allows negative a, which I find helpful in practice; sometimes it's better to go in the opposite direction from what the gradient suggests. To disallow this, change the bounds to 0, 1 (or 0, 10 for a more aggressive search in the forward direction) .

answered Mar 22, 2017 at 22:16

user6655984

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Creating function for implementing steepest descent algorithm

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related