Convex Optimization · Problem 9.23

Equality constrained minimization — Boyd & Vandenberghe

Mathematics — Optimization · precomputation-line-searches

Problem

Pre-computation for line searches. For each of the following functions, explain how the computational cost of a line search can be reduced by a pre-computation. Give the cost of the pre-computation, and the cost of evaluating g(t)=f(x+tΔx)g(t) = f(x + t\Delta x) and g′(t)g'(t) with and without the pre-computation. ((a)) f(x)=−∑i=1mlog⁡(bi−aiTx)f(x) = -\sum_{i=1}^m \log(b_i - a_i^T x). ((b)) f(x)=log⁡(∑i=1mexp⁡(aiTx+bi))f(x) = \log\left(\sum_{i=1}^m \exp(a_i^T x + b_i)\right). ((c)) f(x)=(Ax−b)T(P0+x1P1+⋯+xnPn)−1(Ax−b)f(x) = (Ax-b)^T(P_0 + x_1 P_1 + \cdots + x_n P_n)^{-1}(Ax-b), where Pi∈SmP_i \in \mathbf{S}^m, A∈Rm×nA \in \mathbf{R}^{m \times n}, b∈Rmb \in \mathbf{R}^m and dom f={x∣P0+∑i=1nxiPi≻0}\mathbf{dom}\, f = \{x \mid P_0 + \sum_{i=1}^n x_i P_i \succ 0\}.

Browse the problem library