Optimality for set functions with values in ordered vector spaces

Let (X, , ) be a finite atomless measure space,L a convex subfamily of , andY andZ locally convex Hausdorff topological vector spaces which are ordered by the conesC andD, respectively. LetF:LY beC-convex andG:LZ beD-convex set functions. Consider the following optimization problem (P): minimizeF(), subject to L andG() _D . The paper generalizes the Moreau-Rockafellar theorem with set functions. By applying this theorem, a Kuhn-Tucker type optimality condition and a Fritz John type optimality condition for problem (P) are established. The duality theorem for problem (P) is also studied.This work was partially supported by National Science Council, Taipei, Taiwan. This paper was written while the first author was visiting at the University of Iowa, 1987-88.The authors would like to express their gratitude to the two anonymous referees for their valuable comments. Also, they would like to thank Professor P. L. Yu for his encouragement and suggestions which improved the material presented here considerably.     

Approximate first-order and second-order directional derivatives of a marginal function in convex optimization

Given a convex functionf: ^p × ^q (–, +], the marginal function is defined on ^p by (x)=inf{f(x, y)|y ^q }. Our purpose in this paper is to express the approximate first-order and second-order directional derivatives of atx ₀ in terms of those off at (x ₀,y ₀), wherey ₀ is any element for which (x ₀)=f(x ₀,y ₀).The author is indebted to one referee for pointing out an inaccuracy in an earlier version of Theorem 4.1.     

Asymptotically independent topological indices on random trees

Topological indices are graph invariants used in computational chemistry to encode molecules. A frequent problem when performing structure-activity studies is that topological indices are inter-correlated. We consider a simple topological index and show asymptotic independence for a random tree model. This continues previous work on the correlation among topological indices. These findings suggest that a size-dependence in a certain class of distance-based topological indices can be eliminated.AMS subject classification: 05C80, 60E10, 92E10     

Analysis of RNA sequence structure maps by exhaustive enumeration I. Neutral networks

Summary Global relations between RNA sequences and secondary structures are understood as mappings from sequence space into shape space. These mappings are investigated by exhaustive folding of allGC andAU sequences with chain lengths up to 30. The computed structural data are evaluated through exhaustive enumeration and used as an exact reference for testing analytical results derived from mathematical models and sampling based on statistical methods. Several new concepts of RNA sequence to secondary structure mappings are investigated, among them that ofneutral networks (being sets of sequences folding into the same structure). Exhaustive enumeration allows to test several previously suggested relations: the number of (minimum free energy) secondary structures as a function of the chain length as well as the frequency distribution of structures at constant chain length (commonly resulting in generalized forms ofZipf's law).

---

Analyse der Beziehungen zwischen RNA-Sequenzen und Sekundärstrukturen durch vollständige Faltung, 1. Mitt. Faltung, Neutrale Netzwerke

Zusammenfassung Die globalen Benziehungen zwischen RNA-Sequenzen und Sekundärstrukturen werden als Abbildungen aus einem Raum aller Sequenzen in einen Raum aller Strukturen aufgefaßt. Diese Abbildungen werden durch Falten aller binären Sequenzen desGC-undAU-Alphabets mit Kettenlängen bis zun=30 untersucht. Die berechneten Strukturdaten werden durch vollständiges Abzählen ausgewertet und als eine exakte Referenz zum Überprüfen analytischer Resultate aus mathematischen Modellen sowie zum Testen statistisch erhobener Proben verwendet. Einige neuartige Konzepte zur Beschreibung der Beziehungen zwischen Sequenzen und Strukturen werden eingehend untersucht, unter ihnen der Begriff derneutralen Netzwerke. Ein neutrales Netzwerk besteht aus allen Sequenzen, die eine bestimmte Struktur ausbilden. Vollständiges Abzählen ermöglicht beispielsweise die Bestimmung aller Strukturen minimaler freier Energie in Abhängigkeit von der Kettenlänge ebenso wie die Bestimmung der Häufigkeitsverteilungen der Strukturen bei konstanten Kettenlängen. Die letzteren folgen einer verallgemeinerten FormZipfschen Gesetzes.

     

A greedy algorithm for finding maximum spanning trees in infinite graphs

In finite graphs, greedy algorithms are used to find minimum spanning trees (MinST) and maximum spanning trees (MaxST). In infinite graphs, we illustrate a general class of problems where a greedy approach discovers a MaxST while a MinST may be unreachable. Our algorithm is a natural extension of Prim's to infinite graphs with summable and strictly positive edge weights, producing a sequence of finite trees that converge to a MaxST.     

Large cycles in random generalized Johnson graphs

This paper studies thresholds in random generalized Johnson graphs for containing large cycles, i.e. cycles of variable length growing with the size of the graph. Thresholds are obtained for different growth rates.     

Finding normal solutions in piecewise linear programming

Letf: ⁿ (–, ] be a convex polyhedral function. We show that if any standard active set method for quadratic programming (QP) findsx(t)= arg min _x ¦x¦²/2+t f(x) for somet> 0, then its final working set defines a simple equality QP subproblem, whose Lagrange multiplier can be used both for testing ift is large enough forx(t) to coincide with the normal minimizer off, and for increasingt otherwise. The QP subproblem may easily be solved via the matrix factorizations used for findingx(t). This opens up the way for efficient implementations. We also give finite methods for computing the whole trajectory {x(t)} _t 0, minimizingf over an ellipsoid, and choosing penalty parameters inL ₁QP methods for strictly convex QP.This research was supported by the State Committee for Scientific Research under Grant 8S50502206.     

Potential reduction method for harmonically convex programming

In this paper, we introduce a potential reduction method for harmonically convex programming. We show that, if the objective function and them constraint functions are allk-harmonically convex in the feasible set, then the number of iterations needed to find an -optimal solution is bounded by a polynomial inm, k, and log(1/). The method requires either the optimal objective value of the problem or an upper bound of the harmonic constantk as a working parameter. Moreover, we discuss the relation between the harmonic convexity condition used in this paper and some other convexity and smoothness conditions used in the literature.The authors like to thank Dr. Hans Nieuwenhuis for carefully reading this paper and the anonymous referees for the worthy suggestions.     

Spectra of graphs and fractal dimensions II

This paper continues the study of exponentsd(x), d (x), d _R (x) andd (x) for graphG; and the nearest neighbor random walk {X _n } _nN onG, if the starting pointX ₀=x is fixed. These exponents are responsible for the geometric, resistance, diffusion and spectral properties of the graph. The main concern of this paper is the relation of these exponents to the spectral density of the transition matrix. A series of new exponentse, e ,e _R ,e are introduced by allowingx to vary along the vertices. The results suggest that the geometric and resistance properties of the graph are responsible for the diffusion speed on the graph.