Optimization problems with nonlinear cost functions and combinatorial constraints appear in many real-world applications but remain challenging to solve efficiently compared to their linear counterparts. To bridge this gap, we propose $\textbf{\emph{\texttt{SurCo}}}$ that learns linear $\underline{\text{Sur}}$rogate costs which can be used in existing $\underline{\text{Co}}$mbinatorial solvers to output good solutions to the original nonlinear combinatorial optimization problem. The surrogate costs are learned end-to-end with nonlinear loss by differentiating through the linear surrogate solver, combining the flexibility of gradient-based methods with the structure of linear combinatorial optimization. We propose three $\texttt{SurCo}$ variants: $\texttt{SurCo}-\texttt{zero}$ for individual nonlinear problems, $\texttt{SurCo}-\texttt{prior}$ for problem distributions, and $\texttt{SurCo}-\texttt{hybrid}$ to combine both distribution and problem-specific information. We give theoretical intuition motivating $\texttt{SurCo}$, and evaluate it empirically. Experiments show that $\texttt{SurCo}$ finds better solutions faster than state-of-the-art and domain expert approaches in real-world optimization problems such as embedding table sharding, inverse photonic design, and nonlinear route planning.

Many common instances of power control problems for cellular and cell-free massive MIMO networks can be interpreted as max-min utility optimization problems involving affine interference mappings and polyhedral constraints. We show that these problems admit a closed-form solution which depends on the spectral radius of known matrices. In contrast, previous solutions in the literature have been indirectly obtained using iterative algorithms based on the bisection method, or on fixed-point iterations. Furthermore, we also show an asymptotically tight bound for the optimal utility, which in turn provides a simple rule of thumb for evaluating whether the network is operating in the noise or interference limited regime. We finally illustrate our results by focusing on classical max-min fair power control for cell-free massive MIMO networks.

Advanced wireless communication use cases relying on sidelinks require guaranteed network performance. However, fulfilling the desired Quality-of-Service (QoS) requirements can-not be always ensured due to factors such as varying interference and dynamicity in the network. To reduce the impact of varying network performance on sidelink applications, we address the problem of long-term proactive adaptation of sidelink applications based on network performance. Specifically, we propose a modular algorithmic framework comprising of data-driven prediction models and model-based optimization to predict the feasibility of given application data rate requirements. Further-more, the framework is capable of predicting the simultaneously achievable data rate demands (in the max-min sense). A vehicular communication scenario is considered as an example to show the applicability of the framework. Evaluations show that variations in feasibility and achievable data rate demands can be well captured to enable robust application layer adaptations.

ONE5G (E2E-aware Optimizations and advancements for the Network Edge of 5G New Radio) is an European funded collaborative project, aiming at designing Radio Access Network (RAN) enhancements to address the multiplicity of services and deployment scenarios for 5G. The project will build upon the specification already defined in 3GPP to propose advanced link techniques and optimization schemes taking into account an end-to-end (E2E) performance view. This paper describes the scenarios considered in the project and the set of uses cases considered, as well as the approach to define Key Performance Indicators reflecting the E2E performance. The technical areas investigated in the project are presented, as well as the planned prototypes.

For time division duplex systems with increased bandwidth in 5G, the concept of self-contained transmission has been proposed. Aiming at reduced latency and more flexible resource allocation, this concept involves frequent uplink and downlink switching and relatively short transmission in both directions. In this work, we consider single OFDM symbol transmission within self-contained transmission time intervals. Focusing on OFDM with pulse shaping, we propose a pulse shape with smooth transients in the time domain. Performance evaluation shows that an OFDM system with the proposed pulse shape exhibits better robustness against both noise and self-interference in comparison to the OFDM system with cyclic prefix. From the implementation point of view, pulse shaping requires only small modification to the transceiver and negligible computational complexity increase.

This paper studies the convergence of a fixed point iteration algorithm for the problem of max-min signal-to-interference ratio (SIR) balancing. Differently from the existing work on the subject, the interference in the system is assumed to fall into the axiomatic framework of general interference functions. Monotonicity of the extremal SIR values during the iterations of the algorithm is shown. In the case of strictly monotonic interference functions, a novel sufficient condition for the convergence of the algorithm to an optimal solution is derived. The obtained condition is easily verifiable, and presents a generalization of a related requirement for the power method from matrix analysis. It is also shown how the results transfer to the power-constrained case and standard interference functions.

We provide a combinatorial characterization of interference coupling in wireless systems, with the intent of obtaining a better insight into interference coordination and management. We introduce two bipartite graphs, namely the power graph and interference graph. We utilize these graphs and global dependency matrix containing only binary (0 and 1) entries to capture the effects of interference coupling in communication systems. We show that the irreducibility of the global dependency matrix G is related to the connectivity of the power graph and the irreducibility of the matrix GGTis related to the connectivity of the interference graph. We prove that for strictly positive and strictly log-convex interference functions, the irreducibility of the matrices G and GGTare necessary and sufficient conditions for the considered utility sets to be strictly convex. In this case there exists a unique optimizer for the problem of maximizing the product of utilities. We show that an interference balancing function is strictly log-convex, if and only if matrices G and GGTare irreducible. We provide a simple yet comprehensive combinatorial characterization of interference coupled systems which abstracts away certain complexities of the physical layer.

Many solutions and concepts in resource allocation and game theory rely on the assumption of a convex utility set. In this paper, we show that the less restrictive assumption of a logarithmic “hidden” convexity is sometimes sufficient. We consider the problems of Nash bargaining and proportional fairness, which are closely related. We extend the Nash bargaining framework to a broader family of log-convex sets. We then focus on the set of feasible signal-to-interference-plus-noise ratios (SINRs), for the cases of individual power constraints and a sum power constraint. Under the assumption of log-convex interference functions, we show how Pareto optimality of boundary points depends on the interference coupling between the users. Finally, we provide necessary and sufficient conditions for strict log-convexity of the feasible SINR region.

Pareto optimality is an important property in game theory and mechanism design, which can be utilized to design resource allocation strategies in wireless systems. We analyze the structure of the boundary points of certain utility sets based on interference functions. We particularly investigate the cases with no power constraints, with individual power constraints, and with a total power constraint. We display the dependency between Pareto optimality and interference coupling in wireless systems. An axiomatic framework of interference functions and a global dependency matrix is used to characterize interference coupling in wireless systems. The relationship between interference-balancing functions and Pareto optimality of the boundary points is elucidated. Among other results, it is shown that the boundary points of utility sets with individual power constraints and with strictly monotonic interference functions are Pareto-optimal if and only if the corresponding restricted global dependency matrix is irreducible. The obtained results provide certain insight when suitable algorithms can be designed for network utility maximization.

We establish a general optimization framework for joint resource allocation and interference mitigation. By utilizing axiomatic interference functions, our problem formulation is very general and includes many problems as special cases. We consider the sum rate maximization problem, which is known to be NP hard. It is shown that due to the structural model of the interference function, the joint optimization of powers and adaptive receive strategies ends up with the optimization solely with respect to powers. This facilitates a reformulation of the problem under consideration as a problem of difference of convex functions (DC). Based on this DC representation, we employ a prismatic branch and bound algorithm to find a global optimum.

In this paper we analyze the structure of certain power-constrained utility sets, based on the axiomatic framework of log-convex interference functions. Log-convex interference functions contain convex and linear interference functions as a special case. We analyze the boundary of the set. It is shown how Pareto optimality of boundary points depends on the interference coupling between the users. Finally, we investigate feasible sets of signal-to-interference-plus-noise ratios for individual power constraints and a sum power constraint. We show certain properties that are desirable, e.g. in the context of cooperative game theory.

The paper addresses the problem of interference modeling for wireless networks. Two axiomatic frameworks are known from the literature: (1) standard interference functions introduced by Yates in [JSAC 1995], and (2) general interference functions proposed by the authors in their previous work. In this paper, both frameworks are analyzed and compared. It is shown that (1) is contained in the more general framework (2). This means that certain structure results, which were recently derived for (2) can also be applied to (1). A focus of this paper is on convexity and concavity properties, which are important because they often lead to interesting algorithmic opportunities. The results provide a bridge between both frameworks, which have been studied separately in the past.

Interference in multiuser systems is often characterized by a non-negative and irreducible coupling matrix. The maximum eigenvalue (Perron root) of the weighted coupling matrix provides a single measure for the joint achievability of certain signal-to-interference ratios (SIR). In this paper, we address the more general case where the users are coupled by concave interference functions. This corresponds to a system with adaptive receive strategies which minimize the interference received by each user. A necessary and sufficient condition for feasibility is obtained by minimizing the Perron root over the set of possible receive strategies. This type of problem is directly related to the problem of (weighted) max-min-SIR balancing. This paper provides an analytical framework and an iterative algorithm that converges monotonically to a global optimum. We also study an alternative approach based on a fixed point iteration. This iteration is shown to converge to the global optimum if the SIR targets lie on the boundary of the region.

Collective choice functions and an axiomatic framework will be used to characterize the structure of solutions of resource allocation problems on feasible utility sets. Feasible utility sets will be characterized as level sets of general interference functions. General fairness constraints will be introduced and solution outcomes satisfying the properties of efficiency, robustness and fairness will be analyzed. A new type of sets, basic bargaining sets will be defined and if the properties of the solution outcome are known on these sets then we know it's properties for all feasible utility regions.

For comprehensive convex compact positive utility sets, the Nash bargaining solution (NBS) is obtained by maximizing a product of utilities, a strategy which is also known as "proportional fairness". However, the standard assumption of convexity may not be fulfilled. This is especially true for wireless communication systems, where interference and adaptive techniques can lead to complicated non-convex utility sets (e.g. the 2-user SIR region with linear receivers). In this paper, we show that the Nash bargaining framework can be extended to certain non-convex utility sets, whose logarithmic transformation is strictly convex comprehensive. As application examples, we consider feasible sets of signal-to-interference ratios (SIR), based on axiomatic log-convex interference functions. The resulting SIR region is known to be log-convex. However, strict log-convexity and compactness is required here. We derive conditions under which this is fulfilled. In this case, there is a single-valued Nash bargaining solution, which is equivalent to the proportionally fair operating point. The results are shown for a total power constraint, as well as for individual power constraints.

Cooperative transmission with multiple base stations is a way to overcome the interference limitation of conventional cellular system. We investigate the problem of linear transceiver design for such a network Multiple-Input-Multiple- Output (MIMO) system with per-base-station power constraints. Four design goals are considered: minimizing the total sum-MSE subject to per-base-station power constraints; minimizing the total transmit power subject to a total sum-MSE target and per-base-station power constraints; minimizing the maximum weighted user-MSE subject to per-base-station power constraints; minimizing the total transmit power subject to a set of user-MSE targets and per-base-station power constraints. For these problems, we derive globally optimal transmitters by reformulating the problems as convex Second Order Cone Programs (SOCPs). We also propose iterative algorithms for joint transmitter/receiver optimization. The joint transceiver optimization exploits that for the optimal transmitter, the receivers can be updated as linear MMSE filters. We prove that the proposed algorithms converge to local optima due to the non-convexity of the problems.

This paper provides a theoretical framework for the analysis of interference-coupled multiuser systems. The fundamental behavior of such a system is modeled by interference functions, defined by axioms ldquononnegativity, rdquoscale-invariance,rdquo and ldquomonotonicity.rdquo It is shown that every interference function has an interpretation as the optimum of a min-max problem, where the optimization is over a closed comprehensive positive coefficient set. This provides new insight into the structure of general interference functions and its elementary building blocks. Conversely, it is shown that every closed comprehensive positive set can be expressed as a level set of an interference function. This shows a close connection between the analysis of interference functions and multiuser performance regions, which are typically closed comprehensive. The generality of this framework allows for a wide range of potential applications. As an example, we analyze the problem of interference balancing.

The behavior of certain interference-coupled multiuser systems can be modeled by means of logarithmically convex (log-convex) interference functions. In this paper, we show fundamental properties of this framework. A key observation is that any log-convex interference function can be expressed as an optimum over elementary log-convex interference functions. The results also contribute to a better understanding of certain quality-of-service (QoS) tradeoff regions, which can be expressed as sublevel sets of log-convex interference functions. We analyze the structure of the QoS region and provide conditions for the achievability of boundary points. The proposed framework of log-convex interference functions generalizes the classical linear interference model, which is closely connected with the theory of irreducible nonnegative matrices (Perron-Frobenius theory). We discuss some possible applications in robust communication, cooperative game theory, and max-min fairness.

We address the problem of interference coupling and achievability of SIR targets in a multiuser system. Interference is modeled by an axiomatic framework, with log-convex interference functions. There are efficient algorithms which perform optimization over the boundary of the SIR region, but they typically require that the boundary is achievable. We show that achievability is closely linked to the interference coupling in the system. This effect is already known from power control theory, where achievability is commonly ensured by assuming an irreducible coupling matrix. In this paper, we consider a more general interference model which is based on an axiomatic framework. In order to describe the interference coupling in the system, the concept of a dependency matrix is introduced. It is shown that the achievability of the boundary only depends on the combinatorial structure of this matrix. Necessary and sufficient conditions are derived.

This paper investigates the problem of transceiver design with individual rate constraints for multiuser MIMO systems. We focus on linear processing with two design goals: one is to maximize the minimum rate per user under a total power constraint, and the other is to minimize the total transmit power while maintaining certain rate requirements. The optimization is carried out in an alternating manner in both virtual uplink and downlink channels. Each iteration contains the optimization of uplink power allocation, and uplink and downlink MMSE receive filters. The uplink power control to balance the rates or to achieve the rate requirements is taken by optimizing the product of MSEs, which can be formulated as a geometric programming (GP) problem. Additionally, this alternating optimization approach is suitable for the case with successive interference cancellation (SIC) in the uplink and interference pre-compensation (IPC) in the downlink as well. With a fixed precoding ordering, this provides new sub-optimal solutions to the above problems.

We address the problem of maximizing the minimum signal-to-interference ratio (SIR) in a multiuser system. In the context of resource allocation, this is referred to as max-min fairness. Moreover, the balanced SIR margin is an indicator for feasibility, so the problem also plays a fundamental role for the characterization of the SIR achievable region and related regions. In this paper, we propose an iterative solution for max-min SIR balancing under the assumption of convex interference functions. It is proven that the proposed iteration always finds the unique global optimum. Similar results in the beamforming context [1] differ in two respects: Firstly, a much more general interference model is used. Secondly, the results a found by using a different analytical approach, which allows to show convergence directly, without the need of compactness arguments. This way, uniqueness of the optimum can be shown. Finally, we show that Yates' fixed-point iteration [2], which is successfully used in a different context, does generally not converge to the max-min optimum, unless an additional scaling is introduced.

This paper provides a theoretical framework for the analysis of interference-coupled multiuser systems. Interference is characterized by a set of axioms defining some fundamental properties. The generality of this approach allows for a wide range of potential applications, including adaptive receive strategies and worst-case designs. One main result is to show that every interference function has a max-min and a min-max representation over parameter-dependent elementary interference functions. The analysis of these elementary components provides new insight into the structure of general interference functions. In particular, every interference function can be interpreted as an optimum over a closed set with certain monotonicity properties. Under certain conditions this can be interpreted as an optimization of a network utility/cost over a multiuser QoS region. So the analysis of interference functions is closely connected with the analysis of multiuser QoS regions. The proposed framework provides a better general understanding of cross-layer optimization and resource allocation in the presence of interference.

We propose a generic framework for jointly optimizing the transmit power allocation and the adaptive receive strategies in a multiuser network with individual quality-of-service (QoS) requirements. The QoS is assumed to be a one-to-one mapping of the signal-to-interference-plus-noise ratio (SINR). The feasibility of certain target QoS depends on the mutual interference and on a given sum-power constraint. This coupling can be modeled by interference functions, which determine how the transmit powers cause interference to the individual users. We show fundamental properties, like continuity and feasibility for the most general case when the functions are defined by axioms. Additional properties are shown for the case when the interference functions are based on a parameter-dependent coupling matrix, which allows to apply techniques from the theory of nonnegative matrices. We derive a class of iterative algorithms, which exploit the matrix structure. The proposed iteration converges monotonically to the global optimum. Starting from the same initialization, it is better than the known fixed-point iteration. It achieves arbitrary QoS values within the QoS-feasible region.

We propose a general framework for joint resource allocation and interference control for classes of interference functions based on an axiomatic model. This model holds for a wide range of multiuser channels and even allows the incorporation of interference suppression techniques. The quality of service (QoS) of each user is modeled as a function of the interference. It is shown that for certain mappings between interference and QoS, the resulting achievable region is a convex set. Furthermore, we show that the problem of optimizing the sum of weighted QoS over the transmit powers is convex for certain classes of QoS functions. The choice of the weights determines the trade-off between fairness and overall efficiency. The problem can be solved efficiently by standard convex optimization techniques.

We address the problem of linear mean square error (MSE) transmitter design for point-to-multipoint multiuser systems, where the transmitter is equipped with multiple antennas and each of the independent receivers has a single antenna. This downlink scenario is more difficult to handle than its uplink counterpart, since all users are coupled by transmit filters and powers. Our main result is to show that downlink and uplink share the same normalized MSE achievable region under a sum power constraint. Thus, the problem of downlink transmitter design can be solved by focusing on an equivalent uplink problem, which has a more suitable structure and allows for efficient algorithmic solutions. As application examples, we solve the problem of minimizing the maximal normalized MSE of all users (fairness), and the problem of minimizing the sum of all normalized MSE (overall efficiency).

In this paper we study a cellular wireless system with joint beamforming and power allocation. All users are assumed to be coupled by co-channel interference. We address the problem of optimizing the sum of individually weighted QoS functions, where the weights can be used to trade-off the overall system efficiency against max-min fairness. A computationally efficient algorithm is proposed, which is shown to be monotonically convergent for any choice of weighting factors. Finally, it is shown how the weights must be chosen in order for the algorithm to converge towards optimal max-min fairness.

We study the geometry of the feasible MSE region of multiuser MIMO systems with fixed transmitters and receivers. The sum of all powers is assumed to be constrained. We consider both linear processing and non-linear processing, i.e., interference pre-compensation in the downlink and successive interference cancellation in the uplink. We show that, for both cases, the feasible MSE region of uplink and downlink is a convex set. In addition, we show for adaptive multiuser reception/precoding, that the maximal feasible MSE region for two-user beamforming systems with adaptive MMSE filtering are convex.

The problem of joint multiuser beam-forming and power control can be reduced to the search of the minimal-norm element over a set of polynomial roots. This problem belongs to the field of semialgebraic geometry. In this paper we use semialgebraic techniques to show that the optimal power allocation is unique

We consider the problem of maximizing the throughput (sum rate) of the Gaussian MIMO broadcast channel under a sum power constraint. Assuming that decision feedback precoding is used at the transmitter, this is a concave optimization problem. A computationally efficient algorithm has been proposed (Jorswieck, E. and Boche, H., WPMC, 2002), which successively performs iterative waterfilling and power control. This strategy is based on uplink/downlink duality. We expand those results, by providing necessary and sufficient conditions for when this dedicated strategy achieves the optimal sum capacity. For the low SNR regime, it is shown that the capacity achieving strategy is single user transmission over the channel with the largest maximal eigenvalue. Furthermore, we illustrate, by numerical simulations, the properties of the sum capacity without precoding.

We study optimization criteria for uplink and downlink wireless transmission, assuming that the base station is equipped with multiple antennas and the mobiles have single antennas. In particular, we focus on the mean effective bandwidth, which provides a measure for the overall quality of the multiuser channel. In the uplink, maximizing the mean effective bandwidth is a convex optimization problem, which can be solved by standard optimization tools. The downlink has a more complicated analytical structure, which prevents direct optimization. In this work we make use of the duality between uplink and downlink, which facilitates an indirect approach: the optimizer of the downlink mean effective bandwidth is found by first solving the convex uplink problem, then adjusting the downlink transmission powers.

We address the problem of joint downlink beamforming and power control in a wireless cellular system, where several users share the same time slot and the same frequency band. In order to enable a fair sharing of resources among all users, the SIR levels should be balanced by minimizing the ∞-norm of a certain vector. To this end, Gerlach and Paulraj [1] proposed an iterative algorithm, which is based on a 1-norm cost function. It has been observed that this algorithm approximates the optimum ∞-norm solution. In this paper we characterize the case where this algorithm is optimal. The analytical results are used to develop a new algorithm, which always converges to the optimum ∞-norm solution, regardless of the chosen initialization. A proof of convergence is given.

The downlink spectral efficiency of interference limited wireless systems can be drastically increased by employing multiuser transmit beamforming at the base station. The goal is the joint optimization of the user transmission powers and the beamforming weights. An important problem is to find the range where a feasible solution can be expected. Recently, it has been shown (see Boche, H. and Schubert, M., European Trans. on Telecom., vol.12, no.5, p.417-26, 2001) that this problem is equivalent to the minimization of the maximum eigenvalue of the system coupling matrix. An iterative scheme to solve this min-max type problem was proposed by G. Montalbano and D.T.M. Slock (see Proc. IEEE ICUPC, 1998), but no convergence analysis was given. We analyze the convergence behavior of the algorithm and extend the results to the more general case of individual QoS requirements. It is shown that the iteration sequence is strictly monotonically decreasing as long as the global optimum is not reached. This proves the optimality of the algorithm and provides valuable insight into the analytical structure of the problem.

We address the problem of joint downlink beamforming and power control in a frequency flat multi-antenna broadcast channel. In this context, a common optimization strategy is to maximize the system throughput under a certain power constraint. This, however, does not guarantee a fair sharing of throughput among the users, which is required in case that the receivers cannot cooperate. Thus, we propose a different approach, which always assumes optimally balanced data rates. If the problem is feasible, i.e., desired target rates can be reached, spare degrees of freedom can be used in order to minimize the total transmission power. This strategy can even be applied if only spatial covariance channel information is available. The authors have developed a theoretical framework based upon uplink/downlink duality, feasibility considerations, and bounds on the maximal eigenvalue of the resulting coupling matrix. An overview of the results is given and they are discussed in the context of existing literature. Finally, a theoretical benchmark is provided for the case of perfect channel knowledge. Then, beamforming can be combined with Costa (1983) pre-coding, as proposed by Caire and Shamai (see 36th Asilomar Conf. on Signals, Systems and Computers Asilomar Pacific Grove, CA, Nov. 2001). This leads to a closed-form solution of the problem.

We address the problem of joint downlink beamforming and power control in interference limited cellular wireless systems. The goal is to support each user with a certain signal-to-interference level at the mobile. Several iterative algorithms have recently been proposed in the literature to solve this non-linear optimization problem. Obviously, no solution exists if the requirements are too demanding. This explains situations where the algorithms do not converge. On the other hand, the observation of convergence is only a necessary condition for the existence of a solution. We investigate the analytical structure of the problem and formulate a unifying framework. In particular, we provide a necessary and sufficient condition which can be used to judge whether or not a solution can be considered as valid. The results give new insights and may prove useful for the design of new fast convergent algorithms.

When using downlink beamforming at the base station of a cellular system, care must be taken to assure that all users satisfy the given SINR requirements. Generally, this leads to a computationally prohibitive joint optimization problem, therefore decoupled techniques based on eigenvalue decomposition of the spatial covariance have been proposed. However, these techniques require additional power adjustment of the steering vectors in order to satisfy the given SINR requirements. Conventional power control schemes are not suited for this purpose because the SINRs primarily depend on the shape of the radiation patterns. In this paper we propose a new power adjustment algorithm, which adjusts the beamforming weights, such that all users have the same SINR Additionally, it is possible to limit the maximum radiated user power.

Downlink beamforming has been proposed for high-capacity and spectrally-efficient DS-CDMA wireless systems. It mitigates the effects of multiple access interference, self interference and inter-cell interference. We propose a new direction-based downlink beamforming algorithm for frequency selective TD/CDMA multipath channels. It minimises the radiated array power while suppressing dominant interferers. By considering the directivity of the beam pattern, improved robustness and good spatial filtering properties are achieved. This approach also supports path diversity, assuming that a conventional RAKE is deployed at the mobile. Moreover, it can easily be expanded to facilitate space division multiple access (SDMA).

In this paper a new spatial filtering approach for the uplink space-time Rake receiver is investigated. Recent field trials have shown that classical beamforming algorithms are not always reliable in the presence of strong interference and rapidly time-varying channels. More robust beam pattern control can be achieved by combining null steering and directivity optimisation. The necessary directional information can be extracted from the covariance matrix, e.g. by code filtering. The main focus of this work is the analytical investigation of the capability of the beam pattern to suppress self-interference and multiple access interference (MAI). It is proved that for a large number of equally spaced interferers and under assumption of ideal power control, the SNIR is optimised by maximising the directivity of the beam pattern. In case of less ideal scenarios, additional nulls of the beam pattern may be placed. This approach can also be extended by an additional pilot signal, if available.