Practical Optimization With MATLAB

Practical Optimizationwith MATLAB

Practical Optimizationwith MATLABByMircea Ancău

Practical Optimization with MATLABBy Mircea AncăuThis book first published 2019Cambridge Scholars PublishingLady Stephenson Library, Newcastle upon Tyne, NE6 2PA, UKBritish Library Cataloguing in Publication DataA catalogue record for this book is available from the British LibraryCopyright 2019 by Mircea AncăuAll rights for this book reserved. No part of this book may be reproduced,stored in a retrieval system, or transmitted, in any form or by any means,electronic, mechanical, photocopying, recording or otherwise, withoutthe prior permission of the copyright owner.ISBN (10): 1-5275-3849-4ISBN (13): 978-1-5275-3849-8

CONTENTSPreface . ix1. Brief Introduction to MATLAB Programming . 11.1 Introduction . 11.2 Format to display . 11.3 Scalar variables . 11.4 Matrices and operations . 21.5 Input and output operations. 61.6 Programming guidelines . 81.6.1 The for statement . 81.6.2 The while statement. 101.6.3 The if-elseif-else statement . 111.6.4 The break statement . 121.6.5 The switch-case-otherwise statement . 121.6.6 The continue statement. 141.6.7 The return statement . 151.7 Scripts and functions . 151.8 Graphic representations . 181.9 Conclusions . 272. Basic Concepts . 292.1 Introduction . 292.2 The concept of optimization . 292.3 The general mathematical model . 362.4 The iterative computation . 372.5 The existence and uniqueness of the optimal solution . 392.5.1 The existence and uniqueness of the optimalsolution in the absence of constraints . 402.5.2 The existence and uniqueness of the optimalsolution in the presence of constraints . 432.6 Conclusions . 46

viContents3. Optimization Techniques for One Variable UnconstrainedFunctions . 473.1 Introduction . 473.2 Finding the boundaries of the interval containing the optimalsolution . 473.3 The grid method . 503.4 The golden section method . 543.5 The Fibonacci method. 583.6 Quadratic approximation . 633.7 Cubic approximation . 663.8 The minimum of a single variable constrained function . 703.9 Conclusions . 774. Optimization Techniques for N Variables UnconstrainedFunctions . 794.1 Introduction . 794.2 The random search method . 804.3 The random path method . 834.4 The relaxation method . 874.5 The gradient method . 914.6 The conjugate gradient method . 954.7 About convergence criteria . 994.7.1 The absolute difference of the objective function values . 994.7.2 The relative difference of the objective function values. 1004.7.3 The gradient equal to zero . 1014.7.4 The maximum number of iterations . 1014.8 Conclusions . 1015. Optimization Techniques for N Variables ConstrainedFunctions . 1035.1 Introduction . 1035.2 The random search method with constraints . 1035.3 The exterior penalty function method . 1085.4 The interior penalty function method . 1185.5 Conclusions . 126

Practical Optimization with MATLABvii6. Global Optimization . 1276.1 Introduction . 1276.2 The Monte Carlo method . 1286.3 Global optimization algorithm . 1316.4 Conclusions . 1407. Multicriteria Optimization . 1417.1 Introduction . 1417.2 Some mathematical foundations of multi-criteria optimization . 1417.3 The method of global criterion. 1437.4 The Pareto-optimal set . 1527.5 Conclusions . 1558. Traveling Salesman Problem . 1578.1 Introduction . 1578.2 Conventional methods to solve TSP . 1598.2.1 Sorting horizontally . 1598.2.2 Sorting vertically . 1638.3 Nearest Neighbor . 1668.4 Determining the intersection of two segments . 1718.5 Removing segments intersection . 1728.6 Design of an insertion-type method . 1798.7 Conclusions . 1899. Optimal Nesting . 1919.1 Introduction . 1919.2 The Minkowski sum . 1939.3 The Minkowski sum for convex polygons . 1949.4 The Minkowski sum for concave polygons . 2029.5 Optimal orientation of a polygon . 2109.6 Nesting 2D design . 2209.7 Conclusions . 23610. Flowshop Scheduling Problem . 23710.1 Introduction . 23710.2 Total inactivity time calculation . 24010.3 The algorithm of Johnson . 24610.4 Constructive heuristic algorithm . 25210.5 Improvement heuristic algorithm . 25910.6 Conclusions . 264

viiiContentsBibliography. 265List of Source Codes . 275

PREFACEThis book is a brief introduction to the theory and practice of thenumerical optimization techniques. It addresses all those interested indetermining extreme values of functions. Because the book does not delveinto mathematical demonstrations, it is accessible even to users without atheoretical background of optimization theory or detailed knowledge ofcomputer programming. The concepts are presented in a simple way,starting with optimization methods for single variable functions withoutconstraints and finishing with optimization methods for multivariablefunctions with constraints. Each of the methods presented is accompaniedby its source code written in Matlab. The programs in the book are writtenas simply as possible. To make things even easier to follow, the firstchapter of the book makes a brief overview of all the commands andprogramming instructions used in the source codes. Explanationsaccompanying each of the source codes within the book allow for theadaptation of programs to users' needs either by changing functions andrestrictions expressions, or by including these programs only as simplefunctions in other, larger applications.There is no method able to solve any type of optimization problem.Matlab possesses the Optimization toolbox, capable of solving a multitudeof problems. Before grasping Matlab functions, you need to have enoughknowledge to allow you to choose the right optimization methods for yourproblems. This book can help you take this first step. In addition to othersimilar works, this book also initiates in multicriteria optimization andcombinatorial optimization problems. Because several of the source codesare derived from other source codes explained in the previous chapters, itis advisable for the scholarly reader to study each chapter of the book.However, it is also possible to use the source codes without reading theprevious chapters, by providing the appropriate functions in the foldercontaining the program source code.The book is structured in ten chapters. The first chapter addressesbeginner programmers and reviews the basic Matlab programmingknowledge. Fundamental concepts of reading and saving data in a specificformat are explained. At the same time, with simple examples, the mainprogramming syntax is explained, which is, anyway, similar to thatencountered in other programming languages. Also presented are ways to

xPrefaceplot the functions, their specific implementation detailed in the followingchapters.The second chapter is called Basic concepts and its role is tofamiliarize the reader with some optimization concepts such as objectivefunction, decision variables, explicit or implicit constraints, optimizationproblems without or with constraints. The conditions of existence anduniqueness of the optimization solution, in the absence or presence ofrestrictions, are explained. The general mathematical model of anoptimization problem is defined. Despite its lack of importance at firstglance, the role of this chapter is to familiarize the reader with certainrules, starting with the way in which an optimization problem isformulated, the conditions in which the problem can be solved, and howthe solution can be presented graphically.In the third chapter, entitled Optimization techniques for one variableunconstrained functions, some optimization methods for functions that aredependent on a single variable without constraints are presented. Althoughthe mathematical model of the optimization problem to be solved does notimply any constraint, the search must be limited to a specific domain.Most often, the interval containing the solution of the problem is notknown. This is why, for the beginning, a simple method to find the limitsof the interval that includes the solution to the problem is presented. Thechapter continues with the grid optimization methods, the golden sectionmethod, the Fibonacci method, the quadratic approximation and the cubicapproximation methods. At the end of the chapter, a method to solve theoptimization problem that contains constraints is presented, based on anunconstrained optimization method, only by appropriately modifying theobjective function. Each method explains the applied technique for stepby-step reduction of the length of the domain containing the optimalsolution to a length less than or equal to an initially imposed precisionfactor. Each method is tested on the same optimization problem, so thatthe reader can compare the performance of each method. At first sight,solving an optimization problem whose objective function depends on asingle variable, without constraints, may seem to have less practicalapplicability. However, the importance of these methods is significant. Aswill be seen in the following chapters, these optimization methods are thefoundation of the most sophisticated optimization methods.The fourth chapter, titled Optimization techniques for n variablesunconstrained functions, takes a step further than the previous chapter.The optimization methods in this chapter are able to solve anyoptimization problems without restrictions, but optimization functionsdepend this time on n decision variables. From the multitude of