Files in this item
Files  Description  Format 

application/pdf Rui_Yang.pdf (377kB)  (no description provided) 
Description
Title:  New results on some quadratic programming problems 
Author(s):  Yang, Rui 
Director of Research:  Peng, Jiming 
Doctoral Committee Chair(s):  Peng, Jiming 
Doctoral Committee Member(s):  Sreenivas, Ramavarapu S.; Ouyang, Yanfeng; Nedich, Angelia 
Department / Program:  Industrial&Enterprise Sys Eng 
Discipline:  Industrial Engineering 
Degree Granting Institution:  University of Illinois at UrbanaChampaign 
Degree:  Ph.D. 
Genre:  Dissertation 
Subject(s):  optimization
quadratic programming matrix factorization online algorithm portfolio selection 
Abstract:  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 2approximation 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 2approximation 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 learningbased 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 distributionfree random permutation model and some mild assumptions, we propose a 1 − O(ϵ) learning algorithm for this online problem. The results can be applied to make better decisions when facing online problems with quadratic objective function. 
Issue Date:  20130822 
URI:  http://hdl.handle.net/2142/45346 
Rights Information:  Copyright 2013 Rui Yang 
Date Available in IDEALS:  20130822 
Date Deposited:  201308 
This item appears in the following Collection(s)

Dissertations and Theses  Industrial and Enterprise Systems Engineering

Graduate Dissertations and Theses at Illinois
Graduate Theses and Dissertations at Illinois