946. On scaling methods for linear programming and convex optimization
Invited abstract in session MB-20: Integer Programming and Combinatorial Optimization: Complexity Questions and Algorithms, stream Combinatorial Optimization.
Monday, 10:30-12:00Room: Esther Simpson 2.11
Authors (first author is the speaker)
| 1. | Sergei Chubanov
|
| Bosch Center For Artificial Intelligence |
Abstract
The performance of certain methods for linear programming and convex optimization depends on the chosen coordinate system. Changing the coordinate system can either increase or decrease the running time of the respective algorithm for the same task. A systematic study of how scaling affects the behavior of exponential algorithms, such as the relaxation method for linear inequalities, leads to polynomial-time algorithms—meaning the complexity status of an algorithm can be improved by applying an appropriate scaling procedure. In this talk, we will discuss various scaling approaches of this kind. In particular, we will show that a suitable class of projective transformations results in a polynomial-time algorithm for positive semi-definite feasibility problems.
Keywords
- Algorithms
- Convex Optimization
- Complexity and Approximation
Status: accepted
Back to the list of papers