On Two Measures of Problem Instance Complexity and their Correlation with the Performance of SeDuMi on Second-Order Cone Problems

We evaluate the practical relevance of two measures of conic convex problem complexity as applied to second-order cone problems solved using the homogeneous self-dual (HSD) embedding model in the software SeDuMi. The first measure we evaluate is Renegar's data-based condition measure C(d), and the second measure is a combined measure of the optimal solution size and the initial infeasibility/optimality residuals denoted by S (where the solution size is measured in a norm that is naturally associated with the HSD model). We constructed a set of 144 second-order cone test problems with widely distributed values of C(d) and S and solved these problems using SeDuMi. For each problem instance in the test set, we also computed estimates of C(d) (using Peña’s method) and computed S directly. Our computational experience indicates that SeDuMi iteration counts and log (C(d)) are fairly highly correlated (sample correlation R = 0.675), whereas SeDuMi iteration counts are not quite as highly correlated with S (R = 0.600). Furthermore, the experimental evidence indicates that the average rate of convergence of SeDuMi iterations is affected by the condition number C(d) of the problem instance, a phenomenon that makes some intuitive sense yet is not directly implied by existing theory.     

Substitution and condensation reactions with poly(anilineboronic acid): reactivity and characterization of thin films

Poly(anilineboronic acid) thin films are treated under various conditions to achieve substitution or condensation reactions involving the boronic acid moiety. These reactions are studied with polarization modulated infrared reflection absorption spectroscopy, cyclic voltammetry, and UV-vis spectroscopy. The results suggest the single-step formation of substituted polyanilines, such as poly(hydroxyaniline), halogenated polyanilines, and mercury chloride-substituted polyaniline. A condensation reaction of poly(anilineboronic acid) with cis-diol compounds in aqueous solution, as well as with phenylenebisboronic acid and salycilamide in THF, indicates the formation of boronic esters. The latter reactions appear to be a good entry point for the formation of complex or supramolecular polymer structures.     

A potential-function reduction algorithm for solving a linear program directly from an infeasible “warm start”

This paper develops an algorithm for solving a standard-form linear program directly from an infeasible “warm start”, i.e., directly from a given infeasible solution \(\hat x\) that satisfies \(A\hat x = b\) but \(\hat x \ngeqslant 0\) . The algorithm is a potential function reduction algorithm, but the potential function is somewhat different than other interior-point method potential functions, and is given by $$F(x,B) = q\ln (c^T x - B) - \sum\limits_{j = 1}^n {\ln (x_j + h_j (c^T x - B))}$$ where \(q = n + \sqrt n\) is a given constant,h is a given strictly positive shift vector used to shift the nonnegativity constaints, andB is a lower bound on the optimal value of the linear program. The duality gapc ^T x ? B is used both in the leading term as well as in the barrier term to help shift the nonnegativity constraints. The algorithm is shown under suitable conditions to achieve a constant decrease in the potential function and so achieves a constant decrease in the duality gap (and hence also in the infeasibility) in O(n) iterations. Under more restrictive assumptions regarding the dual feasible region, this algorithm is modified by the addition of a dual barrier term, and will achieve a constant decrease in the duality gap (and in the infeasibility) in \(O(\sqrt n )\) iterations.     

Polynomial-time algorithms for linear programming based only on primal scaling and projected gradients of a potential function

This paper presents extensions and further analytical properties of algorithms for linear programming based only on primal scaling and projected gradients of a potential function. The paper contains extensions and analysis of two polynomial-time algorithms for linear programming. We first present an extension of Gonzaga's O(nL) iteration algorithm, that computes dual variables and does not assume a known optimal objective function value. This algorithm uses only affine scaling, and is based on computing the projected gradient of the potential function $$q\ln (x^T s) - \sum\limits_{j = 1}^n {\ln (x_j )} $$ wherex is the vector of primal variables ands is the vector of dual slack variables, and q = n + \(\sqrt n \) . The algorithm takes either a primal step or recomputes dual variables at each iteration. We next present an alternate form of Ye's O( \(\sqrt n \) L) iteration algorithm, that is an extension of the first algorithm of the paper, but uses the potential function $$q\ln (x^T s) - \sum\limits_{j = 1}^n {\ln (x_j ) - \sum\limits_{j - 1}^n {\ln (s_j )} } $$ where q = n + \(\sqrt n \) . We use this alternate form of Ye's algorithm to show that Ye's algorithm is optimal with respect to the choice of the parameterq in the following sense. Suppose thatq = n + n ^t wheret?0. Then the algorithm will solve the linear program in O(n ^r L) iterations, wherer = max{t, 1 ? t}. Thus the value oft that minimizes the complexity bound ist = 1/2, yielding Ye's O( \(\sqrt n \) L) iteration bound.     

Macdonald polynomials from Sklyanin algebras: A conceptual basis for thep-adics-quantum group connection

We establish a previously conjectured connection betweenp-adics and quantum groups. We find in Sklyanin's two parameter elliptic quantum algebra and its generalizations, the conceptual basis for the Macdonald polynomials, which interpolate between the zonal spherical functions of related real andp-adic symmetric spaces. The elliptic quantum algebras underlie theZ _n -Baxter models. We show that in then limit, the Jost function for the scattering offirst level excitations in the 1+1 dimensional field theory model associated to theZ _n -Baxter model coincides with the Harish-Chandra-likec-function constructed from the Macdonald polynomials associated to the root systemA ₁. The partition function of theZ ₂-Baxter model itself is also expressed in terms of this Macdonald-Harish-Chandrac-function, albeit in a less simple way. We relate the two parametersq andt of the Macdonald polynomials to the anisotropy and modular parameters of the Baxter model. In particular thep-adic regimes in the Macdonald polynomials correspond to a discrete sequence of XXZ models. We also discuss the possibility of q-deforming Euler products.Work supported in part by the NSF: PHY-9000386