An Introduction to Unconstrained Optimisation

J. McKeown, D. Meegan, D. Sprevak, J McKeown, D Meegan, D Sprevak

• Publisher: CRC Press
• Year: 2022
• eBook ISBN: 9781351466813
• Topic: Mathematics
• Subtopic: Applied Mathematics
• Index: Mathematics

Integrating computer graphics and computer-based exercises with the text, An Introduction to Unconstrained Optimisation illustrates key methods with many examples and exercises using the computer. The book takes an elementary approach to this advanced topic, allowing readers to concentrate on learning and understanding the concepts of numerical optimization without unnecessary involvement in the intricacies of the subject. In addition, the modular approach of the software provides the opportunity to explore the algorithms used and to develop them further or try alternative approaches. Most of the algorithms are based upon a "hill-climbing" concept which, in two dimensions, is illustrated dynamically on the computer screen in the form of contour plots and search directions. The text is not specific to any particular microcomputer. Software is available for the BBC series of machines (40/80 track disc formats) and PC-compatible machines. The software is not available from your local bookstore, but is easily obtainable using the order form in the book. Keeping proofs and lists of methods to a minimum, the book is at a level suitable for a first course in numerical analysis, with a basic knowledge of calculus and vector algebra assumed. This book/software package will be of interest to professionals, teachers, and undergraduate students in mathematics, operational research, science, and engineering as well as economics and management courses that deal with quantitative methods.

> Chapter 1

> Getting Started

> 1.1 Installing the software

The software associated with this book is supplied on a floppy disc. This disc is write protected and should be used to make a working copy which must not be write protected and will be used to run the programs. The original copy should then be kept in a safe place.

The information required to make a working copy on your system is contained in a README file on the original disc. View this file and proceed as directed.

> 1.2 Starting the software

To start the package, insert the working copy into the disc drive and activate the menu program following the procedure given in the README file.

> 1.3 Activating programs

The first program in the menu is used to prepare functions and make them available to other programs. It is therefore an appropriate choice to illustrate the use of the package.

Select PREPARE by placing the selection bar on the first item in the menu and pressing the RETURN key. The screen will clear briefly while PREPARE is being loaded from disc. On completion of this process, a new menu, we will call it the main menu, will be displayed on the first line of the screen. The second line will display a message to indicate that a function has not been prepared.

The first line is always used to request information while the second line is always used to display information or results.

The rectangle in the bottom left quadrant of the screen is used to display contour plots; this facility will be discussed in Chapter 2.

As a function has yet to be prepared, the only valid options at this stage are E(dit, L(oad, and Q(uit. The Q(uit option is used to return to the Menu program, L(oad to load a function from a disc, and E(dit is used to manipulate a function. When a function is available, it can be saved to a disc file with the S(ave option or displayed as a contour plot with the D(isplay option.

Start with the E(dit option. An option is selected by typing the letter that appears before the bracket, so press the E key to select edit. A new menu appears. This menu contains more options than will fit on the 40 column line and you can view the other options by pressing the LEFT ARROW key or the RIGHT ARROW key to scroll through the menu. E(dit is used to prepare a function. The preparation of a function may consist of defining the function and its derivatives, and setting limits on the dependant variables. However, defaults have already been set for the limits and we do not need to define the derivatives at this stage.

In general, to enter a function the F(X1,X2) option is used.

However a different procedure for entering the function is required when the function is formed by sum of squares and the least squares method of Chapter 5 is to be used.

We discuss first the F(X1,X2) option. Let us enter the function:

$F(x_1,x_2)=-x_2^2+x_1^2+2x_1+x_2+({x_1-x_2^2)}^2$

by activating the F(X1,X2) option; the request line changes to:

$F(X1,X2)=$

which is an invitation for you to enter the function. The function is entered using the conventions of BBC Basic and, while you do not need to be familiar with it to use the package, you must know how to enter an expression in BBC Basic.¹ If you do not have this information you should consult the relevent Acorn documentation. Enter the function by typing:

$-(\text{X}{2}^{^}2)+\text{X}{1}^{^}2+2*\text{X}1+\text{X}2+{(\text{X}1-\text{X}{2}^{^}2)}^{^}2$

Use the DELETE key to correct mistakes and the RETURN key to enter the function. If typing mistakes are found later, they can be easily corrected by selecting the F(X1,X2) option again. In addition to the prompt

$F(X1,X2)=$

being shown on the request line, the current setting is displayed on the information line.

The arrow keys can be used to move an edit cursor to any location on the information line and the COPY key may be used to copy information to the prompt line.

Having entered the function, you should return to the main menu by pressing the RETURN key at the menu prompt. A grid of dots will be displayed while the program scans the function over the limits set for x₁ and x₂. On completion of this process, it will have obtained a rough estimate for the range of function values covered by the region and will display this information as a table.

The option S(quared function is used to enter a function formed by a sum of squares. When activating this option you will be asked for the number of squared terms in the function. The screen also shows the default value for the option and the range of its allowed values. To input the function select now the option F(X1,X2) and enter the different squared terms in order.

From the main menu you can now select the D(isplay option to have the surface displayed as a contour plot. While the plot is being generated, the information line will show that the function is being calculated and stored in a disc file. Once it is stored on the disc, the contour plot can be displayed more quickly.

The number of contour bands which are displayed is fixed; so to show details of a surface in a region with a large range of contour values it may be necessary to make a plot with a reduced range of contour values. The option H(igh F in the Edit menu can be used to specify the highest value of the contour to be displayed. When H(igh F is activated the program calculates the function over a crude grid of points, after which it displays the average height of the contours and their range of values over the grid. The user can enter any value within the shown range, or simply by pressing the RETURN key select the average calculated height on the grid. If the option H(igh F is not activated the program uses the whole range of calculated values.

1  A peculiarity of BBC Basic is that the unary minus operator has a higher priority than the exponentiation operator (^). So the expression −2 ^ 2+2 gives the result 6.If the exponentiation is to be performed first, the expression must be entered as either −(2^ 2)+2 or 2−2 ^ 2, both of which give the expected value of −2.

> Chapter 2

> Searching for an optimum

> 2.1 Introduction

Optimisation deals with the study of methods for solving problems of the type:

Fin...

Table of contents

• Cover
• Half Title
• Series Page
• Title Page
• Copyright Page
• Table of Contents
• Preface
• 1 Getting started
• 2 Searching for an optimum
• 3 Line searches
• 4 Direct search methods
• 5 Gradient methods I
• 6 Gradient methods II
• 7 Optimisation in practice
• Bibliography
• Index