New results on some quadratic programming problems

optimization;quadratic programming;matrix factorization;online algorithm;portfolio selection

Yang, Rui

关键词: optimization;    quadratic programming;    matrix factorization;    online algorithm;    portfolio selection;   

Others  :  https://www.ideals.illinois.edu/bitstream/handle/2142/45346/Rui_Yang.pdf?sequence=1&isAllowed=y

美国|英语

来源: The Illinois Digital Environment for Access to Learning and Scholarship

【 摘 要 】

In this thesis we present new effective algorithms for several special classes of quadratic programming problems. The problems we study can be classifiedinto two categories. The first group contains two optimization problems with binary constraints. To solve these problems, we first explore some intrinsic relation between binary quadratic problem and data clustering. Then we utilize the explored relation to develop effective approximation algorithms. For example, the first problem we consider is a special class of binary quadratic problem where the number of nonzero elements is fixed. We use convex quadratic relaxation as a geometric embedding tool to reformulate the underlying BQP as a clustering problem where the target is to find a single cluster of fixed size. A simple 2-approximation algorithm for the clustering problem is proposed. In the second project we study the Binary Matrix Factorization problem(BMF) with additional restriction that the matrix product should be binary and call it constrained binary matrix factorization(CBMF). We propose alternating update procedures for CBMF where we actually solve a binary LP subproblem to update the involved matrix argument. We have both a deterministic 2-approximation and also a randomized approximation algorithm. The deterministic algorithm has a complexity exponential in k, while the randomized algorithm runs in O(kmn) time. The second part of this thesis is about portfolio selection under some (hard) realistic setting. We first considered a new approach for portfolio selection problem with cardinality and thresholds constraints that employs the new technique (based on lp penalty with 0 < p < 1) for finding sparse solutions. The key idea is to interpret the cardinality constraint as a constraint on the sparsity of the solution. This allows us to use the recently developed techniques for sparse solutions in linear and quadratic optimization problems to find a solution that satisfies the cardinality constraint. Numerical experiments indicate that our proposed Hybrid algorithm is fast, and able to provide good approximation solution that has attractive features in financial applications. In the last project we developed an online learning algorithm for quadratic programming problems. Our learning-based algorithm works by constructing a pricing vector from a training problem of previous period and the price vector is used to make decisions sequentially. Under the distribution-free random permutation model and some mild assumptions, we propose a 1 − O(ϵ) learning algorithm for this online problem. The resultscan be applied to make better decisions when facing online problems with quadratic objective function.