Optimization Over the Efficient Set of Multi-objective Convex Optimal Control Problems

We consider multi-objective convex optimal control problems. First we state a relationship between the (weakly or properly) efficient set of the multi-objective problem and the solution of the problem scalarized via a convex combination of objectives through a vector of parameters (or weights). Then we establish that (i) the solution of the scalarized (parametric) problem for any given parameter vector is unique and (weakly or properly) efficient and (ii) for each solution in the (weakly or properly) efficient set, there exists at least one corresponding parameter vector for the scalarized problem yielding the same solution. Therefore the set of all parametric solutions (obtained by solving the scalarized problem) is equal to the efficient set. Next we consider an additional objective over the efficient set. Based on the main result, the new objective can instead be considered over the (parametric) solution set of the scalarized problem. For the purpose of constructing numerical methods, we point to existing solution differentiability results for parametric optimal control problems. We propose numerical methods and give an example application to illustrate our approach.     

Optimal partitions having disjoint convex and conic hulls

LetA ¹,,A ⁿ be distinctk-dimensional vectors. We consider the problem of partitioning these vectors intom sets so as to maximize an objective which is a quasi-convex function of the sum of vectors in each set. We show that there exists an optimal partition whose sets have (pairwise) disjoint conic hulls. We also show that if the number of vectors in each of the sets is constrained, then a weaker conclusion holds, namely, there exists an optimal partition whose sets have (pairwise) disjoint convex hulls. The results rely on deriving necessary and sufficient conditions for a point to be an extreme point of a corresponding polytope.Research of this author was partially supported by NSF Grant ECS-83-10213 and by a Grant for the Promotion of Research at the Technion.     

Nonsymmetric Lanczos and finding orthogonal polynomials associated with indefinite weights

The nonsymmetric Lanczos algorithm reduces a general matrix to tridiagonal by generating two sequences of vectors which satisfy a mutual bi-orthogonality property. The process can proceed as long as the two vectors generated at each stage are not mutually orthogonal, otherwise the process breaks down. In this paper, we propose a variant that does not break down by grouping the vectors into clusters and enforcing the bi-orthogonality property only between different clusters, but relaxing the property within clusters. We show how this variant of the matrix Lanczos algorithm applies directly to a problem of computing a set of orthogonal polynomials and associated indefinite weights with respect to an indefinite inner product, given the associated moments. We discuss the close relationship between the modified Lanczos algorithm and the modified Chebyshev algorithm. We further show the connection between this last problem and checksum-based error correction schemes for fault-tolerant computing.The research reported by this author was supported in part by NSF grant CCR-8813493.The research reported by this author was supported in part by ARO grant DAAL03-90-G-0105 and in part by NSF grant DCR-8412314.     

Optimality of Balanced Proper Orthogonal Decomposition for Data Reconstruction

Proper orthogonal decomposition (POD) finds an orthonormal basis yielding an optimal reconstruction of a given dataset. We consider an optimal data reconstruction problem for two general datasets related to balanced POD, which is an algorithm for balanced truncation model reduction for linear systems. We consider balanced POD outside of the linear systems framework, and prove that it solves the optimal data reconstruction problem. The theoretical result is illustrated with an example.     

Duality for location problems with unbounded unit balls

Given an optimization problem with a composite of a convex and componentwise increasing function with a convex vector function as objective function, by means of the conjugacy approach based on the perturbation theory, we determine a dual to it. Necessary and sufficient optimality conditions are derived using strong duality. Furthermore, as special case of this problem, we consider a location problem, where the “distances” are measured by gauges of closed convex sets. We prove that the geometric characterization of the set of optimal solutions for this location problem given by Hinojosa and Puerto in a recently published paper can be obtained via the presented dual problem. Finally, the Weber and the minmax location problems with gauges are given as applications.     

Solution of a multiple Nevanlinna-Pick problem via orthogonal rational functions

We consider a Nevanlinna-Pick type interpolation problem for Carathéodory functions, where the values of the function and its derivatives up to certain orders are given at finitely many points of the unit disk. The set of all solutions of this problem is described by means of the orthogonal rational functions which play here a similar role as the orthogonal polynomials on the unit circle in the classical case of the trigonometric moment problem. In particular, we use a connection between Szegö and Schur parameters which in the classical situation was discovered by Ja.L. Geronimus.     

Solution of a multiple Nevanlinna–Pick problem for Carathéodory functions via orthogonal rational functions in the matrix case

We consider an interpolation problem of Nevanlinna–Pick type for matrix‐valued Carathéodory functions, where the values of the functions and its derivatives up to certain orders are given at finitely many points of the open unit disk. For the non‐degenerate case, i.e., in the particular situation that a specific block matrix (which is formed by the given data in the problem) is positive Hermitian, the solution set of this problem is described in terms of orthogonal rational matrix‐valued functions. These rational matrix functions play here a similar role as Szegő's orthogonal polynomials on the unit circle in the classical case of the trigonometric moment problem. In particular, we present and use a connection between Szegő and Schur parameters for orthogonal rational matrix‐valued functions which in the primary situation of orthogonal polynomials was found by Geronimus. (© 2007 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

On Stochastic Mirror-prox Algorithms for Stochastic Cartesian Variational Inequalities: Randomized Block Coordinate and Optimal Averaging Schemes

Motivated by multi-user optimization problems and non-cooperative Nash games in uncertain regimes, we consider stochastic Cartesian variational inequality problems where the set is given as the Cartesian product of a collection of component sets. First, we consider the case where the number of the component sets is large and develop a randomized block stochastic mirror-prox algorithm, where at each iteration only a randomly selected block coordinate of the solution vector is updated through implementing two consecutive projection steps. We show that when the mapping is strictly pseudo-monotone, the algorithm generates a sequence of iterates that converges to the solution of the problem almost surely. When the maps are strongly pseudo-monotone, we prove that the mean-squared error diminishes at the optimal rate. Second, we consider large-scale stochastic optimization problems with convex objectives and develop a new averaging scheme for the randomized block stochastic mirror-prox algorithm. We show that by using a different set of weights than those employed in the classical stochastic mirror-prox methods, the objective values of the averaged sequence converges to the optimal value in the mean sense at an optimal rate. Third, we consider stochastic Cartesian variational inequality problems and develop a stochastic mirror-prox algorithm that employs the new weighted averaging scheme. We show that the expected value of a suitably defined gap function converges to zero at an optimal rate.     

Weak Invariance of a Cylindrical Set with Smooth Boundary with Respect to a Control System

We consider the problem of constructing resolving sets for a differential game or an optimal control problem based on information on the dynamics of the system, control resources, and boundary conditions. The construction of largest possible sets with such properties (the maximal stable bridge in a differential game or the controllability set in a control problem) is a nontrivial problem due to their complicated geometry; in particular, the boundaries may be nonconvex and nonsmooth. In practical engineering tasks, which permit some tolerance and deviations, it is often admissible to construct a resolving set that is not maximal. The constructed set may possess certain characteristics that would make the formation of control actions easier. For example, the set may have convex sections or a smooth boundary. In this context, we study the property of stability (weak invariance) for one class of sets in the space of positions of a differential game. Using the notion of stability defect of a set introduced by V.N. Ushakov, we derive a criterion of weak invariance with respect to a conflict control dynamic system for cylindrical sets. In a particular case of a linear control system, we obtain easily verified sufficient conditions of weak invariance for cylindrical sets with ellipsoidal sections. The proof of the conditions is based on constructions and facts of subdifferential calculation. An illustrating example is given.     

Optimal implementation of selectors in a data-base

The records of a data base can be accessed from other records or from a set of data items (inverted access, primary and secondary index of IMS, search keys of CODASYL etc.) which we call selectors. The implementation of this selectors can use different techniques as hash coding, inverted lists or hierarchical index (indexed sequential, B-trees etc…) We consider here the last one and we search for a given set of selectors an optimal index structure. We show how this problem can be put as the search of an optimal rooted tree among the partial subgraphs of a given graph G (this problem is known in graph theory as Steiner problem) and we give several properties which allow the graph G to be notabily reduced. Then we present a branch and bound algorithm to solve this problem.     

On a measure of quasistability of a certain vector linearly combinatorial Boolean problem

We consider a multicriteria problem of finding the Pareto set in the case when linear forms (functions) are minimized both on a set of permutations and on a set of Boolean vectors. We obtain a formula for the radius of that type of the problem stability (with respect to perturbations of parameters of the vector criterion) that guarantees the preservation of all Pareto optimal solutions of the initial problem and allows the occurrence of new ones.     

Optimal control problems with unbounded constraint sets

We consider in this paper optimal control problems in which some of the constraint sets are unbounded. Firstly we deal with problems in which the control set is unbounded, so that ‘impulses’ are allowed as admissible controls, discontinuous functions as admissible trajectories. The second type of problem treated is that of infinite horizons, the time set being unbounded. Both class of problems are treated in a similar way. Firstly, a problem is transformed into a semi-infinite linear programming problem by embedding the spacesof admissible trajectory-control pairs into spaces of measures. Then this is mapped into an appropriate nonstandard structure, where a near-minimizer is found for the non-standard optimization; this entity is mapped back as a minimizer for the original problem. An appendix is including introducing the basic concepts of nonstandard analysis

Numerical methods are presented for the estimation of the minimizing measure, and the construction of nearly optimal trajectory-control pairs. Examples are given involving multiplicative controls     

A Lower Bound for the Penalty Parameter in the Exact Minimax Penalty Function Method for Solving Nondifferentiable Extremum Problems

In the paper, we consider the exact minimax penalty function method used for solving a general nondifferentiable extremum problem with both inequality and equality constraints. We analyze the relationship between an optimal solution in the given constrained extremum problem and a minimizer in its associated penalized optimization problem with the exact minimax penalty function under the assumption of convexity of the functions constituting the considered optimization problem (with the exception of those equality constraint functions for which the associated Lagrange multipliers are negative—these functions should be assumed to be concave). The lower bound of the penalty parameter is given such that, for every value of the penalty parameter above the threshold, the equivalence holds between the set of optimal solutions in the given extremum problem and the set of minimizers in its associated penalized optimization problem with the exact minimax penalty function.     

Optimization of the Hausdorff distance between sets in Euclidean space

Set approximation problems play an important role in many areas of mathematics and mechanics. For example, approximation problems for solvability sets and reachable sets of control systems are intensively studied in differential game theory and optimal control theory. In N.N. Krasovskii and A.I. Subbotin’s investigations devoted to positional differential games, one of the key problems was the problem of identification of solvability sets, which are maximal stable bridges. Since this problem can be solved exactly in rare cases only, the question of the approximate calculation of solvability sets arises. In papers by A.B. Kurzhanskii and F.L. Chernous’ko and their colleagues, reachable sets were approximated by ellipsoids and parallelepipeds.In the present paper, we consider problems in which it is required to approximate a given set by arbitrary polytopes. Two sets, polytopes A and B, are given in Euclidean space. It is required to find a position of the polytopes that provides a minimum Hausdorff distance between them. Though the statement of the problem is geometric, methods of convex and nonsmooth analysis are used for its investigation.One of the approaches to dealing with planar sets in control theory is their approximation by families of disks of equal radii. A basic component of constructing such families is best n-nets and their generalizations, which were described, in particular, by A.L. Garkavi. The authors designed an algorithm for constructing best nets based on decomposing a given set into subsets and calculating their Chebyshev centers. Qualitative estimates for the deviation of sets from their best n-nets as n grows to infinity were given in the general case by A.N. Kolmogorov. We derive a numerical estimate for the Hausdorff deviation of one class of sets. Examples of constructing best n-nets are given.     

Quadratic control for linear periodic systems

We propose a new quadratic control problem for linear periodic systems which can be finite or infinite dimensional. We consider both deterministic and stochastic cases. It is a generalization of average cost criterion, which is usually considered for time-invariant systems. We give sufficient conditions for the existence of periodic solutions.Under stabilizability and detectability conditions we show that the optimal control is given by a periodic feedback which involves the periodic solution of a Riccati equation. The optimal closed-loop system has a unique periodic solution which is globally exponentially asymptotically stable. In the stochastic case we also consider the quadratic problem under partial observation. Under two sets of stabilizability and detectability conditions we obtain the separation principle. The filter equation is not periodic, but we show that it can be effectively replaced by a periodic filter. The theory is illustrated by simple examples.This work was done while this author was a visiting professor at the Scuola Normale Superiore, Pisa.     

Spectral optimization for the Stekloff–Laplacian: The stability issue

We consider the problem of minimizing the first non-trivial Stekloff eigenvalue of the Laplacian, among sets with given measure. We prove that the Brock–Weinstock inequality, asserting that optimal shapes for this spectral optimization problem are balls, can be improved by means of a (sharp) quantitative stability estimate. This result is based on the analysis of a certain class of weighted isoperimetric inequalities already proved in Betta et al. (1999) [2]: we provide some new (sharp) quantitative versions of these, achieved by means of a suitable calibration technique.     

Weakly invariant sets of hybrid systems

We consider a mathematical model of a hybrid system in which the continuous dynamics generated at any point in time by one of a given finite family of continuous systems alternates with discrete operations commanding either an instantaneous switching from one system to another, or an instantaneous passage from current coordinates to some other coordinates, or both operations simultaneously. As a special case, we consider a model of a linear switching system. For a hybrid system, we introduce the notion of a weakly invariant set and analyze its structure. We obtain a representation of a weakly invariant set as a union of sets of simpler structure. For the latter sets, we introduce special value functions, for which we obtain expressions by methods of convex analysis. For the same functions, we derive equations of the Hamilton-Jacobi-Bellman type, which permit one to pass from the problem of constructing weakly invariant sets to the control synthesis problem for a hybrid system.