# Technical reports - 1997

## 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

### 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