Hildreth's algorithm with applications to soft constraints for user interface layout

DOI10.1016/J.CAM.2015.04.014zbMATH Open1326.65068arXiv1409.2902OpenAlexW1976936504MaRDI QIDQ2351069FDOQ2351069

Authors: Noreen Jamil, Xuemei Chen, Alexander Cloninger 

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

Recommendations

• A Mathematical Model for the Motion of a Towed Pipeline Bundle
• Extending linear relaxation for non-square matrices and soft constraints
• scientific article; zbMATH DE number 2080309
• Accelerated sampling Kaczmarz Motzkin algorithm for the linear feasibility problem
• A conjugate gradient algorithm for sparse linear inequalities

zbMATH Keywords

linear inequalitiessoft constraintsHildreth's algorithmUI layout

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Linear programming (90C05) Numerical linear algebra (65F99)

Cites Work

• Title not available (Why is that?)
• A randomized Kaczmarz algorithm with exponential convergence
• Preconditioning techniques for large linear systems: A survey
• Title not available (Why is that?)
• 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
• Title not available (Why is that?)
• 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 (7)

• A Mathematical Model for the Motion of a Towed Pipeline Bundle
• 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

• Matlab
• QOCA
• linprog
• HiRise
• Cassowary

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)