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.
$\begingroup$
$\endgroup$
2
-
2$\begingroup$ Tell us the structure. $\endgroup$– Mark L. StoneAug 19, 2022 at 16:26
-
$\begingroup$ The matrix A is a close relative of a graph Laplacian, where the underlying graph is a lattice. $\endgroup$– user12345678Aug 20, 2022 at 11:25
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
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}$.
