Výpočetní aspekty optimalizace piece-wise lineární funkce s motivací pro robustní statistiku

This thesis studies computational aspects of optimizing Jaeckel’s Dispersion Function, a convex piecewise-linear objective function arising in rank-based regression. The main focus is on the construction of difficult instances for selected heuristic optimization methods. Instead of choosing the data matrix and the response vector directly, the thesis develops a geometric construction procedure that transforms prescribed local geometry into matrix X and vector y. The geometry is prescribed active permutation on cells (this controls the adjacency of the cells), gradient of the objective function, which is linear on the cell, and by vertices on which respective permutations are active. Two main classes of instances are constructed. The Infinitely Narrow Cone is designed to be difficult for gradient descent with line search. The method repeatedly reaches nondifferentiability boundaries and makes only very slow progress toward the optimizer. The Infinitely Anisotropic Canyon is designed to be difficult for Nelder-Mead Simplex. Its geometry is steep across the canyon and almost flat along its floor, which can cause a quick contraction in the simplex and exceeding of the iteration limit before reaching optimizer. The numerical experiments show that different heuristics can fail for different geometric reasons. The constructed instances are not rare examples, but representatives of broader classes of geometrically similar instances.