New results on some quadratic programming problems

Yang, Rui

Permalink

https://hdl.handle.net/2142/45346 Copy

Description

Title

New results on some quadratic programming problems

Author(s)

Yang, Rui

Issue Date

2013-08-22T16:37:19Z

Director of Research (if dissertation) or Advisor (if thesis)

Peng, Jiming

Doctoral Committee Chair(s)

Peng, Jiming

Committee Member(s)

• Sreenivas, Ramavarapu S.
• Ouyang, Yanfeng
• Nedich, Angelia

Department of Study

Industrial&Enterprise Sys Eng

Discipline

Industrial Engineering

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(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.

Graduation Semester

2013-08

Permalink

http://hdl.handle.net/2142/45346

Copyright and License Information

Copyright 2013 Rui Yang

Owning Collections