Hildreth's algorithm with applications to soft constraints for user interface layout
From MaRDI portal
Publication:2351069
DOI10.1016/J.CAM.2015.04.014zbMATH Open1326.65068arXiv1409.2902OpenAlexW1976936504MaRDI QIDQ2351069FDOQ2351069
Noreen Jamil, Alexander Cloninger, Xuemei Chen
Publication date: 22 June 2015
Published in: Journal of Computational and Applied Mathematics (Search for Journal in Brave)
Abstract: The Hildreth's algorithm is a row action method for solving large systems of inequalities. This algorithm is efficient for problems with sparse matrices, as opposed to direct methods such as Gaussian elimination or QR-factorization. We apply the Hildreth's algorithm, as well as a randomized version, along with prioritized selection of the inequalities, to efficiently detect the highest priority feasible subsystem of equations. We prove convergence results and feasibility criteria for both cyclic and randomized Hildreth's algorithm, as well as a mixed algorithm which uses Hildreth's algorithm for inequalities and Kaczmarz algorithm for equalities. These prioritized, sparse systems of inequalities commonly appear in constraint-based user interface (UI) layout specifications. The performance and convergence of these proposed algorithms are evaluated empirically using randomly generated UI layout specifications of various sizes. The results show that these methods offer improvements in performance over standard methods like Matlab's LINPROG, a well-known efficient linear programming solver, and the recent developed Kaczmarz algorithm with prioritized IIS detection.
Full work available at URL: https://arxiv.org/abs/1409.2902
Numerical mathematical programming methods (65K05) Linear programming (90C05) Numerical linear algebra (65F99)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- A randomized Kaczmarz algorithm with exponential convergence
- Preconditioning techniques for large linear systems: A survey
- Row-Action Methods for Huge and Sparse Systems and Their Applications
- Randomized Methods for Linear Constraints: Convergence Rates and Conditioning
- Locating Minimal Infeasible Constraint Sets in Linear Programs
- Branch-and-Cut for the Maximum Feasible Subsystem Problem
- Misclassification minimization
- Fast heuristics for the maximum feasible subsystem problem
- Analyzing Infeasible Mixed-Integer and Integer Linear Programs
- Randomized extended Kaczmarz for solving least squares
- Randomized Kaczmarz solver for noisy linear systems
- The Relaxation Method for Solving Systems of Linear Inequalities
- Detecting IIS in infeasible linear programmes using techniques from goal programming
- Almost sure convergence of the Kaczmarz algorithm with random measurements
- On the convergence properties of Hildreth's quadratic programming algorithm
- Preserving Form-Features in Interactive Mesh Deformation
- Extensions of Hildreth’s Row-Action Method for Quadratic Programming
- A two-phase relaxation-based heuristic for the maximum feasible subsystem problem
- Domain specific high-level constraints for user interface layout
- Convergence of the cyclical relaxation method for linear inequalities
Cited In (6)
- Extending linear relaxation for non-square matrices and soft constraints
- On the behaviour of the underrelaxed Hildreth's row-action method for computing projections onto Polyhedra
- The Kaczmarz algorithm, row action methods, and statistical learning algorithms
- Quantile-Based Iterative Methods for Corrupted Systems of Linear Equations
- Randomized Projection Methods for Linear Systems with Arbitrarily Large Sparse Corruptions
- Metric-Constrained Optimization for Graph Clustering Algorithms
Uses Software
This page was built for publication: Hildreth's algorithm with applications to soft constraints for user interface layout
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2351069)
