Oyun teorisi ve makine öğrenimi uygulamalarıyla seyreklik kısıtlı minimum-maksimum optimizasyon

Classical game-theoretic methods often yield dense strategies for a player, which might not be practical in real-world implementations. This thesis studies incorporating the sparsity constraint to the minimax optimization problem to compute sparse strategies in bimatrix games. The theory and algorithms also apply to the equivalent problem of computing sparse classifiers in the margin maximizing boosting problem. Optimality conditions in the sparse optimization literature are extended to nonsmooth functions. A new optimality condition for neighborhood search that covers the existing conditions is proposed. Practical greedy algorithms are developed to find candidate points satisfying optimality conditions. Based on the properties of the Minimax function, connections between the cardinality-constrained problem and the cardinality-regularized problem are established. A new concave penalty for cardinality-regularized optimization problems over the unit simplex is proposed, which offers an alternative to the sparsity-promoting penalties in the literature. The resulting problem is solved efficiently using a faster version of the Difference of Convex (DC) algorithm. The proposed algorithms are tested empirically on random game matrices and real data for binary classification. The performance is compared to well-known regularization techniques and the MILP formulation of the problem.