Fluent Essays

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; project_3.pdf Unformatted Attachment Preview Math 160 (Spring Quarter 2020) Homework Project 3 (Nonlinear Optimization Models) Due date: 05/23/2020, 11:59pm INSTRUCTIONS • All homework projects need to be done individually. No teams can be formed. • All homework projects will have many problems, both theoretical and practical. • Submit your homework project to Canvas as one single pdf file. In this project, you don’t need to submit your codes. • Note that since MAT-167 is a prerequisite, concepts/terminology/results related to MAT-167 are presumed. • Knowledge on using MATLAB is presumed. • Write legibly preferably using word processing if your hand-writing is unclear. • Be organized and use the notation appropriately. Show your work on every problem. Correct answers without support work will not receive full credit. 1. Convex Optimization and Nonlinear Optimization (a) Consider the optimization problem min x3 subject to: (x1 − 1)2 + x22 + x23 − 1 ≥ 0, (x1 + 1)2 + x22 + x23 − 1 ≥ 0, x21 + x22 + x23 − 4 ≤ 0 . • Is the feasible region convex? • What is the convex hull of the feasible region? • Solve the above optimization problem over the convex hull. (b) Find the maximum value of the function f (x, y) = x2 + y 4 + xy inside the convex hull of the points (−1, 1), (−1, 2), (−2, 2), (−3, 1). Is the maximum unique? What about the minimum value of f (x, y)? Does this function have a unique global minimum in R2 . (Hint: You may need to solve an equation with cubic term, i.e., find the roots of a 3rd-order polynomial function. There is a formula for this. Please check this webpage for details: https://math.vanderbilt.edu/schectex/ courses/cubic/) (c) Consider the optimization problem min 2x1 arctan(x1 ) − ln(x21 + 1) + x42 + (x3 − 1)2 , subject to the conditions: x21 + x22 + x23 − 4 ≤ 0, x1 ≥ 0. Prove that this problem is a convex optimization problem. Use the Karush -Kuhn-Tucker theorem to find an optimal solution. (d) Give examples of convex optimization problems in two variables x, y that satisfy: • the feasible region is bounded with objective function optimized at a unique point. • the feasible region is unbounded, but the objective function is optimized at more than one point. • The feasible region is unbounded and the objective function value is unbounded. (e) Use the KKT conditions to determine whether (1, 1, 1) can be optimal for the following problem min 2x1 + x32 + x23 subject to: x21 + 2x22 + x23 ≥ 4, x1 ≥ 0, x2 ≥ 0, x3 ≥ 0. (f) Consider the nonlinear optimization problem max x1 x2 + 1 subject to: x1 − x2 ≤ 2, x1 ≥ 0, x2 ≥ 0. • • • • Use the KKT conditions to show that (4,2) is not optimal. Derive a solution that does satisfy the KKT conditions. Show this problem is not convex. Can you solve this problem to optimality? 2. Three Gradient Descent Experiments: Gradient descent algorithms are the most popular methods to solve non-linear optimization problems, specially those arising in artificial intelligence. Here we briefly explore the Gradient Descent method and its variations. For minimization problem: min f (x), x the gradient descent method iterates as: xk+1 := xk − s∇f (xk ), where xk denotes the iterate in the k-th iteration, and s is a step size (also called learning rate in the machine learning literature). For maximization problem max f (x), x you need to use gradient ascent method, which iterates as: xk+1 := xk + s∇f (xk ), (A) Consider the optimization problem max f (x) = 1000x−400x2 +40x3 −x4 , subject to: x2 + x ≤ 500, x ≥ 0. • Identify the feasible values of x. Draw a rough sketch of f (x) over the feasible region. mark in your picture the rough location of local minima/maxima. • Write an implementation of gradient descent to compute local maxima. Which one is a global maximum? Play with the learning rate or step-size  you use in your algorithm. Try  = 0.05 for sure, but try a few more values. Do you notice a difference of convergence (number steps it takes to reach optima)? (B) Download the data set ex3x.dat of housing prices from the same canvas folder. Those data points x(i) indicate the living area and the number of bedrooms information of m = 47 houses. The file ex3y.dat has the prices of houses y (i) . Note the scale of house area and number of bedrooms is quite different. • You learned a long time ago, in linear algebra, how to fit the data by a plane wT x−α = 0 by the least-square method. Use what you learned to compute w = (w1 , w2 ) and α. This is an easy MATLAB computation. • Now we can take also an optimization perspective. Find w and α using the gradient descent algorithm applied to the (least-squares) error function. m 1 X (i) (i) (w1 x1 + w2 x2 − α − y (i) )2 . Er(w1 , w2 , α) = 2m i=1 We wish to minimize the function. Compute the gradient of Er and use it in the gradient descent algorithm to find the vector w and α. Implement this in MATLAB. • Now, in practice you require to first choose a good step size s in the range 0.001 ≤ s ≤ 10. To pick s make an initial selection, run gradient descent and observe the resulting value for Er(w, α). After stepping through many iterations, you will see how Er(w, α) change as the iterations advance. Run gradient descent for 50 iterations at your chosen learning rate. In each iteration, calculate Er(w, α) and store the result. After the last iteration, plot the values against the number of the iteration. Do you see a clear decrease in the error function value per iteration? If not, you screwed up someplace! E.g., if you have no bugs and the function you plot increases or blows up, adjust your learning rate s and try again. • Try several values of s, each 3 times the previous value (i.e., 0.01, 0.03, 0.1, 0.3, 0.9, and so on). When debugging your code, you may also want to adjust the number of iterations you are running if that will help you see the overall trend in the curve of Er (50 iterations maybe too much at the beginning). To compare how different values of s affect convergence. Plot Er for several learning rates on the same graph. Observe the changes in the cost function happens as the learning rate changes. What happens when s is too small? Too large? • Using the best learning rate s that you found, run gradient descent again for 500 iterations or convergence to find the final values of w, α. Use both the least-square w, α and your gradient descent w, α to predict the price of a house with 1650 square feet and 3 bedrooms (Watch out for the scale of data). Are they very different? (C) Stochastic Gradient Descent experiment: Consider a matrix A (20 by 4) and vector b (20 by 1) generated at random. Implement in MATLAB a stochastic gradient descent algorithm that, using batch sizes 1 and 2, solves the minimization of the function ||Ax − b||2 . Compare the ratios rk = ||xk+1 − x∗ ||/||xk − x∗ ||. 3. Playing with Neural Networks The following problems use the examples found in playground.tensorflow.org (cool website!). You are going to train a network without any programming!! But you need to think what is going on. The site offers some data sets shown as pictures with blue and orange colors. When learning succeeds , a white polygon will separate blue points from orange points in the figure. (a) First, construct an architecture with one hidden layer and activation by ReLU. Consider the data example with one blue blob and the orange ring. Does learning succeed for N = 4? If yes, what is is the number of flat pieces of the white polygon? Does learning succeed with N = 3 and 2? If yes how many sides in the white polygon? (b) Data set two (figure) has a blue and orange in two quadrants each. With one layer, do N = 3 and N = 2 neurons succeed on learning this data set? (c) Data set four with blue and orange spirals is harder. With one hidden layer, can the network learn this training data? Describe the result as N , the number of neurons, increases. Try that data set now with two hidden layers. Start with 4 + 4 and 6 + 2, 2 + 6 neurons. Which is the best architecture? (d) How many neurons bring complete separation of the spirals with two hidden layers? Can three layers succeed with fewer neurons than two layers? ... Purchase answer to see full attachment