Lam Sze Wan. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2002. / Includes bibliographical references (leaves 93-95). / Abstracts in English and Chinese. / Chapter 1 --- Introduction --- p.1 / Chapter 2 --- Background --- p.4 / Chapter 3 --- Review of Iri-Imai Algorithm for Convex Programming Prob- lems --- p.10 / Chapter 3.1 --- Iri-Imai Algorithm for Convex Programming --- p.11 / Chapter 3.2 --- Numerical Results --- p.14 / Chapter 3.2.1 --- Linear Programming Problems --- p.15 / Chapter 3.2.2 --- Convex Quadratic Programming Problems with Linear Inequality Constraints --- p.17 / Chapter 3.2.3 --- Convex Quadratic Programming Problems with Con- vex Quadratic Inequality Constraints --- p.18 / Chapter 3.2.4 --- Summary of Numerical Results --- p.21 / Chapter 3.3 --- Chapter Summary --- p.22 / Chapter 4 --- Value Estimation Approach to Iri-Imai Method for Con- strained Optimization --- p.23 / Chapter 4.1 --- Value Estimation Function Method --- p.24 / Chapter 4.1.1 --- Formulation and Properties --- p.24 / Chapter 4.1.2 --- Value Estimation Approach to Iri-Imai Method --- p.33 / Chapter 4.2 --- "A New Smooth Multiplicative Barrier Function Φθ+,u" --- p.35 / Chapter 4.2.1 --- Formulation and Properties --- p.35 / Chapter 4.2.2 --- "Value Estimation Approach to Iri-Imai Method by Us- ing Φθ+,u" --- p.41 / Chapter 4.3 --- Convergence Analysis --- p.43 / Chapter 4.4 --- Numerical Results --- p.46 / Chapter 4.4.1 --- Numerical Results Based on Algorithm 4.1 --- p.46 / Chapter 4.4.2 --- Numerical Results Based on Algorithm 4.2 --- p.50 / Chapter 4.4.3 --- Summary of Numerical Results --- p.59 / Chapter 4.5 --- Chapter Summary --- p.60 / Chapter 5 --- Extension of Value Estimation Approach to Iri-Imai Method for More General Constrained Optimization --- p.61 / Chapter 5.1 --- Extension of Iri-Imai Algorithm 3.1 for More General Con- strained Optimization --- p.62 / Chapter 5.1.1 --- Formulation and Properties --- p.62 / Chapter 5.1.2 --- Extension of Iri-Imai Algorithm 3.1 --- p.63 / Chapter 5.2 --- Extension of Value Estimation Approach to Iri-Imai Algo- rithm 4.1 for More General Constrained Optimization --- p.64 / Chapter 5.2.1 --- Formulation and Properties --- p.64 / Chapter 5.2.2 --- Value Estimation Approach to Iri-Imai Method --- p.67 / Chapter 5.3 --- Extension of Value Estimation Approach to Iri-Imai Algo- rithm 4.2 for More General Constrained Optimization --- p.69 / Chapter 5.3.1 --- Formulation and Properties --- p.69 / Chapter 5.3.2 --- Value Estimation Approach to Iri-Imai Method --- p.71 / Chapter 5.4 --- Numerical Results --- p.72 / Chapter 5.4.1 --- Numerical Results Based on Algorithm 5.1 --- p.73 / Chapter 5.4.2 --- Numerical Results Based on Algorithm 5.2 --- p.76 / Chapter 5.4.3 --- Numerical Results Based on Algorithm 5.3 --- p.78 / Chapter 5.4.4 --- Summary of Numerical Results --- p.86 / Chapter 5.5 --- Chapter Summary --- p.87 / Chapter 6 --- Conclusion --- p.88 / Bibliography --- p.93 / Chapter A --- Search Directions --- p.96 / Chapter A.1 --- Newton's Method --- p.97 / Chapter A.1.1 --- Golden Section Method --- p.99 / Chapter A.2 --- Gradients and Hessian Matrices --- p.100 / Chapter A.2.1 --- Gradient of Φθ(x) --- p.100 / Chapter A.2.2 --- Hessian Matrix of Φθ(x) --- p.101 / Chapter A.2.3 --- Gradient of Φθ(x) --- p.101 / Chapter A.2.4 --- Hessian Matrix of φθ (x) --- p.102 / Chapter A.2.5 --- Gradient and Hessian Matrix of Φθ(x) in Terms of ∇xφθ (x) and∇2xxφθ (x) --- p.102 / Chapter A.2.6 --- "Gradient of φθ+,u(x)" --- p.102 / Chapter A.2.7 --- "Hessian Matrix of φθ+,u(x)" --- p.103 / Chapter A.2.8 --- "Gradient and Hessian Matrix of Φθ+,u(x) in Terms of ∇xφθ+,u(x)and ∇2xxφθ+,u(x)" --- p.103 / Chapter A.3 --- Newton's Directions --- p.103 / Chapter A.3.1 --- Newton Direction of Φθ (x) in Terms of ∇xφθ (x) and ∇2xxφθ(x) --- p.104 / Chapter A.3.2 --- "Newton Direction of Φθ+,u(x) in Terms of ∇xφθ+,u(x) and ∇2xxφθ,u(x)" --- p.104 / Chapter A.4 --- Feasible Descent Directions for the Minimization Problems (Pθ) and (Pθ+) --- p.105 / Chapter A.4.1 --- Feasible Descent Direction for the Minimization Prob- lems (Pθ) --- p.105 / Chapter A.4.2 --- Feasible Descent Direction for the Minimization Prob- lems (Pθ+) --- p.107 / Chapter B --- Randomly Generated Test Problems for Positive Definite Quadratic Programming --- p.109 / Chapter B.l --- Convex Quadratic Programming Problems with Linear Con- straints --- p.110 / Chapter B.l.1 --- General Description of Test Problems --- p.110 / Chapter B.l.2 --- The Objective Function --- p.112 / Chapter B.l.3 --- The Linear Constraints --- p.113 / Chapter B.2 --- Convex Quadratic Programming Problems with Quadratic In- equality Constraints --- p.116 / Chapter B.2.1 --- The Quadratic Constraints --- p.117

by Choi Mo Fung Kenneth. / Thesis (M.Phil.)--Chinese University of Hong Kong, 1998. / Includes bibliographical references (leaves 105-112). / Abstract also in Chinese. / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Constraint Satisfaction Problems --- p.2 / Chapter 1.2 --- Constraint Satisfaction Techniques --- p.2 / Chapter 1.3 --- Motivation of the Research --- p.4 / Chapter 1.4 --- Overview of the Thesis --- p.5 / Chapter 2 --- Related Work --- p.7 / Chapter 2.1 --- Min-conflicts Heuristic --- p.7 / Chapter 2.2 --- GSAT --- p.8 / Chapter 2.3 --- Breakout Method --- p.8 / Chapter 2.4 --- GENET --- p.9 / Chapter 2.5 --- E-GENET --- p.9 / Chapter 2.6 --- DLM --- p.10 / Chapter 2.7 --- Simulated Annealing --- p.11 / Chapter 2.8 --- Genetic Algorithms --- p.12 / Chapter 2.9 --- Tabu Search --- p.12 / Chapter 2.10 --- Integer Programming --- p.13 / Chapter 3 --- Background --- p.15 / Chapter 3.1 --- GENET --- p.15 / Chapter 3.1.1 --- Network Architecture --- p.15 / Chapter 3.1.2 --- Convergence Procedure --- p.18 / Chapter 3.2 --- Classical Optimization --- p.22 / Chapter 3.2.1 --- Optimization Problems --- p.22 / Chapter 3.2.2 --- The Lagrange Multiplier Method --- p.23 / Chapter 3.2.3 --- Saddle Point of Lagrangian Function --- p.25 / Chapter 4 --- Binary CSP's as Zero-One Integer Constrained Minimization Prob- lems --- p.27 / Chapter 4.1 --- From CSP to SAT --- p.27 / Chapter 4.2 --- From SAT to Zero-One Integer Constrained Minimization --- p.29 / Chapter 5 --- A Continuous Lagrangian Approach for Solving Binary CSP's --- p.33 / Chapter 5.1 --- From Integer Problems to Real Problems --- p.33 / Chapter 5.2 --- The Lagrange Multiplier Method --- p.36 / Chapter 5.3 --- Experiment --- p.37 / Chapter 6 --- A Discrete Lagrangian Approach for Solving Binary CSP's --- p.39 / Chapter 6.1 --- The Discrete Lagrange Multiplier Method --- p.39 / Chapter 6.2 --- Parameters of CSVC --- p.43 / Chapter 6.2.1 --- Objective Function --- p.43 / Chapter 6.2.2 --- Discrete Gradient Operator --- p.44 / Chapter 6.2.3 --- Integer Variables Initialization --- p.45 / Chapter 6.2.4 --- Lagrange Multipliers Initialization --- p.46 / Chapter 6.2.5 --- Condition for Updating Lagrange Multipliers --- p.46 / Chapter 6.3 --- A Lagrangian Reconstruction of GENET --- p.46 / Chapter 6.4 --- Experiments --- p.52 / Chapter 6.4.1 --- Evaluation of LSDL(genet) --- p.53 / Chapter 6.4.2 --- Evaluation of Various Parameters --- p.55 / Chapter 6.4.3 --- Evaluation of LSDL(max) --- p.63 / Chapter 6.5 --- Extension of LSDL --- p.66 / Chapter 6.5.1 --- Arc Consistency --- p.66 / Chapter 6.5.2 --- Lazy Arc Consistency --- p.67 / Chapter 6.5.3 --- Experiments --- p.70 / Chapter 7 --- Extending LSDL for General CSP's: Initial Results --- p.77 / Chapter 7.1 --- General CSP's as Integer Constrained Minimization Problems --- p.77 / Chapter 7.1.1 --- Formulation --- p.78 / Chapter 7.1.2 --- Incompatibility Functions --- p.79 / Chapter 7.2 --- The Discrete Lagrange Multiplier Method --- p.84 / Chapter 7.3 --- A Comparison between the Binary and the General Formulation --- p.85 / Chapter 7.4 --- Experiments --- p.87 / Chapter 7.4.1 --- The N-queens Problems --- p.89 / Chapter 7.4.2 --- The Graph-coloring Problems --- p.91 / Chapter 7.4.3 --- The Car-Sequencing Problems --- p.92 / Chapter 7.5 --- Inadequacy of the Formulation --- p.94 / Chapter 7.5.1 --- Insufficiency of the Incompatibility Functions --- p.94 / Chapter 7.5.2 --- Dynamic Illegal Constraint --- p.96 / Chapter 7.5.3 --- Experiments --- p.97 / Chapter 8 --- Concluding Remarks --- p.100 / Chapter 8.1 --- Contributions --- p.100 / Chapter 8.2 --- Discussions --- p.102 / Chapter 8.3 --- Future Work --- p.103 / Bibliography --- p.105

São Roque situa-se a 60 km de São Paulo, em uma região composta por serras e morros. A hidrografia do município é composta por bacias tributárias do Rio Tietê. A cidade se desenvolveu às margens dos córregos Aracaí e Carambeí, cujos leitos fluem em margens canalizadas até o deságue no Ribeirão Guaçu. Estes córregos, bem como o Ribeirão do Marmeleiro, encaminham resíduos, detritos e todo o volume de águas pluviais ao Ribeirão Guaçu. Em 2017, foi instalada no município uma estação de tratamento de esgoto visando a melhoria das condições de saneamento na região. Diante disso, este trabalho teve por objetivo avaliar as relações hidroquímicas quanto ao estado de trofia e demais impactos antrópicos na qualidade das águas do Ribeirão Guaçu, São Roque, SP, de modo espacial e temporal, mediante abordagem integrada de multitraçadores ambientais, situando a qualidade da microbacia hidrográfica pré e pós instalação de um sistema de coleta e tratamento de esgoto. Para avaliar a qualidade das águas dos corpos hídricos, foram efetuadas amostragens bimestrais de água superficial, obedecendo às épocas de chuva e de seca. Foram selecionados sete locais estrategicamente escolhidos e georreferenciados. As análises foram realizadas de acordo com os métodos analíticos baseados no Standard Methods for Examination of Water and Wastewater. Foram analisados parâmetros físicos, químicos e microbiológicos, sendo os resultados comparados com os valores permitidos por lei. O IQA foi empregado a fim de se obter um panorama sobre a qualidade hídrica da microbacia em função da sazonalidade e um comparativo entre o período pré e pós-operação da ETE. Os pontos Marmeleiro e Guaçu 4 apresentaram maior influência antrópica. Todos os pontos analisados demonstraram-se comprometidos com contaminantes microbiológicos. Em relação aos físicos e químicos, diversos pontos apresentaram inconformidades. / São Roque is located 60 km from São Paulo, in a region composed of hills. The hydrography of the municipality is composed of tributary basins of the Tietê River. The city developed on the margins of the streams of Aracaí and Carambeí, whose channels channeled flows until the drain in the Guaçu River. These streams, as well as Marmeleiro River, send waste, debris and all the volume of rainwater to the Guaçu River. In 2017, a sewage treatment plant was installed in the municipality aiming to improve the sanitation conditions in the region. The objective of this work was to evaluate the hydrochemical relationships regarding trophic status and other anthropic impacts in the water quality of the Guaçu River, São Roque, SP, in a spatial and temporal way, through an integrated approach of environmental multipliers, placing the quality of the hydrographic microbasin pre and post installation of a sewage collection and treatment system. In order to evaluate the water quality of the water bodies, bimonthly sampling of surface water was carried out, obeying rain and dry seasons. Seven strategically chosen and geo-referenced sites were selected. The analyzes shall be carried out in accordance with analytical methods based on the Standard Methods for Examination of Water and Wastewater. Physical, chemical and microbiological parameters were analyzed, and the results were compared with the values allowed by law. The WQI was used in order to obtain an overview of the water quality of the microbasin according to the seasonality and a comparison between the pre and post-operation period of the STS. The collect points Marmeleiro and Guaçu 4 presented greater anthropic influence. All analyzed points were shown to be compromised with microbiological contaminants. Regarding physicochemicals, several points presented nonconformities.

É consensual que questões políticas acarretam impactos econômicos significativos, entretanto, saber a direção e magnitude destes não é trivial. A contribuição desta dissertação ao assunto se divide em duas frentes: verificação da existência de ciclo político-orçamentário na execução de investimentos públicos; e estimação de relações macroeconômicas ao longo do ciclo político. Para o primeiro ponto, utilizou-se um modelo estrutural para a série mensal de investimento das Administrações Públicas (níveis federal, estadual e municipal), encontrando ciclos de curto e médio prazo, com duração de, aproximadamente, 2 e 4 anos, respectivamente. Ademais, os ciclos coincidem com o calendário eleitoral, sendo que suas fases de expansão se encontram no período pré-eleitoral e as de contração, sempre em anos ímpares. Para o segundo ponto, um VAR linear e outro com mudança de regime foram estimados, incorporando neste as informações obtidas pelo Modelo Estrutural. Os resultados do modelo linear indicam que investimento público causa crowding-out sobre investimento privado e que tanto investimento público quanto privado exercem efeito positivo sobre o PIB, a magnitude do segundo, entretanto, é consideravelmente superior à do primeiro. O modelo não-linear evidencia que os multiplicadores fiscais são distintos para os períodos pré e pós-eleitoral, salientando que o ajuste fiscal não implica redução da atividade econômica, e sim o contrário. O impacto dos investimentos privados sobre o crescimento, por sua vez, é sempre alto, positivo e independente de ciclo político. / There is consensus that political issues carry significant economic impact, however, it\'s not trivial to determine the direction and magnitude of these ones. The contribution of this thesis to the subject is divided into two fronts: the determination of political budget cycle in the execution of public investments; and estimation of macroeconomic relationships over the political cycle. For the first point, we used a structural model for the general government (federal, state and municipal levels) monthly series of investment, finding short and medium term cycles, with duration of, approximately, 2 and 4 years, respectively. Furthermore, the cycles coincide with the electoral calendar, since phases of expansion are in the pre-election period and the contraction ones, always in odd years. For the second point, a linear and a regime switching VAR were estimated, incorporating in the latter information obtained by the Structural Model. The results of the linear model indicate that public investment causes crowding-out in private investment and that public and private investment has a positive effect on the GDP, the magnitude of the second, however, is considerably higher than the first. The nonlinear model shows that fiscal multipliers are distinct for the pre and post-election period, stressing that the fiscal adjustment does not imply reduction of the economic activity, but otherwise. On the other hand, the impact of private investment on economic growth is always high, positive and independent of the political cycle.

We generalize a simple New Keynesian model and show that a flattening of the Phillips curve reduces the size of fiscal multipliers at the zero lower bound (ZLB) on the nominal interest rate. The factors behind the flatting are consistent with micro- and macroeconomic empirical evidence: it is a result of, not a higher level of price rigidity, but an increase in the degree of strategic complementarity in price-setting -- invoked by the assumption of a specific instead of an economy-wide labour market, and decreasing instead of constant-returns-to-scale. In normal times, the efficacy of fiscal policy and resulting multipliers tends to be small because negative wealth effects crowd out consumption, and because monetary policy endogenously reacts to fiscally-driven increases in inflation and output by raising rates, offsetting part of the stimulus. In times of a binding ZLB and a fixed nominal rate, an increase in (expected) inflation instead lowers the real rate, leading to larger fiscal multipliers. Conditional on being in a ZLB-environment, under a flatter Phillips curve, increases in expected inflation are lower, so that fiscal multipliers at the ZLB tend to be lower. Finally, we also discuss the role of solution methods in determining the size of fiscal multipliers. / Series: Department of Economics Working Paper Series

Motivated by the work of Hognas and Mukherjea on semigroups,we study semihypergroups, which are structures closer to semigroups than hypergroups in the sense that they do not require an identity or an involution. Dunkl[Du73] calls them hypergroups (without involution), and Jewett[Je75] calls them semiconvos. A semihypergroup does not assume any algebraic operation on itself. To generalize results from semigroups to semihypergroups, we first put together the fundamental algebraic concept a semihypergroup inherits from its measure algebra. Among other things, we define the Rees convolution product, and prove that if X; Y are non-empty sets and H is a hypergroup, then with the Rees convolution product, X x H x Y is a completely simple semihypergroup which has all its idempotent elements in its center. We also point out striking differences between semigroups and semihypergroups. For instance, we construct an example of a commutative simple semihypergroup, which is not completely simple. In a commutative semihypergroup S, we solve the Choquet equation μ * v = v, under certain mild conditions.We also give the most general result for the non-commutative case.We give an example of an idempotent measure on a commutative semihypergroup whose support does not contain an idempotent element and so could not be completely simple. This is in contrast with the context of semigroups, where idempotent measures have completely simple supports. The results of Hognas and Mukherjea [HM95] on the weak convergence of the sequence of averages of convolution powers of probability measures is generalized to semihypergroups. We use these results to give an alternative method of solving the Choquet equation on hypergroups (which was initially solved in [BH95] with many steps). We show that If S is a compact semihypergroup and μ is a probability measure with S = [ U∞n=1 Supp(μ)n], then for any open set G ⊃ K where K is the kernel of S limn-→∞μn(G) = 1. Finally, we extend to hypergroups basic techniques on multipliers set forth for groups in [HR70], namely propositions 5.2.1 and 5.2.2 , we give a proof of an extended version of Wendel's theorem for locally compact commutative hypergroups and show that this version also holds for compact non-commutative hypergroups. For a compact commutative hypergroup H, we establish relationships between semigroup S = S = {T(ξ) : ξ > 0} of operators on Lp(H), 1 ≤ p < 1 < ∞, which commutes with translations, and semigroup M = {Eξ : ξ > 0} of Lp(H) multipliers. These results generalize those of [HP57] for the circle groups and [B074] for compact abelian groups.

<p>Multiplication is an important part of real-time system applications. Various hardware parallel multipliers used in such applications have been proposed. However, when the operand sizes of the multipliers and the process technology need to be changed, the existing multipliers have to be redesigned. </p><p>From the point of library cell reuse, this master thesis work aims at developing a module generator for parallel multipliers with the help of software programs. This generator can be used to create the gate-level schematic for fixed point two's complement number multipliers. Based on the generated schematic, the entire multiplier can be implemented by small manual intervention. This feature can reduce the time of chip design. </p><p>The design phases consist of the logic, circuit and physical designs. The logic design includes gate-level schematic generation with C and SKILL programs and structural VHDL-code descriptions as well as validation. The circuit and physical design are custom in Cadence and the routing uses automatic place and route tools. </p><p>To demonstrate the design method, an 18 by 18-bit modified Booth recoded multiplier was implemented in 0.18 µm CMOS process with a supply voltage of 1.2 V and simulated using simulator (Spectre). The number of integrated transistors is 13000 and the active area is 85000 µm². The postlayout simulation shows the critical path with a delay of 17 ns.</p>

Security issues have started to play an important role in the wireless communication and computer networks due to the migration of commerce practices to the electronic medium. The deployment of security procedures requires the implementation of cryptographic algorithms. Performance has always been one of the most critical issues of a cryptographic function, which determines its effectiveness. Among those cryptographic algorithms are the elliptic curve cryptosystems which use the arithmetic of finite fields. Furthermore, fields of characteristic two are preferred since they provide carry-free arithmetic and at the same time a simple way to represent field elements on current processor architectures. Multiplication is a very crucial operation in finite field computations. In this contribution, we compare most of the multiplier architectures found in the literature to clarify the issue of choosing a suitable architecture for a specific application. The importance of the measuring the energy consumption in addition to the conventional measures for energy-critical applications is also emphasized. A new parallel-in serial-out multiplier based on all-one polynomials (AOP) using the shifted polynomial basis of representation is presented. The proposed multiplier is area efficient for hardware realization. Low hardware complexity is advantageous for implementation in constrained environments such as smart cards. Architecture of an elliptic curve coprocessor has been developed using the proposed multiplier. The instruction set architecture has been also designed. The coprocessor has been simulated using VHDL to very the functionality. The coprocessor is capable of performing the scalar multiplication operation over elliptic curves. Point doubling and addition procedures are hardwired inside the coprocessor to allow for faster operation.

Multiplication is an important part of real-time system applications. Various hardware parallel multipliers used in such applications have been proposed. However, when the operand sizes of the multipliers and the process technology need to be changed, the existing multipliers have to be redesigned. From the point of library cell reuse, this master thesis work aims at developing a module generator for parallel multipliers with the help of software programs. This generator can be used to create the gate-level schematic for fixed point two's complement number multipliers. Based on the generated schematic, the entire multiplier can be implemented by small manual intervention. This feature can reduce the time of chip design. The design phases consist of the logic, circuit and physical designs. The logic design includes gate-level schematic generation with C and SKILL programs and structural VHDL-code descriptions as well as validation. The circuit and physical design are custom in Cadence and the routing uses automatic place and route tools. To demonstrate the design method, an 18 by 18-bit modified Booth recoded multiplier was implemented in 0.18 µm CMOS process with a supply voltage of 1.2 V and simulated using simulator (Spectre). The number of integrated transistors is 13000 and the active area is 85000 µm2. The postlayout simulation shows the critical path with a delay of 17 ns.

Security issues have started to play an important role in the wireless communication and computer networks due to the migration of commerce practices to the electronic medium. The deployment of security procedures requires the implementation of cryptographic algorithms. Performance has always been one of the most critical issues of a cryptographic function, which determines its effectiveness. Among those cryptographic algorithms are the elliptic curve cryptosystems which use the arithmetic of finite fields. Furthermore, fields of characteristic two are preferred since they provide carry-free arithmetic and at the same time a simple way to represent field elements on current processor architectures. Multiplication is a very crucial operation in finite field computations. In this contribution, we compare most of the multiplier architectures found in the literature to clarify the issue of choosing a suitable architecture for a specific application. The importance of the measuring the energy consumption in addition to the conventional measures for energy-critical applications is also emphasized. A new parallel-in serial-out multiplier based on all-one polynomials (AOP) using the shifted polynomial basis of representation is presented. The proposed multiplier is area efficient for hardware realization. Low hardware complexity is advantageous for implementation in constrained environments such as smart cards. Architecture of an elliptic curve coprocessor has been developed using the proposed multiplier. The instruction set architecture has been also designed. The coprocessor has been simulated using VHDL to very the functionality. The coprocessor is capable of performing the scalar multiplication operation over elliptic curves. Point doubling and addition procedures are hardwired inside the coprocessor to allow for faster operation.