Comparative analysis of affine scaling algorithms based on simplifying assumptions (Q1181906)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Comparative analysis of affine scaling algorithms based on simplifying assumptions |
scientific article |
Statements
Comparative analysis of affine scaling algorithms based on simplifying assumptions (English)
0 references
27 June 1992
0 references
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.
0 references
affine potential reduction methods
0 references
0 references
0 references
0 references