Thesis (M. Phil.)--University of Hong Kong, 2001. / Includes bibliographical references (leaves 186-203).

Next generation wireless systems will use multiple antenna technologies, also known as multiple-input multiple-output (MIMO), to provide high data rates and robustness against fading. MIMO communication strategies for single user communication systems and their practical application in wireless networks are by now well known. MIMO communication systems, however, can benefit from multiuser processing by coordinating the transmissions to multiple users simultaneously. For numerous reasons, work on the theory of multiuser MIMO communication has yet to see broad adoption in wireless communication standards. For example, global knowledge of channel state information is often required. Such an unrealistic assumption, however, makes it difficult in practice to implement precoding techniques. Furthermore, the achievable rates of the conventional multiuser MIMO techniques are far from the theoretical performance bounds. These and other factors motivate research on practical multiuser communication strategies for the MIMO broadcast channel (point to multi-point communication) and the analysis of those strategies. The primary contributions of this dissertation are i) the development of four novel low complexity coordinated MIMO transceiver design techniques to approach the theoretical performance bound and ii) the investigation of the optimality of the proposed coordinated wireless MIMO networks. Several coordinated beamforming algorithms are proposed, where each mobile station uses quantized combining vectors or each base station uses limited feedback from the MS. The asymptotic optimality of the proposed coordinated beamforming system for the MIMO Gaussian broadcast channel is next investigated. For multi-stream transmission, a novel block diagonalized vector perturbation is proposed and the achievable sum rate upper bound of the proposed system is derived. Finally, for multi-cell environments, linear and non-linear network CBF algorithms supporting multiple cell-boundary users are proposed. The optimality of network coordinated beamforming in terms of the number of receive antennas is also investigated. / text

The average cost of operating a queueing network depends on several factors such as the complexity of the network and the service policy used. Approximate linear programming (ALP) is a method that can be used to compute an accurate lower bound on the optimal average cost as well as generate policies to be used in operating the network. These average cost solutions and policies are dependent on the type of basis function used in the ALP. In this paper, the ALP average cost solutions and policies are analyzed for twelve networks with four different types of basis functions (quadratic, linear, pure exponential, and mixed exponential). An approximate bound on the optimality gap between the ALP average cost solution and the optimal average cost solution is computed for each system, and the size of this bound is determined relative to the ALP average cost solution. Using the same set of networks, the performance of ALP generated policies are compared to the performance of the heuristic policies first-buffer-first-served (FBFS), last-buffer-first-served (LBFS), highest-queue-first-served (HQFS), and random-queue-first-served (RQFS). In general, ALP generated average cost solutions are considerably smaller than the simulated average cost under the corresponding policy, and therefore the approximate bounds on the optimality gaps are quite large. This bound increases with the complexity of the queueing network. Some ALP generated policies are not stabilizing policies for their corresponding networks, especially those produced using pure exponential and mixed exponential basis functions. For almost all systems, at least one of the heuristic policies results in mean average cost less than or nearly equal to the smallest mean average cost of all ALP generated policies in simulation runs. This means that generally there exists a heuristic policy which can perform as well as or better than any ALP generated policy. In conclusion, a useful bound on the optimality gap between the ALP average cost solution and the optimal average cost solution cannot be computed with this method. Further, heuristic policies, which are more computationally tractable than ALP generated policies, can generally match or exceed the performance of ALP generated policies, and thus computing such policies is often unnecessary for realizing cost benefits in queueing networks. / text

published_or_final_version / Linguistics / Master / Master of Philosophy

In the rapidly changing world of today, people have to make decisions under some degree of uncertainty. At the same time, the development of computing technologies enables people to take uncertain factors into considerations while making their decisions.Stochastic programming techniques have been widely applied in finance engineering, supply chain management, logistics, transportation, etc. Such applications often involve a large, possibly infinite, set of scenarios. Hence the resulting programstend to be large in scale.The need to solve large scale programs calls for a combination of mathematical programming techniques and sample-based approximation. When using sample-based approximations, it is important to determine the extent to which the resulting solutions are dependent on thespecific sample used. This dissertation research focuses on computational evaluation of the solutions from sample-based two-stage/multistage stochastic linear programming algorithms, with a focus on the effectiveness of optimality tests and the quality ofa proposed solution.In the first part of this dissertation, two alternative approaches of optimality tests of sample-based solutions, adaptive and non-adaptive sampling methods, are examined and computationally compared. The results of the computational experiment are in favor of the adaptive methods. In the second part of this dissertation, statistically motivated bound-based solution validation techniques in multistage linear stochastic programs are studied both theoretically and computationally. Different approaches of representations of the nonanticipativity constraints are studied. Bounds are established through manipulations of the nonanticipativity constraints.

Blackfoot (Siksika), an Algonquian language spoken in Southern Alberta and in Northwestern Montana, is claimed to have a pitch-accent system (Frantz 1991). However, no complete analysis of the Blackfoot word accent system is available in the literature. This thesis examines Blackfoot nominal accent by means of metrical analysis (Halle and Vergnaud 1987) in Optimality Theory (OT) (Prince and Smolensky 1993). All of the data in this thesis are elicited from native speakers of Blackfoot. Regardless of noun type, every word contains one and only one pitch peak. Bare nouns (mono-morphemic nouns) and relational nouns (dependent nouns) show that Blackfoot has a mixed predictable and lexical accent system. Accent is quantity-sensitive, i.e. a heavy syllable attracts accent, while in nouns which contain no heavy syllable or more than one heavy syllable, it is lexically specified. An interesting contrast is found in long vowels - they contrast a high-level pitch, a falling pitch, and a rising pitch. Derived nouns (compounds) demonstrate four kinds of accent patterns, depending on the status (free vs. bound) and the accentual property (accented vs. unaccented) of morphemes. The leftmost accent of the compound members is retained, but the accent shifts to the juncture of them if it is word-final. If compound members are unaccented, the accent is assigned to word-final position by default. Speaker variation also occurs. One speaker systematically changes vowel length depending on the type of accented syllable, while the other speaker shows a wide variety of accent patterns. This thesis concludes that all the accent patterns can be accounted for by a single ranking of constraints in an OT analysis, in spite of the fact that the accent system is both lexical and predictable. Addition of constraints is needed specifically for compounds! Speaker variation is accounted for by reranking the same set of constraints. Priority is given to constraints that refer to the predictable accent in the grammar of one speaker. The lexical information is more respected in the other speaker's grammar. In addition to the analysis of general pitch-accent patterns, four types of irregular patterns are examined. The conclusions reached in this thesis demonstrate that the accent system interacts with other phonological properties of Blackfoot.

No description available.

This study focuses on English loanwords in Thai, particularly the treatment of consonants in different environments, namely onset/coda simplification, laryngeal features, medial consonants, and liquid alternation, within the framework of Optimality Theory (OT: Prince and Smolensky 1993/2004). The major objectives are: (1) to examine the way English loanwords are adapted to a new environment, (2) to investigate how conflict between faithfulness and markedness constraints is resolved and in what ways through OT grammars, and (3) finally to be a contribution to the literature of loan phonology in OT since there has not been much literature on English loanwords in Thai within the recent theoretical framework of Optimality TheoryThe data are drawn from an English-Thai dictionary (Sethaputa 1995), an on-line English-Thai dictionary, an English loanword dictionary (Komutthamwiboon 2003), and earlier studies of English loans in Thai by Udomwong (1981), Nacaskul (1989), Raksaphet (2000), and Kenstowicz and Atiwong (2004).The study has found that Thais replace unlicensed consonants with either auditory similar segments or shared natural class segments, as in /v/ in the English and [w] in word borrowing due to auditory similarity, /g/ in the English source replaced by [k] because of shared place of articulation. Vowel insertion is found if the English source begins with /sC/ as in /skaen/ scan -> [stkc cn]. Since Thai allows consonant clusters, a second segment of the clusters is always retained if it fits the Thai phonotactics, as in /gruup/ `group' -4 [kruip]. In coda, consonant clusters must be simplified. Consonant clusters in the English source are divided into five main subgroups. Sometimes Thais retain a segment adjacent to a vowel and delete the edge, as in /lcnzi lens -4 [len].However, a postvocalic lateral [1] followed by a segment are replaced by either a nasal [n] or a glide [w]. In terms of repair strategies, the lowest ranked faithfulness constraints indicate what motivates Thais to have consonant adaptation. MAX-I0, DEP-I0, IDENT-I0 (place) reveal that segmental deletion, insertion, and replacement on the place of articulation are employed to deal with marked structures, respectively. The two lines of approaches (Positional Faithfulness, Positional Markedness) have been examined with respect to segments bearing aspiration or voicing. The findings have shown that both approaches can be employed to achieve the same result. In medial consonants, ambisyllabic consonants in the English source undergo syllable adaptation and behave like geminates in word borrowings in Thai. Most cases show that ambisyllabic/geminate consonants in loanwords are unaspirated. A few cases are aspirated.The study has revealed that there is still more room for improvement in 0T. The standard OT allowing only a single output in the surface form is challenged. Some English loanwords have multiple outputs. For instance, /aesfoolt/ `asphalt' can be pronounced either [26tf6n] or [26tf6w]. Another example is the word /k h riim / `cream' can be pronounced as [k h riim], [khliim], and [khiim]. To account for these phenomena requires a sociolinguistic explanation. / Department of English

The overall purpose of this study is to analyze the acquisition of English word-stress by Arabic speakers in light of advancements in Optimality Theory. It has been reported that Arab second language learners of English have difficulty in acquiring the various patterns of English word stress. According to OT, the reason for this difficulty is that although these speakers, like native speakers, have full command of the universal and violable constraints that are operative in determining where stress falls in the word, they fail to capture or induce the exact ordering of these constraints. The basic premise of OT is that each grammar is a unique way of ordering the set of universal and violable constraints that determine the actual output form of a certain linguistic feature, say word-stress in this case. In other words, whereas Arabic word-stress and English word-stress are both subject to the same set of universal and violable constraints, they differ in one respect: the ordering of these constraints. The sole task of the learner then is to capture the correct ordering that determines which syllable in each word carries main stress.This study consists of four chapters. In chapter one, we introduce the problem of the study and the basic background information for an OT analysis, the task we undertake for word stress in subsequent chapters. Chapter two reviews word-stress placement in three competing models: linear approach (Chomsky and Halle 1968), nonlinear approach (Liberman and Prince 1977; McCarthy 1979; Hayes 1980, 1982, 1991), and finally Optimality Theory (Prince and Smolensky 1993; McCarthy and Prince 1993a, b). In chapter three, we introduce the set of constraints that are relevant for predicting the place of stress, not just in English and Arabic, but in all languages. Hence, these constraints are literally present in all languages, though their ranking is language-specific. Then, we develop a ranking of the set of constraints particular to Arabic and another one particular to English. In chapter four, we set out to compare the two constraint rankings in order to (1) predict stress errors in the interlanguage of native speakers of Arabic when learning English, and (2) demonstrate how, by making use of the notion of constraint demotion, those learners can make their English more native-like with respect to stress placement.This study has diverted from a standard OT analysis in at least two ways. First, we allow for some alignment constraint (namely MAIN-RIGHT) to be interpreted as a nongradient constraint. Second, we allow for constraint parameterization. NONFINAL is parameterized to account for Arabic word stress; and WSP is parameterized to account for English word stress.This study has shown that there are significant differences between Arabic and English as far as the ranking of the universal and violable constraints is concerned. Among the major differences are the following. (1) WSP is irrelevant for stress placement in Arabic. (2) Arabic requires that FOOT-BINARITY be interpreted under a moraic analysis, but English requires it to be interpreted under a syllabic analysis. (3) Arabic requires constructing metrical feet from left to right (i.e. ALL-FEET-LEFT >> ALL-FEET RIGHT), English require that it be the other way around (i.e. ALL-FEETRIGHT >> ALL-FEET-LEFT). (4) In. ploysyllabic words, whereas a final syllable that weighs two or more moras is parsed in English, only a final syllable that weighs three moras is parsed in Arabic. (5) Arabic requires that PARSEσ dominates FOOTBINARITY, but English requires the opposite ranking.

The main purpose of this dissertation is to investigate necessary optimality conditions for a class of very general nonsmooth optimization problems called the mathematical program with geometric constraints (MPGC). The geometric constraint means that the image of certain mapping is included in a nonempty and closed set. We first study the conventional nonlinear program with equality, inequality and abstract set constraints as a special case of MPGC. We derive the enhanced Fritz John condition and from which, we obtain the enhanced Karush-Kuhn-Tucker (KKT) condition and introduce the associated pseudonormality and quasinormality condition. We prove that either pseudonormality or quasinormality with regularity implies the existence of a local error bound. We also give a tighter upper estimate for the Fr\'chet subdifferential and the limiting subdifferential of the value function in terms of quasinormal multipliers which is usually a smaller set than the set of classical normal multipliers. We then consider a more general MPGC where the image of the mapping from a Banach space is included in a nonempty and closed subset of a finite dimensional space. We obtain the enhanced Fritz John necessary optimality conditions in terms of the approximate subdifferential. One of the technical difficulties in obtaining such a result in an infinite dimensional space is that no compactness result can be used to show the existence of local minimizers of a perturbed problem. We employ the celebrated Ekeland's variational principle to obtain the results instead. We then apply our results to the study of exact penalty and sensitivity analysis. We also study a special class of MPCG named mathematical programs with equilibrium constraints (MPECs). We argue that the MPEC-linear independence constraint qualification is not a constraint qualification for the strong (S-) stationary condition when the objective function is nonsmooth. We derive the enhanced Fritz John Mordukhovich (M-) stationary condition for MPECs. From this enhanced Fritz John M-stationary condition we introduce the associated MPEC generalized pseudonormality and quasinormality condition and build the relations between them and some other widely used MPEC constraint qualifications. We give upper estimates for the subdifferential of the value function in terms of the enhanced M- and C-multipliers respectively. Besides, we focus on some new constraint qualifications introduced for nonlinear extremum problems in the recent literature. We show that, if the constraint functions are continuously differentiable, the relaxed Mangasarian-Fromovitz constraint qualification (or, equivalently, the constant rank of the subspace component condition) implies the existence of local error bounds. We further extend the new result to the MPECs. / Graduate / 0405