Minimax Optimization by Algorithms Employing Modified Lagrangians (Short Papers)

Two general, modified Langrangian algorithms related to recent developments in nonlinear programming are presented. The methods give accurate results and are easy to program. An N-section transmission-line transformer is used as a test problem for minimax (equal ripple) optimization and the methods are compared to existing algorithms for network optimization.     

Self-Organizing Migrating Strategies Applied to Reliability-Redundancy Optimization of Systems

The reliability-redundancy allocation problem is a mixed-integer programming problem. It has been solved by using optimization techniques such as dynamic programming, integer programming, mixed-integer non-linear programming, heuristics, and meta-heuristics. Meanwhile, the development of meta-heuristics has been an active research area in optimizing system reliability wherein the redundancy, the component reliability, or both are to be determined. In recent years, a broad class of stochastic algorithms, such as simulated annealing, evolutionary computation, and swarm intelligence algorithms, has been developed for reliability-redundancy optimization of systems. Recently, a new class of stochastic optimization algorithm called SOMA (Self-Organizing Migrating Algorithm) has emerged. SOMA works on a population of potential solutions called specimen, and is based on the self-organizing behavior of groups of individuals in a "social environment". This paper introduces a modified SOMA approach based on a Gaussian operator to solve reliability-redundancy optimization problems. In this context, three examples of mixed integer programming in reliability-redundancy design problems are evaluated. In this application domain, SOMA was found to outperform the previously best-known solutions available.     

Reliability Optimization by Generalized Lagrangian-Function and Reduced-Gradient Methods

Nonlinear optimization problems for reliability of a complex system are solved using the generalized Lagrangian function (GLF) method and the generalized reduced gradient (GRG) method. GLF is twice continuously differentiable and closely related to the generalized penalty function which includes the interior and exterior penalty functions as a special case. GRG generalizes the Wolfe reduced gradient method and has been coded in FORTRAN title ``GREG' by Abadie et al. Two system reliability optimization problems are solved. The first maximizes complex-system reliability with a tangent cost-function; the second minimizes the cost, with a minimum system reliability. The results are compared with those using the Sequential Unconstrained Minimization Technique (SUMT) and the direct search approach by Luus and Jaakola (LJ). Many algorithms have been proposed for solving the general nonlinear programming problem. Only a few have been demonstrated to be effective when applied to large-scale nonlinear programming problems, and none has proved to be so superior that it can be classified as a universal algorithm. Both GLF and GRG methods presented here have been successfully used in solving a number of general nonlinear programming problems in a variety of engineering applications and are better methods among the many algorithms.     

Review of Optimal Reliability Design, Fundamentals and Applications

This reference covers the extent of the state-of-the-art in optimizing systems reliability. The book consists of fifteen chapters and an appendix. The main part of the book is organized by problem type and solution method. Some of the topics covered include: redundancy allocation methods using heuristics, dynamic programming solutions and discrete optimization methods; reliability optimization using nonlinear programming and meta-heuristic algorithms; and methods to solve reliability-redundancy optimization. The book may serve as a textbook for students or as a reference for researchers and practitioners. It is a comprehensive book that is recommended for anyone concerned with designing reliable systems.     

An Introduction to Convex Optimization for Communications and Signal Processing

Convex optimization methods are widely used in the design and analysis of communication systems and signal processing algorithms. This tutorial surveys some of recent progress in this area. The tutorial contains two parts. The first part gives a survey of basic concepts and main techniques in convex optimization. Special emphasis is placed on a class of conic optimization problems, including second-order cone programming and semidefinite programming. The second half of the survey gives several examples of the application of conic programming to communication problems. We give an interpretation of Lagrangian duality in a multiuser multi-antenna communication problem; we illustrate the role of semidefinite relaxation in multiuser detection problems; we review methods to formulate robust optimization problems via second-order cone programming techniques.     

Neighbor discovery and routing schemes for mobile ad-hoc networks with beamwidth adaptive smart antennas

With the rapid development of high-speed railway (HSR) system, there is an increasing demand on providing high throughput and continuous multimedia (CM) services for HSR passengers. In this paper, we investigate the downlink resource allocation problem for on-demand CM services in HSR OFDMA systems with a cellular/infostation integrated network architecture. Considering both the integrity and continuity of service transmission, the resource allocation problem is formulated as a two-stage optimization programming. The aim of this study is to maximize the total reward of delivered services then to minimize the weighted total number of cumulative discontinuity packets over the trip of the train. To resolve the difficulty of multi-stage optimization, an equivalent one-stage programming is proposed. Since the resultant mixed integer programming is NP-hard in general, we reformulate it as a sparse \(\ell _{0}\)-minimization problem and then relax it to a linear programming. Furthermore, a reweighted \(\ell _1\)-minimization technique is applied to improve the system performance. Guided by the proposed optimization approaches, we next develop two efficient online resource allocation algorithms for practical systems,where a-priori knowledge of future service arrivals and channel gains is not available. Finally, simulation results are provided to validate the feasibility and effectiveness of the proposed algorithms.     

A Unified Review of Optimization

The main objective of this paper is to give a survey of recent automatic optimization methods which either have found or should find useful application in the area of computer-aided network design. Huang's family of algorithms for unconstrained optimization is reviewed. The Fletcher method and the Charalambous family of algorithms for unconstrained optimization, which abandon the "full linear search," are presented. Special emphasis is devoted to algorithms by Bandler and Charalambous on least pth and minimax optimization which can be readily programmed and used. Due to work by Bandler and Charalambous, it is shown how constrained minimax problems can be solved exactly as unconstrained minimax problems by using a new approach to nonlinear programming. The application of minirnax optimization on the design of lumped-distributed active filters, problems for future investigation, and a select list of references are also included.     

A new class of B/W halftoning algorithms

A new class of dithering algorithms for black and white (B/W) images is presented. The basic idea behind the technique is to divide the image into small blocks and minimize the distortion between the original continuous-tone image and its low-pass-filtered halftone. This corresponds to a quadratic programming problem with linear constraints, which is solved via standard optimization techniques. Examples of B/W halftone images obtained by this technique are compared to halftones obtained via existing dithering algorithms.     

Coverage planning for optimizing HSDPA performance and?controlling R99 soft handover

Coverage planning is an important engineering task in deploying UMTS networks implementing both high speed downlink packet access (HSDPA) and Release 99 (R99) services. Coverage planning amounts to determining the cell coverage pattern by means of setting the common pilot channel (CPICH) power of the cells. A conventional strategy is to uniformly allocate a proportion of the total power to CPICH. In this paper, we develop mathematical modeling and optimization approaches to bring the benefit of power saving enabled by optimizing non-uniform CPICH to enhance HSDPA performance, while preserving a desired degree of soft handover (SHO) for R99. The study focuses on HSDPA performance at cell edges, where data throughput is typically low. An integer linear programming model is developed for the resulting optimization problem. The model admits optimal or near-optimal planning solutions for relatively small networks. Solution algorithms based on local search and repeated local search are developed. These algorithms are able to perform the optimization for large-scale networks time-efficiently. Experimental results for both synthesized networks as well as instances originating from real planning scenarios demonstrate the benefit of our optimization approach.     

基于云接入网络的多目标资源分配算法设计

由于可以有效地提高频谱效率,能量效率与前程效率,云接入网络（C-RAN）被认为是未来第五代无线网络中的重要组成部分。不同于传统蜂窝网络,在云接入网络中,基带处理单元（BBU）被从基站分离,并聚合成一个中央计算云。无论如何,这些优化目标（频谱效率,能量效率,前程效率）在大多数情况下相互冲突,并且单个目标性能提升通常会导致其他目标性能的下降。据作者所知,在云接入网络中的多目标优化(MOO)问题,仍未被考虑过。在本文中,我们针对基于正交频分多址(OFDMA)的云接入网络,设计对应的联合优化算法以解决多目标优化问题。仿真结果显示,比起仅考虑单目标优化,本文提出的算法可以有效的解决不同优化目标之间的权衡,并且为云接入网络的资源分配提供一个新的方向。      

Resource Allocation and Adaptive Modulation in Uplink SC-FDMA Systems

In this paper, we study joint power and sub-channel allocation, and adaptive modulation in Single Carrier Frequency Division Multiple Access (SC-FDMA) which is adopted as the multiple access scheme for the uplink in the 3GPP-LTE standard. A sum-utility maximization problem is considered. Unlike OFDMA, in addition to the restriction of allocating a sub-channel to one user at most, the multiple sub-channels allocated to a user in SC-FDMA should be consecutive as well. This renders the resource allocation problem prohibitively difficult and the standard optimization tools (e.g., Lagrange dual approach widely used for OFDMA, etc.) can not help towards its optimal solution. We propose a novel optimization framework for the solution of this problem which is inspired from the recently developed canonical duality theory. We first formulate the optimization problem as binary-integer programming problem, and then transform this binary-integer programming problems into a continuous space canonical dual problem that is a concave maximization problem. Based on the solution of the continuous space dual problem, we derive joint power and sub-channel allocation algorithm whose computational complexity is polynomial. We provide conditions under which the proposed algorithms are optimal. We also propose an adaptive modulation scheme which selects an appropriate modulation strategy for each user. We compare the proposed algorithm with the existing algorithms in the literature to assess their performance. The results show a tremendous performance gain.     

GPUBlocks: GUI Programming Tool for CUDA and OpenCL

Recent advances in general-purpose graphics processing units (GPGPUs) have resulted in massively parallel hardware that is widely available to achieve high performance in desktop, notebook, and even mobile computer systems. While multicore technology has become the norm of modern computers, programming such systems requires the understanding of underlying hardware architecture and hence posts a great challenge for average programmers, who might be professionals in specific domains, but not experts in parallel programming. This paper presents a GUI tool called GPUBlocks that can facilitate parallel programming on multicore computer systems. GPUBlocks is developed based on the OpenBlocks framework, an extendable tool for graphical programming, to construct the GUI-based programming environment for CUDA and OpenCL parallel computing platforms. Programmers simply need to drag-n-drop blocks, fill the fields of the blocks, and connect them according to array or matrix computations that are specified by algorithms. GPUBlocks can then translate block-based code to CUDA or OpenCL programs. Furthermore, a couple of optimization constructs have also been offered for rapid program optimization. Experimental results have shown that the generated CUDA and OpenCL programs can achieve reasonable speedups on GPUs. Consequently, GPUBlocks can be used as a tool for fast prototyping of GPU applications or a platform for educational parallel programming.

     

考虑收发机损耗的多小区多用户下行链路波束成形算法

在现有收发机损耗模型基础上以最小化最差用户均方误差或者最小化用户均方误差之和为优化目标,设计一种考虑收发机残留损耗的多小区多用户下行链路波束成形算法。通过将优化问题转化成二阶锥规划的标准形式,并设计分层优化迭代算法来求解原始问题。数值仿真表明,相对于传统收发机的波束成形算法而言,所提算法将极大地减小收发机损耗对系统性能的影响,进而显著提高系统性能。     

Link optimization for energy‐constrained wireless networks with packet retransmissions

With the objective to minimize the energy consumption for packet based communications in energy‐constrained wireless networks, this paper establishes a theoretical model for the joint optimization of the parameters at the physical layer and data link layer. Multilevel quadrature amplitude modulation (MQAM) and automatic repeat request (ARQ) techniques are considered in the system model. The optimization problem is formulated into a three dimensional nonlinear integer programming (NIP) problem with the modulation order, packet size, and retransmission limit as variables. For the retransmission limit, a simple search method is applied to degenerate the three dimensional problem into a two dimensional NIP problem, for which two optimization algorithms are proposed. One is the successive quadratic programming (SQP) algorithm, combining with the continuous relaxation based branch‐and‐bound method, which can obtain the global optimal solution since the continuous relaxation problem is proved to be hidden convex. The other is a low‐complexity sub‐optimal iterative algorithm, combining with the nearest‐neighboring method, which can be implemented with a polynomial complexity. Numerical examples are given to illustrate the optimization solution, which suggests that the joint optimization of the physical/data link layer parameters contributes noticeably to the energy saving in energy‐constrained wireless networks. Copyright © 2010 John Wiley & Sons, Ltd.     

基于特征线方法的无源传输线模型

基于特征线方法的传输线模型只能保证模型的因果性,但是不能保证模型的无源性。针对上述问题,该文提出了一种无源性补偿方法来实现传输线宏模型的无源性。该方法扩展了现有的用于集总模型的无源性补偿算法,以等式约束的二次规划方法为基础,采用拉格朗日乘数法进行优化。数值例子表明该方法在有限的仿真时间内产生了精确的无源宏模型。     

Optimal apportionment of reliability and redundancy in seriessystems under multiple objectives

A multiobjective reliability apportionment problem for a series system with time-dependent reliability is presented. The resulting mathematical programming formulation determines the optimal level of component reliability and the number of redundant components at each stage. The problem is a multiobjective, nonlinear, mixed-integer mathematical programming problem, subject to several design constraints. Sequential unconstrained minimization techniques in conjunction with heuristic algorithms are used to find an optimum solution. A generalization of the problem in view of inherent vagueness in the objective and the constraint functions results in an ill-structured reliability apportionment problem. This multiobjective fuzzy optimization problem is solved using nonlinear programming. The computational procedure is illustrated through a numerical example. The fuzzy optimization techniques can be useful during initial stages of the conceptual design of engineering systems where the design goals and design constraints have not been clearly identified or stated, and for decision making problems in ill-structured situations     

New peak-to-average power-ratio reduction algorithms for multicarrier communications

New peak-to-average power-ratio (PAPR) reduction algorithms for multicarrier systems are developed by modifying the modulation constellation in active subcarriers and the modulation symbols in unused subcarriers. The proposed algorithms yield optimal PAPR-reduction solutions. For real-baseband multicarrier systems, the proposed PAPR-reduction algorithm is developed using a fast linear programming approach and considerable performance improvement can be achieved relative to that achieved with several existing algorithms. For passband multicarrier systems, a new PAPR-reduction algorithm is constructed whereby the associated minimax optimization problem is solved using an accelerated least-p th algorithm. Simulation results are presented which demonstrate that the proposed algorithm outperforms an algorithm due to Jones and that improved PAPR reduction can be achieved when the proposed algorithm is combined with another algorithm known as selective mapping scheme.     

Joint Optimization of Transmit Power-Time and Bit Energy Efficiency in CDMA Wireless Sensor Networks

In this paper, we address the problem of minimizing energy consumption in a CDMA-based wireless sensor network (WSN). A comprehensive energy consumption model is proposed, which accounts for both the transmit and circuit energies. Energy consumption is minimized by jointly optimizing the transmit power and transmission time for each active node in the network. The problem is formulated as a non-convex optimization. Numerical as well as closed-form approximate solutions are provided. For the numerical solution, we show that the formulation can be transformed into a convex geometric programming (GP), for which fast algorithms, such as interior point method, can be applied. For the closed-form solution, we prove that the joint power/time optimization can be decoupled into two sequential sub-problems: optimization of transmit power with transmission time serving as a parameter, and then optimization of the transmission time. We show that the first sub-problem is a linear program while the second one can be well approximated as a convex programming problem. Taking advantage of these analytical results, we further derive the per-bit energy efficiency. Our results are verified through numerical examples and simulations     

QoE-based routing algorithms for H.264/SVC video over ad-hoc networks

Multi-hop relaying combined with scarcity of wireless resources in ad-hoc networks can deteriorate the quality of service. As a result, one of the major challenges in video streaming over ad-hoc networks is enhancing users’ experience and network utilization. The emergence of scalable video coding standard enables smooth adaptation of video quality to network conditions. In this paper, we study two optimization problems: (1) maximize the global quality of experience of all users and (2) maximize the number of qualified streams. We formulate the both problems as mixed integer linear programming problems. These optimization problems are shown to be NP-hard. Consequently, we propose heuristic algorithms to solve them. Simulation results show that the proposed algorithms can provide the near-optimal video quality while the calculation times are much shorter than the one of optimal solution.     

Distributed Lifetime and Data Rate Optimization with Dynamic Approximation in Wireless Networks

In this paper, we study the problem of jointly maximizing network lifetime and data rate in wireless networks. For this problem, we introduce a general network utility maximization (NUM) cross-layer formulation that accommodates routing, scheduling and stream control from different layers of network with relevant constraints. In particular, based on both Lagrangian approach and Markov Chain Monte Carlo method, we extend our programming model to distributed algorithms that can dynamically approximate the optimal solution to this problem. Finally, we present computational results for the insight that can be gained from the cross-layer optimization and the distributed algorithms.