Convex Optimization · Problem 10.13

Interior-point methods — Boyd & Vandenberghe

Mathematics — Optimization · elimination-method-convex-concave-game

Problem

Elimination method for computing Newton step for convex-concave game. Consider a convex-concave game with payoff function f:Rp×Rq→Rf: \mathbf{R}^p \times \mathbf{R}^q \to \mathbf{R} (see page 541). We assume that ff is strongly convex-concave, i.e., for all (u,v)∈dom f(u,v) \in \mathbf{dom}\, f and some m>0m > 0, we have ∇uu2f(u,v)⪰mI\nabla^2_{uu} f(u,v) \succeq mI and ∇vv2f(u,v)⪯−mI\nabla^2_{vv} f(u,v) \preceq -mI. (a) Show how to compute the Newton step using Cholesky factorizations of ∇uu2f(u,v)\nabla^2_{uu} f(u,v) and −∇2fvv(u,v)-\nabla^2 f_{vv}(u,v). Compare the cost of this method with the cost of using an LDLT\mathrm{LDL}^T factorization of ∇f(u,v)\nabla f(u,v), assuming ∇2f(u,v)\nabla^2 f(u,v) is dense. (b) Show how you can exploit diagonal or block diagonal structure in ∇uu2f(u,v)\nabla^2_{uu} f(u,v) and/or ∇vv2f(u,v)\nabla^2_{vv} f(u,v). How much do you save, if you assume ∇uv2f(u,v)\nabla^2_{uv} f(u,v) is dense?
Intuitive explanation

The Newton step for a game requires solving a saddle-point system, but strong convex-concave structure lets you eliminate one player's variables and solve two smaller, better-conditioned problems instead. By factoring the diagonal blocks ∇uu2f\nabla^2_{uu} f and −∇vv2f-\nabla^2_{vv} f separately via Cholesky, you avoid the expense and numerical instability of factoring the full indefinite Hessian, and you can further exploit any sparsity or block structure in those diagonal blocks to reduce cost dramatically.

Intuitive explanation

The Newton step for a game requires solving a saddle-point system, but strong convex-concave structure lets you eliminate one player's variables and solve two smaller, better-conditioned problems instead. By factoring the diagonal blocks ∇uu2f\nabla^2_{uu} f and −∇vv2f-\nabla^2_{vv} f separately via Cholesky, you avoid the expense and numerical instability of factoring the full indefinite Hessian, and you can further exploit any sparsity or block structure in those diagonal blocks to reduce cost dramatically.

Related theory

Browse the problem library