Stabilization by a linear feedback under phase constraints

We suggest a new method for solving the stabilization problem under phase constraints with the use of linear matrix inequalities. We consider the cases of complete and incomplete state measurements and the presence of nonstationary parametric perturbations. In the synthesis of linear control laws, the suggested method permits one to cover all possible quadratic Lyapunov functions and indicate a set of initial values for trajectories satisfying the phase constraints.     

An Improved Delay-Dependent Criterion for Asymptotic Stability of Uncertain Dynamic Systems with Time-Varying Delays

In this paper, the problem of stability analysis for uncertain dynamic systems with time-varying delays is considered. The parametric uncertainties are assumed to be bounded in magnitude. Based on the Lyapunov stability theory, a new delay-dependent stability criterion for the system is established in terms of linear matrix inequalities, which can be solved easily by various efficient convex optimization algorithms. Two numerical examples are illustrated to show the effectiveness of proposed method.     

Zur Identifikation redundanter Nebenbedingungen in linearen Programmen

Zusammenfassung Ein bekanntes Kriterium zur Erkennung redundanter Ungleichungen in einem linearen Ungleichungssystem wird in einer vereinfachten Form hergeleitet. Dieses Kriterium wird dann als Optimalitätskriterium in ein systematisches Verfahren zur Identifikation streng redundanter Ungleichungen eines linearen Ungleichungssystems bzw. eines Systems von Nebenbedingungen eines linearen Programms eingebaut. Das beschriebene Verfahren besteht im Grunde in der Minimierung von Schlupfvariablen über das Lösungspolyeder des ursprünglichen Ungleichungssystems. Ein kleines illustratives Beispiel mit vorzeichenunbeschränkten Variablen wird vorgeführt.

---

Summary A known criterion for redundant inequalities in a system of linear inequalities is derived in a simplified form. This criterion is then used as an optimality-criterion in the framework of a procedure for identifying of strictly redundant inequalities in a system of linear inequalities or in a system of constraints of a linear programming problem. The described method consists basically of the minimization of slack variables over the solution-polyhedron of the original system of inequalities. A small illustrative example is given with variables not constrained in sign.

     

Lower semicontinuity of the solution map to a parametric elliptic optimal control problem with mixed pointwise constraints

This paper studies the solution stability of a parametric optimal control problem governed by single linear elliptic equations with mixed control-state constraints and convex cost functions. By reducing the problem to a parametric programming problem and a parametric variational inequality, we obtain sufficient conditions under which the solution map to an elliptic optimal control problem is lower semicontinuous.     

Robust Stability Criteria for Uncertain Neutral Systems with Interval Time-Varying Delay

In this paper, we consider the problem of robust stability of a class of linear uncertain neutral systems with interval time-varying delay under (i) nonlinear perturbations in state, and (ii) time-varying parametric uncertainties using Lyapunov-Krasovskii approach. By constructing a candidate Lyapunov-Krasovskii (LK) functional, that takes into account the delay-range information appropriately, less conservative robust stability criteria are proposed in terms of linear matrix inequalities (LMI) to compute the maximum allowable bound for the delay-range within which the uncertain neutral system under consideration remains asymptotically stable. The reduction in conservatism of the proposed stability criterion over recently reported results is attributed to the fact that time-derivative of the LK functional is bounded tightly without neglecting any useful terms using a minimal number of slack matrix variables. The analysis, subsequently, yields a stability condition in convex LMI framework, that can be solved non-conservatively at boundary conditions using standard LMI solvers. The effectiveness of the proposed stability criterion is demonstrated through standard numerical examples.     

Lyapunov function method for control law synthesis under one integral and several phase constraints

We consider the synthesis of linear control laws under one integral and several phase constraints on the basis of the Lyapunov function method and the technique of linear matrix inequalities. In particular, our method permits one to obtain suboptimal state or output feedbacks providing the minimum upper bound for a quadratic functional under phase and control constrains or the minimum bound for the maximum deviation of the controlled variable under one integral and several phase constraints. The synthesis is generalized to the case of nonstationary parametric perturbations in the plant.     

Subgradients of the Value Function to a Parametric Optimal Control Problem

This paper studies the first-order behavior of the value function of a parametric optimal control problem with linear constraints and nonconvex cost functions. By establishing an abstract result on the Fréchet subdifferential of the value functions of a parametric mathematical programming problem, a new formula for computing the Fréchet subdifferential of the value function to a parametric optimal control problem is obtained.     

Markov control processes with pathwise constraints

This paper deals with discrete-time Markov control processes in Borel spaces, with unbounded rewards. The criterion to be optimized is a long-run sample-path (or pathwise) average reward subject to constraints on a long-run pathwise average cost. To study this pathwise problem, we give conditions for the existence of optimal policies for the problem with “expected” constraints. Moreover, we show that the expected case can be solved by means of a parametric family of optimality equations. These results are then extended to the problem with pathwise constraints.     

Valid inequalities for separable concave constraints with indicator variables

We study valid inequalities for optimization models that contain both binary indicator variables and separable concave constraints. These models reduce to a mixed-integer linear program (MILP) when the concave constraints are ignored, or to a nonconvex global optimization problem when the binary restrictions are ignored. In algorithms designed to solve these problems to global optimality, cutting planes to strengthen the relaxation are traditionally obtained using valid inequalities for the MILP only. We propose a technique to obtain valid inequalities that are based on both the MILP constraints and the concave constraints. We begin by characterizing the convex hull of a four-dimensional set consisting of a single binary indicator variable, a single concave constraint, and two linear inequalities. Using this analysis, we demonstrate how valid inequalities for the single node flow set and for the lot-sizing polyhedron can be “tilted” to give valid inequalities that also account for separable concave functions of the arc flows. We present computational results demonstrating the utility of the new inequalities for nonlinear transportation problems and for lot-sizing problems with concave costs. To our knowledge, this is one of the first works that simultaneously convexifies both nonconvex functions and binary variables to strengthen the relaxations of practical mixed-integer nonlinear programs.     

On the Continuity of the Optimal Value in Parametric Linear Optimization: Stable Discretization of the Lagrangian Dual of Nonlinear Problems

This paper is focused on the stability of the optimal value, and its immediate repercussion on the stability of the optimal set, for a general parametric family of linear optimization problems in ⁿ. In our approach, the parameter ranges over an arbitrary metric space, and each parameter determines directly a set of coefficient vectors describing the linear system of constraints. Thus, systems associated with different parameters are not required to have the same number (cardinality) of inequalities. In this way, discretization techniques for solving a nominal linear semi-infinite optimization problem may be modeled in terms of suitable parametrized problems. The stability results given in the paper are applied to the stability analysis of the Lagrangian dual associated with a parametric family of nonlinear programming problems. This dual problem is translated into a linear (semi-infinite) programming problem and, then, we prove that the lower semicontinuity of the corresponding feasible set mapping, the continuity of the optimal value function, and the upper semicontinuity of the optimal set mapping are satisfied. Then, the paper shows how these stability properties for the dual problem entail a nice behavior of parametric approximation and discretization strategies (in which an ordinary linear programming problem may be considered in each step). This approximation–discretization process is formalized by means of considering a double parameter: the original one and the finite subset of indices (grid) itself. Finally, the convex case is analyzed, showing that the referred process also allows us to approach the primal problem.Mathematics Subject Classifications (2000) Primary 90C34, 90C31; secondary 90C25, 90C05.     

Equivalences between Data Envelopment Analysis and the theory of redundancy in linear systems

This paper establishes how the non-parametric frontier estimation methodology of Data Envelopment Analysis (DEA) and the classical problem of detecting redundancy in a system of linear inequalities are connected. We present an analysis of the sets generated in two of DEA's models from where the empirical efficient production frontier is established from the point of view of polyhedral set theory. This yields convenient alternative characterizations of these sets which provide new insights about their properties. We use these insights to show how these polyhedral sets connect DEA to redundancy in linear systems. This means that DEA can benefit from a rich and well-established collection of computational and theoretical results which apply directly from redundancy in linear systems.     

Uniform saturation in linear inequality systems

Redundant constraints in linear inequality systems can be characterized as those inequalities that can be removed from an arbitrary linear optimization problem posed on its solution set without modifying its value and its optimal set. A constraint is saturated in a given linear optimization problem when it is binding at the optimal set. Saturation is a property related with the preservation of the value and the optimal set under the elimination of the given constraint, phenomena which can be seen as weaker forms of excess information in linear optimization problems. We say that an inequality of a given linear inequality system is uniformly saturated when it is saturated for any solvable linear optimization problem posed on its solution set. This paper characterizes the uniform saturated inequalities and other related classes of inequalities. This work was supported by the MCYT of Spain and FEDER of UE, Grant BFM2002-04114-C02-01.     

Partial linear characterizations of the asymmetric travelling salesman polytope

We consider the linear programming formulation of the asymmetric travelling salesman problem. Several new inequalities are stated which yield a sharper characterization in terms of linear inequalities of the travelling salesman polytope, i.e., the convex hull of tours. In fact, some of the new inequalities as well as some of the well-known subtour elimination constraints are indeed facets of the travelling salesman polytope, i.e., belong to the class of inequalities that uniquely characterize the convex hull of tours to an-city problem.     

Benders's method revisited

The master problem in Benders's partitioning method is an integer program with a very large number of constraints, each of which is usually generated by solving the integer program with the constraints generated earlier. Computational experience shows that the subset B of those constraints of the master problem that are satisfied with equality at the linear programming optimum often play a crucial role in determining the integer optimum, in the sense that only a few of the remaining inequalities are needed. We characterize this subset B of inequalities. If an optimal basic solution to the linear program is nondegenerate in the continuous variables and has p integer-constrained basic variables, then the corresponding set B contains at most 2^p inequalities, none of which is implied by the others. We give an efficient procedure for generating an appropriate subset of the inequalities in B, which leads to a considerably improved version of Benders's method.     

含非线性扰动的变时滞中立系统时滞相关稳定性新条件

研究一类含非线性扰动和混合时变时滞的中立型系统时滞相关鲁棒稳定性问题.通过构造包含三重积分项的Lyapunov-Krasovskii的泛函,结合积分不等式和自由权矩阵技术,建立了基于线性矩阵不等式(LMI)形式的离散时滞和中立时滞均相关的稳定性新判据.判据扩大了系统稳定所允许的最大时滞上界范围,具有更低的保守性.利用MATLAB的LMI工具箱进行了数值仿真,仿真算例验证了所提出的稳定性判据的有效性.     

基于可信性测度的模糊线性不等式组的确定性等价

在模糊优化决策问题中,约束条件包含模糊线性不等式组.如何把它们转化为确定性的等价形式,这在模糊控制和模糊决策中起着重要的作用.可信性测度是模糊数学实现公理化体系的一个基础.本文在可信性测度的基础上,探讨了模糊约束在一定的满意度水平之下转化为确定性的等价式,同时就三角形模糊变量给出了模糊线性不等式组的确定性等价的具体表达式.     

Localization of eigenvalues of polynomial matrices

We consider the problem of localization of eigenvalues of polynomial matrices. We propose sufficient conditions for the spectrum of a regular matrix polynomial to belong to a broad class of domains bounded by algebraic curves. These conditions generalize the known method for the localization of the spectrum of polynomial matrices based on the solution of linear matrix inequalities. We also develop a method for the localization of eigenvalues of a parametric family of matrix polynomials in the form of a system of linear matrix inequalities.     

Smoothing approach to Nash equilibrium formulations for a class of equilibrium problems with shared complementarity constraints

The equilibrium problem with equilibrium constraints (EPEC) can be looked on as a generalization of Nash equilibrium problem (NEP) and the mathematical program with equilibrium constraints (MPEC) whose constraints contain a parametric variational inequality or complementarity system. In this paper, we particularly consider a special class of EPECs where a common parametric P-matrix linear complementarity system is contained in all players?? strategy sets. After reformulating the EPEC as an equivalent nonsmooth NEP, we use a smoothing method to construct a sequence of smoothed NEPs that approximate the original problem. We consider two solution concepts, global Nash equilibrium and stationary Nash equilibrium, and establish some results about the convergence of approximate Nash equilibria. Moreover we show some illustrative numerical examples.     

Minimax linear programming problem

In this paper, we consider the following minimax linear programming problem: min z = max_{1 ≤ j ≤ n}{C_jX_j}, subject to Ax = g, x ≥ 0. It is well known that this problem can be transformed into a linear program by introducing n additional constraints. We note that these additional constraints can be considered implicitly by treating them as parametric upper bounds. Based on this approach we develop two algorithms: a parametric algorithm and a primal—dual algorithm. The parametric algorithm solves a linear programming problem with parametric upper bounds and the primal—dual algorithm solves a sequence of related dual feasible linear programming problems. Computation results are also presented, which indicate that both the algorithms are substantially faster than the simplex algorithm applied to the enlarged linear programming problem.