The non-negative matrix factorization (NMF) model with an additional orthogonality constraint on one of the factor matrices, called the orthogonal NMF (ONMF), has been found to provide improved clustering performance over the K-means. The ONMF model is a challenging optimization problem due to the orthogonality constraint, and most of the existing methods directly deal with the constraint in its original form via various optimization techniques. In this paper, we propose an equivalent problem reformulation that transforms the orthogonality constraint into a set of norm-based non-convex equality constraints. We then apply a penalty approach to handle these non-convex constraints. The penalized formulation is smooth and has convex constraints, which is amenable to efficient computation. We analytically show that the penalized formulation will provide a feasible stationary point of the reformulated ONMF problem when the penalty is large. Numerical results show that the proposed method greatly outperforms the existing methods.

Noncooperative game-theoretic tools have been increasingly used to study many important resource allocation problems in communications, networking, smart grids, and portfolio optimization. In this paper, we consider a general class of convex Nash equilibrium problems (NEPs), where each player aims at solving an arbitrary smooth convex optimization problem. Differently from most of current works, we do not assume any specific structure for the players' problems, and we allow the optimization variables of the players to be matrices in the complex domain. Our main contribution is the design of a novel class of distributed (asynchronous) best-response-algorithms suitable for solving the proposed NEPs, even in the presence of multiple solutions. The new methods, whose convergence analysis is based on variational inequality (VI) techniques, can select, among all the equilibria of a game, those that optimize a given performance criterion, at the cost of limited signaling among the players. This is a major departure from existing best-response algorithms, whose convergence conditions imply the uniqueness of the NE. Some of our results hinge on the use of VI problems directly in the complex domain; the study of these new kind of VIs also represents a noteworthy innovative contribution. We then apply the developed methods to solve some new generalizations of Single Input Single Output (SISO) and Multiple Input Multiple Output (MIMO) games in cognitive radio systems, showing a considerable performance improvement over classical pure noncooperative schemes.

We propose a decomposition framework for the distributed optimization of general nonconvex sum-utility functions arising in the design of wireless multi-user interfering systems. Our main contributions are: the development of the first provably convergent Jacobi best-response algorithm, where all users simultaneously solve a suitably convexified version of the original sum-utility optimization problem; the derivation of a general dynamic pricing mechanism that provides a unified view of existing pricing schemes that are based, instead, on heuristics; and a framework that can be easily particularized to well-known applications, giving rise to practical algorithms that outperform all existing ad-hoc methods proposed for very specific problems. Our framework contains as special cases well-known gradient algorithms for nonconvex sum-utility problems, and many block-coordinate descents schemes for convex functions.

In this paper, we propose a novel class of Nash problems for cognitive radio (CR) networks, modeled as Gaussian frequency-selective interference channels, wherein each secondary user (SU) competes against the others to maximize his own opportunistic throughput by choosing jointly the sensing duration, the detection thresholds, and the vector power allocation. The proposed general formulation allows us to accommodate several (transmit) power and (deterministic/probabilistic) interference constraints, such as constraints on the maximum individual and/or aggregate (probabilistic) interference tolerable at the primary receivers. To keep the optimization as decentralized as possible, global (coupling) interference constraints are imposed by penalizing each SU with a set of time-varying prices based upon his contribution to the total interference; the prices are thus additional variable to optimize. The resulting players' optimization problems are nonconvex; moreover, there are possibly price clearing conditions associated with the global constraints to be satisfied by the solution. All this makes the analysis of the proposed games a challenging task; none of classical results in the game theory literature can be successfully applied. The main contribution of this paper is to develop a novel optimization-based theory for studying the proposed nonconvex games; we provide a comprehensive analysis of the existence and uniqueness of a standard Nash equilibrium, devise alternative best-response based algorithms, and establish their convergence. Some of the proposed algorithms are totally distributed and asynchronous, whereas some others require limited signaling among the SUs (in the form of consensus algorithms) in favor of better performance; overall, they are thus applicable to a variety of CR scenarios, either cooperative or noncooperative, which allows the SUs to explore the existing tradeoff between signaling and performance.

In recent years, game-theoretic tools have been increasingly used to study many important resource allocation problems in communications and networking. One common feature shared by all these approaches is that, when it comes to (distributed) computation of equilibria, assumptions are always made that imply uniqueness of the Nash Equilibrium. This simplifies considerably the analysis of the games under investigation and permits to design distributed solution methods with convergence guarantee. However, requiring the uniqueness of the solution may be too demanding in many practical situations, thus strongly limiting the applicability of current game theoretical methodologies. In this paper, we overcome this limitation and propose novel distributed algorithms for noncooperative games having multiple solutions. The new methods, whose convergence analysis is based on variational inequality techniques, are able to select, among all the equilibria of a game, those which optimize a given performance criterion. We apply the developed methods to a power control problem over parallel Gaussian interference channels and show that they yield a considerable performance improvement over classical power control schemes.

The concept of cognitive radio has recently received great attention from the research community as a promising paradigm to achieve efficient use of the frequency resource by allowing the coexistence of primary and secondary users in the same bandwidth. In this paper, we propose a novel Nash equilibrium (NE) problem to model concurrent communications of cognitive secondary users who compete with each other to maximize their information rate, subject to constraints on the transmit power (and possibly spectral masks) as well as on per-carrier and total aggregate interference tolerable at the primary users' receivers. The coupling among the strategies of the players due to the interference constraints presents a new challenge for the analysis of this class of Nash games that cannot be addressed using the game theoretical models proposed in the literature. For this purpose, we need the framework given by the more advanced theory of finite-dimensional Variational Inequalities. This provides us with all the mathematical tools necessary to analyze the proposed NE problem (e.g., existence and uniqueness of the solution) and to devise alternative distributed algorithms along with their convergence properties.

Consider a scenario in which K users and a jammer have a limited power budget and share a common spectrum of N orthogonal tones. The goal of each user is to allocate its power across the N tones in such a way that maximizes the total sum rate that he/she can achieve, while treating the interference of other users and the jammer's signal as additive Gaussian noise. The jammer, on the other hand, wishes to allocate its power in such a way that minimizes the utility of the whole system; that being the total sum of the rates communicated over the network. For this non-cooperative game, we propose a generalized version of the existing iterative water-filling algorithm whereby the users and the jammer update their power allocations in a greedy manner. We study conditions under which the generalized iterative water-filling algorithm converges to a Nash equilibrium of the game. The conditions that we derive in this paper depend only on the system parameters, and hence can be checked a priori.

This paper considers the minimization of transmit power in Gaussian parallel interference channels, subject to a rate constraint for each user. To derive decentralized solutions that do not require any cooperation among the users, we formulate this power control problem as a (generalized) Nash equilibrium (NE) game. We obtain sufficient conditions that guarantee the existence and nonemptiness of the solution set to our problem. Then, to compute the solutions of the game, we propose two distributed algorithms based on the single user water-filling solution: Thesequentialand thesimultaneousiterative water-filling algorithms, wherein the users update their own strategies sequentially and simultaneously, respectively. We derive a unified set of sufficient conditions that guarantee the uniqueness of the solution and global convergence of both algorithms. Our results are applicable to all practical distributed multipoint-to-multipoint interference systems, either wired or wireless, where a quality of service in (QoS) terms of information rate must be guaranteed for each link.

A key step in many statistical learning methods used in machine learning involves solving a convex optimization problem containing one or more hyper-parameters that must be selected by the users. While cross validation is a commonly employed and widely accepted method for selecting these parameters, its implementation by a grid-search procedure in the parameter space effectively limits the desirable number of hyper-parameters in a model, due to the combinatorial explosion of grid points in high dimensions. This paper proposes a novel bilevel optimization approach to cross validation that provides a systematic search of the hyper-parameters. The bilevel approach enables the use of the state-of-the-art optimization methods and their well-supported softwares. After introducing the bilevel programming approach, we discuss computational methods for solving a bilevel cross-validation program, and present numerical results to substantiate the viability of this novel approach as a promising computational tool for model selection in machine learning.

We introduce computational support tools for the analysis and design of systems with multiple frictional contacts, with a focus on applications to part feeding and assembly processes. The tools rely on dynamic models of the processes. We describe two approaches to modeling, the Stewart-Trinkle model (1996) and the Song-Pang-Kumar model (2003), that allow the designer to experiment with different geometric, material and dynamic properties and optimize the design for performance. In order to accommodate contact transitions, we introduce a smooth cone model for friction. We illustrate the models and the design process by describing the design optimization of a part feeder.

This paper formally introduces several stability characterizations of fixtured three-dimensional rigid bodies initially at rest and in unilateral contact with Coulomb friction. These characterizations, weak stability and strong stability, arise naturally from the dynamic model of the system, formulated as a complementarity problem. Using the tools of complementarity theory, these characterizations are studied in detail to understand their properties and to develop techniques to identify the stability classifications of general systems subjected to known external loads.

Consider a system of bodies with multiple concurrent contacts. The multi-rigid-body contact problem is to predict the accelerations of the bodies and the normal and friction loads acting at the contacts. This paper presents theoretical results for the multi-rigid-body contact problem under the assumptions that one or more contacts occur over locally planar finite regions and friction forces are consistent with the maximum work inequality. We present an existence and uniqueness result for this problem under some mild assumptions on the system inputs. The application of our results to two examples is discussed.

Abstract In this paper, we study a special single‐commodity spatial equilibrium problem. We show how the problem is related to a shortest‐path problem and develop a simple algorithm for its solution. We also discuss an extension of the single‐commodity problem to a multicommodity problem.

Abstract This article discusses the solution of the fixed‐demand traffic equilibrium problem by certain linearized simplicial decomposition methods. These methods are derived from the family of linear approximation methods for solving a general variational inequality problem. The central idea of a linearized simplicial decomposition method is that instead of solving linear variational inequality subproblems over the entire set of feasible flows as in a typical linear approximation method, one solves the same subproblems over subsets of feasible flows where each such subset is defined explicitly by certain extreme points of the (polyhedral) set of feasible flows. A global convergence result of the linearized decomposition methods will be established under suitable assumptions on the change of the set of “working” extreme points in each iteration plus some standard conditions on the linear approximating mappings used. Extensive computational results with the use of such methods are reported. Sizes of problems solved range from relatively small to reasonably large.