Asymptotic analysis of the exponential penalty trajectory in linear programming
From MaRDI portal
The practicable interior point methods for linear programming are all based on the logarithmic barrier function. The authors suggest an exponential penalty function for the same purpose in the following form: Primal problem (LP): \(\min_x \{c'x; Ax\leq b\}\), its unconstrained penalized version \((\text{P}_r)\): \(\min_x c'x+ r\sum \exp[(A_i x- b_i)/r]\). This problem has a unique solution \(x(r)\). The authors show that the trajectory \(x(r)\) is essentially a straight line directed towards the center of the optimal face of (LP) meaning that the error term tends to 0 exponentially fast as \(r\to 0\). A similar investigation is presented for the dual and the dual trajectory that show similar characteristics. The authors suggest that a path-following method could easily follow the optimal trajectory. Another advantageous feature of their approach is that, in contrast to the interior point methods, the exponential penalty function is defined everywhere. The paper discusses the theoretical aspects of the method, computational results are not reported.
Recommendations
- On the entropic perturbation and exponential penalty methods for linear programming
- Asymptotic Analysis for Penalty and Barrier Methods in Convex and Linear Programming
- On the -exponential trajectory of linear programming
- scientific article; zbMATH DE number 823376
- Quadratic rate of convergence for a primal-dual exponential penalty algorithm
Cites work
- A new polynomial-time algorithm for linear programming
- An exponential penalty method for nondifferentiable minimax problems with general constraints
- Entropy in linear programs
- scientific article; zbMATH DE number 3644821 (Why is no real title available?)
- scientific article; zbMATH DE number 3914081 (Why is no real title available?)
- scientific article; zbMATH DE number 4012323 (Why is no real title available?)
- scientific article; zbMATH DE number 4089320 (Why is no real title available?)
- scientific article; zbMATH DE number 4126998 (Why is no real title available?)
- scientific article; zbMATH DE number 4184947 (Why is no real title available?)
- Interior-point methods for convex programming
- Inverse barrier methods for linear programming
- On some methods for entropy maximization and matrix scaling
- Path-Following Methods for Linear Programming
- Stable exponential-penalty algorithm with superlinear convergence
Cited in
(59)- On the convergence of the entropy-exponential penalty trajectories and generalized proximal point methods in semidefinite optimization
- Coupling the proximal point algorithm with approximation methods
- Entropic approach to interior point solution of linear programs
- On the -exponential trajectory of linear programming
- On the entropic perturbation and exponential penalty methods for linear programming
- An interior-proximal method for convex linearly constrained problems and its extension to variational inequalities
- Viscosity approximation methods for fixed-points problems
- Computation of optimal transport and related hedging problems via penalization and neural networks
- Domain decomposition for entropy regularized optimal transport
- Entropic optimal transport: convergence of potentials
- Entropic optimal transport: geometry and large deviations
- Entropic regularization in hierarchical games
- Asymptotic analysis of domain decomposition for optimal transport
- Convergence rate of general entropic optimal transport costs
- Lp approximation of variational problems in L1 and L∞
- Steepest descent evolution equations: asymptotic behavior of solutions and rate of convergence
- Quadratic rate of convergence for a primal-dual exponential penalty algorithm
- Asymptotic Analysis for Penalty and Barrier Methods in Convex and Linear Programming
- Semidual regularized optimal transport
- Regularized optimal transport and the rot mover's distance
- Calmness of partially perturbed linear systems with an application to the central path
- Hybrid extragradient proximal algorithm coupled with parametric approximation and penalty/barrier methods
- On the effectiveness of Richardson extrapolation in data science
- Empirical regularized optimal transport: statistical theory and applications
- Supervised optimal transport
- Quantitative stability of regularized optimal transport and convergence of Sinkhorn's algorithm
- Asymptotics for semidiscrete entropic optimal transport
- Stabilized Sparse Scaling Algorithms for Entropy Regularized Transport Problems
- Iterative Bregman projections for regularized transportation problems
- Learning to match via inverse optimal transport
- Convergence of entropic schemes for optimal transport and gradient flows
- Dual convergence of the proximal point method with Bregman distances for linear programming
- Dual space preconditioning for gradient descent
- Optimal transportation, modelling and numerical simulation
- Why the logarithmic barrier function in convex and linear programming?
- A convergence result for nonautonomous subgradient evolution equations and its application to the steepest descent exponential penalty trajectory in linear programming
- Steepest descent with curvature dynamical system
- Semi-discrete optimal transport: hardness, regularization and numerical solution
- A fast solver for generalized optimal transport problems based on dynamical system and algebraic multigrid
- Stability of Schrödinger potentials and convergence of Sinkhorn's algorithm
- Entropic model predictive optimal transport over dynamical systems
- Quantitative uniform stability of the iterative proportional fitting procedure
- Limit distributions and sensitivity analysis for empirical entropic optimal transport on countable spaces
- Enhanced computation of the proximity operator for perspective functions
- Detecting data-driven robust statistical arbitrage strategies with deep neural networks
- From optimal transport to discrepancy
- Stability and sample complexity of divergence regularized optimal transport
- Complementary composite minimization, small gradients in general norms, and applications
- An ordinary differential equation for entropic optimal transport and its linearly constrained variants
- Quantitative convergence of quadratically regularized linear programs
- Convergence rates of the regularized optimal transport: disentangling suboptimality and entropy
- Fisher-Rao gradient flows of linear programs and state-action natural policy gradients
- Flow updates for domain decomposition of entropic optimal transport
- Characterization of transport optimizers via graphs and applications to Stackelberg-Cournot-Nash equilibria
- On the sample complexity of entropic optimal transport
- A uniform rate of convergence for the entropic potentials in the quadratic euclidean setting
- Doubly stochastic inter-assembly coupling via entropic optimal transport in echo-state networks for chaotic flows
- Wasserstein mirror gradient flow as the limit of the Sinkhorn algorithm
- Sparsity of quadratically regularized optimal transport: scalar case
This page was built for publication: Asymptotic analysis of the exponential penalty trajectory in linear programming
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1341567)
