Instructions 2. Please upload your code as a jupyter notebook on Google Classrooom. Written work, if any, should be scanned as a pdf and then uploaded. You should preferably do your written work in the same jupyter notebook using markdown cells. 3. Please run your code and show the output by printing meaningful output statements. 4. Readability of code is a criterion for grading. So write code with ample comments. Problem 1 (5 points). (Taylor approximation) Consider the univariate function f(x) = x2 + logx Suppose we want to approximate the function values in the vicinity of x = 1 using Taylor polynomials. Lets call the linear approximation function (linear Taylor polynomial) as L(x) and the quadratic approximation function (quadratic Taylor polynomial) as Q(x). (a) Plot f(x), L(x) and Q(x) in the interval [0,2] in the same graph. (b) Let the error associated with the linear approximation be given by eL(x) = f(x)−L(x), and the error associated with the quadratic approximation be given by eQ(x) = f(x)−Q(x). Plot and in the interval [0,2] in the same graph. 1 Problem 2 (6 points). (Combination descent algorithm) Write a code to compute the unconstrained minimum of the following optimization problem by implementing a combination descent algorithm with initial point (1,1).
Problem 3 (9 points). (Combination descent algorithm) Suppose S is a subset of Rn that is defined by a collection of inequalities: S = {x∈Rn : for every j = 1,...,m, gj(x) ≥ 0} Associated with any such set S is the potential function defined as
The analytic center of the set S is the vector that minimizes the associated potential function i.e. the vector x that solves min Ψ(x) x As an example instance, suppose S is a subset of R2 described as above by three linear inequalities given by g1(x1,x2) = 2x2 − x1 g2(x1,x2) = 2x1 − x2 g3(x1,x2) = 1 − x1 − x2 Frame the problem as an unconstrained optimization problem and write a code that uses the combination descent algorithm with initial point (0.25,0.25) to compute the analytic center of S. (Hint: Since log is a monotonically increasing function, minimizing logf(x) is equivalent to minimizing f(x)) 2
