The Quasi-Cauchy Relation and Diagonal Updating
CORR 1997-25
M. Zhu, J.L. Nazareth, and H. Wolkowicz
Abstract
The quasi-Cauchy (QC) relation is the weak-secant or weak-quasi-Newton relation of Dennis and Wolkowicz [3] with the added restriction that full matrices are replaced by diagonal matrices. The latter are especially appropriate for scaling a Cauchy (steepest-descent) algorith, hence our choice of terminology.
In this article, we explore the QC relation and develop variational techniques for updating diagonal matrices that satisfy it. Numerical results are also given to illustrate the use of such updates within a Cauchy algorithm.
On the Condition Numbers for Polyhedra in Karmarkar's Form
CORR 1997-24
Levent Tuncel
Abstract
We present formulations of two condition measures (one for linear programming (LP) due to Ye, and the other for a matrix) as optimization problems over sign constraints. We construct, based on LP duality, a dual characterization of Ye's condition measure in the setting of Karmarkar's form. The elementary formulations (without utilizing the dual characterization) lead to trivial proofs of some results relating these two condition measures for polyhedra in Karmarkar's form. Such interpretations, using the sign constraints, allow for the definition of families of condition measures that are "between" the two condition measures. Our viewpoint provides further understanding of the relationship of the two condition measures. As a result of this new understanding, we point to a connection with oriented matroids and prove that a conjecture of Vavasis and Ye on the relationship of these two condition measures is false.
Fenchel conjugates and subdifferentials in Maple
CORR 1997-23
Heinz H. Bauschke and Martin von Mohrenschildt
Abstract
The notions of the Fenchel conjugate and the subdifferential of a convex function are fundamental in optimization. The package fenchel allows the symbolic computation of these objects for numerous convex functions defined on the real line.
Logarithmic Concavity and sl_2 (C)
CORR 1997-22
David G. Wagner
Abstract
We observe that for any logarithmically concave finite sequence \(a_0, a_1 \cdots , a_n\) of positive integers there is a representation of the Lie algebra \(sl_2\)(C) from which this logarithmic concavity follows. Thus, in applying this strategy to prove logarithmic concavity, the issue is to construct such a representation naturally from given combinatorial data. As an example, we do this when \(a_j\) is the number of \(j\)-element stable sets in a claw-free graph, reproving a theorem of Hamidoune.
The Optimal Path-Matching Problem
CORR 1997-21
William H. Cunningham and James F. Geelen
Abstract
We describe a common generalization of the weighted matching problem and the weighted matroid intersection problem. In this context we establish common generalizations of the main results on those two problems - polynomial-time solvability, min-max theorems, and totally dual integral polyhedral descriptions. New applications of these results include a strongly polynomial separation algorithm for the convex hull of matchable sets of a graph, and a polynomial-time algorithm to compute the rank of a certain matrix of indeterminates.
Analysis of Ben-Or's polynomial irreducibility test
CORR 1997-20
Daniel Panario and Bruce Richmond
Abstract
We give a precise average-case analysis of Ben-Or's algorithm for testing the irreducibility of polynomials over finite fields. First, we study the probability that a random polynomial of degree n over F_q contains no irreducible factors of degree less than \(m, 1 \leq m \leq n\). The results are given in terms of the Buchstab function. Then, we compute the expectation and variance of the smallest degree among the irreducible factors of a random polynomial. The analysis of Ben-Or's algorithm readily follows from this expectation. We also compute the probability of a polynomial being irreducible when it has no irreducible factors of degree less than \(m, 1 \leq m \leq n \). This probability is useful in the analysis of some algorithms for factoring polynomials over finite fields.
Strong conical hull intersections property, bounded linear regularity, Jameson's property (G), and error bounds in convex optimization
CORR 1997-19
Heinz H. Bauschke, Jonathan M. Borwei,n and Wu Li
Abstract
The strong conical hull intersection property and bounded linear regularity are properties of a collection of finitely many closed convex intersecting sets in Euclidean space. These fundamental notions occur in various branches of convex optimization (constrained approximation, convex feasibility problems, linear inequalities, for instance). It is shown that the standard constraint qualification from convex analysis implies bounded linear regularity, which in turn yields the strong conical hull intersection property. Jameson's duality for two cones, which relates bounded linear regularity to property (G), is re-derived and refined. For polyhedral cones, a statement dual to Hoffman's error bound result is obtained. A sharpening of a result on error bounds for convex inequalities by Auslender and Crouzeix is presented. Finally, for two subspaces, property (G) is quantified by the angle between the subspaces.
Dykstra's Algorithm with Bregman Projections: a convergence proof
CORR 1997-18
Heinz H. Bauschke and Adrian S. Lewis
Abstract
Dykstra's algorithm and the method of cyclic Bregman projections are often employed to solve best approximation and convex feasibility problems, which are fundamental in mathematics and the physical sciences. Censor and Reich very recently suggested a synthesis of these methods, Dkystra's algorithm with Bregman projections, to tackle a non-orthogonal best approximation problem. They obtained convergence when each constraint is a halfspace. It is shown here that this new algorithm works for general closed convex constraints; this complements Censor and Reich's result and related to a framework by Tseng. The proof rests on Boyle and Dykstra's original work and on strong properties of Bregman distances corresponding to legendre functions. Special cases and observations simplifying the implementation of the algorithm are also discussed.
Key Agreement Protocols and their Security Analysis
CORR 1997-17
Simon Blake-Wilson, Don Johnson, and Alfred Menezes
Abstract
This paper proposes new protocols for two goals: authenticated key agreement and authenticated key agreement with key confirmation in the asymmetric (public-key) setting. A formal model of distributed computing is provided, and a definition of the goals within this model supplied. The protocols proposed are then proven correct within this framework in the random oracle model. We emphasize the relevance of these theoretical results to the security of systems used in practice. Practical implementation of the protocols is discussed. Such implementations are currently under consideration for standardization [2,3,21].
On the Generic Properties of Convex Optimization Problems in Conic Form
CORR 1997-16
Gabor Pataki and Levent Tuncel
Abstract
We prove that strict complementarity, primal and dual nondegeneracy are generic properties of convex optimization problems in conic form. Our proof is elementary and it employs an important result due to Larman on the boundary structure of convex bodies.
Zeros of Genus Polynomials of Graphs in Some Linear Families
CORR 1997-15
David G. Wagner
Abstract
The genus polynomials \(gp_G(x)\) of a graph \(G\) enumerates oriented two-cell embeddings of \(G\) with respect to the genus of the ambient surface. In 1997, Stahl conjectured that for any graph \(G\) all zeros of \(gp_G(x)\) are real and nonpositive. We establish conditions sufficient to imply that all graphs in a linear family satisfy Stahl's conjecture, and use this to provide further evidence for it.
Ear Decompositions of Matching Covered Graphs
CORR 1997-14
Marcelo H. Carvalho, Claudio L. Lucchesi, and U.S.R. Murty
Abstract
Ear decompositions of matching covered graphs are important for understanding their structure. By exploiting the properties of the dependence relation introduced by Carvalho and Lucchesi in [2], we are able to provide simple proofs of several well-known theorems concerning ear decompositions. Our method actually provides proofs of generalizations of these theorems. For example, we show that every matching covered graph \(G\) different from \(K_2\) has at least \(\Delta\) edge-disjoint removable ears, where \(\Delta\) is the maximum degree of $G$. This shows that any matching covered graph \(G\) has at least $\Delta!$ different ear decompositions, and thus is a generalization of the fundamental theorem of Lovasz and Plummer establishing the existence of ear decompositions. We also show that every brick $G$ different from $K_4$ and \(\bar{C}_6\) has \(\Delta - 2\) edges, each of which is a removable edge in $G$, that is, an edge whose deletion from $\(G\) results in a matching covered graph. This generalizes a well-known theorem of Lovasz. Using this theorem, we give a simple proof of another theorem due to Lovasz which says that every non-bipartite matching covered graph has a canonical ear decomposition, that is, one in which either the third graph in the sequence is an odd-subdivision of \(K_4\) or the fourth graph in the sequence is an odd-subdivision of \(\bar{C}_6\). Our method in fact shows that every non-bipartite matching covered graph has a canonical ear decomposition which is optimal, that is one which has as few double ears as possible. Most of these results appear in the Ph.D. thesis, [3], of the first author written under the supervision of the second author.
Transitive Factorisations in the Symmetric Group, and Combinatorial Aspects of Singularity Theory
CORR 1997-13
I.P. Goulden and D.M. Jackson
Abstract
We consider the determination of the number $c_k(\alpha)$ of ordered factorisations of an arbitrary permutation on $n$ symbols, with cycle distribution $\alpha$, into $k$-cycles such that the factorisations have minimal length and such that the group generated by the factors acts transitively on the $n$ symbols. The case $k=2$ corresponds to the celebrated result of Hurwitz on the number of topologically distinct holomorphic functions on the 2-sphere that preserve a given number of elementary branch point singularities. In this case the monodromy group is the full symmetric group. For $k=3$, the monodromy group is the alternating group, and this is another case that, in principle, is of considerable interest.
We conjecture an explicit form, for arbitrary $k$, for the generating series for $c_k(\alpha)$, and prove that it holds for factorisations of permutations with one, two and three cycles ($\alpha$ is a partition with at most three parts). The generating series is naturally expressed in terms of the symmetric functions dual to the those introduced by Macdonald for the "top" connection coefficients in the class algebra of the symmetric group.
Our approach is to determine a differential equation for the generating series from a combinatorial analysis of the creation and annihilation of cycles in products under the minimality condition.
A Combinatorial Relationship Between Eulerian Maps and Hypermaps in Orientable Surfaces
CORR 1997-12
D.M. Jackson and T.I. Visentin
Abstract
There is a remarkable relationship between the genus series for rooted maps and rooted quadrangulations that has been obtained by a character theoretic argument. Hitherto no combinatorial explanation for this has been given. In this paper we generalise this relationship to a larger set of maps for which such a relationship can be found and we ascertain some of the properties that a putative bijection must possess. Several examples of images of sets under this bijection are given. We give them in detail since they may contain useful information about the bijection.
On a Representation of the Matching Polytope Via Semidefinite Liftings
CORR 1997-11
Tamon Stephen and Levent Tuncel
Abstract
We consider the relaxation of the matching polytope defined by the non-negativity and degree constraints. We prove that given an undirected graph on $n$ nodes and the corresponding relaxation of the matching polytope, $\lfloor \frac{n}{2} \rfloor$ iterations of the Lovasz-Schrijver semidefinite lifting procedure are needed to obtain the matching polytope, in the worst case. We show that $\lfloor \frac{n}{2} \rfloor$ iterations of the procedure always suffice.
The Product $\Prod^n_{j=1} (1 - x^{a_{j}})$
CORR 1997-10
J. Bell, P. Borwein, and L.B. Richmond
Abstract
We estimate the maximum of $\Prod^n_{j=1} |1 - x^{a_{j}}|$ on the unit circle where $1 \leq a_1 \leq a_2 \leq$ is a sequence of integers. We show that when $a_j$ is $j^k$ or when $a_j$ is a quadratic in $j$ that takes on positive integer values, the maximum grows as exp(cn), where $c$ is a positive constant. This complements results of Sudler and Wright that show exponential growth when $a_j$ is $j$.
In contrast we show, under fairly general conditions, that the maximum is less than $2^n/n^r$, where $r$ is an arbitrary positive number. One consequence is that the number of partitions of $m$ with an even number of parts chosen from $a_1, a_2, \ldots , a_n$ is asymptotically equal to the number of such partitions with an odd number of parts when $a_i$ satisfies these general conditions.
An Interior-Point Method for the Euclidean Distance Matrix Completion Problem
CORR 1997-09
Abdo Y. Alfakih, Amir Khandani, and Henry Wolkowicz
Abstract
Given a partial symmetric matrix $A$ with only certain elements specified, the Euclidean distance matrix completion problem (EDMCP) consists in finding the unspecified elements of $A$ in order to make $A$ a Euclidean distance matrix (EDM). In this paper, we follow the successful approach in [11] and solve the EDMCP by generalizing the completion problem to allow for approximate completions. In particular, we introduce a primal-dual interior-point algorithm for both approximate and exact completion problems.
This algorithm solves an equivalent semidefinite programming problem (SDP). In particular, the algorithm uses a new search direction for semidefinite programming introduced in [13]. This search direction is based on a Gauss-Newton approach and requires no symmetrization. Numerical results are included which illustrate the high efficiency and robustness of the interior-point approach.
Chromatic Polynomials of Homeomorphism Classes of Graphs
CORR 1997-08
Ronald C. Read and Earl Glen Whitehead, Jr.
Abstract
We study a multilinear polynomial which subsumes the chromatic polynomials of all the graphs in a given homeomorphism class. We show that this polynomial can be extended to include further families of homeomorphic graphs, and derive some properties of its coefficients. We also prove similar results for the dual concept of graphs with multiple edges.
An Algorithm for a Class of Copositivity Problems
CORR 1997-07
M.J. Best and B. Ding
Abstract
For a given (n,n) symmetric matrix with exactly one negative eigenvalue and a polyhedral cone, it is proved that determining if the matrix is compositive on the cone can be solved in a polynomial time and an algorithm is established for this class of problems. A slight modification of the algorithm can solve a class of compositivity problems in which the matrix has exactly two negative eigenvalues.
Global and Local Non-convex Minimization
CORR 1997-06
M.J. Best and B. Ding
Abstract
We present a method which when applied to certain non-convex programming problems will locate the global minimum, all isolated local minima and some of the non-isolated local minima. The method proceeds by formulating a (multi) parametric quasi-convex (or convex)programming in term of the data of the given non-convex programming problem. Based on the solution of the parametric quasi-convex (or convex) programming, an unconstrained minimization problem is formulated. A key result is that the isolated local minimizers (including the global minimizer) of the original non-convex problem are in one-to-one correspondence with those of the derived unconstrained problem.
The theory is illustrated with several examples from the literature. Some computational aspects are discussed for linear fractional programming problems, quadratic fractional programming problems, indefinite quadratic programming problems and cubic programming problems.
M.J. Best and B. Ding
CORR 1997-05
A. Knopfmacher, A.M. Odlyzko, B. Pittel, L.B. Richmond, D. Stark, G. Szekeres, and N.C. Wormald
Abstract
The asymptotic behavior of the number of set partitions of an $n$-element set into blocks of distinct sizes is determined. This behavior is more complicated than is typical for set partition problems. Although there is a simple generating function, the usual analytic methods for estimating coefficients fail in the direct approach, and elementary approaches are used to obtain most of the results.
A proof of Lih's Conjecture on Spernerity
CORR 1997-04
David G.C. Horrocks
Abstract
Let ${\cal F}$ be a nonempty collection of subsets of $[n]={1,2,...,n}$, each having cardinality $t$. Denote by P_{\cal F}$ the poset consisting of all subsets of $[n]$ which contain at least one member of ${\cal F}$, ordered by set-theoretic inclusion. In 1980, K.W. Lih conjectured that $P_{\cal F}$ has the Sperner property for all $1 \leq t \leq n$ and every choice of ${\cal F}$. This conjecture is known to be true for $t=1$ but false, in general, for $t \geq 4$. In this paper, we prove Lih's conjecture in the case $t=2$.
We make extensive use of fundamental theorems concerning the preservation of Sperner-type properties under direct products of posets.
The node multiterminal cut polyhedron
CORR 1997-03
Bo Yu and Joseph Cheriyan
Abstract
Given an undirected graph \(G=(V \cup A,E)\), where \(A\) is a set of terminal nodes and \(V\) is a set of nonterminal nodes, a node multiterminal cut is a set of nonterminal nodes whose deletion disconnects every pair of terminal nodes. We study the node multiterminal cut polyhedron, denoted \(P(G,A)\). We give some general results concerning facets of \(P(G,A)\), and introduce several classes of facet-inducing inequalities. We focus on the so-called \(A\)-tree inequalities (a generalization of the well-known path inequalities), and show that if \(G\) is a tree, then these inequalities give a complete description of \(P(G,A)\) Assuming that the number of terminal nodes in an \(A\)-tree is \(O(1)$ or $G\) is a tree, we give efficient separation algorithms for the \(A\)-tree inequalities.
Restricted 2-Factor Polytopes
CORR 1997-02
William H. Cunningham and Yaoguang Wang
Abstract
The optimal \(k\)-restricted 2-factor problem consists of finding, in a complete undirected graph \(K_n\), a minimum cost 2-factor (subgraph having degree 2 at every node) with all components having more than \(k\) nodes. The problem is a relaxation of the well-known symmetric travelling salesman problem, and is equivalent to it when \({n \choose 2} \leq k \leq n - 1\). We study the \(k\)-restricted 2-factor polytope. We present a large class of valid inequalities, called bipartition inequalities, and describe some of their properties; some of these results are new even for the travelling salesman polytope. For the case \(k=3\), the triangle-free 2-factor polytope, we derive a necessary and sufficient condition for such inequalities to be facet inducing.
SQ^2P, Sequential Quadratic Constrained Quadratic Programming
CORR 1997-01
Serge Kruk and Henry Wolkowicz
Abstract
Arguably the most successful family of techniques used to solve general nonlinear programs is known as Sequential Quadratic Programming. This iterative approach rests on a quadratic model of the Lagrangean subjected to linear approximations of the constraints. For all its success, the practical implementations must somehow overcome the weaker model of the feasible region.
A model demonstrably closer to the original problem uses second-order Taylor expansions of both objective function and constraints. Such a model preserves all curvature information and can therefore provide better Lagrange multipliers estimates. While considered before, this approach has generally been discarded as intractable. But the expanding field of semidefinite programming offers tools, both theoretical and practical, to overcome for a large class of problems this presumed intractability.
The theory and practice of semidefinite programming, in recent years, produced notable breakthroughs in combinatorial optimization. The approach described here tries to apply the same framework to continuous optimization problems.