Properties of Solutions to Second Order Evolution Control Systems. II

We continue the research of the first part of the article. We mainly study codensity for the set of admissible trajectory-control pairs of a system with nonconvex constraints in the set of admissible trajectory-control pairs of the system with convexified constraints. We state necessary and sufficient conditions for the set of admissible trajectory-control pairs of a system with nonconvex constraints to be closed in the corresponding function spaces. Using an example of a control hyperbolic system, we give an interpretation of the abstract results obtained. As application we consider the minimization problem for an integral functional on solutions of a control system.     

On the Complex of Sobolev Spaces Associated with an Abstract Hilbert Complex

We consider the complexes of Hilbert spaces whose differentials are closed densely-defined operators. A peculiarity of these complexes is that from their differentials we can construct Laplace operators in every dimension. The Laplace operator together with a sufficiently nice measurable function enables us to define a generalized Sobolev space. There exist pairs of measurable functions allowing us to construct some canonical mappings of the corresponding Sobolev spaces. We find necessary and sufficient conditions for those mappings to be compact. In some cases for a given Hilbert complex we can construct an associated Sobolev complex. We show that the differentials of the original complex are normally solvable simultaneously with the differentials of the associated complex and that the reduced cohomologies of these complexes coincide.     

On affine scaling algorithms for nonconvex quadratic programming

We investigate the use of interior algorithms, especially the affine-scaling algorithm, to solve nonconvex — indefinite or negative definite — quadratic programming (QP) problems. Although the nonconvex QP with a polytope constraint is a hard problem, we show that the problem with an ellipsoidal constraint is easy. When the hard QP is solved by successively solving the easy QP, the sequence of points monotonically converge to a feasible point satisfying both the first and the second order optimality conditions.Research supported in part by NSF Grant DDM-8922636 and the College Summer Grant, College of Business Administration, The University of Iowa.     

Uncertain convex programs: randomized solutions and confidence levels

Many engineering problems can be cast as optimization problems subject to convex constraints that are parameterized by an uncertainty or instance parameter. Two main approaches are generally available to tackle constrained optimization problems in presence of uncertainty: robust optimization and chance-constrained optimization. Robust optimization is a deterministic paradigm where one seeks a solution which simultaneously satisfies all possible constraint instances. In chance-constrained optimization a probability distribution is instead assumed on the uncertain parameters, and the constraints are enforced up to a pre-specified level of probability. Unfortunately however, both approaches lead to computationally intractable problem formulations.In this paper, we consider an alternative randomized or scenario approach for dealing with uncertainty in optimization, based on constraint sampling. In particular, we study the constrained optimization problem resulting by taking into account only a finite set of N constraints, chosen at random among the possible constraint instances of the uncertain problem. We show that the resulting randomized solution fails to satisfy only a small portion of the original constraints, provided that a sufficient number of samples is drawn. Our key result is to provide an efficient and explicit bound on the measure (probability or volume) of the original constraints that are possibly violated by the randomized solution. This volume rapidly decreases to zero as N is increased.This work is supported in part by the European Commission under the project HYBRIDGE IST-2001-32460, and by MIUR under the project New methods for Identification and Adaptive Control for Industrial Systems, and the FIRB project Learning, randomization and guaranteed predictive inference for complex uncertain systems.Acknowledgement We wish to thank Professor Arkadi Nemirovski for his encouragement in pursuing this line of research. We also acknowledge the many valuable comments from anonymous reviewers that helped improve this paper.     

On Isomorphisms of Relations Embedded into Each Other

In this paper, we consider analogs of the Cantor--Bernstein theorem for sets with binary relations. In Sec. 1, we prove an analog of this theorem for arbitrary binary relations; in Sec. 2, we consider an application; in Sec. 3, we study a class of relations with the Cantor-- Bernstein property and a class of exact relations, and prove that these classes are closed under certain operations.     

On the predicate logics of continuous t-norm BL-algebras

Given a class C of t-norm BL-algebras, one may wonder which is the complexity of the set Taut(C) of predicate formulas which are valid in any algebra in C. We first characterize the classes C for which Taut(C) is recursively axiomatizable, and we show that this is the case iff C only consists of the Gödel algebra on [0,1]. We then prove that in all cases except from a finite number Taut(C) is not even arithmetical. Finally we consider predicate monadic logics Taut_M(C) of classes C of t-norm BL-algebras, and we prove that (possibly with finitely many exceptions) they are undecidable.Mathematics Subject Classification (2000): Primary: 03B50, Secondary: 03B47Acknowledgement The author is deeply indebted to Petr Hájek, whose results about the complexity problems of predicate fuzzy logics constitute the main motivation for this paper, and whose suggestions and remarks have been always stimulating. He is also indebted to Matthias Baaz, who pointed out to him a method used in [BCF] for the case of monadic Gödel logic which works with some modifications also in the case of monadic BL logic.     

Point Code Minimum Steiner Triple Systems

The point code of a Steiner triple system uniquely determines the system when the number of vectors whose weight equals the replication number agrees with the number of points. The existence of a Steiner triple system with this minimum point code property is established for all v 1,3 (mod 6) with v 15.     

Embedding Theorems for a Certain Function Class of Sobolev Type on Metric Spaces

Given a metric space with a Borel measure , we consider a class of functions whose increment is controlled by the measure of a ball containing the corresponding points and a nonnegative function p-summable with respect to . We prove some analogs of the classical theorems on embedding Sobolev function classes into Lebesgue spaces.     

Some remarks on the approximation in the strong sense

. , , , , . , . , , .

---

---

On the 70th birthday of Professor S. M. Nikol'skii     

Teoremi di esistenza del minimo per problemi di Bolza con stato a valori in spazi di Banach

Summary We examine nonconvex problems of Bolza, in which the state is V-valued, with derivative V-valued, where VHV, V is a Banach space, V is its dual space and H is a Hilbert space. For these problems we prove some existence theorems for the minimum, when we consider state constraints and other constraints that are represented by a nonlinear differential equation that relates the state and the control.

---

---

Lavoro eseguito nell'ambito del Laboratorio per la Matematica Applicata del C.N.R. presso l'Università di Genova.     

Optimal control and relaxation of nonlinear elliptic systems

In this paper we study the optimal control of systems driven by nonlinear elliptic partial differential equations. First, with the aid of an appropriate convexity hypothesis we establish the existence of optimal admissible pairs. Then we drop the convexity hypothesis and we pass to the larger relaxed system. First we consider a relaxed system based on the Gamkrelidze-Warga approach, in which the controls are transition probabilities. We show that this relaxed problem has always had a solution and the value of the problem is that of the original one. We also introduce two alternative formulations of the relaxed problem (one of them control free), which we show that they are both equivalent to the first one. Then we compare those relaxed problems, with that of Buttazzo which is based on the -regularization of the extended cost functional. Finally, using a powerful multiplier rule of Ioffe-Tichomirov, we derive necessary conditions for optimality in systems with inequality state constraints.Research supported by NSF Grant DMS-8802688     

Convex Separable Minimization Subject to Bounded Variables

A minimization problem with convex and separable objective function subject to a separable convex inequality constraint and bounded variables is considered. A necessary and sufficient condition is proved for a feasible solution to be an optimal solution to this problem. Convex minimization problems subject to linear equality/linear inequality constraint, and bounds on the variables are also considered. A necessary and sufficient condition and a sufficient condition, respectively, are proved for a feasible solution to be an optimal solution to these two problems. Algorithms of polynomial complexity for solving the three problems are suggested and their convergence is proved. Some important forms of convex functions and computational results are given in the Appendix.     

Asymptotic Analysis and Solution of a Finite-Horizon H ∞ Control Problem for Singularly-Perturbed Linear Systems with Small State Delay

A finite-horizon H state-feedback control problem for singularly-perturbed linear time-dependent systems with a small state delay is considered. Two approaches to the asymptotic analysis and solution of this problem are proposed. In the first approach, an asymptotic solution of the singularly-perturbed system of functional-differential equations of Riccati type, associated with the original H problem by the sufficient conditions of the existence of its solution, is constructed. Based on this asymptotic solution, conditions for the existence of a solution of the original H problem, independent of the small parameter of singular perturbations, are derived. A simplified controller with parameter-independent gain matrices, solving the original H problem for all sufficiently small values of this parameter, is obtained. In the second approach, the original H problem is decomposed into two lower-dimensional parameter-independent H subproblems, the reduced-order (slow) and the boundary-layer (fast) subproblems; controllers solving these subproblems are constructed. Based on these controllers, a composite controller is derived, which solves the original H problem for all sufficiently small values of the singular perturbation parameter. An illustrative example is presented.     

αBB: A global optimization method for general constrained nonconvex problems

A branch and bound global optimization method,BB, for general continuous optimization problems involving nonconvexities in the objective function and/or constraints is presented. The nonconvexities are categorized as being either of special structure or generic. A convex relaxation of the original nonconvex problem is obtained by (i) replacing all nonconvex terms of special structure (i.e. bilinear, fractional, signomial) with customized tight convex lower bounding functions and (ii) by utilizing the parameter as defined in [17] to underestimate nonconvex terms of generic structure. The proposed branch and bound type algorithm attains finite-convergence to the global minimum through the successive subdivision of the original region and the subsequent solution of a series of nonlinear convex minimization problems. The global optimization method,BB, is implemented in C and tested on a variety of example problems.     

A Deterministic Approach to Linear Programs with Several Additional Multiplicative Constraints

We consider a global optimization problem of minimizing a linear function subject to p linear multiplicative constraints as well as ordinary linear constraints. We show that this problem can reduce to a 2p-dimensional reverse convex program, and present an algorithm for solving the resulting problem. Our algorithm converges to a globally optimal solution and yields an -approximate solution in finite time for any > 0. We also report some results of computational experiment.     

Large transversals to small families of unit disks

Summary It is proved that if the nonempty intersection of bounded closed convex sets AnB is contained in (A + F)U(B+F) and one of the following holds true: (i) the space X is less-than-three dimensional, (ii) AUB is convex, (iii) F is a one-point set, then AnBCA+F or AnBCB+F (Theorems 2 and 3). Moreover, under some hypotheses the characterization of A and B such that AnB is a summand of AUB is given (Theorem 3).     

Rubber life over a broad interval of stresses and aggressive medium concentrations

A generalized dependence of rubber life on stress and the concentration of the aggressive medium is proposed for a broad interval of variation of stresses and concentrations. The known expressions for the life in air and aggressive media as functions of stress (at large values of ) and concentration at constant stress are obtained as special cases. At zero concentration the proposed relation goes over into Zhurkov's equation with =(). The proposed equation and the graphic construction can be used, in particular, for determining rubber life in air at low stresses, i.e., under conditions similar to those encountered in service.The experiments were performed by N. L. Novikova.Scientific-Research Institute of the Rubber Industry, Moscow. Translated from Mekhanika Polimerov, Vol. 4, No. 6, pp. 1020–1025, November–December, 1968.     

Approximate solution of a class of singular control problems

A class of singular control problems involving amplitude constraints on the controls is examined. IfL is the space of control functionsU, the control constraint setS can be identified with the unit ball inL . Now, for anyn (1, ), an analogous problem may be set up withL ⁿ forU and the unit ball inL ⁿ forS. This modified problem is necessarily nonsingular for controllable systems. It is shown that, by takingn sufficiently large, the solution to the modified problem also solves the original problem arbitrarily closely (in a sense made precise). Behavior asn is investigated.This research was supported by the Science Research Council of Great Britain and the Commonwealth Fund (Harkness Fellowship).     

Linear-programming approach to nonconvex variational problems

Summary. In nonconvex optimization problems, in particular in nonconvex variational problems, there usually does not exist any classical solution but only generalized solutions which involve Young measures. In this paper, after reviewing briefly the relaxation theory for such problems, an iterative scheme leading to a sequential linear programming (=SLP) scheme is introduced, and its convergence is proved by a Banach fixed-point technique. Then an approximation scheme is proposed and analyzed, and calculations of an illustrative 2D broken-extremal example are presented.Mathematics Subject Classification (2000): 49M05, 65K10, 65N30Acknowledgement S.B. gratefully acknowledges support by the DFG through the priority program 1095 Analysis, Modeling and Simulation of Multiscale Problems while T.R.s research was partly covered by the grants A 107 5005 (GA AV R), and MSM 11320007 (MMT R).     

Computable Structure and Non-Structure Theorems

In a lecture in Kazan (1977), Goncharov dubbed a number of problems regarding the classification of computable members of various classes of structures. Some of the problems seemed likely to have nice answers, while others did not. At the end of the lecture, Shore asked what would be a convincing negative result. The goal of the present article is to consider some possible answers to Shore's question. We consider structures of some computable language, whose universes are computable sets of constants. In measuring complexity, we identify with its atomic diagram D(), which, via the Gödel numbering, may be treated as a subset of . In particular, is computable if D() is computable. If K is some class, then K^c denotes the set of computable members of K. A computable characterization for K should separate the computable members of K from other structures, that is, those that either are not in K or are not computable. A computable classification (structure theorem) should describe each member of K^c up to isomorphism, or other equivalence, in terms of relatively simple invariants. A computable non-structure theorem would assert that there is no computable structure theorem. We use three approaches. They all give the correct answer for vector spaces over Q, and for linear orderings. Under all of the approaches, both classes have a computable characterization, and there is a computable classification for vector spaces, but not for linear orderings. Finally, we formulate some open problems.