No description available.

No description available.

Two bis-imidazol-2-ylidine N-heterocyclic carbenes have been employed as ancillary ligands in an attempt to illustrate their utility in the palladium-mediated preparation of aryl ethers from aryl halides. Ullman-type homo-coupling of the aryl halides persistently occurred instead of ether formation. One of the well known N-heterocyclic carbenes, IPr, was employed with the same results. A variety of reaction conditions and reagents were investigated including solvents, N-heterocyclic carbene species, palladium source, alkoxide base, palladium to ligand ratio and reaction time. Reactivity of the individual N-heterocyclic carbenes as ancillary ligands in the palladium-catalyzed amination reaction of aryl halides was investigated to determine functionality of the carbenes. Alternative procedures to prepare the key intermediates in the synthesis of the bisimidazol- 2-ylidines were developed. In this study the aryl imidazoles were prepared from the corresponding phenol and carbonyldiimidazole. Subsequent N-alkylation then furnished the Nheterocyclic carbenes in high yield. Novel unsymmetrical N-heterocyclic carbenes with aryl and benzylic side groups have been synthesized as models for the subsequent synthesis of unsymmetrical polymer-bound Nheterocyclic carbenes. The unsymmetrical ligands were employed in the palladium-catalyzed amination of aryl halides and in the Suzuki-Miyaura Reaction. Two Merrifield resin polymerbound N-heterocyclic carbene ligands were then synthesized and employed in the aryl amination and Suzuki-Miyaura Reactions. Both reactions were greatly accelerated by the implementation of microwave heating. The Merrifield resin polymer-bound palladium-ligand complexes have been recycled through several reactions without loss of activity.

In this article a new branch & bound method is described. It uses an artificial target to improve its bounding capabilities. Therefore the new approach is faster compared to the classical one. It is applied to the stochastic problem of optimal scenario tree reduction. The aspects of global optimization are emphasized here. All necessary components for that problem are developed and some experimental results underline the benefits of the new approach. (author's abstract) / Series: Working Papers on Information Systems, Information Business and Operations

Dans ce travail, nous nous intéressons à la résolution exacte de problèmes de localisation de service en variables mixtes. Les problèmes de programmation linéaire bi-objectif en variables mixtes ont été très étudiés dans les dernières années, mais uniquement dans un contexte générique. De même, les problèmes de localisation de services bi-objectif n’ont été étudiés que dans un cas purement discret. Nous considérons dans un premier temps le problème de localisation de services bi-objectif sans capacité. Afin de le résoudre, nous adaptons la méthode de pavage par boîtes proposée pour le cas discret. Les boîtes rectangulaires deviennent triangulaires dans le cas mixte. De plus, leur exploration est grandement facilitée, ce qui déplace la difficulté du problème dans l’énumération et le filtrage de ces boîtes. Différentes stratégies d’énumération sont proposées. Le problème de localisation de services bi-objectif avec capacité est ensuite considéré. Tout d’abord, une adaptation de la méthode de pavage par boîtes triangulaires est réalisée pour le cas avec capacité. Cependant, la nature du problème rend cette méthode beaucoup plus limitée. Nous considérons ensuite une méthode en deux phases dont la principale routine d’exploration repose sur une adaptation d’un algorithme de branch and bound initialement proposé par Beasley, dans le contexte bi-objectif. Les résultats expérimentaux sur des instances aux caractéristiques variées attestent de la pertinence des méthodes que nous proposons. / The purpose of this work is the exact solution of biobjective mixed-integer facility location problems. Biobjective mixed integer linear programming problem have been largely studied in recent years but only in the generic context. The same way, the study of biobjective facility location problems has been restricted to the discrete case. We consider first the bi-objective uncapacitated facility location problem. To solve it, we adapt the box paving method proposed for the discrete case. Rectangular boxes become triangular. Moreover, their exploration becomes considerably easier. The difficulty of the problem is therefore translated to the enumeration and the filtering of these boxes. Different enumeration strategies are proposed. Next, we consider the bi-objective capacitated facility location problem. We first propose an adaptation of the triangular box paving method to the capacitated case. However, the structure of the problem highly limits the method. Thus, we consider a two phase method. The main exploration routine is based on the adaptation of a branch and bound algorithm proposed by Beasley that we adapt to the bi-objective context. Experimental results on various instances show the efficiency of the proposed methods.

by Mei Long. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2003. / Includes bibliographical references (leaves 93-98). / Abstracts in English and Chinese. / Table of Contents --- p.v / Abstract --- p.viii / Acknowledgements --- p.x / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Satisfiability Problem --- p.1 / Chapter 1.2 --- Motivation of the Research --- p.1 / Chapter 1.3 --- Overview of the Thesis --- p.2 / Chapter 2 --- Satisfiability Problem --- p.4 / Chapter 2.1 --- Satisfiability Problem --- p.5 / Chapter 2.1.1 --- Basic Definition --- p.5 / Chapter 2.1.2 --- Phase Transitions --- p.5 / Chapter 2.2 --- History --- p.6 / Chapter 2.3 --- The Basic Search Algorithm --- p.8 / Chapter 2.4 --- Some Improvements to the Basic Algorithm --- p.9 / Chapter 2.4.1 --- Satz by Chu-Min Li --- p.9 / Chapter 2.4.2 --- Heuristics and Local Search --- p.12 / Chapter 2.4.3 --- Relaxation --- p.13 / Chapter 2.5 --- Benchmarks --- p.14 / Chapter 2.5.1 --- Specific Problems --- p.14 / Chapter 2.5.2 --- Randomly Generated Problems --- p.14 / Chapter 2.6 --- Software and Internet Information for SAT solving --- p.16 / Chapter 2.6.1 --- Stochastic Local Search Algorithms (incomplete) --- p.16 / Chapter 2.6.2 --- Systematic Search Algorithms (complete) --- p.16 / Chapter 2.6.3 --- Some useful Links to SAT Related Sites --- p.17 / Chapter 3 --- Integer Programming Formulation for Logic Problem --- p.18 / Chapter 3.1 --- SAT Problem --- p.19 / Chapter 3.2 --- MAXSAT Problem --- p.19 / Chapter 3.3 --- Logical Inference Problem --- p.19 / Chapter 3.4 --- Weighted Exact Satisfiability Problem --- p.20 / Chapter 4 --- Integer Programming Formulation for SAT Problem --- p.22 / Chapter 4.1 --- From 3-CNF SAT Clauses to Zero-One IP Constraints --- p.22 / Chapter 4.2 --- Integer Programming Model for 3-SAT --- p.23 / Chapter 4.3 --- The Equivalence of the SAT and the IP --- p.23 / Chapter 4.4 --- Example --- p.24 / Chapter 5 --- Integer Solvability of Linear Programs --- p.27 / Chapter 5.1 --- Unimodularity --- p.27 / Chapter 5.2 --- Totally Unimodularity --- p.28 / Chapter 5.3 --- Some Results on Recognition of Linear Solvability of IP --- p.32 / Chapter 6 --- TU Based Matrix Research Results --- p.33 / Chapter 6.1 --- 2x2 Matrix's TU Property --- p.33 / Chapter 6.2 --- Extended Integer Programming Model for SAT --- p.34 / Chapter 6.3 --- 3x3 Matrix's TU Property --- p.35 / Chapter 7 --- Totally Unimodularity Based Branching-and-Bound Algorithm --- p.38 / Chapter 7.1 --- Introduction --- p.38 / Chapter 7.1.1 --- Enumeration Trees --- p.39 / Chapter 7.1.2 --- The Concept of Branch and Bound --- p.42 / Chapter 7.2 --- TU Based Branching Rule --- p.43 / Chapter 7.2.1 --- How to sort variables based on 2x2 submatrices --- p.43 / Chapter 7.2.2 --- How to sort the rest variables --- p.45 / Chapter 7.3 --- TU Based Bounding Rule --- p.46 / Chapter 7.4 --- TU Based Branch-and-Bound Algorithm --- p.47 / Chapter 7.5 --- Example --- p.49 / Chapter 8 --- Numerical Result --- p.57 / Chapter 8.1 --- Experimental Result --- p.57 / Chapter 8.2 --- Statistical Results of ILOG CPLEX --- p.59 / Chapter 9 --- Conclusions --- p.61 / Chapter 9.1 --- Contributions --- p.61 / Chapter 9.2 --- Future Work --- p.62 / Chapter A --- The Coefficient Matrix A for Example in Chapter 7 --- p.64 / Chapter B --- The Detailed Numerical Information of Solution Process for Exam- ple in Chapter 7 --- p.66 / Chapter C --- Experimental Result --- p.67 / Chapter C.1 --- "# of variables: 20, # of clauses: 91" --- p.67 / Chapter C.2 --- "# of variables: 50, # of clauses: 218" --- p.70 / Chapter C.3 --- # of variables: 75，# of clauses: 325 --- p.73 / Chapter C.4 --- "# of variables: 100, # of clauses: 430" --- p.76 / Chapter D --- Experimental Result of ILOG CPLEX --- p.80 / Chapter D.1 --- # of variables: 20´ة # of clauses: 91 --- p.80 / Chapter D.2 --- # of variables: 50，#of clauses: 218 --- p.83 / Chapter D.3 --- # of variables: 75，# of clauses: 325 --- p.86 / Chapter D.4 --- "# of variables: 100, # of clauses: 430" --- p.89 / Bibliography --- p.93

In recent years, unprecedented growths in scale and dimensionality of data raise big computational challenges for traditional optimization algorithms; thus it becomes very important to develop efficient and effective optimization algorithms for solving numerous machine learning problems. Many traditional algorithms (e.g., gradient descent method) are black-box algorithms, which are simple to implement but ignore the underlying geometrical property of the objective function. Recent trend in accelerating these traditional black-box algorithms is to leverage geometrical properties of the objective function such as strong convexity. However, most existing methods rely too much on the knowledge of strong convexity, which makes them not applicable to problems without strong convexity or without knowledge of strong convexity. To bridge the gap between traditional black-box algorithms without knowing the problem's geometrical property and accelerated algorithms under strong convexity, how can we develop adaptive algorithms that can be adaptive to the objective function's underlying geometrical property? To answer this question, in this dissertation we focus on convex optimization problems and propose to explore an error bound condition that characterizes the functional growth condition of the objective function around a global minimum. Under this error bound condition, we develop algorithms that (1) can adapt to the problem's geometrical property to enjoy faster convergence in stochastic optimization; (2) can leverage the problem's structural regularizer to further improve the convergence speed; (3) can address both deterministic and stochastic optimization problems with explicit max-structural loss; (4) can leverage the objective function's smoothness property to improve the convergence rate for stochastic optimization. We first considered stochastic optimization problems with general stochastic loss. We proposed two accelerated stochastic subgradient (ASSG) methods with theoretical guarantees by iteratively solving the original problem approximately in a local region around a historical solution with the size of the local region gradually decreasing as the solution approaches the optimal set. Second, we developed a new theory of alternating direction method of multipliers (ADMM) with a new adaptive scheme of the penalty parameter for both deterministic and stochastic optimization problems with structured regularizers. With LEB condition, the proposed deterministic and stochastic ADMM enjoy improved iteration complexities of $\widetilde O(1/\epsilon^{1-\theta})$ and $\widetilde O(1/\epsilon^{2(1-\theta)})$ respectively. Then, we considered a family of optimization problems with an explicit max-structural loss. We developed a novel homotopy smoothing (HOPS) algorithm that employs Nesterov's smoothing technique and accelerated gradient method and runs in stages. Under a generic condition so-called local error bound (LEB) condition, it can improve the iteration complexity of $O(1/\epsilon)$ to $\widetilde O(1/\epsilon^{1-\theta})$ omitting a logarithmic factor with $\theta\in(0,1]$. Next, we proposed new restarted stochastic primal-dual (RSPD) algorithms for solving the problem with stochastic explicit max-structural loss. We successfully got a better iteration complexity than $O(1/\epsilon^2)$ without bilinear structure assumption, which is a big challenge of obtaining faster convergence for the considered problem. Finally, we consider finite-sum optimization problems with smooth loss and simple regularizer. We proposed novel techniques to automatically search for the unknown parameter on the fly of optimization while maintaining almost the same convergence rate as an oracle setting assuming the involved parameter is given. Under the Holderian error bound (HEB) condition with $\theta\in(0,1/2)$, the proposed algorithm also enjoys intermediate faster convergence rates than its standard counterparts with only the smoothness assumption.

The objective of this thesis is to develop and computationally test a new algorithm for the class of network models with generalized upper bound (GUB) side constraints. Various algorithms have been developed to solve the network with arbitrary side constraints problem; however, no algorithm that exploits the special structure of the GUB side constraints previously existed. The proposed algorithm solves the network with GUB side constraints problem using two sequences of problems. One sequence yields a lower bound on the optimal value for the problem by using a Lagrangean relaxation based on relaxing copies of some subset of the original variables. This is achieved by first solving a pure network subproblem and then solving a set of single constraint bounded variable linear programs. Because only the cost coefficients change from one pure network subproblem to another, the optimal solution for one subproblem is at least feasible, if not optimal, for the next pure network subproblem. The second sequence yields an upper bound on the optimal value by using a decomposition of the problem based on changes in the capacity vector. Solving for the decomposed problem corresponds to solving for pure network subproblems that have undergone changes in lower and/or upper bounds. Recently developed reoptimization techniques are incorporated in the algorithm to find an initial (artificial) feasible solution to the pure network subproblem. A program is developed for solving the network with GUB side constraints problem by using the relaxation and decomposition techniques. The algorithm has been tested on problems with up to 200 nodes, 2000 arcs and 100 GUB constraints. Computational experience indicates that the upper bound procedure seems to perform well; however, the lower bound procedure has a fairly slow convergence rate. It also indicates that the lower bound step size, the initial lower bound value, and the lower and upper bound iteration strategies have a significant effect on the convergence rate of the lower bound algorithm. / Graduation date: 1990

No description available.

A star graph consists of an arbitrary number of segments that are joined at a point which is called the vertex. In this work it is investigated from a pure theoretical point of view, in the framework of quantum field theory. As a concrete physical application, the electric conductance tensor is obtained. In particular it is shown that this conductance behaves differently according to whether the scattering matrix associated with the vertex of the graph has bound-state poles or not.