Convex Optimization · Problem 9.30

Equality constrained minimization — Boyd & Vandenberghe

Mathematics — Optimization · gradient-newton-methods-numerical

Problem

Gradient and Newton methods. Consider the unconstrained problem minimizef(x)=−∑i=1mlog⁡(1−aiTx)−∑i=1nlog⁡(1−xi2),\text{minimize} \quad f(x) = -\sum_{i=1}^m \log(1 - a_i^T x) - \sum_{i=1}^n \log(1 - x_i^2), with variable x∈Rnx \in \mathbf{R}^n, and dom f={x∣aiTx<1, i=1,…,m, ∣xi∣<1, i=1,…,n}\mathbf{dom}\, f = \{x \mid a_i^T x < 1,\, i = 1, \ldots, m,\, |x_i| < 1,\, i = 1, \ldots, n\}. This is the problem of computing the analytic center of the set of linear inequalities aiTx≤1,i=1,…,m,∣xi∣≤1,i=1,…,n.a_i^T x \leq 1, \quad i = 1, \ldots, m, \qquad |x_i| \leq 1, \quad i = 1, \ldots, n. Note that we can choose x(0)=0x^{(0)} = 0 as our initial point. You can generate instances of this problem by choosing aia_i from some distribution on Rn\mathbf{R}^n. ((a)) Use the gradient method to solve the problem, using reasonable choices for the backtracking parameters, and a stopping criterion of the form ∥∇f(x)∥2≤η\|\nabla f(x)\|_2 \leq \eta. Plot the objective function and step length versus iteration number. (Once you have determined p⋆p^\star to high accuracy, you can also plot f−p⋆f - p^\star versus iteration.) Experiment with the backtracking parameters α\alpha and β\beta to see their effect on the total number of iterations required. Carry these experiments out for several instances of the problem, of different sizes. ((b)) Repeat using Newton's method, with stopping criterion based on the Newton decrement λ2\lambda^2. Look for quadratic convergence. You do not have to use an efficient method to compute the Newton step, as in exercise 9.27; you can use a general purpose dense solver, although it is better to use one that is based on a Cholesky factorization. Hint. Use the chain rule to find expressions for ∇f(x)\nabla f(x) and ∇2f(x)\nabla^2 f(x).
Intuitive explanation

This problem asks you to implement and compare two iterative optimization methods on a log-barrier objective that encodes geometric constraints. The key insight is that the gradient and Hessian have closed forms via the chain rule applied to the sum-of-logs structure—once you compute those, you can run standard descent algorithms and observe how their convergence rates differ. Gradient descent should show linear convergence (slow, steady progress), while Newton's method should exhibit quadratic convergence (explosive speedup near the optimum). By varying problem size and tuning backtracking parameters, you'll see how problem geometry and algorithm choices affect practical performance.

Intuitive explanation

This problem asks you to implement and compare two iterative optimization methods on a log-barrier objective that encodes geometric constraints. The key insight is that the gradient and Hessian have closed forms via the chain rule applied to the sum-of-logs structure—once you compute those, you can run standard descent algorithms and observe how their convergence rates differ. Gradient descent should show linear convergence (slow, steady progress), while Newton's method should exhibit quadratic convergence (explosive speedup near the optimum). By varying problem size and tuning backtracking parameters, you'll see how problem geometry and algorithm choices affect practical performance.

Related theory

Browse the problem library