Calmness of partially perturbed linear systems with an application to the central path

ABSTRACT

In this paper we develop point-based formulas for the calmness modulus of the feasible set mapping in the context of linear inequality systems with a fixed abstract constraint and (partially) perturbed linear constraints. The case of totally perturbed linear systems was previously analyzed in [Cánovas MJ, López MA, Parra J, et al. Calmness of the feasible set mapping for linear inequality systems. Set-Valued Var Anal. 2014;22:375–389, Section 5]. We point out that the presence of such an abstract constraint yields the current paper to appeal to a notable different methodology with respect to previous works on the calmness modulus in linear programming. The interest of this model comes from the fact that partially perturbed systems naturally appear in many applications. As an illustration, the paper includes an example related to the classical central path construction. In this example we consider a certain feasible set mapping whose calmness modulus provides a measure of the convergence of the central path. Finally, we underline the fact that the expression for the calmness modulus obtained in this paper is (conceptually) implementable as far as it only involves the nominal data.     

Upper Semicontinuity of the Feasible Set Mapping for Linear Inequality Systems

In this paper we characterize the upper semicontinuity of the feasible set mapping at a consistent linear semi-infinite system (LSIS, in brief). In our context, no standard hypothesis is required in relation to the set indexing the constraints and, consequently, the functional dependence between the linear constraints and their associated indices has no special property. We consider, as parameter space, the set of all LSIS having the same index set, endowed with an extended metric to measure the size of the perturbations. We introduce the concept of reinforced system associated with our nominal system. Then, the upper semicontinuity property of the feasible set mapping at the nominal system is characterized looking at the feasible sets of both systems. The fact that this characterization depends only on the nominal system, not involving systems in a neighbourhood, is remarkable. We also provide a necessary and sufficient condition for the aimed property exclusively in terms of the coefficients of the system.     

Calmness of the Argmin Mapping in Linear Semi-Infinite Optimization

This paper characterizes the calmness property of the argmin mapping in the framework of linear semi-infinite optimization problems under canonical perturbations; i.e., continuous perturbations of the right-hand side of the constraints (inequalities) together with perturbations of the objective function coefficient vector. This characterization is new for semi-infinite problems without requiring uniqueness of minimizers. For ordinary (finitely constrained) linear programs, the calmness of the argmin mapping always holds, since its graph is piecewise polyhedral (as a consequence of a classical result by Robinson). Moreover, the so-called isolated calmness (corresponding to the case of unique optimal solution for the nominal problem) has been previously characterized. As a key tool in this paper, we appeal to a certain supremum function associated with our nominal problem, not involving problems in a neighborhood, which is related to (sub)level sets. The main result establishes that, under Slater constraint qualification, perturbations of the objective function are negligible when characterizing the calmness of the argmin mapping. This result also states that the calmness of the argmin mapping is equivalent to the calmness of the level set mapping.     

Banach空间集值映射的度量正则性与变分方程的Lipschitz稳定性

综述了集值映射的某些概念,例如度量正则性、伪Lipschitz性质(Aubin性质)、度量次正则性和Calm性质和这些概念的相互关系以及某些判据.也给出了他们在变分方程解的鲁棒Lipschitz稳定性、约束优化问题的最优性条件、集合族的线性正则性质和广义方程迭代过程的收敛性.     

Strong Abadie CQ,ACQ, calmness and linear regularity

The Abadie CQ (ACQ) for convex inequality systems is a fundamental notion in optimization and approximation theory. In terms of the contingent cone and tangent derivative, we extend the Abadie CQ to more general convex multifunction cases and introduce the strong ACQ for both multifunctions and inequality systems. Some seemly unrelated notions are unified by the new ACQ and strong ACQ. Relationships among ACQ, strong ACQ, basic constraint qualification (BCQ) and strong BCQ are discussed. Using the strong ACQ, we study calmness of a closed and convex multifunction between two Banach spaces and, different from many existing dual conditions for calmness, establish several primal characterizations of calmness. As applications, some primal characterizations for error bounds and linear regularity are established; in particular, some existing results are improved.     

Inclusions in general spaces: Hoelder stability, solution schemes and Ekeland's principle

We present two basic lemmas on exact and approximate solutions of inclusions and equations in general spaces. Its applications involve Ekeland's principle, characterize calmness, lower semicontinuity and the Aubin property of solution sets in some Hoelder-type setting and connect these properties with certain iteration schemes of descent type. In this way, the mentioned stability properties can be directly characterized by convergence of more or less abstract solution procedures. New stability conditions will be derived, too. Our basic models are (multi-) functions on a complete metric space with images in a linear normed space.     

Optimization methods and stability of inclusions in Banach spaces

Our paper deals with the interrelation of optimization methods and Lipschitz stability of multifunctions in arbitrary Banach spaces. Roughly speaking, we show that linear convergence of several first order methods and Lipschitz stability mean the same. Particularly, we characterize calmness and the Aubin property by uniformly (with respect to certain starting points) linear convergence of descent methods and approximate projection methods. So we obtain, e.g., solution methods (for solving equations or variational problems) which require calmness only. The relations of these methods to several known basic algorithms are discussed, and errors in the subroutines as well as deformations of the given mappings are permitted. We also recall how such deformations are related to standard algorithms like barrier, penalty or regularization methods in optimization.     

Stability Analysis for Parameterized Variational Systems with Implicit Constraints

In the paper we provide new conditions ensuring the isolated calmness property and the Aubin property of parameterized variational systems with constraints depending, apart from the parameter, also on the solution itself. Such systems include, e.g., quasi-variational inequalities and implicit complementarity problems. Concerning the Aubin property, possible restrictions imposed on the parameter are also admitted. Throughout the paper, tools from the directional limiting generalized differential calculus are employed enabling us to impose only rather weak (non- restrictive) qualification conditions. Despite the very general problem setting, the resulting conditions are workable as documented by some academic examples.

     

Time-constrained temporal logic control of multi-affine systems

In this paper, we consider the problem of controlling a dynamical system such that its trajectories satisfy a temporal logic property in a given amount of time. We focus on multi-affine systems and specifications given as syntactically co-safe linear temporal logic formulas over rectangular regions in the state space. The proposed algorithm is based on estimating the time bounds for facet reachability problems and solving a time optimal reachability problem on the product between a weighted transition system and an automaton that enforces the satisfaction of the specification. A random optimization algorithm is used to iteratively improve the solution.     

Error bounds,metric subregularity and stability in Generalized Nash Equilibrium Problems with nonsmooth payoff functions

In this paper, we study the calmness of a generalized Nash equilibrium problem (GNEP) with non-differentiable data. The approach consists in obtaining some error bound property for the KKT system associated with the generalized Nash equilibrium problem, and returning to the primal problem thanks to the Slater constraint qualification.     

A polyhedral approach to the alldifferent system

This paper examines the facial structure of the convex hull of integer vectors satisfying a system of alldifferent predicates, also called an alldifferent system. The underlying analysis is based on a property, called inclusion, pertinent to such a system. For the alldifferent systems for which this property holds, we present two families of facet-defining inequalities, establish that they completely describe the convex hull and show that they can be separated in polynomial time. Consequently, the inclusion property characterises a group of alldifferent systems for which the linear optimization problem (i.e. the problem of optimizing a linear function over that system) can be solved in polynomial time. Furthermore, we establish that, for systems with three predicates, the inclusion property is also a necessary condition for the convex hull to be described by those two families of inequalities. For the alldifferent systems that do not possess that property, we establish another family of facet-defining inequalities and an accompanied polynomial-time separation algorithm. All the separation algorithms are incorporated within a cutting-plane scheme and computational experience on a set of randomly generated instances is reported. In concluding, we show that the pertinence of the inclusion property can be decided in polynomial time.     

向量丛动力系统研究註记(Ⅱ)──部份1

过去,向量丛线性动力系统的整体线性性质研究已经显得相当广泛。现在,我们提议研究这种线性系统的扰动性质。我们要考虑的这种扰动系统将不再是线性的,但要研究的性质一般仍是整体性的。再者我们感兴趣的为非一致双曲性。在本文中我们给出了这种扰动的恰当的定义。它虽表现得有几分不太通常,然而它较深地植根于有关微分动力系统理论的典泛方程组中。这里一般的问题是要观察,当扰动发生后,原给系统的何种性质得以保持下来。本文的全部内容是要建立这种类型的一个定理。     

Exact penalty functions and calmness for mathematical programming under nonlinear perturbations

In the present paper, the effects of nonlinear perturbations of constraint systems are considered over the relationship between calmness and exact penalization, within the context of mathematical programming with equilibrium constraints. Two counterexamples are provided showing that the crucial link between the existence of penalty functions and the property of calmness for perturbed problems is broken in the presence of general perturbations. Then, some properties from variational analysis are singled out, which are able to restore to a certain extent the broken link. Consequently, conditions on the value function associated to perturbed optimization problems are investigated in order to guarantee the occurrence of the above properties.     

Isolated calmness of solution mappings in convex semi-infinite optimization

This paper is concerned with isolated calmness of the solution mapping of a parameterized convex semi-infinite optimization problem subject to canonical perturbations. We provide a sufficient condition for isolated calmness of this mapping. This sufficient condition characterizes the strong uniqueness of minimizers, under the Slater constraint qualification. Moreover, on the assumption that the objective function and the constraints are linear, we show that this condition is also necessary for isolated calmness.     

一类抽象动力系统的C0群性质及其在迁移理论中的应用

本文研究一类抽象动力系统的性质.使用Hilbert空间的分解方法,获得了主算子的谱和相应的群的表示;使用有界线性算子的扰动理论,获得了抽象动力算子的谱分解.作为应用,研究了迁移理论中的一类积-微分方程.     

Stabilization of linear distributed control systems with unbounded delay

In this paper we study the asymptotic stabilization of linear distributed parameter control systems with unbounded delay. Assuming that the semigroup of operators associated with the uncontrolled and nondelayed equation is compact and that the phase space is a uniform fading memory space, we characterize those systems that can be stabilized using a feedback control. As consequence we conclude that every system of this type is stabilizable with an appropriated finite dimensional control.     

Bochner可积函数空间上线性算子的积分表示

在研究Bochner可积函数空间上线性算子的积分表示时,一般总要求函数值域空间X具有Radon-Nikodym性质.本文从线性算子本身出发,在不要求X具有Radon-Nikodym性质的条件下研究线性算子的积分表示,给出一个充要条件.     

Falsification of hybrid systems with symbolic reachability analysis and trajectory splicing

The falsification of a hybrid system aims at finding trajectories that violate a given safety property. This is a challenging problem, and the practical applicability of current falsification algorithms still suffers from their high time complexity. In contrast to falsification, verification algorithms aim at providing guarantees that no such trajectories exist. Recent symbolic reachability techniques are capable of efficiently computing linear constraints that enclose all trajectories of the system with reasonable precision. In this paper, we leverage the power of symbolic reachability algorithms to improve the scalability of falsification techniques. Recent approaches to falsification reduce the problem to a nonlinear optimization problem. We propose to reduce the search space of the optimization problem by adding linear state constraints obtained with a reachability algorithm. An empirical study of how varying abstractions during symbolic reachability analysis affect the performance of solving a falsification problem is presented. In addition, for solving a falsification problem, we propose an alternating minimization algorithm that solves a linear programming problem and a non-linear programming problem in alternation finitely many times. We showcase the efficacy of our algorithms on a number of standard hybrid systems benchmarks demonstrating the performance increase and number of falsifyable instances.     

Critical Objective Size and Calmness Modulus in Linear Programming

This paper introduces the concept of critical objective size associated with a linear program in order to provide operative point-based formulas (only involving the nominal data, and not data in a neighborhood) for computing or estimating the calmness modulus of the optimal set (argmin) mapping under uniqueness of nominal optimal solution and perturbations of all coefficients. Our starting point is an upper bound on this modulus given in Cánovas et al. (4). In this paper we prove that this upper bound is attained if and only if the norm of the objective function coefficient vector is less than or equal to the critical objective size. This concept also allows us to obtain operative lower bounds on the calmness modulus. We analyze in detail an illustrative example in order to explore some strategies that can improve the referred upper and lower bounds.