3 Implementing a simple Barrier Method for QP problems Algorithm 1: Simple Barrier Method. In the following problem you will implement a barrier method to solve the following problem: Result: r* certificate with duality gap 0 (preferably small e do s.t. Ar Sb 1. Computer; by solving the unconstrained problem on which r E R" and A E Rman. This amounts to finding the point in the polyhedron {r : Ar S b} of minimum norm min fo(z) + (-f.(z) ). As usual, we recommend to use scripting languages such as Python, Julia or Matlab. using gradient descent with a backtracking line search, starting at point r; 2. Update r via z +- r;; Background 3. Decrease t via t + uit. Barrier methods are interior point methods used to deal with inequality constraints, Consider the We have provided matrix A and vector b in bCourses, in a file named small LP . zip. The following convex program dimension of the problem is m = 10 constraints, and n = 15 variables. min fo(x) A few tips for your implementation: s.t. fi(x) 50, 1= 1, .. ..m . The vector r(0) = [-2,0,0, .. 0) is a strictly feasible starting point for the given problem. . You can use ((0) = 10. p = 0.5, and parameters a = 3 = 0.25 for your backtracking line As we saw in class, one way of approximationg the inequality constraints is including them as a search. There is nothing special about this choice of parameters, and you are free to tune penalization terms in the objective function with the help of a barrier function o, leading to the them and see how things change. following unconstrained problem for t > 0: . When solving the unconstrained problem in Step 1 to find a;. you can terminate your gradi- min fo(x) + (-f.(x)) ent descent algorithm when the gradient at the current iterate is sufficiently small (e.g. less than 10 " in squared norm). For this problem, we'll use the log-barrier function (a) (12 points) Implement Algorithm I to find an approximate solution to problem (2) (use E = 10-6). Attach your code. (Hint: when you do your backtracking line search, you'll need (2) = log(1/2) z>0 to check for both feasibility of the step, and the desired decrease in the objective.) 1+ 00 250 (b) (2 points) For the given A, b. the system of equations Ar = b is underdetermined and admits a solution. So. y = Alb is the solution of minimum norm. How does the norm of y compare If r; is a solution for this problem, then we've seen by weak duality that the suboptimality for the to the norm of the solution you found in the previous part? (Write the norm of y and the original problem is controlled by norm of your solution from the previous part.) fo(z; )

0, (c) (6 points) Using your optimization package of your choice (e.g. linprog. cvx. Pyomo. JuMP). compute the optimal objective value of the problem. Present your code used to compute it, where p* is the value of our original optimization problem. Hence. as t | 0, our point r; will be and compare against the value you find in the first part. nearly optimal for our original problem. Algorithm I presents the barrier method that you have to implement in your language of preference