Files in this item

FilesDescriptionFormat

application/pdf

application/pdfRui_Yang.pdf (377kB)
(no description provided)PDF

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 Urbana-Champaign
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 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 results can be applied to make better decisions when facing online problems with quadratic objective function.
Issue Date:2013-08-22
URI:http://hdl.handle.net/2142/45346
Rights Information:Copyright 2013 Rui Yang
Date Available in IDEALS:2013-08-22
Date Deposited:2013-08


This item appears in the following Collection(s)

Item Statistics