THESIS
2017
xv, 164 pages : illustrations (some color) ; 30 cm
Abstract
Optimisation is ubiquitous and essential in almost all areas of engineering and computer
science for the design and analysis of efficient systems and algorithms. Indeed, many engineering
problems can be cast as optimisation problems, in which a decision must be made
upon certain control parameters in order to maximise revenue or minimise an incurred cost in
designing a system. Whereas deterministic optimization problems are formulated with known
parameters, real-world problems almost invariably include parameters which are unknown at
the time a decision is made. Stochastic optimisation is the approach for modeling optimization
problems that involve uncertainty, and it has attracted a lot of attention from a variety
of research elds. Specically, in the areas of communication netw...[
Read more ]
Optimisation is ubiquitous and essential in almost all areas of engineering and computer
science for the design and analysis of efficient systems and algorithms. Indeed, many engineering
problems can be cast as optimisation problems, in which a decision must be made
upon certain control parameters in order to maximise revenue or minimise an incurred cost in
designing a system. Whereas deterministic optimization problems are formulated with known
parameters, real-world problems almost invariably include parameters which are unknown at
the time a decision is made. Stochastic optimisation is the approach for modeling optimization
problems that involve uncertainty, and it has attracted a lot of attention from a variety
of research elds. Specically, in the areas of communication networks, signal processing and
machine learning, stochastic optimisation methods have been recognized as extremely useful
tools for addressing important problems.
When designing optimisation algorithms for different applications, there are a variety of
issues that need to be carefully considered, including complexity, optimality, convergence
speed, scalability, robustness and ease of implementation. Therefore, although many works
on stochastic optimisation methods exist, each particular problem within the various applications typically requires its own extensive studies. Moreover, with the new requirements
from emerging applications with large-scale systems, off-the-shelf stochastic optimization
techniques for general programs quickly become intractable in their time and memory requirements.
Consequently, there is an increasing need to design new stochastic optimisation
algorithms that can handle large-scale problems while converging very fast and maintaining
low complexity and storage requirements.
In this thesis, we investigate various emerging optimisation problems in areas including
communication networks, wireless communication systems and large-scale machine learning.
Firstly, we consider a deterministic optimisation problem to address the problem of energy-aware
routing with the complementary help of redundancy elimination. Secondly, we focus
on the problem of radio resource management (RRM) for future heterogeneous networks
with
flexible backhaul. We formulate the problem of hierarchical cross-layer RRM in such
networks with a two-timescale non-convex stochastic optimisation. We then propose a novel
iterative algorithm to solve the problem and address its challenges. We prove that the
proposed algorithm converges to the global optimal solution. Moreover, we show that it
benefits from low signalling overhead and computational complexity. Thirdly, we extend
the previous work to guarantee the quality of service (QoS) of users as well. We formulate
the associated QoS-aware cross-layer RRM problem. Then, using a stochastic cutting plane
approach, we propose a cross-layer hierarchical algorithm to solve the problem iteratively.
We also propose a heuristic hierarchical QoS-aware solution that considers the urgency of
the users data
flows and guarantees the delay performance and stability of the queues in the
network.
Next, we focus on improving the theory of stochastic optimisation, and propose a parallel
stochastic optimisation framework for solving a large class of constrained stochastic
non-convex optimisation problems. The convergence of the proposed method to the optimal
solution for the convex problems and to a stationary point for the general non-convex
problems is established. Finally, we elaborate on large-scale support vector machines, which
are one of the important problems in the context of machine learning, as a representative
application of our proposed stochastic optimisation framework. This problem appears widely
in a variety of fields for dealing with high-dimensional sparse data commonly encountered
in many applications such as cancer diagnostic in bioinformatics, image classification, face
recognition in computer vision and text categorisation in document processing, to name just a few. We demonstrate how our algorithm can efficiently solve this problem, especially in
the modern applications with huge datasets. We present experimental results to demonstrate
the merits of our proposed framework by comparing its performance to the state-of-the-art
methods in the literature, using real-world datasets.
Post a Comment