On the convergence of general regularization and smoothing schemes for mathematical programs with complementarity constraints

We extend the convergence analysis of a smoothing method [M. Fukushima and J.-S. Pang (2000). Convergence of a smoothing continuation method for mathematical programs with complementarity constraints. In: M. Théra and R. Tichatschke (Eds.), Ill-posed Variational Problems and Regularization Techniques, pp. 99–110. Springer, Berlin/Heidelberg.] to a general class of smoothing functions and show that a weak second-order necessary optimality condition holds at the limit point of a sequence of stationary points found by the smoothing method. We also show that convergence and stability results in [S. Scholtes (2001). Convergence properties of a regularization scheme for mathematical programs with complementarity constraints. SIAM J. Optim., 11, 918–936.] hold for a relaxation problem suggested by Scholtes [S. Scholtes (2003). Private communications.] using a class of smoothing functions. In addition, the relationship between two technical, yet critical, concepts in [M. Fukushima and J.-S. Pang (2000). Convergence of a smoothing continuation method for mathematical programs with complementarity constraints. In: M. Théra and R. Tichatschke (Eds.), Ill-posed Variational Problems and Regularization Techniques, pp. 99–110. Springer, Berlin/Heidelberg; S. Scholtes (2001). Convergence properties of a regularization scheme for mathematical programs with complementarity constraints. SIAM J. Optim., 11, 918–936.] for the convergence analysis of the smoothing and regularization methods is discussed and a counter-example is provided to show that the stability result in [S. Scholtes (2001). Convergence properties of a regularization scheme for mathematical programs with complementarity constraints. SIAM J. Optim., 11, 918–936.] cannot be extended to a weaker regularization.     

On the mixing time of a simple random walk on the super critical percolation cluster

 We study the robustness under perturbations of mixing times, by studying mixing times of random walks in percolation clusters inside boxes in Z ^d . We show that for d≥2 and p>p _c (Z ^d ), the mixing time of simple random walk on the largest cluster inside is Θ(n ² ) – thus the mixing time is robust up to a constant factor. The mixing time bound utilizes the Lovàsz-Kannan average conductance method. This is the first non-trivial application of this method which yields a tight result. Received: 16 December 2001 / Revised version: 13 August 2002 / Published online: 19 December 2002     

Univalence Criteria Starting from the Method of Loewner Chains

The paper continues the work of Royster (Duke Math J 19:447–457, 1952), Mocanu [Mathematica (Cluj) 22(1):77–83, 1980; Mathematica (Cluj) 29:49–55, 1987], Cristea [Mathematica (Cluj) 36(2):137–144, 1994; Complex Var 42:333–345, 2000; Mathematica (Cluj) 43(1):23–34, 2001; Mathematica (Cluj), 2010, to appear; Teoria Topologica a Functiilor Analitice, Editura Universitatii Bucuresti, Romania, 1999] of extending univalence criteria for complex mappings to C ¹ mappings. We improve now the method of Loewner chains which is usually used in complex univalence theory for proving univalence criteria or for proving quasiconformal extensions of holomorphic mappings f : B → C ⁿ to C ⁿ . The results are surprisingly strong. We show that the usual results from the theory, like Becker’s univalence criteria remain true for C ¹ mappings and since we use a stronger form of Loewner’s theory, we obtain results which are stronger even for holomorphic mappings f : B → C ⁿ . In our main result (Theorem 4.1) we end the researches dedicated to quasiconformal extensions of K-quasiregular and holomorphic mappings f : B → C ⁿ to C ⁿ . We show that a C ¹ quasiconformal map f : B → C ⁿ can be extended to a quasiconformal map F : C ⁿ → C ⁿ , without any metric condition imposed to the map f.     

Well Posedness for Multilane Traffic Models

Abstract We give rigorous results on the analytical properties of multilane traffic flow models based on hyperbolic balance laws. Keywords: Traffic flows, Hyperbolic conservatin laws, Operator splitting method     

On a perturbed anisotropic equation with a critical exponent

Abstract We study a perturbed anisotropic equation without using the knowledge of the limiting problem. This provides a different method from that introduced by Brézis and Nirenberg [4]. Our arguments use some tools recently developed in [5, 6]. Keywords: Anisotropic critical exponent, Critical level, Compactness, Nehari manifold Mathematics Subject Classification (2000): 35J25, 35J60, 35J65     

The core and nucleolus of games: A note on a paper by Göthe-Lundgren et al.

In the paper “On the nucleolus of the basic vehicle routing game”, Mathematical Programming 72, 83–100 (1996), G?the-Lundgren et al. develop a constraint generation method to compute the pre-nucleolus of a game. Their method assumes that constraints that are redundant in the representation of the core can be ignored in the computation of the pre-nucleolus. We provide an example that shows that for a game with an empty core such an assumption is, in general, not valid. Further, we show that a statement made by G?the-Lundgren et al. about an intuitive interpretation of the pre-nucleolus is misleading. Received: January 1996 / Accepted: February 2000?Published online January 17, 2001     

A proof of independent Bartlett correctability of nested likelihood ratio tests

It is well known that likelihood ratio statistic is Bartlett correctable. We consider decomposition of a likelihood ratio statistic into 1 degree of freedom components based on sequence of nested hypotheses. We give a proof of the fact that the component likelihood ratio statistics are distributed mutually independently up to the order O(1/n) and each component is independently Bartlett correctable. This was implicit in Lawley (1956, Biometrika, 43, 295–303) and proved in Bickel and Ghosh (1990, Ann. Statist., 18, 1070–1090) using a Bayes method. We present a more direct frequentist proof.     

IPO estimation of heaviness of the distribution beyond regularly varying tails

Abstract

We introduce a completely novel method for estimation of the parameter which governs the tail behavior of the cumulative distribution function of the observed random variable. We call it Inverse Probabilities for p-Outside values (IPO) estimation method. We show that this approach is applicable for wider class of distributions than the one with regularly varying tails. We demonstrate that IPO method is a valuable competitor to regularly varying tails based estimation methods. Some of the properties of the estimators are derived. The results are illustrated by a convenient simulation study.     

On the distribution of Lachlan nonsplitting bases

 We say that a computably enumerable (c.e.) degree b is a Lachlan nonsplitting base (LNB), if there is a computably enumerable degree a such that a > b, and for any c.e. degrees w,v ≤ a, if a ≤ w or; v or; b then either a ≤ w or; b or a ≤ v or; b. In this paper we investigate the relationship between bounding and nonbounding of Lachlan nonsplitting bases and the high /low hierarchy. We prove that there is a non-Low₂ c.e. degree which bounds no Lachlan nonsplitting base. Received: 11 October 1999 / Published online: 7 May 2002     

Implementation of an adaptive finite-element approximation of the Mumford-Shah functional

Summary. We present and detail a method for the numerical solving of the Mumford-Shah problem, based on a finite element method and on adaptive meshes. We start with the formulation introduced in [13], detail its numerical implementation and then propose a variant which is proved to converge to the Mumford-Shah problem. A few experiments are illustrated. Received October 8, 1998 / Published online: April 20, 2000     

On the predicate logics of continuous t-norm BL-algebras

Given a class C of t-norm BL-algebras, one may wonder which is the complexity of the set Taut(C) of predicate formulas which are valid in any algebra in C. We first characterize the classes C for which Taut(C) is recursively axiomatizable, and we show that this is the case iff C only consists of the Gödel algebra on [0,1]. We then prove that in all cases except from a finite number Taut(C) is not even arithmetical. Finally we consider predicate monadic logics Taut_M(C) of classes C of t-norm BL-algebras, and we prove that (possibly with finitely many exceptions) they are undecidable.Mathematics Subject Classification (2000): Primary: 03B50, Secondary: 03B47Acknowledgement The author is deeply indebted to Petr Hájek, whose results about the complexity problems of predicate fuzzy logics constitute the main motivation for this paper, and whose suggestions and remarks have been always stimulating. He is also indebted to Matthias Baaz, who pointed out to him a method used in [BCF] for the case of monadic Gödel logic which works with some modifications also in the case of monadic BL logic.     

Comments on an ancient Greek racecourse: finding minimum width annuluses

For a set of measured points, we describe a linear-programming model that enables us to find concentric circumscribed and inscribed circles whose annulus encompasses all the points and whose width tends to be minimum in a Chebychev minmax sense. We illustrate the process using the data of Rorres and Romano (SIAM Rev. 39: 745–754, 1997) that is taken from an ancient Greek stadium in Corinth. The stadium’s racecourse had an unusual circular arc starting line, and measurements along this arc form the basic data sets of Rorres and Romano (SIAM Rev. 39: 745–754, 1997). Here we are interested in finding the center and radius of the circle that defined the starting line arc. We contrast our results with those found in Rorres and Romano (SIAM Rev. 39: 745–754, 1997).     

Note on implementing the new sphere method for LP using matrix inversions sparingly

A new IPM (interior point method) for LPs has been discussed in Murty (Algorithmic Oper Res 1:3–19, 2006; Tutorials in OR, INFORMS, pp 1–36, 2006) based on a centering step that attempts to maximize the radius of the inscribed sphere with center on the current objective plane, and using descent directions derived without using matrix inversions. The method is a descent method and may be called the sphere method for LP. In contrast to all the existing IPMs which involve heavy matrix inversions in each step, an advantage of the new method is that it can be implemented with no matrix inversions, or using them only sparingly. We discuss various techniques for implementing this method. These implementations offer the prospect of extending the superior performance of existing software systems for LP, to models that do not have the property of being very sparse.     

On relative enumerability of Turing degrees

Let d be a Turing degree, R[d] and Q[d] denote respectively classes of recursively enumerable (r.e.) and all degrees in which d is relatively enumerable. We proved in Ishmukhametov [1999] that there is a degree d containing differences of r.e.sets (briefly, d.r.e.degree) such that R[d] possess a least elementm 0. Now we show the existence of a d.r.e. d such that R[d] has no a least element. We prove also that for any REA-degree d below 0 the class Q[d] cannot have a least element and more generally is not bounded below by a non-zero degree, except in the trivial cases. Received: 17 January 1996     

The volume algorithm revisited: relation with bundle methods

 We revise the Volume Algorithm (VA) for linear programming and relate it to bundle methods. When first introduced, VA was presented as a subgradient-like method for solving the original problem in its dual form. In a way similar to the serious/null steps philosophy of bundle methods, VA produces green, yellow or red steps. In order to give convergence results, we introduce in VA a precise measure for the improvement needed to declare a green or serious step. This addition yields a revised formulation (RVA) that is halfway between VA and a specific bundle method, that we call BVA. We analyze the convergence properties of both RVA and BVA. Finally, we compare the performance of the modified algorithms versus VA on a set of Rectilinear Steiner problems of various sizes and increasing complexity, derived from real world VLSI design instances. Received: December 1999 / Accepted: September 2002 Published online: December 19, 2002 Key Words. volume algorithm – bundle methods – Steiner problems Correspondence to: Claudia A. Sagastizábal, e-mail: sagastiz@impa.br     

Facial reduction for symmetry reduced semidefinite and doubly nonnegative programs

We consider both facial reduction, FR, and symmetry reduction, SR, techniques for semidefinite programming, SDP. We show that the two together fit surprisingly well in an alternating direction method of multipliers, ADMM, approach. In fact, this approach allows for simply adding on nonnegativity constraints, and solving the doubly nonnegative, DNN , relaxation of many classes of hard combinatorial problems. We also show that the singularity degree remains the same after SR, and that the DNN relaxations considered here have singularity degree one, that is reduced to zero after FR. The combination of FR and SR leads to a significant improvement in both numerical stability and running time for both the ADMM and interior point approaches. We test our method on various DNN relaxations of hard combinatorial problems including quadratic assignment problems with sizes of more than \(n=500\). This translates to a semidefinite constraint of order 250, 000 and \(625\times 10^8\) nonnegative constrained variables, before applying the reduction techniques.

     

Two complexity results on c-optimality in experimental design

Finding a c-optimal design of a regression model is a basic optimization problem in statistics. We study the computational complexity of the problem in the case of a finite experimental domain. We formulate a decision version of the problem and prove its NP\boldsymbol{\mathit{NP}}-completeness. We provide examples of computationally complex instances of the design problem, motivated by cryptography. The problem, being NP\boldsymbol{\mathit{NP}}-complete, is then relaxed; we prove that a decision version of the relaxation, called approximate c-optimality, is P-complete. We derive an equivalence theorem for linear programming: we show that the relaxed c-optimality is equivalent (in the sense of many-one LOGSPACE-reducibility) to general linear programming.     

A Stochastic Minimum Cross-Entropy Method for Combinatorial Optimization and Rare-event Estimation*

We present a new method, called the minimum cross-entropy (MCE) method for approximating the optimal solution of NP-hard combinatorial optimization problems and rare-event probability estimation, which can be viewed as an alternative to the standard cross entropy (CE) method. The MCE method presents a generic adaptive stochastic version of Kull-backs classic MinxEnt method. We discuss its similarities and differences with the standard cross-entropy (CE) method and prove its convergence. We show numerically that MCE is a little more accurate than CE, but at the same time a little slower than CE. We also present a new method for trajectory generation for TSP and some related problems. We finally give some numerical results using MCE for rare-events probability estimation for simple static models, the maximal cut problem and the TSP, and point out some new areas of possible applications.AMS 2000 Subject Classification: 65C05, 60C05, 68W20, 90C59*This reseach was supported by the Israel Science Foundation (grant no 191-565).     

The regular p-gonal prism tilings and their optimal hyperball packings in the hyperbolic 3-space

Summary We investigate the regular p-gonal prism tilings (mosaics) in the hyperbolic 3-space that were classified by I. Vermes in<span lang=EN-US style='font-size:10.0pt; mso-ansi-language:EN-US'>[12]and [13]. The optimal hyperball packings of these tilings are generated by the ``inscribed hyperspheres' whose metric data can be calculated by our method -- based on the projective interpretation of the hyperbolic geometry -- by the volume formulas of J. Bolyai and R. Kellerhals, respectively. We summarize in some tables the data and the densities of the optimal hyperball packings to each prism tiling in the hyperbolic space H³.     

Change of generalized indices of stationary solutions. to multiparametric optimization

We study the local change of the generalized index, which is a modification of the Morse index and the stationary index, for the multiparametric optimization. Under the Regular Value Condition, the change of the generalized index around a triplet (x,v,t) is locally bounded by the dimension of the parameter vector t, where x is a variable vector and v a vector of the Lagrange multiplier space. We also discuss the local change of the generalized index around a pair (x,t). Received: March 27, 1998 / Accepted: January 29, 2000?Published online April 20, 2000