898 research outputs found
Large-Update Infeasible Interior-Point Methods for Linear Optimization
No full textRecently, C. Roos proposed a full-Newton step infeasible interior-point method (IIPM) for linear optimization (LO). Shortly afterwards, Mansouri and Roos presented a variant of this algorithm and Gu et al. a version with a simplified analysis. Roos' algorithm is a path-following method. It uses the so-called homotopy path as a guideline to an optimal solution. The algorithm has the advantage that it uses only full Newton steps (the step size is always 1, hence requires no computation), and its convergence rate is O(n), which coincides with the best known convergence rate for IIPMs. Apart from these nice features, the algorithm has the deficiency that it is a small-update method and hence it is too slow for practical purposes. In this thesis we design a large-update version of Roos' algorithm. We present a practically efficient implementation of (a variant of) the algorithm and compare its performance with that of the well- known LIPSOL package. The numerical results are promising as the iteration numbers of our algorithm are close to those of LIPSOL; in a few cases they outperform LIPSOL. Not surprisingly, as in large-update feasible interior-point methods (FIPMs), there is a gap between the practical and the theoretical behavior of our large-update IIPM. To be more precise, its theoretical convergence rate is O(n?n (log n)³) which is worse than the convergence rate of its full-Newton step variant. This phenomenon is well-known in the field of IPMs, and has been called the irony of IPMs: small-update methods have the best complexity results and are slow in practice, whereas large-update methods have worse complexity results and excellent performance in practice. For example, large-update FIPMs are by a factor worse than that of the full-Newton step FIPMs, i.e., O(?nlogn) versus O(?n). The thesis also contains a survey of IIPMs that have been presented by several authors in last two decades. It covers a wide range of methods, starting from Lustig's algorithm, to the infeasible potential-reduction methods of Mizuno, Kojima and Todd. We focus on convergence properties and polynomiality of the IIPMs presented in our survey.EWIElectrical Engineering, Mathematics and Computer Scienc
What's on a machine's mind? Models for reasoning with incomplete and uncertain knowledge
No full textElectrical Engineering, Mathematics and Computer Scienc
Counterexample to a Conjecture on an Infeasible Interior-Point Method
No full textIn [SIAM J. Optim., 16 (2006), pp. 1110–1136], Roos proved that the devised full-step infeasible algorithm has worst-case iteration complexity. This complexity bound depends linearly on a parameter , which is proved to be less than . Based on extensive computational evidence (hundreds of thousands of randomly generated problems), Roos conjectured that (Conjecture 5.1 in the above-mentioned paper), which would yield an iteration full-Newton step infeasible interior-point algorithm. In this paper we present an example showing that is in the order of , the same order as that proved in Roos's original paper. In other words, the conjecture is false.Software TechnologyElectrical Engineering, Mathematics and Computer Scienc
Full-step interior-point methods for symmetric optimization
No full textIn [SIAM J. Optim., 16(4):1110--1136 (electronic), 2006] Roos proposed a full-Newton step Infeasible Interior-Point Method (IIPM) for Linear Optimization (LO). It is a primal-dual homotopy method; it differs from the classical IIPMs in that it uses only full steps. This means that no line searches are needed. In this thesis, we first present an improved full-Newton step IIPM for LO. Then, based on the properties of Euclidean Jordan algebras, we generalize the improved full-Newton step IIPM for LO to full Nesterov-Todd step (NT-step) IIPM for Symmetric Optimization (SO). Since the analysis requires a quadratic convergence result for the feasible case, primal-dual feasible IPMs with full steps are presented as well. Although our devised IIPMs admit the best known iteration bound, from a practical perspective they are not efficient. This is because they always perform according to their worst-case theoretical complexity bounds, which means that only tiny reductions of the so-called barrier parameter are admitted. As a remedy, we propose a more aggressive (adaptive) updating strategy. Finally, our full NT-step IIPM for SO is implemented with both standard and adaptive updates of the barrier parameter. The significant improvement in performance of the adaptive updating strategy over the original short updating strategy is illustrated. The algorithm with adaptive updates is also used to solve problems from the well known library SDPLIB [Optim. Methods Softw., 11/12(1-4):683--690, 1999] of test problems. The results are promising, and to some extend competing with SDPT3 [Math. Program., 95(2, Ser. B):189--217, 2003].Software TechnologyElectrical Engineering, Mathematics and Computer Scienc
Guest Post: Julia Roos' Response to Victoria Harris
No full textJulia Roos, the author of Weimar through the Lens of Gender, has asked the Weimar Studies Network to publish her response to Victoria Harris' review of her book in the current issue of German History. We happily comply with her request, as the support of a lively scholarly debate is the stated aim of this forum. However, the opinions expressed in the following text are those of the author, and do not necessarily reflect those of the editors. "Victoria Harris and I disagree in our evaluation ..
Improvements to the Secure Construction and Utilization of Greedy Embeddings in Friend-to-Friend Overlays
No full textRouting based on greedy network embeddings enables efficient and privacy-preserving routing in overlays where connectivity is restricted to mutually trusted nodes. In previous works, we proposed security enhancements to the embedding and routing procedures to protect against denial-of-service attacks by malicious overlay participants. In this work, we propose an improved timeout scheme to reduce the stabilization overhead of secure tree maintenance in response to node failures and malicious behavior. Furthermore, we present an attack-resistant packet replication scheme that leverages alternative paths discovered during routing
The inscription and subsequent disclaimer of its authenticity in Thomas Reinesius and James Gruter, , Leipzig and Frankfurt, Johann Fritschens Erben, 1682, p
No full text<p><b>Copyright information:</b></p><p>Taken from "Johann Heinrich Cohausen (1665–1750), Salt Iatrochemistry, and Theories of Longevity in his Satire, (1742)"</p><p></p><p>Medical History 2007;51(2):181-200.</p><p>Published online 01 Apr 2007</p><p>PMCID:PMC1871718.</p><p>© Anna Marie Roos 2007</p> 156. (Photo by the author. With permission from the Harris Manchester College Library, Harris Manchester College, University of Oxford.
Improving Blockchain Anonymity Using Hop Changes with Partial Route Computation
No full textThe Lightning Network aims to solve Bitcoin's scalability problem by providing a way to transact with minimal use of the blockchain. Instead, payments are routed over payment channel networks. This routing is done by LN clients, which use cost functions to compute the optimal transaction path. With the use of onion routing, LN tries to hide the identity of transaction participants from each other. However, the cost functions of these routing protocols are currently too deterministic, making it possible for curious transaction participants to comprise the identity of sender and receiver by computing the optimal path themselves.Here we show that we can increase the anonymity of this network by adding randomness to these routing algorithms. More specifically, during path computation we will randomly deviate from the optimal path by hopping to a random node and continue by computing a new optimal path from there. The unpredictability of this process improves the anonymity of the network, such that malicious nodes can identify the sender and recipient of transactions with negligible probability in most cases.CSE3000 Research ProjectComputer Science and Engineerin
His+ reversions Caused in Salmonella typhimurium by different types of ionizing radiation
No full textThe yield of his+ reversions in the Ames Salmonella tester strain TA2638 has been determined for 60Co γ rays, 140 kV X rays, 5.4 keV characteristic X rays, 2.2 MeV protons, 3.1 MeV α particles, and 18 MeV/U Fe ions. Inactivation studies were performed with the same radiations. For both mutation and inactivation, the maximum effectiveness per unit absorbed dose was obtained for the characteristic X rays, which have a dose averaged linear energy transfer (LET) of roughly 10 keV/μm. The ratio of the effectiveness of this radiation to γ rays was 2 for inactivation and about 1.4 for the his+ reversion. For both end points the effectiveness decreases substantially at high LET, i.e., for the α particles and the Fe ions. The composition of the bottom and the top agar was the one recommended by Maron and Ames [Mutat. Res. 113, 173-215 (1983)] for application in chemical mutagenicity tests. The experiments with the less penetrating radiations differed from the usual protocol by utilization of a technique of plating the bacteria on the surface of the top agar. As in an earlier study [Roos et al., Radiat. Res. 104, 102-108 (1985)] greatly enhanced yields of mutations, relative to the spontaneous reversion rate, were obtained in these experiments by performing the irradiations 6 h after plating, which differs from the conventional procedure to irradiate the bacteria shortly after plating
Very Feminine, Yet Unmercifully Intelligent. A Portrait of the Dutch Critic and Translator Elisabeth de Roos (1903-1981)
No full textThe Dutch author and translator Elisabeth de Roos has largely been ignored by literary historians. Nevertheless, she played a major role in the literary scene in the Netherlands between 1925 and 1955. She was a very productive and respected essayist, critic, journalist and translator, but in the rearview mirror of literary history her husband Eddy du Perron outshined her. The contemporary gender discourse, in which de Roos herself took part, created a blind spot for the contribution to innovation and poetical conceptualisation of female authors. The infamous journal Forum to which both she and her husband contributed was a mouthpiece for a masculine discourse: being a fellow was the highest goal. After their marriage her husband pursued his writing career, whereas de Roos took care of the household and was the family breadwinner by writing journalistic pieces instead of literary work. After her husband’s death at the start of the Second World War, de Roos started to work as a translator, a profession in which she soon gained a high degree of expertise and professionalism. She wrote lengthy and substantial essays as prefaces to her translations, revealing her thoughtful literary ideas that preferred intellect and lucidity to melodrama and sentimentality and partis pris to half-heartedness. An analysis of her translation of Wuthering Heights suggests she didn’t smoothen the source text to please the target audience, in accordance with her poetics.</jats:p
- …
