Consider the resource allocation problem described in example 10.1. You can assume the fi are strongly convex, i.e., fi′′(z)≥m>0 for all z.
((a)) Find the computational effort required to compute a Newton step for the reduced problem. Be sure to exploit the special structure of the Newton equations.
((b)) Explain how to solve the problem via the dual. You can assume that the conjugate functions fi∗, and their derivatives, are readily computable, and that the equation fi′(x)=ν is readily solved for x, given ν. What is the computational complexity of finding a Newton step for the dual problem?
((c)) What is the computational complexity of computing a Newton step for the resource allocation problem? Be sure to exploit the special structure of the KKT equations.