Comparative analysis of affine scaling algorithms based on simplifying assumptions (Q1181906)

Several affine potential reduction methods for linear programming are analyzed under different probabilistic assumptions on the occurring search directions. The potential function \(\rho \ln(c^ Tx)- \sum_{j=1}^ n\ln (x_ j)\) is considered for LP of the form \(0=\min\{c^ Tx\mid Ax=b, x\geq 0\}\). E.g. it is assumed that the components of \(AX^ k\) are independent random variables and that the nonzero components of \(X^ k c\) are the absolute values of independent random variables, all with standard normal distribution. Then, for optimal stepsize, the decrease in the potential function \(\Omega(\rho/\sqrt{(\log n)})\) with high probability, compared to the guaranteed decrease \(\Omega(1)\). Under the same assumption, the decrease of the objective function in Dikin's affine scaling algorithm is \(1- \Omega(1/\sqrt{(\log n)})\) with high probability, compared to no guaranteed convergence rate.