Relaxation of an optimal control problem involving a perturbed sweeping process

We establish first, in the setting of infinite dimensional Hilbert space, a result concerning the existence of solutions for perturbed sweeping processes whose perturbations are Lipschitz single-valued maps. Then we use this result to extend to the infinite dimensional setting a relaxation result concerning optimal control problems involving such processes. Dedicated to R. Tyrrell Rockafellar on the occasion of his 70th birthday     

Products of orthogonal projections as Carleman operators

In this paper, we consider the product of two orthogonal projectionsP andQ on a separable, infinite dimensional Hilbert spaceH. For the operatorQP, there holds the dichotomy:QP is either a Carleman operator or a semi-Fredholm operator with finite defect. Both cases are characterized in terms of the dimensions of the ranges and null spaces ofP andQ and some of their intersections. This extends the case, whereP andQ are the special projections onto the subspaces of time- and band-limited functions inL ²() resp., first considered by Slepian, Pollak and Landau.     

Inverse integer optimization with an imperfect observation

This study develops and evaluates methods for inverse integer optimization problems with an imperfect observation where the unknown parameters are the cost coefficients. We propose a cutting plane algorithm for this problem and compare it to a heuristic which solves the inverse of the linear relaxation of the forward problem. We then propose a hybrid approach that initializes the cutting plane algorithm from the solution of the heuristic.     

Basis problems for matrix valued functions

Basis problems for self-adjoint matrix valued functions are studied. We suggest a new and nonstandard method to solve basis problems both in finite and infinite dimensional spaces. Although many results in this paper are given for operator functions in infinite dimensional Hilbert spaces, but to demonstrate practicability of this method and to present a full solution of basis problems, in this paper we often restrict ourselves to matrix valued functions which generate Rayleigh systems on the n-dimensional complex space Cn. The suggested method is an improvement of an approach given recently in our paper [M. Hasanov, A class of nonlinear equations in Hilbert space and its applications to completeness problems, J. Math. Anal. Appl. 328 (2007) 1487-1494], which is based on the extension of the resolvent of a self-adjoint operator function to isolated eigenvalues and the properties of quadratic forms of the extended resolvent. This approach is especially useful for nonanalytic and nonsmooth operator functions when a suitable factorization formula fails to exist.     

Enhancing RLT relaxations via a new class of semidefinite cuts

In this paper, we propose a mechanism to tighten Reformulation-Linearization Technique (RLT) based relaxations for solving nonconvex programming problems by importing concepts from semidefinite programming (SDP), leading to a new class of semidefinite cutting planes. Given an RLT relaxation, the usual nonnegativity restrictions on the matrix of RLT product variables is replaced by a suitable positive semidefinite constraint. Instead of relying on specific SDP solvers, the positive semidefinite stipulation is re-written to develop a semi-infinite linear programming representation of the problem, and an approach is developed that can be implemented using traditional optimization software. Specifically, the infinite set of constraints is relaxed, and members of this set are generated as needed via a separation routine in polynomial time. In essence, this process yields an RLT relaxation that is augmented with valid inequalities, which are themselves classes of RLT constraints that we call semidefinite cuts. These semidefinite cuts comprise a relaxation of the underlying semidefinite constraint. We illustrate this strategy by applying it to the case of optimizing a nonconvex quadratic objective function over a simplex. The algorithm has been implemented in C++, using CPLEX callable routines, and two types of semidefinite restrictions are explored along with several implementation strategies. Several of the most promising lower bounding strategies have been implemented within a branch-and-bound framework. Computational results indicate that the cutting plane algorithm provides a significant tightening of the lower bound obtained by using RLT alone. Moreover, when used within a branch-and-bound framework, the proposed lower bound significantly reduces the effort required to obtain globally optimal solutions.     

Coherent Reflection of Electromagnetic Plane Waves from Infinite Rough Slabs

We adopt the prospect of an observer interested to optimise the signal-to-noise ratio in the reception of the backward radiation coming from a surface illuminated by an electromagnetic wave with a wavelength chosen to minimize the diffuse scattering so that he has just to point his receiver in the direction of the coherent reflection. Then, to analyse the coherent reflection for harmonic plane waves impinging on a dielectric infinite film deposited on a metallic substrate we develop a formalism generalizing the customary angular spectrum representation used to tackle this kind of problem. This new approach whose efficiency is proved in the easier situation of a dielectric film endowed with an impedance, is used to get the coherent reflection from a structured 1D-dielectric film illuminated by TE and TM electromagnetic plane waves when the rough amplitude h is small enough to justify 0(h ²) approximations. The Idemen technique is used to get the boundary conditions needed to tackle these scattering problems.     

A property of strictly singular one-to-one operators

We prove that ifT is a strictly singular one-to-one operator defined on an infinite dimensional Banach spaceX, then for every infinite dimensional subspaceY ofX there exists an infinite dimensional subspaceZ ofX such thatZ∩Y is infinite dimensional,Z contains orbits ofT of every finite length and the restriction ofT toZ is a compact operator. The research was partially supported by NSF.     

Cutting Plane Algorithms for Nonlinear Semi-Definite Programming Problems with Applications

We will propose an outer-approximation (cutting plane) method for minimizing a function f X subject to semi-definite constraints on the variables XR ⁿ. A number of efficient algorithms have been proposed when the objective function is linear. However, there are very few practical algorithms when the objective function is nonlinear. An algorithm to be proposed here is a kind of outer-approximation(cutting plane) method, which has been successfully applied to several low rank global optimization problems including generalized convex multiplicative programming problems and generalized linear fractional programming problems, etc. We will show that this algorithm works well when f is convex and n is relatively small. Also, we will provide the proof of its convergence under various technical assumptions.     

Relations between facets of low- and high-dimensional group problems

One-dimensional infinite group problems have been extensively studied and have yielded strong cutting planes for mixed integer programs. Although numerical and theoretical studies suggest that group cuts can be significantly improved by considering higher-dimensional groups, there are no known facets for infinite group problems whose dimension is larger than two. In this paper, we introduce an operation that we call sequential-merge. We prove that the sequential-merge operator creates a very large family of facet-defining inequalities for high-dimensional infinite group problems using facet-defining inequalities of lower-dimensional group problems. Further, they exhibit two properties that reflect the benefits of using facets of high-dimensional group problems: they have continuous variables’ coefficients that are not dominated by those of the constituent low-dimensional cuts and they can produce cutting planes that do not belong to the first split closure of MIPs. Further, we introduce a general scheme for generating valid inequalities for lower-dimensional group problems using valid inequalities of higher-dimensional group problems. We present conditions under which this construction generates facet-defining inequalities when applied to sequential-merge inequalities. We show that this procedure yields some two-step MIR inequalities of Dash and Günlük.     

Numerical Solution of Hamilton-Jacobi-Bellman Equations by an Upwind Finite Volume Method

In this paper we present a finite volume method for solving Hamilton-Jacobi-Bellman(HJB) equations governing a class of optimal feedback control problems. This method is based on a finite volume discretization in state space coupled with an upwind finite difference technique, and on an implicit backward Euler finite differencing in time, which is absolutely stable. It is shown that the system matrix of the resulting discrete equation is an M-matrix. To show the effectiveness of this approach, numerical experiments on test problems with up to three states and two control variables were performed. The numerical results show that the method yields accurate approximate solutions to both the control and the state variables.     

On Optimal Feedback Control for Stationary Linear Systems

We study linear-quadratic optimal control problems for finite dimensional stationary linear systems A X+B U=Z with output Y=C X+D U from the viewpoint of linear feedback solution. We interpret solutions in relation to system robustness with respect to disturbances Z and relate them to nonlinear matrix equations of Riccati type and eigenvalue-eigenvector problems for the corresponding Hamiltonian system. Examples are included along with an indication of extensions to continuous, i.e., infinite dimensional, systems, primarily of elliptic type.     

Simple continued fractions and cutting sequences

Abstract

The connection between cutting sequences of a directed geodesic in the tessellated hyperbolic plane ?², the modular group Γ = PSL(2, ?) and the simple continued fractions of an end point w of the geodesic have been established by Series [13]. In this paper we represent the simple continued fractions of w ∈ ? and the “L” and “R” codes of the cutting sequence in terms of modular and extended modular transformations. We will define a T ₀-path on a graph whose vertices are the set of Farey triangles, as the equivalent of the cutting sequence. The relationship between the directed geodesic with end point w on ?, the Farey tessellation and the simple continued fraction expansion of w ∈ ? _∞ then follows easily as a consequence of this redefinition. Finite, infinite and periodic simple continued fractions are subsequently examined in this light.     

Solving General Capacity Problem by Relaxed Cutting Plane Approach

This paper studies a class of infinite dimensional linear programming problems known as the general capacity problem. A relaxed cutting plane algorithm is proposed. A convergence proof together with some analysis of the results produced by the algorithm are given. A numerical example is also included to illustrate the computational procedure.     

First-Order Algorithms for Generalized Semi-Infinite Min-Max Problems

We present a first-order algorithm for solving semi-infinite generalized min-max problems which consist of minimizing a function f⁰(x) = F(¹(x), .... , ^m (x)), where F is a smooth function and each ⁱ is the maximum of an infinite number of smooth functions.In Section 3.3 of [17] Polak finds a methodology for solving infinite dimensional problems by expanding them into an infinite sequence of consistent finite dimensional approximating problems, and then using a master algorithm that selects an appropriate subsequence of these problems and applies a number of iterations of a finite dimensional optimization algorithm to each of these problems, sequentially. Our algorithm was constructed within this framework; it calls an algorithm by Kiwiel as a subroutine. The number of iterations of the Kiwiel algorithm to be applied to the approximating problems is determined by a test that ensures that the overall scheme retains the rate of convergence of the Kiwiel algorithm.Under reasonable assumptions we show that all the accumulation points of sequences constructed by our algorithm are stationary, and, under an additional strong convexity assumption, that the Kiwiel algorithm converges at least linearly, and that our algorithm also converges at least linearly, with the same rate constant bounds as Kiwiel's.     

Separable anisotropic elliptic operators and applications

This paper focuses on boundary value problems for anisotropic differential-operator equations of high order with variable coefficients in the half plane. Several conditions are obtained which guarantee the maximal regularity of anisotropic elliptic and parabolic problems in Banach-valued L _p -spaces. Especially, it is shown that this differential operator is R-positive and is a generator of an analytic semigroup. These results are also applied to infinite systems of anisotropic type partial differential equations in the half plane.     

Equivalent complete norms and positivity

In the first part of the article we characterize automatic continuity of positive operators. As a corollary we consider complete norms for which a given cone E₊ in an infinite dimensional Banach space E is closed and we obtain the following result: every two such norms are equivalent if and only if has finite codimension. Without preservation of an order structure, on an infinite dimensional Banach space one can always construct infinitely many mutually non-equivalent complete norms. We use different techniques to prove this. The most striking is a set theoretic approach which allows us to construct infinitely many complete norms such that the resulting Banach spaces are mutually non-isomorphic. Received: 28 January 2009     

CR Structures on the 3‐Sphere and the Blow‐Up of the Projective Plane

Motivated by a problem of characterizing CR‐structures on the 3‐sphere, we give a geometric construction of formal deformations of a complex surface, which is the complement of a ball in the projective plane. They are described by cohomology groups of the blow‐up X of the projective plane. Moreover it will be shown that the space of these formal deformations is an infinite dimensional space with a natural stratification by finite dimensional subspaces. This stratification re ects algebro‐geometric properties of X. It is expected that our construction will clarify the complex geometric nature of the space of non‐embeddable CR‐structures on the 3‐sphere.     

On the cohomology of one dimensional foliated manifolds

We show that the cohomology groupH ¹ (M, f) is an infinite dimensional vector space, for a dense set of one dimensional foliations on a closed manifold. In particular we compute this cohomology, for some foliations on the torus T².     

Splitting methods with complex times for parabolic equations

Using composition procedures, we build up high order splitting methods to solve evolution equations posed in finite or infinite dimensional spaces. Since high-order splitting methods with real time are known to involve large and/or negative time steps, which destabilizes the overall procedure, the key point of our analysis is, we develop splitting methods that use complex time steps having positive real part: going to the complex plane allows to considerably increase the accuracy, while keeping small time steps; on the other hand, restricting our attention to time steps with positive real part makes our methods more stable, and in particular well adapted in the case when the considered evolution equation involves unbounded operators in infinite dimensional spaces, like parabolic (diffusion) equations. We provide a thorough analysis in the case of linear equations posed in general Banach spaces. We also numerically investigate the nonlinear situation. We illustrate our results in the case of (linear and nonlinear) parabolic equations.