# Linear programming with "nice" matrices

Consider the following linear programming problem $$\begin{array}{ll} \text{minimize} & \mathrm 1^{\top} \mathrm x\\ \text{subject to} & v\le \mathrm A \mathrm x \le u\\ & \mathrm x \geq 0 \end{array}$$ Suppose $$A$$ is a 'very nice' matrix: highly structured, positive-definite, we know all eigenvalues/eigenvectors. Are there any special methods, approaches, or tricks which could help us accelerate numerical solution and/or analysis of the problem.

• Tell us the structure. Aug 19, 2022 at 16:26
• The matrix A is a close relative of a graph Laplacian, where the underlying graph is a lattice. Aug 20, 2022 at 11:25

I am not sure if it helps much unless we know more about the structure of $$A\in\mathbb{R}^{n\times n}$$ beyond symmetric positive definiteness. The LP as given can be rewritten as $$\begin{array}{ll} \underset{y\in\mathbb{R}^n}{\text{minimize}} & \mathrm c^{\top} y\\ \text{subject to} & v \preceq \mathrm y \preceq u,\\ & A^{-1}y \succeq 0, \end{array}$$ with $$y:=Ax$$ and $$c:=A^{-1}\rm{1}$$. Following standard calculations, the Lagrange dual LP is $$\begin{array}{ll} \underset{\lambda\in\mathbb{R}^{3n}}{\text{minimize}} & d^{\top} \lambda\\ \text{subject to} & M\lambda = c,\\ & \lambda \succeq 0, \end{array}$$ where $$d:=\begin{pmatrix} u\\ -v\\ 0_{n\times 1} \end{pmatrix}\in\mathbb{R}^{3n}$$, $$M:=[-I_n \: I_n \: A^{-1}]\in\mathbb{R}^{n\times 3n}$$.