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.