ECE257ECE257 NumericalNumerical Methods Methods andandScientificScientific ComputingComputingOptimization MethodsOptimization MethodsECE 257 Numerical Methods and Scientific ComputingFall 2004Lecture 11John A. ChandyDept. of Electrical and Computer EngineeringUniversity of ConnecticutTodayToday’’s class:s class:••OptimizationOptimization••One-dimensional unconstrainedOne-dimensional unconstrainedECE 257 Numerical Methods and Scientific ComputingFall 2004Lecture 11John A. ChandyDept. of Electrical and Computer EngineeringUniversity of ConnecticutOptimizationOptimization••Given a function Given a function f(xf(x11, x, x22, x, x33, , ……, x, xnn)) find the find theset of values that minimize or maximizeset of values that minimize or maximizethe functionthe function••Examples:Examples:––Lowering power usage in a circuit whileLowering power usage in a circuit whilemaximizing speedmaximizing speed––Least-cost management of supply chainLeast-cost management of supply chainECE 257 Numerical Methods and Scientific ComputingFall 2004Lecture 11John A. ChandyDept. of Electrical and Computer EngineeringUniversity of ConnecticutOptimizationOptimization••From calculus, optimization means setting theFrom calculus, optimization means setting thederivative derivative ff’’(x(x11, x, x22, x, x33, , ……, x, xnn)) to zero and finding to zero and findingsolutions to that equation.solutions to that equation.••If If ff’’’’(x(x11, x, x22, x, x33, , ……, x, xnn) > 0) > 0, it is a minimum and if, it is a minimum and ifff’’’’ (x (x11, x, x22, x, x33, , ……, x, xnn) < 0) < 0, it is a maximum., it is a maximum.••To find where the derivative is zero, we can useTo find where the derivative is zero, we can usethe root-finding techniques we discussed beforethe root-finding techniques we discussed beforeECE 257 Numerical Methods and Scientific ComputingFall 2004Lecture 11John A. ChandyDept. of Electrical and Computer EngineeringUniversity of ConnecticutOptimizationOptimizationFrom Numerical Methods for Engineers, Chapra and Canale, Copyright © The McGraw-Hill Companies, Inc.ECE 257 Numerical Methods and Scientific ComputingFall 2004Lecture 11John A. ChandyDept. of Electrical and Computer EngineeringUniversity of ConnecticutOptimizationOptimization••In VLSI circuits, you typically use cascadedIn VLSI circuits, you typically use cascadedinverters to reduce transistor sizes when drivinginverters to reduce transistor sizes when drivinglarge capacitanceslarge capacitances€ CL€ R€ Ra€ Ra2€ Ra3€ Ran−1€ aC€ a2C€ a3C€ an−1C€ td= n −1( )aRC +Ran−1CLTake the derivative and get€ an=CLC€ dtdda= n −1( )RC − n −1( )RanCL= n −1( )1−CLCa−n      Set the derivative to 0 and getECE 257 Numerical Methods and Scientific ComputingFall 2004Lecture 11John A. ChandyDept. of Electrical and Computer EngineeringUniversity of ConnecticutTransistor SizingTransistor Sizing€ an=CLCn = logaCLC      ••Minimum delay is reached when Minimum delay is reached when aa is equal to is equal to e(~2.72)e(~2.72)••At optimum,At optimum,€ n = lnCLC      € td= n −1( )aRC +Ran−1CL= n −1( )aRC +RanaCL= n −1( )aRC + aRC= naRC€ td= logaCLC      aRC€ ⇒dtdda= RC lnCLC      ln a −1ln a( )2        € ⇒ a = eECE 257 Numerical Methods and Scientific ComputingFall 2004Lecture 11John A. ChandyDept. of Electrical and Computer EngineeringUniversity of ConnecticutOptimizationOptimization••Finding the roots of the derivative requiresFinding the roots of the derivative requiresknowing what the derivative isknowing what the derivative is••Often, the function is not well-defined and youOften, the function is not well-defined and youcan not analytically derive the derivativecan not analytically derive the derivative••Requires finite-difference approximation of theRequires finite-difference approximation of thederivativederivativeECE 257 Numerical Methods and Scientific ComputingFall 2004Lecture 11John A. ChandyDept. of Electrical and Computer EngineeringUniversity of ConnecticutOptimizationOptimization••General optimization problem:General optimization problem: € Find x, which minimizes or maximizes f x( ) subject todix( )≤ ai i = 1,2,K,meix( )= bi i = 1,2,K,mwhere x is a n - dimensional design vector, f x( ) is theobjective function, dix( ) are inequality constraints andeix( ) are equality constraints.ECE 257 Numerical Methods and Scientific ComputingFall 2004Lecture 11John A. ChandyDept. of Electrical and Computer EngineeringUniversity of ConnecticutOptimizationOptimization••Constrained optimizationConstrained optimization––Degrees of freedomDegrees of freedom••n-p-mn-p-m––Under-constrainedUnder-constrained••p+mp+m≤≤nn••Solution possibleSolution possible––Over-constrainedOver-constrained••p+m>np+m>n••Solution unlikelySolution unlikelyECE 257 Numerical Methods and Scientific ComputingFall 2004Lecture 11John A. ChandyDept. of Electrical and Computer EngineeringUniversity of ConnecticutOptimizationOptimization••Linear ProgrammingLinear Programming––Objective function and the constraints are all linearObjective function and the constraints are all linear••Quadratic ProgrammingQuadratic Programming––Objective function is quadratic and the constraintsObjective function is quadratic and the constraintsare linearare linear••Nonlinear ProgrammingNonlinear Programming––Objective function is not linear or quadratic and/or theObjective function is not linear or quadratic and/or theconstraints are nonlinearconstraints are nonlinearECE 257 Numerical Methods and Scientific ComputingFall 2004Lecture 11John A. ChandyDept. of Electrical and Computer EngineeringUniversity of ConnecticutOptimizationOptimization••DimensionalityDimensionality––One-dimensionalOne-dimensional••Single function variableSingle function variable––Multi-dimensionalMulti-dimensional••Function is dependent on more than oneFunction is dependent on more than onevariablevariableECE 257 Numerical Methods and Scientific ComputingFall 2004Lecture 11John A. ChandyDept. of Electrical and Computer EngineeringUniversity of ConnecticutOptimizationOptimization••How do you know that the minimum or maximumHow do you know that the minimum or maximumthat you