On input/output stabilization of singular integrodifferential systems

In this paper we consider a class of systems described by singular integrodifferential equations. This type of systems appear, for example, in the modeling of certain aeroelastic control problems. We study these systems in frequency domain framework and show the existence of finite-dimensional stabilizing controllers. An algorithmic procedure is outlined for the construction of such controllers. In order to illustrate the numerical aspects of this algorithm, we present an example involving the classical Theodorsen model of an airfoil, which fits in the class of systems considered here.This work was supported in part by the National Science Foundation under Grants DMS-8907019 and MSS-9203418.     

Design considerations and computer modeling related to the development of molecular scaffolds and peptide mimetics for combinatorial chemistry

Summary A critical issue in drug discovery utilizing combinatorial chemistry as part of the discovery process is the choice of scaffolds to be used for a proper presentation, in a three-dimensional space, of the critical elements of structure necessary for molecular recognition (binding) and information transfer (agonist/ antagonist). In the case of polypeptide ligands, considerations related to the properties of various backbone structures (-helix, -sheets, etc.; , space) and those related to three-dimensional presentation of side-chain moieties (topography; (chi) space) must be addressed, although they often present quite different elements in the molecular recognition puzzle. We have addressed aspects of this problem by examining the three-dimensional structures of chemically different scaffolds at various distances from the scaffold to evaluate their putative diversity. We find that chemically diverse scaffolds can readily become topographically similar. We suggest a topographical approach involving design in chi space to deal with these problems.     

A new heuristic algorithm solving the linear ordering problem

The linear ordering problem is an NP-hard combinatorial problem with a large number of applications. Contrary to another very popular problem from the same category, the traveling salesman problem, relatively little space in the literature has been devoted to the linear ordering problem so far. This is particularly true for the question of developing good heuristic algorithms solving this problem.In the paper we propose a new heuristic algorithm solving the linear ordering problem. In this algorithm we made use of the sorting through insertion pattern as well as of the operation of permutation reversal. The surprisingly positive effect of the reversal operation, justified in part theoretically and confirmed in computational examples, seems to be the result of a unique property of the problem, called in the paper the symmetry of the linear ordering problem. This property consists in the fact that if a given permutation is an optimal solution of the problem with the criterion function being maximized, then the reversed permutation is a solution of the problem with the same criterion function being minimized.     

Approximate minimum-cost multicommodity flows in\tilde O(ɛ −2 KNM) timetime

We show that an ε-approximate solution of the cost-constrainedK-commodity flow problem on anN-nodeM-arc network,G can be computed by sequentially solving O(K(? ^?2+logGK) logGM log (G? ^?1 GK)) single-commodity minimum-cost flow problems on the same network. In particular, an approximate minimum-cost multicommodity flow can be computed in $\tilde O$ (G? ^?2 GKNM) running time, where the notation Õ(·) means “up to logarithmic factors”. This result improves the time bound mentioned by Grigoriadis and Khachiyan [4] by a factor ofM/N and that developed more recently by Karger and Plotkin [8] by a factor of? ^?1. We also provide a simple $\tilde O$ (NM)-time algorithm for single-commodity budget-constrained minimum-cost flows which is $\tilde O$ (? ^?3) times faster than the algorithm developed in the latter paper.     

Nonmonotone bundle-type scheme for convex nonsmooth minimization

In this paper, we present a general scheme for bundle-type algorithms which includes a nonmonotone line search procedure and for which global convergence can be proved. Some numerical examples are reported, showing that the nonmonotonicity can be beneficial from a computational point of view.This work was partially supported by the National Research Program on Metodi di ottimizzazione per le decisioni, Ministero dell' Universitá e della Ricerca Scientifica e Tecnologica and by ASI: Agenzia Spaziale Italiana.     

Quantitative stability of variational systems: III.ε-approximate solutions

We prove that the-optimal solutions of convex optimization problems are Lipschitz continuous with respect to data perturbations when these are measured in terms of the epi-distance. A similar property is obtained for the distance between the level sets of extended real valued functions. We also show that these properties imply that the-subgradient mapping is Lipschitz continuous.Research supported in part by the National Science Foundation and the Air Force Office of Scientific Research.     

A generalized Dantzig—Wolfe decomposition principle for a class of nonconvex programming problems

Since Dantzig—Wolfe's pioneering contribution, the decomposition approach using a pricing mechanism has been developed for a wide class of mathematical programs. For convex programs a linear space of Lagrangean multipliers is enough to define price functions. For general mathematical programs the price functions could be defined by using a subclass of nondecreasing functions. However the space of nondecreasing functions is no longer finite dimensional. In this paper we consider a specific nonconvex optimization problem min {f(x):h _j (x)g(x),j=1, ,m, xX}, wheref(·),h _j (·) andg(·) are finite convex functions andX is a closed convex set. We generalize optimal price functions for this problem in such a way that the parameters of generalized price functions are defined in a finite dimensional space. Combining convex duality and a nonconvex duality we can develop a decomposition method to find a globally optimal solution.This paper is dedicated to Phil Wolfe on the occasion of his 65th birthday.     

A smooth method for the finite minimax problem

We consider unconstrained minimax problems where the objective function is the maximum of a finite number of smooth functions. We prove that, under usual assumptions, it is possible to construct a continuously differentiable function, whose minimizers yield the minimizers of the max function and the corresponding minimum values. On this basis, we can define implementable algorithms for the solution of the minimax problem, which are globally convergent at a superlinear convergence rate. Preliminary numerical results are reported.This research was partially supported by the National Research Program on Metodi di ottimizzazione per le decisioni, Ministero dell'Università e della Ricerca Scientifica e Tecnologica, Italy.     

On the global optimization properties of finite-difference local descent algorithms

The paper is devoted to the convergence properties of finite-difference local descent algorithms in global optimization problems with a special -convex structure. It is assumed that the objective function can be closely approximated by some smooth convex function. Stability properties of the perturbed gradient descent and coordinate descent methods are investigated. Basing on this results some global optimization properties of finite-difference local descent algorithms, in particular, coordinate descent method, are discovered. These properties are not inherent in methods using exact gradients.The paper was presented at the II. IIASA-Workshop on Global Optimization, Sopron (Hungary), December 9–14, 1990.     

Thermodynamical approach to the traveling salesman problem: An efficient simulation algorithm

We present a Monte Carlo algorithm to find approximate solutions of the traveling salesman problem. The algorithm generates randomly the permutations of the stations of the traveling salesman trip, with probability depending on the length of the corresponding route. Reasoning by analogy with statistical thermodynamics, we use the probability given by the Boltzmann-Gibbs distribution. Surprisingly enough, using this simple algorithm, one can get very close to the optimal solution of the problem or even find the true optimum. We demonstrate this on several examples.We conjecture that the analogy with thermodynamics can offer a new insight into optimization problems and can suggest efficient algorithms for solving them.The author acknowledges stimulating discussions with J. Piút concerning the main ideas of the present paper. The author is also indebted to P. Brunovský, J. erný, M. Hamala, . Peko, . Znám, and R. Zajac for useful comments.