»» Linear Programming

# Linear Programming

In the following section, Set Theory, Topology and Nonstandard Analysis are presupposed. Dropping the finite limitation allows the analogous transfer of the following theorem to polyhedra:

Diameter theorem for polytopes: Every diameter of an $$n$$-dimensional polytope defined by $$m$$ constraints for $$m, n \in {}^{\omega}\mathbb{N}_{\ge 2}$$ is at most $$2(m + n – 3)$$.

Proof: At most $$\acute{m}$$ hyperplanes can be assembled into an incomplete cycle of dimension 2 and there are at most $$n – 2$$ alternatives sidewards in all remaining dimensions. Overcoming every minimal distance requires at most two edges and yields the factor 2.$$\square$$

Runtime of the Strassen algorithm for the matrix product $$AA^T$$: For matrix $$A \in \mathbb{C}^{n \times n}$$, it roughly halves that of $$AB$$ in $$\mathcal{O}(n^{(_2 7)})$$ with $$B \in \mathbb{C}^{n \times n}$$ for sufficiently big $$n = 2^k$$ and $$k \in \mathbb{N}^*$$.

Proof: The GS yields the claim because of the following halvings (see top right):$AA^T = \begin{pmatrix}A_{11} & A_{12} \\ A_{21} & A_{22} \end{pmatrix} \begin{pmatrix} A_{11}^T & A_{21}^T \\ A_{12}^T & A_{22}^T\end{pmatrix} = \begin{pmatrix} A_{11}A_{11}^T+A_{12}A_{12}^T & A_{11}A_{21}^T+A_{12}A_{22}^T \\ A_{21}A_{11}^T+A_{22}A_{12}^T & A_{21}A_{21}^T+A_{22}A_{22}^T\end{pmatrix}.\square$Definition: Let $$\vartheta := \omega\,{}_{e}\omega$$ and $${|| \cdot ||}_{1}$$ the 1-norm. If $$x \in X \subseteq {}^{\omega}\mathbb{R}^{\omega}$$ passes to the next step, it is followed by $${}^{*}$$ where $$\Delta x := {x}^{*} – x$$. The unit vector of $$x \in X^{*}$$ is $${_1}{x} := x/||x||$$. Let $$x, y \in X$$ in $$(x, y, …)^T$$ be row vectors. If a method requires computation time in seconds and memory in bits of $$\mathcal{O}({\omega}^{\mathcal{O}(1)})$$, it is polynomial. If one of both quantities is $$\mathcal{O}({e}^{|\mathcal{O}(\omega)|})$$, the method is exponential. Let the eigenproduct (yet: determinant) of a square matrix be the product of its eigenvalues.$$\triangle$$

Theorem: The simplex method1Dantzig, George B.: Lineare Programmierung und Erweiterungen; 1. Aufl.; 1966; Springer; Berlin. may solve a solvable LP almost always in $$\mathcal{O}({\omega}^3\vartheta)$$.

Proof and algorithm: Let LP max $$\{{c}^{T}x : c \in {}^{\omega}\mathbb{R}^{n}, x \in P\}$$ have the feasible domain $$P := \{x \in {}^{\omega}\mathbb{R}^{n} : Ax \le b, b \in {}^{\omega}\mathbb{R}^{m}, A \in {}^{\omega}\mathbb{R}^{m \times n}, m, n \in {}^{\omega}\mathbb{N}^{*}\}$$. Its dual gives $${x}^{*} \in {}^{\omega}\mathbb{R}_{\ge 0}^{m}$$. A (big) $$x^+ \in {}^{\omega}\mathbb{R}_{\geq0}$$ achieves $$x^* \in {}^{\omega}\mathbb{R}_{\geq0}^n$$ for $$x := x^* – {\underline{x}}_n^+$$. Solving max $$\{-h \in {}^{\omega}\mathbb{R}_{\le 0} : Ax – b \le \underline{h}_n\}$$ yields $$x \in P_{\ge 0}$$ if $$b \ge 0$$ does not hold. Let $$|\text{min } \{{b}_{1}, …, {b}_{m}\}|$$ be the initial value for $$h$$ and 0 its target value. Start with $$x := 0$$. Only one pivot step causes that $${b}^{*} \ge 0$$. Let $$i, j, k \in {}^{\omega}\mathbb{N}^{*}$$ and let $${a}_{i}^{T}$$ the $$i$$-th row vector of $$A$$. If $${c}_{j} \le 0$$ for all $$j$$, the LP is solved.

If for some $${c}_{j} > 0$$ also $${a}_{ij} \le 0$$ for all $$i$$, the LP is positively unbounded. If for some $${c}_{j} = 0$$ also $${a}_{ij} \le 0$$ for all $$i$$, drop $${c}_{j}$$ and $${A}_{.j}$$ as well as $${b}_{i}$$ and $${a}_{i}$$, but only when $${a}_{ij} < 0$$ holds. The inequality $${a}_{ij}{x}_{j} \ge 0 > {b}_{i}$$ for all $$j$$ has no solution, too. Dividing all $${a}_{i}^{T}x \le {b}_{i}$$ by $$||{a}_{i}||$$ and all $${c}_{j}$$ and $${a}_{ij}$$ by the minimum of $$|{a}_{ij}|$$ such that $${a}_{ij} \ne 0$$ for each $$j$$ maybe repeated and reversed later. Constraints with $${a}_{i} \le 0$$ may always be removed.

For each $${c}_{j} > 0$$ and non-base variable $${x}_{j}$$ select $${b_k}/{a}_{kj} :=$$ min $$\{{b_i}/{a}_{ij} : {a}_{ij} > 0\}$$ to obtain a next $${x}^{*} \in P_{\ge 0}$$ where $${x}_{j}^{*} = {x}_{j} + {b}_{k}/{a}_{kj}$$. To select the steepest edge, pick the pivot $${a}_{kj}$$ corresponding to $${x}_{j}$$ that maximises $${c}^{T}{_1}{\Delta x}$$ or $${c}_{j}^{2}/\grave{v}_{j}^{2}$$ for $$v_j := ||{A}_{.j}||$$ in the $$k$$-th constraint. Multiple maxima allow to use the rule of best pivot value max$${}_{k,j} {c}_{j}{b}_{k}/{a}_{kj}$$ or (slower) the smallest angle min $${{_{(1)}}\underline{1}^{T}_n}{_1}{c}^{*}$$.

If $$c^Tx^* = c^Tx$$ is repeated, relax all constraints with $${b}_{i} = 0$$ by $$d \in {}^{\omega}\mathbb{R}_{>0}$$. For $${b}_{i} := ||{a}_{i}||$$, drop $$d$$ in the tableau. If another multiple vertex is encountered for once, simply add $$||{a}_{i}||$$ to every $${b}_{i}$$. Leaving it may require to solve an LP with $$c > 0$$ and $$b = 0$$. Then the relaxation (perturbation) is reverted. This task can also finally arise, if further solutions of the LPs are to be determined for at least two $$c_j = 0$$.

This avoids having to compute several minimal relaxations that differ strongly as the lexicographical method does. The rectangle rule simply allows to compute $${c}_{j}^{*}, {a}_{ij}^{*}$$ and $${b}_{i}^{*}$$2cf. Vanderbei, Robert J.: Linear Programming; 3rd Ed.; 2008; Springer; New York, p. 63.. Bland’s rule is not optimal, too. No pivoting rule can prevent the simplex method from being exponential as the case may be: An exponential “drift” for e. g. Klee-Minty or Jeroslow polytopes may always provide an unfavourable edge. The result follows in accordance with the state of research.$$\square$$

Theorem: Intex methods solve almost every solvable LP with inter-/extrapolations in $$\mathcal{O}({\vartheta}^3)$$.

Proof and algorithm: Let $$z := m + n$$ and $$d \in [0, 1]$$ the density of $$A$$. First, normalise and scale $${b}^{T}y – {c}^{T}x \le 0, Ax \le b$$ as well as $${A}^{T}y \ge c$$. Let $$P_r := \{(x, y)^T \in {}^{\omega}\mathbb{R}_{\ge 0}^{z} : {b}^{T}y – {c}^{T}x \le r \in [0, \rho], Ax – b \le \underline{r}_m, c – {A}^{T}y \le \underline{r}_n\}$$ have the radius $$\rho := s|\min \; \{b_1, …, b_m, -c_1, …, -c_n\}|$$ and the scaling factor $$s \in [1, 2]$$. It follows $$\underline{0}_{z} \in \partial P_{\rho}$$. By the strong duality theorem3loc. cit., p. 60 – 65., LP min $$\{ r \in [0, \rho] : (x, y)^T \in P_r\}$$ solves LPs max $$\{{c}^{T}x : c \in {}^{\omega}\mathbb{R}^{n}, x \in {P}_{\ge 0}\}$$ and min $$\{{b}^{T}y : y \in {}^{\omega}\mathbb{R}_{\ge 0}^{m}, {A}^{T}y \ge c\}$$.

Its solution is the geometric centre $$g$$ of the polytope $$P_0$$. For $$p_k^* := \text{min}\,\check{p}_k + \text{max}\,\check{p}_k$$ and $$k = 1, …, \grave{z}$$ approximate $$g$$ by $$p_0 := (x_0, y_0, r_0)^T$$ until $$||\Delta p||_1$$ is sufficiently small. The solution $$t^o(x^o, y^o, r^o)^T$$ of the two-dimensional LP min $$\{ r \in [0, \rho] : t \in {}^{\omega}\mathbb{R}_{> 0}, t(x_0, y_0)^T \in P_r\}$$ approximates $$g$$ better and achieves $$r \le \check{\rho}$$. Repeat this for $$t^o(x^o, y^o)^T$$ until $$g \in P_0$$ is computed in $$\mathcal{O}({}_2\rho^2dmn)$$ if it exists.

Solving all two-dimensional LPs $$\text{min}_k r_k$$ by bisection methods for $$r_k \in {}^{\omega}\mathbb{R}_{\ge 0}$$ and $$k = 1, …, z$$ in $$\mathcal{O}({\vartheta}^2)$$ each time determines $$q \in {}^{\omega}\mathbb{R}^k$$ where $$q_k := \Delta p_k \Delta r_k/r$$ and $$r := \text{min}_k \Delta r_k$$. Let simplified $$|\Delta p_1| = … = |\Delta p_{z}|$$. Here min $$r_{\grave{z}}$$ for $$p^* := p + wq$$ and $$w \in {}^{\omega}\mathbb{R}_{\ge 0}$$ may be solved, too. If $$\text{min}_k \Delta r_k r = 0$$ follows, stop computing, otherwise repeat until min $$r = 0$$ or min $$r > 0$$ is sure.$$\square$$

Remark: Details are only published when no misuse for non-transparent or bad decisions must be feared. Simplex method and face algorithm4Pan, Ping-Qi: Linear Programming Computation; 1st Ed.; 2014; Springer; New York., p. 580 f. solve LPs faster for small $$m$$ and $$n$$. Intex methods are faster than all known (worst-case) LP-algorithms in $$\mathcal{O}(\omega^{37/18}\vartheta)$$. Rounding errors provoked in $$b$$ and $$c$$ make any solution unique.

Remark: If necessary, the same small modulus relaxes constraints temporarily. The runtime for $$m, n \in {}^{\nu}\mathbb{N}^*$$ is $$\mathcal{O}(dmn)$$. Optimising it for distributed computing in $${}^{\nu}\mathbb{R}^{\nu}$$ reduces it to $$\mathcal{O}(1)$$. Integer solutions $$v_j$$ satisfying $$\acute{v}_0 \le \lfloor v_j \rfloor – v_j$$ prove them successful for (mixed) integer problems and (non-) convex (Pareto) optimisation (according to nature5Vasuki, A: Nature-Inspired Optimization Algorithms; 1st Ed.; 2020; CRC Press; Boca Raton.).

Remark: Intex methods make use of the fact that the calculated geometric centre and the centre of the sphere coincide in $$P_0$$. The former is secured by rotating the coordinate axes (in pairs) like $$c$$ with the aid of a simple rotation matrix in a comparable runtime. Numbers of length $$\mathcal{O}({\omega})$$ can only be processed in $$\mathcal{O}(\vartheta)$$ as is generally known. The following results can also be easily transferred to complex numbers:

Conclusion: LP max $$\{{||x – {x}^{o}||}_{1} : {c}^{T}x = {c}^{T}{x}^{o}, Ax \le b, x – {x}^{o} \in {[-1, 1]}^{n}, x \in {}^{\omega}\mathbb{R}_{\ge 0}^{n}\}$$ can determine for the first solution $${x}^{o}$$ any second one in $$\mathcal{O}({\vartheta}^3)$$ where $${y}^{o}$$ may be treated analogously.$$\square$$

Conclusion: LP max $$\{\nu|\lambda_j| + ||x_j||_1: Ax_j = \lambda_j x_j, |\lambda_j| \in [0, r_j], x_j \in {[-1, 1]}^{n*}\}$$ can determine for every $$j = 1, …, n$$ the eigenvalue $$\lambda_j \in {}^{\omega}\mathbb{R}$$ and the eigenvector $$x_j \in {}^{\omega}\mathbb{R}^{n}$$ of matrix $$A \in {}^{\omega}\mathbb{R}^{n \times n}$$ in $$\mathcal{O}({\vartheta}^3).\square$$

Conclusion: LPs max $$\{{x}_{j} : Ax = 0\}$$ yield all solutions to $$Ax = b$$ in $$\mathcal{O}({\vartheta}^3)$$. Matrix $$A$$ is regular if and only if LP max $$\{{||x||}_{1} : Ax = 0\} = 0.\square$$

Conclusion: Let $${\alpha }_{j} := {A}_{.j}^{-1}$$ for matrix $${A}^{-1} \in {}^{\omega}\mathbb{R}^{n \times n}$$ and let $${\delta}_{ij}$$ the Kronecker delta where $$j = 1, …, n$$. A regular $$A$$ has an eigenproduct $$\ne 0$$ and allows every $${A \alpha }_{j} = {({\delta}_{1j}, …, {\delta}_{nj})}^{T}$$ to be solved in $$\mathcal{O}({\vartheta}^3)$$.$$\square$$

Conclusion: The polynomial $$c_{\acute{n}}x^{\acute{n}} + … + c_1x + c_0$$ can be determined in $$\mathcal{O}({\vartheta}^3)$$ by measurement $$(x_j, y_j) \in {}^{\omega}\mathbb{R}^2$$ and residues $$r_j \in {}^{\omega}\mathbb{R}$$ for $$j = 1, …, m$$ and $$(c, x)^T \in {}^{\omega}\mathbb{R}^{\grave{n}}$$ from $$y = r + Xc$$ and $$X^Tr = 0$$ where $$X = \left(x_j^k\right)$$ for $$k = 0, …, \acute{n}$$ (also under additional constraints6cf. loc. cit., p. 196 ff..$$\square$$

Conclusion: The DFT (see Scientific Computing) can determine the Padé approximant $${a(x)}/{b(x)}={{+}_{m=0}^n {a_m x^m}}/{{+}_{m=0}^n {b_m x^m}}$$ of $$f(x)$$ for $$x \in {}^{\omega}\mathbb{R}$$ in $$\mathcal{O}({\vartheta}^3).\square$$

Corollary: Intex methods and two-dimensional bisection or Newton’s methods may solve most solvable convex programmes min $$\{{f}_{1}(x) : x \in {}^{\omega}\mathbb{R}^{n}, {({f}_{2}(x), …, {f}_{m}(x))}^{T} \le 0\}$$ where all $${f}_{k} \in {}^{\omega}\mathbb{R}$$ are convex functions for $$k = 1, …, m$$ in polynomial runtime, if the number of operands $${x}_{j}$$ of all $${f}_{k}$$ is $$\le {\omega}^{\nu-3}$$ and if an $$x$$ exists such that $${f}_{k}(x) < 0$$ for all $$k > 1$$7cf. Geiger, Carl; Kanzow, Christian: Theorie und Numerik restringierter Optimierungsaufgaben; 1. Aufl.; 2002; Springer; Berlin, p. 56 ff..$$\square$$

Corollary: LP max $$\{x : y_{\acute{m}} – xy_m = b_{\acute{m}}, y_n = y_0 = 0, x \le x_0 \in {}^{\omega}\mathbb{R}\}$$ can determine for $$m = 1, …, n$$ by Horner scheme an $$x \in {}^{\omega}\mathbb{R}$$ solving $$n$$-polynomial $$b_{\acute{n}}x^{\acute{n}} + … + b_1x + b_0 = 0$$ in $$\mathcal{O}({\vartheta}^2)$$. Aborting TS can analogously solve every continuous inequation system with convex solution set.$$\square$$