Browsing by Subject "Resource allocation"

Now showing 1 - 3 of 3
  • Thumbnail Image
    Item
    Distributed optimization in an energy-constrained network.
    (2010-02) Razavi Majomard, Seid Alireza
    We consider a distributed optimization problem whereby a network of N nodes, Sℓ, ℓ ∈ {1, . . . ,N}, wish to minimize a common strongly convex function f(x), x = [x1, . . . , xN]T , under the constraint that node Sℓ controls variable xℓ only. The nodes locally update their respective variables and periodically exchange their values over a set of pre-defined communication channels. Previous studies of this problem have focused mainly on the convergence issue and the analysis of convergence rate. In this work, we consider noisy communication channels and study the impact of communication energy on convergence. In particular, we study the minimum amount of communication energy required for nodes to obtain an ϵ-minimizer of f(x) in the mean square sense. For linear analog communication schemes, we prove that the communication energy to obtain an ϵ-minimizer of f(x) must grow at least at the rate of Ω(1/ϵ), and this bound is tight when f is convex quadratic. Furthermore, we show that the same energy requirement can be reduced to O ( log2 1/ϵ ) if suitably designed digital communication schemes are used.
  • Thumbnail Image
    Item
    Dynamic learning and resource management under uncertainties for smart grid and cognitive radio networks
    (2014-05) Yahyasoltani, Nasin
    The importance of timely applications and decisions in dynamic environments, has led to the integration of intelligent networks to increase efficiency and end-user satisfaction in various application domains including telecommunication and power grid networks. Contemporary intelligent networks require advanced statistical signal processing and optimization tools to learn, infer and control their operation. This integration poses new challenges and has witnessed the emergence of novel resource management and learning techniques to cope with dynamics. In addition, in order to have implementable resource management algorithms, it is crucial to model the underlying sources of uncertainty in the optimization framework. This thesis develops algorithms for resource allocation under channel uncertainty in cognitive radio (CR) communication networks and contributes to demand coordination under uncertainty in power networks.Demand coordination through real-time pricing is addressed first by capitalizing on the uncertainty involved in the consumption behavior of consumers. Prerequisite to the demand coordination task is learning the uncertainty present in power consumption data. The dependency of consumers' consumption behavior on the announced prices and their neighbors' behavior, is modeled through graphical models. In particular, the electric vehicle (EV) consumers are considered and the adopted model also captures dynamics of EV consumers' time-varying charging decisions. Leveraging the online convex optimization (OCO) framework, an online algorithm for tracking the model is devised. With minimal assumptions on the structure of the temporal dynamics, and while accounting for the possibly adversarial consumption behavior of consumers, the proposed online algorithm provides performance guarantees. The probability distributions obtained through the tracking algorithm are then deployed as input to stochastic economic profit maximization for real-time price setting.Learning in the presence of missing data is a pervasive problem in statistical data analysis. Next, attention is turned to tracking the dynamic charging behavior of EV consumers, when at each time slot some of the consumers' consumption decisions are possibly missing. The problem amounts to online classification with missing labels. An online algorithm is proposed to wed real-time estimation of the missing data with learning of complete data in the OCO framework.As regards CR networks, this thesis introduces novel resource allocation algorithms for orthogonal frequency-division multiple access (OFDMA) CR under channel uncertainty where the unique approaches can be fitted to a class of large-scale robust mixed-integer problems. Due to the lack of cooperation of the licensed system, CRs must resort to less efficient channel estimation techniques thus incurring an inevitable channel estimation error. It is shown that CR interference constraints under channel uncertainty can be cast as chance constraints. On the other hand, instead of just modeling the user rates by logarithmic functions of transmit-powers, justified under ideal Gaussian coding, practical finite-alphabet constellations are adopted which leads to an optimization objective of a weighted sum of mutual information. When multiple users are present, due to the combinatorial search for optimal subcarrier assignment, the problem is non-convex and hard to solve, as the optimization variables are coupled across all subcarriers. To circumvent the resulting computational hurdle, tight and conservative approximations of the chance constraint are introduced to break the coupling and enforce separability per subcarrier. The separableproblem across subcarriers opens the door to the dual decomposition approach, which leads to a near-optimal and computationally efficient solution.
  • Thumbnail Image
    Item
    Fast exact algorithms for optimization problems in resource allocation and switched linear systems
    (2019-06) Wu, Zeyang
    Discrete optimization is a branch of mathematical optimization where some of the decision variables are restricted to real values in a discrete set. The use of discrete decision variables greatly expands the scope and capacity of mathematical optimization models. In the era of big data, efficiency and scalability are increasingly important in evaluating the performance of an algorithm. However, discrete optimization problems usually are challenging to solve. In this thesis, we develop new fast exact algorithms for discrete optimization problems arising in the field of resource allocation and switched linear systems. The first problem is the discrete resource allocation problem with nested bound constraints. It is a fundamental problem with a wide variety of applications in search theory, economics, inventory systems, etc. Given $B$ units of resource and $n$ activities, each of which associated with a convex allocation cost $f_i(\cdot)$, we aim to find an allocation of resources to the $n$ activities, denoted by $\bm{x} \in \Ze^n$, to minimize the total allocation cost $\sum\limits_{i = 1}^{n} f_i(x_i)$ subject to the total amount of resource constraint as well as lower and upper bound constraints on total resource allocated to subsets of activities. We develop a $\Theta(n^2\log\frac{B}{n})$-time algorithm for it. It is an infeasibility-guided divide-and-conquer algorithm and the worst-case complexity is usually not achieved. Numerical experiments demonstrate that our algorithm significantly outperforms a state-of-the-art optimization solver and the performance of our algorithm is competitive compared to the algorithm with the best worst-case complexity for this problem in the literature. The second problem is the minimum convex cost network flow problem on the dynamic lot size network. In the dynamic lot size network, there are one source node and $n$ sink nodes with demand $d_i, i = 1, \dots, n$. Let $B = \sum_{i=0}^{n}d_i$ be the total demand. We aim to find a flow $\bm{x}$ to minimize the total arc cost and satisfy all the flow balance and capacity constraints. Many optimization models in the literature can be seen as special cases of this problem, including dynamic lot-sizing problem and speed optimization. It is also a generalization of the first problem. We develop the Scaled Flow-improving Algorithm. For the continuous problem, our algorithm finds a solution that is at most $\epsilon$ away from an optimal solution in terms of the infinity norm in $O(n^2\log{\frac{B}{n\epsilon}})$ time. For the integer problem, our algorithm terminates in $O(n^2\log\frac{B}{n})$ time. Our algorithm has the best worst-case complexity in the literature. In particular, it solves the discrete resource allocation problem with nested bound constraints in $O(n\log{n}\log\frac{B}{n})$ time and it also achieves the best worst-case complexity for that problem. We conduct extensive numerical experiments on instances with a variety of convex objectives. The numerical result demonstrates the efficiency of our algorithm in solving large-sized instances. The last problem is the optimal control problem in switched linear systems. We consider the following dynamical system that consists of several linear subsystems: $K$ matrices, each chosen from the given set of matrices, to maximize a convex function over the product of the $K$ matrices and the given vector.This simple problem has many applications in operations research and control, yet a moderate-sized instance is challenging to solve to optimality for state-of-the-art optimization software. We prove the problem is NP-hard. We propose a simple exact algorithm for this problem. Our algorithm runs in polynomial time when the given set of matrices has the oligo-vertex property, a concept we introduce for a set of matrices. We derive several easy-to-verify sufficient conditions for a set of matrices to have the oligo-vertex property. In particular, we show that a pair of binary matrices has the oligo-vertex property. Numerical results demonstrate the clear advantage of our algorithm in solving large-sized instances of the problem over one state-of-the-art global solver. We also pose several open questions on the oligo-vertex property and discuss its potential connection with the finiteness property of a set of matrices, which may be of independent interest.