Mixed-integer nonlinear programs are typically solved using branch-and-bound algorithms. A key determinant of the success of such methods is their ability to construct tight and tractable relaxations. The predominant relaxation strategy used by most state-of-the-art solvers is the factorable programming technique. This technique recursively traverses the expression tree for each nonlinear function and relaxes each operator over a bounding box that covers the ranges for all the operands. While it is versatile, and allows finer control over the number of introduced variables, the factorable programming technique often leads to weak relaxations because it ignores operand structure while constructing the relaxation for the operator.<div>In this thesis, we introduce new relaxations, called composite relaxations, for composite functions by convexifying the outer-function over a polytope, which models an ordering structure of outer-approximators of inner functions. We devise a fast combinatorial algorithm to separate the hypograph of concave-extendable supermodular outer-functions over the polytope, although the separation problem is NP-Hard in general. As a consequence, we obtain large classes of inequalities that tighten prevalent factorable programming relaxations. The limiting composite relaxation obtained with infinitely many outer-approximators for each inner-function is shown to be related to the solution of an optimal transport problem. Moreover, composite relaxations can be seamlessly embedded into a discretization scheme to relax nonlinear programs with mixed-integer linear programs. Combined with linearization, composite relaxations provide a framework for deriving cutting planes used in relaxation hierarchies and more.<br></div>

This thesis focuses on the concept of uniquely factorable constellations (UFCs) in the design of space-time block codes (STBCs) for wireless communication systems using three different approaches. Based on intelligent constellation collaboration, UFCs can provide the systematic design of a full diversity code with improved coding gain. Firstly, motivated by the energy-efficient hexagonal lattice carved from the Eisenstein integer domain, hexagonal UFCs and hexagonal uniquely factorable constellation pairs (UFCPs), of various sizes, are constructed for a noncoherent single-input multiple-output (SIMO) system. It is proved that these designs assure the blind unique identification of channel coefficients and transmitted signals in a noise-free case and full diversity for the noncoherent maximum likelihood (ML) receiver in a noisy case. In addition, an optimal energy scale is found to maximize the coding gain. Secondly, using a matrix similar to the Alamouti matrix and the UFCP concept based on the quadrature amplitude modulation (QAM) constellation, a novel energy-efficient unitary STBC is designed for a noncoherent multiple-input single-output (MISO) system with two transmitter antennas and one receiver antenna by using the QR decomposition. It is shown that the proposed UFCP-STBC design also allows for the blind unique identification of both the transmitted signals and channel coefficients as well as full diversity. In addition, an optimal unitary UFCP-STBC is devised to maximize the coding gain subject to a transmission bit rate constraint. The last approach is to demonstrate how the UFCP concept is applied to the systematic design of a coherent relay network coding system. A class of uniquely factorable Alamouti matrix pairs is proposed for the design of a novel amplify-forward relay network coding scheme, which allows the relay node to transmit its own information. By carefully making use of the Alamouti coding structure and strategically encoding the signals from the two antennas at the relay node, the resulting coding scheme enables the optimal full diversity gain and better coding gain for the ML detector. Comprehensive computer simulations show that the three uniquely factorable designs presented in this thesis have the best error performance compared to the current designs in literature. / Thesis / Candidate in Philosophy

Ever since the advent of the simplex algorithm, linear programming (LP) has been extensively used with great success in many diverse fields. The field of discrete optimization came to the forefront as a result of the impressive developments in the area of linear programming. Although discrete optimization problems can be viewed as belonging to the class of nonconvex programs, it has only been in recent times that optimization research has confronted the more formidable class of continuous nonconvex optimization problems, where the objective function and constraints are often highly nonlinear and nonconvex functions, defined in terms of continuous (and bounded) decision variables. Typical classes of such problems involve polynomial, or more general factorable functions. This dissertation focuses on employing the Reformulation-Linearization Technique (RLT) to enhance model formulations and to design effective solution techniques for solving several practical instances of continuous nonconvex optimization problems, namely, the hard and fuzzy clustering problems, risk management problems, and problems arising in control systems. Under the umbrella of the broad RLT framework, the contributions of this dissertation focus on developing models and algorithms along with related theoretical and computational results pertaining to three specific application domains. In the basic construct, through appropriate surrogation schemes and variable substitution strategies, we derive strong polyhedral approximations for the polynomial functional terms in the problem, and then rely on the demonstrated (robust) ability of the RLT for determining global optimal solutions for polynomial programming problems. The convergence of the proposed branch-and-bound algorithm follows from the tailored branching strategy coupled with consistency and exhaustive properties of the enumeration tree. First, we prescribe an RLT-based framework geared towards solving the hard and fuzzy clustering problems. In the second endeavor, we examine two risk management problems, providing novel models and algorithms. Finally, in the third part, we provide a detailed discussion on studying stability margins for control systems using polynomial programming models along with specialized solution techniques. / Ph. D.

El presente trabajo está dedicado al análisis de una clase particular de operadores (lineales y continuos) entre espacios de Banach de funciones. El objetivo es avanzar en la teoría de los llamados operadores factorizables a la p-potencia analizando todos los aspectos de la dualidad. Esta clase de operadores ha demostrado ser de utilidad tanto en la teoría de factorización de operadores sobre espacios de Banach de funciones (teoría de Maurey-Rosenthal) como en el Análisis Armónico (dominios óptimos de la transformada de Fourier y operadores de convolución). A ¿n de desarrollar esta teoría de dualidad y sus aplicaciones, se de¿ne y estudia una nueva clase de operadores con propiedades de extensión que involucran al operador y a su adjunto. Ésta es la familia de operadores factorizables a la (p,q)- potencia, 1 · p,q Ç 1, y pueden caracterizarse mediante un esquema de factorización a través del espacio de p-potencias del dominio y el dual del espacio de q-potencias del dual del codominio. También se obtiene una equivalencia mediante un diagrama de factorización a través de espacios L p (m) y L q (n) 0 , donde m y n son medidas vectoriales adecuadas y ésta será nuestra principal herramienta. Para esta construcción resultan necesarios algunos resultados preliminares relativos a las p-potencias de los espacios de Banach de funciones que intervienen y que también se estudian. Con estos útiles se dan algunos resultados para caracterizar el rango óptimo ¿el menor espacio de Banach de funciones en el que puede tomar valores el operador¿ para operadores que van de un espacio de Banach a un espacio de Banach de funciones. Además, se desarrolla y presenta formalmente la idea de factorización óptima de un operador que optimiza una factorización previa, en términos del diagrama que debe satisfacer un operador factorizable a su (p,q)-potencia. Todos estos resultados extienden los actuales cálculos del dominio óptimo mediante medidas vectoriales para operadores sobre espacios de Banach de funciones. Dichos cálculos han dado resultados relevantes en diversas áreas del análisis matemático mediante una descripción del mayor espacio de Banach de funciones al cual, operadores relevantes ¿como la transformada de Fourier o el operador de Hardy¿ se pueden extender. La teoría se aplica para encontrar nuevos resultados en determinados campos: como la teoría de interpolación de operadores entre espacios de Banach de funciones, los operadores de núcleo y en particular, la transformada de Laplace. / Galdames Bravo, OE. (2013). Duality theory for p-th power factorable operators and kernel operators [Tesis doctoral no publicada]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/31523 / TESIS

This thesis considers the modulation division based on the concept of uniquely factorable constellation pair (UFCP) and uniquely decodable constellation group (UDCG) in multiuser wireless communication networks. We first consider a two-hop relay network consisting of two single-antenna users and a two-antenna relay node, for which a novel distributed concatenated Alamouti code is devised. This new design allows the source and relay nodes to transmit their own information to the destination node concurrently at the symbol level with the aid of the UFCP generated from both PSK and square QAM constellations as well as by jointly processing the noisy signals received at the relay node. Moreover, an asymptotic symbol error probability (SEP) formula is derived for the ML receiver, showing that the maximum diversity gain function is achieved, which is proportional to $\ln \mathtt{SNR}/\mathtt{SNR}^2$. Then, we concentrate on the point-to-point correlated multiple-input and multiple-output (MIMO) communication systems where full knowledge of channel state information (CSI) is available at the receiver and only the first- and second-order statistics of the channels are available at the transmitter. When the number of antenna elements of both ends goes to infinity while keeping their ratio constant, the asymptotic SEP analysis is carried out for either optimally precoded or uniformly precoded correlated large MIMO fading channels using the zero-forcing (ZF) detector with equally likely PAM, PSK or square QAM constellations. For such systems, we reveal some very nice structures which inspire us to explore two very useful mathematical tools (i.e., the Szego's theorem on large Hermitian Toeplitz matrices and the well-known limit: $\lim_{x\to\infty}(1+1/x)^x=e$), for the systematic study of asymptotic behaviors on their error performance. This new approach enables us to attain a very simple expression for the SEP limit as the number of the available antenna elements goes to infinity. In what follows, the problem of precoder design using a zero-forcing decision-feedback (ZF-DF) detector is also addressed. For such a MIMO system, our principal goal is to efficiently design an optimal precoder that minimizes the asymptotic SEP of the ZF-DF detector under a perfect decision feedback. By fully taking advantage of the product majorization relationship among eigenvalues, singular-values and Cholesky values of the precoded channel matrix parameters, a necessary condition for the optimal solution to satisfy is first developed and then the structure of the optimal solution is characterized. With these results, the original non-convex problem is reformulated into a convex one that can be efficiently solved by using an interior-point method. In addition, by scaling up the antenna array size of both terminals without bound for such a network, we propose a novel method as we did for the ZF receiver scenario to analyze the asymptotic SEP performance of an equal-diagonal QRS precoded large MIMO system when employing an abstract Toeplitz correlation model for the transmitter antenna array. This new approach has a simple expression with a fast convergence rate and thus, is efficient and effective for error performance evaluation. For multiuser communication networks, we first consider a discrete-time multiple-input single-output (MISO) Gaussian broadcast channel (BC) where perfect CSI is available at both the transmitter and all the receivers. We propose a flexible and explicit design of a uniquely decomposable constellation group (UDCG) based on PAM and rectangular QAM constellations. With this new concept, a modulation division (MD) transmission scheme is developed for the considered MISO BC. The proposed MD scheme enables each receiver to uniquely and efficiently recover their desired signals from the superposition of mutually interfering cochannel signals in the absence of noise. Using max-min fairness as a design criterion, the optimal transmitter beamforming problem is solved in a closed-form for two-user MISO BC. Then, for a general case with more than two receivers, a user-grouping based beamforming scheme is developed, where the grouping method, beamforming vector design and power allocation problems are addressed by employing weighted max-min fairness. Then, we consider an uplink massive single-input and multiple-output (SIMO) network consisting of a base station (BS) and several single-antenna users. To recover the transmitted signal matrix of all the users when the antenna array size is large, a novel multi-user space-time modulation (MUSTM) scheme is proposed for the considered network based on the explicit construction of QAM uniquely-decomposable constellation groups (QAM-UDCGs). In addition, we also develop a sub-constellation allocation method at the transmitter side to ensure the signal matrix is always invertible. In the meanwhile, an efficient training correlation receiver (TCR) is proposed which calculates the correlation between the received sum training signal vector and the sum information carrying vector. Moreover, the optimal power allocation problems are addressed by maximizing the coding gain or minimizing the average SEP of the received sum signal under both average and peak power constraints on each user. The proposed transmission scheme not only allows the transmitted signals with strong mutual interference to be decoded by a simple TCR but it also enables the CSI of all the users to be estimated within a minimum number of time slots equal to that of the users. Comprehensive computer simulations are carried out to verify the effectiveness of the proposed uniquely decomposable space-time modulation method in various network topologies and configurations. Our modulation division method will be one of the promising technologies for the fifth generation (5G) communication systems. / Dissertation / Doctor of Philosophy (PhD)

This dissertation addresses five fundamental resource allocation problems on networks, all of which have applications to support Homeland Security or industry challenges. In the first application, we model and solve the strategic problem of minimizing the expected loss inflicted by a hostile terrorist organization. An appropriate allocation of certain capability-related, intent-related, vulnerability-related, and consequence-related resources is used to reduce the probabilities of success in the respective attack-related actions, and to ameliorate losses in case of a successful attack. Given the disparate nature of prioritizing capital and material investments by federal, state, local, and private agencies to combat terrorism, our model and accompanying solution procedure represent an innovative, comprehensive, and quantitative approach to coordinate resource allocations from various agencies across the breadth of domains that deal with preventing attacks and mitigating their consequences. Adopting a nested event tree optimization framework, we present a novel formulation for the problem as a specially structured nonconvex factorable program, and develop two branch-and-bound schemes based respectively on utilizing a convex nonlinear relaxation and a linear outer-approximation, both of which are proven to converge to a global optimal solution. We also investigate a fundamental special-case variant for each of these schemes, and design an alternative direct mixed-integer programming model representation for this scenario. Several range reduction, partitioning, and branching strategies are proposed, and extensive computational results are presented to study the efficacy of different compositions of these algorithmic ingredients, including comparisons with the commercial software BARON. The developed set of algorithmic implementation strategies and enhancements are shown to outperform BARON over a set of simulated test instances, where the best proposed methodology produces an average optimality gap of 0.35% (compared to 4.29% for BARON) and reduces the required computational effort by a factor of 33. A sensitivity analysis is also conducted to explore the effect of certain key model parameters, whereupon we demonstrate that the prescribed algorithm can attain significantly tighter optimality gaps with only a near-linear corresponding increase in computational effort. In addition to enabling effective comprehensive resource allocations, this research permits coordinating agencies to conduct quantitative what-if studies on the impact of alternative resourcing priorities. The second application is motivated by the author's experience with the U.S. Army during a tour in Iraq, during which combined operations involving U.S. Army, Iraqi Army, and Iraqi Police forces sought to interdict the transport of selected materials used for the manufacture of specialized types of Improvised Explosive Devices, as well as to interdict the distribution of assembled devices to operatives in the field. In this application, we model and solve the problem of minimizing the maximum flow through a network from a given source node to a terminus node, integrating different forms of superadditive synergy with respect to the effect of resources applied to the arcs in the network. Herein, the superadditive synergy reflects the additional effectiveness of forces conducting combined operations, vis-à-vis unilateral efforts. We examine linear, concave, and general nonconcave superadditive synergistic relationships between resources, and accordingly develop and test effective solution procedures for the underlying nonlinear programs. For the linear case, we formulate an alternative model representation via Fourier-Motzkin elimination that reduces average computational effort by over 40% on a set of randomly generated test instances. This test is followed by extensive analyses of instance parameters to determine their effect on the levels of synergy attained using different specified metrics. For the case of concave synergy relationships, which yields a convex program, we design an inner-linearization procedure that attains solutions on average within 3% of optimality with a reduction in computational effort by a factor of 18 in comparison with the commercial codes SBB and BARON for small- and medium-sized problems; and outperforms these softwares on large-sized problems, where both solvers failed to attain an optimal solution (and often failed to detect a feasible solution) within 1800 CPU seconds. Examining a general nonlinear synergy relationship, we develop solution methods based on outer-linearizations, inner-linearizations, and mixed-integer approximations, and compare these against the commercial software BARON. Considering increased granularities for the outer-linearization and mixed-integer approximations, as well as different implementation variants for both these approaches, we conduct extensive computational experiments to reveal that, whereas both these techniques perform comparably with respect to BARON on small-sized problems, they significantly improve upon the performance for medium- and large-sized problems. Our superlative procedure reduces the computational effort by a factor of 461 for the subset of test problems for which the commercial global optimization software BARON could identify a feasible solution, while also achieving solutions of objective value 0.20% better than BARON. The third application is likewise motivated by the author's military experience in Iraq, both from several instances involving coalition forces attempting to interdict the transport of a kidnapping victim by a sectarian militia as well as, from the opposite perspective, instances involving coalition forces transporting detainees between interment facilities. For this application, we examine the network interdiction problem of minimizing the maximum probability of evasion by an entity traversing a network from a given source to a designated terminus, while incorporating novel forms of superadditive synergy between resources applied to arcs in the network. Our formulations examine either linear or concave (nonlinear) synergy relationships. Conformant with military strategies that frequently involve a combination of overt and covert operations to achieve an operational objective, we also propose an alternative model for sequential overt and covert deployment of subsets of interdiction resources, and conduct theoretical as well as empirical comparative analyses between models for purely overt (with or without synergy) and composite overt-covert strategies to provide insights into absolute and relative threshold criteria for recommended resource utilization. In contrast to existing static models, in a fourth application, we present a novel dynamic network interdiction model that improves realism by accounting for interactions between an interdictor deploying resources on arcs in a digraph and an evader traversing the network from a designated source to a known terminus, wherein the agents may modify strategies in selected subsequent periods according to respective decision and implementation cycles. We further enhance the realism of our model by considering a multi-component objective function, wherein the interdictor seeks to minimize the maximum value of a regret function that consists of the evader's net flow from the source to the terminus; the interdictor's procurement, deployment, and redeployment costs; and penalties incurred by the evader for misperceptions as to the interdicted state of the network. For the resulting minimax model, we use duality to develop a reformulation that facilitates a direct solution procedure using the commercial software BARON, and examine certain related stability and convergence issues. We demonstrate cases for convergence to a stable equilibrium of strategies for problem structures having a unique solution to minimize the maximum evader flow, as well as convergence to a region of bounded oscillation for structures yielding alternative interdictor strategies that minimize the maximum evader flow. We also provide insights into the computational performance of BARON for these two problem structures, yielding useful guidelines for other research involving similar non-convex optimization problems. For the fifth application, we examine the problem of apportioning railcars to car manufacturers and railroads participating in a pooling agreement for shipping automobiles, given a dynamically determined total fleet size. This study is motivated by the existence of such a consortium of automobile manufacturers and railroads, for which the collaborative fleet sizing and efforts to equitably allocate railcars amongst the participants are currently orchestrated by the \textit{TTX Company} in Chicago, Illinois. In our study, we first demonstrate potential inequities in the industry standard resulting either from failing to address disconnected transportation network components separately, or from utilizing the current manufacturer allocation technique that is based on average nodal empty transit time estimates. We next propose and illustrate four alternative schemes to apportion railcars to manufacturers, respectively based on total transit time that accounts for queuing; two marginal cost-induced methods; and a Shapley value approach. We also provide a game-theoretic insight into the existing procedure for apportioning railcars to railroads, and develop an alternative railroad allocation scheme based on capital plus operating costs. Extensive computational results are presented for the ten combinations of current and proposed allocation techniques for automobile manufacturers and railroads, using realistic instances derived from representative data of the current business environment. We conclude with recommendations for adopting an appropriate apportionment methodology for implementation by the industry. / Ph. D.