Arora, Introduction to Optimum Design, 4e 10-1
CHAPTER
10
Numerical Methods for
Unconstrained Optimum Design
Section 10.3 Descent Direction and Convergence of Algorithms
10.1_______________________________________________________________________________
Answer True or False.
2. A vector of design changes must be computed at each iteration of the iterative process. True
4. The search direction requires evaluation of the gradient of the cost function. True
6. Step size along the search direction can be zero. False
8. A descent direction always exists if the current point is not a local minimum. True
10. The descent direction makes an angle of 0–90° with the gradient of the cost function. False
10.2_______________________________________________________________________________
Determine whether the given direction at the point is that of descent for the following function (show
all of the calculations).
22
1 12
() 3 2 2 7f x xx= ++ +x
; d = [−1, 1] at x = [2, 1]
Solution:
1 11 2 2 2
(2,1) 6 2 14; ( 2,1) 4 4c fx x c fx x=∂∂= += =∂∂ = =
[14,4] [ 1,1] 14( 1) 4(1) 10 0;• = •− = − + =− <cd
Thus, d is descent direction.
10.3_______________________________________________________________________________
Determine whether the given direction at the point is that of descent for the following function (show
all of the calculations).
22
12 1 2
() 2 2 4f xx x x=+− − +x
; d = [2, 1] at x = [1, 1]
Solution:
1 11 2 2 2
(1, 1) 2 2 0; (1, 1) 2 2 0c fx x c fx x=∂∂= −= =∂∂ = −=
[0,0] [2,1] 0(2) 0(1) 0;•= • = + =cd
Thus, d is not a descent direction.
10.4_______________________________________________________________________________
Determine whether the given direction at the point is that of descent for the following function (show
all of the calculations).
; d = [−3, 10, −12] at x = [1, 2, 3]
10.5_______________________________________________________________________________
Determine whether the given direction at the point is that of descent for the following function (show
all of the calculations).
22
12
( ) 0.1x 10fx= +−x
; d = [1, 2] at x = [4, 1]
Solution:
12
( ) [0.2 x , 2 ] [0.8, 2]fx=∇= =cx
[0.8, 2] [1, 2] 0.8(1) 2(2) 4.8 0;•= • = + = >cd
Thus, d is not a descent direction.
10.6_______________________________________________________________________________
Determine whether the given direction at the point is that of descent for the following function (show
all of the calculations).
22
12
( ) ( 2) ( 1)fx x=−+−x
; d = [2, 3] at x = [4, 3]
Arora, Introduction to Optimum Design, 4e
10-3
10.7_____________________________________________________________________________
__
Determine whether the given direction at the point is that of descent for the following functions
(show all of the calculations).
22 2
21 1
( ) 10( ) (1 ) ;f xx x= − +−x
d = [162, -40] at x = [2, 2]
Solution:
22
2 1 1 1 21
( ) [20( x )( 2 x ) 2(1 x ), 20(x x )] [162, 40]fx=∇ = − − −− − = −cx
[162, 40] [162, 40] 162(162) 40( 40) 27844 0;•= − • − = − − = >cd
Thus, d is not a descent direction.
10.8_______________________________________________________________________________
Determine whether the given direction at the point is that of descent for the following functions
(show all of the calculations).
22
12
( ) ( 2) ;fx x=−+x
[ 2, 2]= −d
at
[1, 1]=x
Solution:
12
( ) [2(x 2), 2 x ] [ 2, 2]f=∇= − =−cx
[ 2, 2] [ 2, 2] 2( 2) 2(2) 8 0;• = − •− =− − + = >cd
Thus, d is not a descent direction.
10.9_______________________________________________________________________________
Determine whether the given direction at the point is that of descent for the following functions
(show all of the calculations).
22
1 2 12 1 2
( ) 0.5 7 7 ;f x x xx x x= +− − −x
[7, 6]=d
at
[1, 1]=x
Solution:
12 21
( ) [ 7, 2 7] [ 7, 6]f xx x x=∇ = − − − − =−−cx
[ 7, 6] [7, 6] 7(7) 6(6) 85 0;•=−−• =− − =− <cd
Thus, d is a descent direction.
10.10______________________________________________________________________________
Determine whether the given direction at the point is that of descent for the following functions
(show all of the calculations).
22
12 23
( ) ( ) ( );f xx xx=+ ++x
[4, 8, 4]=d
at
[1, 1, 1]=x
Solution:
12 12 23 23
( ) [2( ), 2( ) 2( ), 2(x )] [4,8, 4]f xx xx xx x=∇ = + ++ + + =cx
[4,8, 4] [4,8, 4] 4(4) 8(8) 4(4) 96 0;•= • = + + = >cd
Thus, d is not a descent direction.
Chapter 10 Numerical Methods for Unconstrained Optimum Design
Arora, Introduction to Optimum Design, 4e
10-4
10.11______________________________________________________________________________
Determine whether the given direction at the point is that of descent for the following functions
(show all of the calculations).
222
1 23
() ;f xxx=++x
[2, 4, 2]= −d
at
[1, 2, 1]= −x
Solution:
[2, 4, 2] [2, 4, 2] 2(2) 4(4) 2( 2) 24 0;•= −• − = + − − = >cd
Thus, d is not a descent direction.
10.12______________________________________________________________________________
Determine whether the given direction at the point is that of descent for the following functions
(show all of the calculations).
22
1 23 12
( ) ( 3 ) 4( ) ;f x x x xx=++ + −x
[ 2, 6, 2]=−−−d
at
[ 1, 1, 1]=−−−x
Solution:
1 23 12 1 23 12 1 23
( ) [2( 3 ) 8( ),6( 3 ) 8( ), 2( 3 )] [ 10, 30, 10]f x xx xx x xx xx x xx=∇ = +++ − ++− − ++ =−−−cx
[ 10, 30, 10] [ 2, 6, 2] 10( 2) 30( 6) 10( 2) 220 0•=−−−•−−−=−−− −−−= >cd
Thus, d is not a descent direction.
10.13______________________________________________________________________________
Determine whether the given direction at the point is that of descent for the following functions
(show all of the calculations).
2 22
1 2 3 1 2 3 12 23
() 9 8 6 4 2 2 2 2 ;f xxxxxxxxxx=− − − − + ++ +x
[ 2, 2, 0]= −d
at
[1, 1, 1]=x
Solution:
12 213 32
() [8 4 2 ,6 4 2 2 ,4 2 2 ] [1,2,0]f xx x xx xx=∇ =−− + −+ + + −+ + =−cx
[ 1, 2,0] [ 2, 2, 0] 1( 2) 2(2) 0(0) 6 0;• = − •− =− − + + = >cd
Thus, d is not a descent direction.
10.14______________________________________________________________________________
Determine whether the given direction at the point is that of descent for the following functions
(show all of the calculations).
2222
12 3 4
()( 1)( 2)( 3)( 4);fx x x x=−+−+−+−x
[2, 2, 2, 2]=−−d
at
[2,1, 4,3]=x
Solution:
12 3 4
( ) [2( 1), 2( 2), 2( 3), 2( 4)] [2, 2, 2, 2]f xx x x=∇ = − − − −=− −cx
[2, 2, 2, 2] [2, 2, 2, 2] 2(2) 2( 2) 2(2) 2( 2) 16 0;•= − −• − −= −−+ −−= >cd
Thus, d is not a descent direction.
Chapter 10 Numerical Methods for Unconstrained Optimum Design
Arora, Introduction to Optimum Design, 4e
10-5
Section 10.5 Numerical Methods to Compute Step Size
10.15______________________________________________________________________________
Answer True or False.
1. Step size determination is always a one-dimensional problem. True
2. In unconstrained optimization, the slope of the cost function along the descent direction at zero
3. The optimum step lies outside the interval of uncertainty. False
4. After initial bracketing, the golden section search requires two function evaluations to reduce the
10.16 ______________________________________________________________________________
Find the minimum of the function f(α)=7α2−20α+22 using the equal-interval search method within
an accuracy of 0.001. Use δ=0.05.
Solution:
The problem is solved using the example program shown below, which was written in C++. This
code can be copied and pasted into a compiler such as Code::Blocks. Or, this code can be modified into
your language of choice.
____________________________________________________________________________________
#include <iostream>
#include <math.h>
using namespace std;
int main()
{
float delta = 0.05; //modify this value for the required delta
float epsilon = 0.001; //modify this value for the required accuracy
int nCount = 0; //tracks number of function evaluations
float f = 0; //holds the value of the function at the minimum
float alpha = 0; //holds the value of alpha at the minimum
}
/* this function implements equal interval search
Chapter 10 Numerical Methods for Unconstrained Optimum Design
a = optimal value of alpha on return
d = initial step length
e = convergence parameter
f = optimum value of the function on return
n = number of function evaluations on return
**/
void equalInterval(float *a, float d, float e, float *f, int *n)
{
int q = 2; //delta multiplier
do
{
fu = funct(au, n);
if( fa >= fu )
{
al = (q–2)*d;
//refine the interval of uncertainty further
while((au–al) > e)
do
{
fu = funct(au, n);
if(fa >= fu)
{
q = q+1;
aa = au;
Chapter 10 Numerical Methods for Unconstrained Optimum Design
Arora, Introduction to Optimum Design, 4e
10-7
*f = funct(*a, n); //send minimum function value to pointer address
}
/* calculates the function value
**/
float funct(float a, int *nC)
{
____________________________________________________________________________________
Chapter 10 Numerical Methods for Unconstrained Optimum Design
Arora, Introduction to Optimum Design, 4e
10-8
10.17______________________________________________________________________________
For the function f(α)=7α2−20α+22, use the golden section method to find the minimum with an
accuracy of 0.005 (final interval of uncertainty should be less than 0.005). Use δ=0.05.
Solution:
The problem is solved using the example program shown below, which was written in C++. This
code can be copied and pasted into a compiler such as Code::Blocks. Or, this code can be modified into
your language of choice.
____________________________________________________________________________________
#include <iostream>
#include <math.h>
//to perform equal interval line search call function equalInterval
goldenInterval(alphaptr, delta, epsilon, fptr, nptr);
/* this function implements golden interval search
a = optimal value of alpha on return
d = initial step length
**/
void goldenInterval(float *a, float d, float e, float *f, int *n)
{
int q = 1; //delta multiplier
Chapter 10 Numerical Methods for Unconstrained Optimum Design
Chapter 10 Numerical Methods for Unconstrained Optimum Design
break;
default:
break;
}
}
*a = (au+al)/(float)2; //send minimum alpha value to pointer address
**/
float funct(float a, int *nC)
{
float fVal = 0;
Arora, Introduction to Optimum Design, 4e
10-11
10.18 ______________________________________________________________________________
Write a computer program to implement the alternate equal-interval search process shown in
Figure 10.7 for any given function f(α). For the function f(α)=2−4α+eα, use your program to find the
minimum within an accuracy of 0.001. Use δ=0.50.
Solution:
The problem is solved using the example program shown below, which was written in C++. This
code can be copied and pasted into a compiler such as Code::Blocks. Or, this code can be modified into
your language of choice.
____________________________________________________________________________________
#include <iostream>
#include <math.h>
using namespace std;
//to perform equal interval line search call function equalInterval
altEqualInterval(alphaptr, delta, epsilon, fptr, nptr);
return 0;
}
/* this function implements the alternate equal interval search
a = optimal value of alpha on return
Chapter 10 Numerical Methods for Unconstrained Optimum Design
float ab = 0; //holds value of mid–point alpha b
float au = q*d; //holds value of upper bound of alpha, initially set to 2*delta
float fa = 0; //holds function value of mid–point alpha
au = q*d;
fa = funct(aa, n);
fu = funct(au, n);
}
aa = al+((au–al)/(float)3);
ab = al+(2*((au–al)/(float)3));
switch(caseInPoint)
{
case 1:
au = ab;
case 2:
al = aa;
case 3:
al = aa;
Chapter 10 Numerical Methods for Unconstrained Optimum Design
Arora, Introduction to Optimum Design, 4e
10-13
break;
}
}
*a = (au+al)/(float)2; //send minimum alpha value to pointer address
*f = funct(*a, n); //send minimum function value to pointer address
}
Chapter 10 Numerical Methods for Unconstrained Optimum Design
10.19 ______________________________________________________________________________
Consider the function
222
1 2 3 1 2 3 12 23
(,,x) 222 2.fxx xxxxxxx=+++ +
Verify whether the vector
[ 12, 40, 48]=−−−d
at the point
[2, 4,10]=x
is a descent direction for f. What is the slope of the function
at the given point? Find an optimum step size along d by any numerical method.
Solution:
1221332
( ) [2 2 ,4 2 2 ,4 2 ] [12,40,48]f xxx xxxx=∇ = + ++ + =cx
10.20 ______________________________________________________________________________
Consider the function
22
12 1 2
( ) 2 2 4.f xx x x=+− − +x
At the point
[1, 1],=x
let a search direction be
defined as
[1, 2].=d
Express f as a function of one variable at the given point along d. Find an optimum
step size along d analytically.
Solution:
10.21 ______________________________________________________________________________
For the following function, direction of change at a point is given. Derive the function of one
variable (line search function) that can be used to determine optimum step size (show all calculations).
22
12
( ) 0.1 10;f xx= +−x
[ 1, 2]=−−d
at
[5,1]=x
Solution:
22
10.22 ______________________________________________________________________________
For the following function, direction of change at a point is given. Derive the function of one
variable (line search function) that can be used to determine optimum step size (show all calculations).
22
12
( ) ( 2) ( 1) ;fx x=−+−x
[ 4, 6]=−−d
at
[4, 4]=x
Solution:
22
Arora, Introduction to Optimum Design, 4e
10-15
10.23 ______________________________________________________________________________
For the following function, direction of change at a point is given. Derive the function of one
variable (line search function) that can be used to determine optimum step size (show all calculations).
22 2
21 1
( ) 10( ) (1 ) ;f xx x= − +−x
[ 162, 40]= −d
at
[2, 2]=x
Solution:
22 2
10.24 ______________________________________________________________________________
For the following function, direction of change at a point is given. Derive the function of one
variable (line search function) that can be used to determine optimum step size (show all calculations).
22
12
( ) ( 2) ;fx x=−+x
[2, 2]= −d
at
[1, 1]=x
Solution:
12
[x , ] [1,1] [ 2, 2] [1 2 , 1 2 ;x
α αα
= + −=+ −
22
12
( ) ( 2)fx x=−+x
22
( ) (1 2 2) (1 2 ) ;f
αα α
=+ − +−
2
() 8 8 2f
ααα
= −+
10.25 ______________________________________________________________________________
For the following function, direction of change at a point is given. Derive the function of one
variable (line search function) that can be used to determine optimum step size (show all calculations).
22
1 2 12 1 2
( ) 0.5 7 7 ;f x x xx x x= +− − −x
[7, 6]=d
at
[1, 1]=x
Solution:
22
10.26 ______________________________________________________________________________
For the following function, direction of change at a point is given. Derive the function of one
variable (line search function) that can be used to determine optimum step size (show all calculations).
22
12 23
( ) ( ) ( );f xx x x=+ ++x
[4,8,4]=−−−d
at
[1, 1, 1]=x
Solution:
22
Chapter 10 Numerical Methods for Unconstrained Optimum Design
10.27 ______________________________________________________________________________
For the following function, direction of change at a point is given. Derive the function of one
variable (line search function) that can be used to determine optimum step size (show all calculations).
222
1 23
() ;f xxx=++x
[ 2, 4, 2]=−−d
at
[1, 2, 1]= −x
10.28 ______________________________________________________________________________
For the following function, direction of change at a point is given. Derive the function of one
variable (line search function) that can be used to determine optimum step size (show all calculations).
22
1 23 12
( ) ( 3 ) 4( ) ;f x x x xx=++ + −x
[1, 3,1]=d
at
[ 1, 1, 1]=−−−x
Solution:
22
10.29 ______________________________________________________________________________
For the following function, direction of change at a point is given. Derive the function of one
variable (line search function) that can be used to determine optimum step size (show all calculations).
2 22
1 2 3 1 2 3 12 23
() 9 8 6 4 2 2 2 2 ;f xxxxxxxxxx=−−−++++ +x
[2, 2, 0]= −d
at
[1, 1, 1]=x
10.30 ______________________________________________________________________________
For the following function, direction of change at a point is given. Derive the function of one
variable (line search function) that can be used to determine optimum step size (show all calculations).
2222
12 3 4
()( 1)( 2)( 3)( 4);fx x x x=−+−+−+−x
[ 2, 2, 2, 2]=−−d
at
[2,1, 4,3]=x
Solution:
Problems 10.31 to 10.40 are solved using a modified form of the program in Section B.2 of
Appendix B.
10.31 ____________________________________________________________________________
For the following function, calculate the initial interval of uncertainty for the equal-interval search
with δ=0.05 at the given point and in the given search direction.
22
12
( ) 0.1 10;f xx= +−x
[ 1, 2]=−−d
at
[5,1]=x
Solution:
2
____________________________________________________________________________________
#include <iostream>
#include <math.h>
using namespace std;
void equalInterval(float *a, float *aui, float *ali, float d, float e, float *f,
int *n);
float *aliptr = &ali; //pointer to ali
float *auiptr = &aui; //pointer to aui
float *fptr = &f; //pointer to f
int *nptr = &nCount; //point to nCount
//to perform equal interval line search call function equalInterval
Chapter 10 Numerical Methods for Unconstrained Optimum Design
cout <<“No. of function evaluations = “<<nCount<<“\n”; //outputs the
number of function evaluations
return 0;
}
float fa = 0; //holds function value of mid–point alpha
float aa = d; //holds value of mid–point alpha, initially set to
delta
float fu = 0; //holds function value of upper alpha bound
float au = q*d; //holds value of upper bound of alpha, initially set to
}
al = (q–2)*d;
*aui = au;
*ali = al;
//refine the interval of uncertainty further
// while((au–al) > e)
Chapter 10 Numerical Methods for Unconstrained Optimum Design
// au = al+(q*d);
// fu = funct(au, n);
// }
**/
float funct(float a, int *nC)
{
float fVal = 0;
*nC = *nC + 1; //send function evaluation count to pointer address
Arora, Introduction to Optimum Design, 4e
10-20
10.32 ______________________________________________________________________________
For the following function, calculate the initial interval of uncertainty for the equal-interval search
with δ=0.05 at the given point and in the given search direction.
22
12
( ) ( 2) ( 1) ;fx x=−+−x
[ 4, 6]=−−d
at
[4, 4]=x
Solution:
2
( ) 52 52 13f
ααα
= −+
(from the solution to Problem 10.22)
10.33 ______________________________________________________________________________
For the following function, calculate the initial interval of uncertainty for the equal-interval search
with δ=0.05 at the given point and in the given search direction.
22 2
21 1
( ) 10( ) (1 ) ;f xx x= − +−x
[ 162, 40]= −d
at
[2, 2]=x
Solution:
4 32
( ) 6887475360 361117440 5809444 27844 41f
α α α αα
= − + −+
(from the solution to Problem
10.34 ______________________________________________________________________________
For the following function, calculate the initial interval of uncertainty for the equal-interval search
with δ=0.05 at the given point and in the given search direction.
22
12
( ) ( 2) ;fx x=−+x
[2, 2]= −d
at
[1, 1]=x
Solution:
2