Tikhonov solutions of approximately given systems of linear algebraic equations under finite perturbations of their matrices

The properties of a mathematical programming problem that arises in finding a stable (in the sense of Tikhonov) solution to a system of linear algebraic equations with an approximately given augmented coefficient matrix are examined. Conditions are obtained that determine whether this problem can be reduced to the minimization of a smoothing functional or to the minimal matrix correction of the underlying system of linear algebraic equations. A method for constructing (exact or approximately given) model systems of linear algebraic equations with known Tikhonov solutions is described. Sharp lower bounds are derived for the maximal error in the solution of an approximately given system of linear algebraic equations under finite perturbations of its coefficient matrix. Numerical examples are given.     

Correction of improper linear programming problems in canonical form by applying the minimax criterion

Given an inconsistent system of linear algebraic equations, necessary and sufficient conditions are established for the solvability of the problem of its matrix correction by applying the minimax criterion with the assumption that the solution is nonnegative. The form of the solution to the corrected system is presented. Two formulations of the problem are considered, specifically, the correction of both sides of the original system and correction with the right-hand-side vector being fixed. The minimax-criterion correction of an improper linear programming problem is reduced to a linear programming problem, which is solved numerically in MATLAB.     

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.     

Mathematical programming via the least-squares method

The least-squares method is used to obtain a stable algorithm for a system of linear inequalities as well as linear and nonlinear programming. For these problems the solution with minimal norm for a system of linear inequalities is found by solving the non-negative least-squares (NNLS) problem. Approximate and exact solutions of these problems are discussed. Attention is mainly paid to finding the initial solution to an LP problem. For this purpose an NNLS problem is formulated, enabling finding the initial solution to the primal or dual problem, which may turn out to be optimal. The presented methods are primarily suitable for ill-conditioned and degenerate problems, as well as for LP problems for which the initial solution is not known. The algorithms are illustrated using some test problems.     

Antiweb-wheel inequalities and their separation problems over the stable set polytopes

A stable set in a graph G is a set of pairwise nonadjacent vertices. The problem of finding a maximum weight stable set is one of the most basic ℕℙ-hard problems. An important approach to this problem is to formulate it as the problem of optimizing a linear function over the convex hull STAB(G) of incidence vectors of stable sets. Since it is impossible (unless ℕℙ=coℕℙ) to obtain a “concise” characterization of STAB(G) as the solution set of a system of linear inequalities, it is a more realistic goal to find large classes of valid inequalities with the property that the corresponding separation problem (given a point x ^*, find, if possible, an inequality in the class that x ^* violates) is efficiently solvable.?Some known large classes of separable inequalities are the trivial, edge, cycle and wheel inequalities. In this paper, we give a polynomial time separation algorithm for the (t)-antiweb inequalities of Trotter. We then introduce an even larger class (in fact, a sequence of classes) of valid inequalities, called (t)-antiweb-s-wheel inequalities. This class is a common generalization of the (t)-antiweb inequalities and the wheel inequalities. We also give efficient separation algorithms for them. Received: June 2000 / Accepted: August 2001?Published online February 14, 2002     

Localization of spectrum and stability of certain classes of dynamical systems

We develop a method for the localization of spectra of multiparameter matrix pencils and matrix functions, which reduces the problem to the solution of linear matrix equations and inequalities. We formulate algebraic conditions for the stability of linear systems of differential, difference, and difference-differential equations.     

Dynamic system methods for solving mixed linear matrix inequalities and linear vector inequalities and equalities

A novel idea is proposed for solving a system of mixed linear matrix inequalities and linear vector inequalities and equalities. First, the problem is converted into an unconstrained minimization problem with a continuously differentiable convex objective function. Then, a continuous-time dynamic system and a discrete-time dynamic system are proposed for solving it. Under some mild conditions, the proposed dynamic systems are shown to be globally convergent to a solution of the problem. The merits of the methods refer to their simple numerical implementations and capability for handling nonstrict LMIs easily. In addition, the methods are promising in neural circuits realization, and therefore have potential applications in many online control problems. Several numerical examples are presented to illustrate the performance of the methods and substantiate the theoretical results.     

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.     

LMI优化问题的择一性定理与对偶

考虑目标函数是线性函数约束条件为线性矩阵不等式的LMI优化问题,讨论了LMI优化问题中的四个择一性定理.每种类型的择一性定理包含两个线性不等式和(或)等式系统,一个原始系统和一个对偶系统.弱择一性定理说明两系统中至多只有其一有解;基于凸集分离理论得到的强择一性定理说明两系统有且仅有其一有解.并在此基础上推导了LMI优化...     

Decentralized Reliable Control of Interconnected Time-Delay Systems Against Sensor Failures

In this paper, we study the problem of designing decentralized reliable feedback control methods under a class of control failures for a class of linear interconnected continuous-time systems having internal subsystem time-delays and additional time-delay couplings. These failures are described by a model that takes into consideration possible outages or partial failures in every single actuator of each decentralized controller. The decentralized control design is performed through two steps. First, a decentralized stabilizing reliable feedback control set is derived at the subsystem level through the construction of appropriate Lyapunov-Krasovskii functional and, second, a feasible linear matrix inequalities procedure is then established for the effective construction of the control set under different feedback schemes. Two schemes are considered: the first is based on state-measurement and the second utilizes static output-feedback. The decentralized feedback gains in both schemes are determined by convex optimization over linear matrix inequalities. We characterize decentralized linear matrix inequality-based feasibility conditions such that every local closed-loop subsystem of the linear interconnected delay system is delay-dependent robustly asymptotically stable with an γ-level ℒ₂-gain. The developed results are tested on a representative example.     

Exponential stabilization for a class of hybrid systems with mixed delays in state and control

This paper proposes a switching design for the exponential stabilization problem of hybrid systems with mixed time-delays in both the state and control. By using an improved Lyapunov–Krasovskii functional, a memoryless switching controller for the exponential stabilization of the system is designed in terms of linear matrix inequalities. The approach also allows us to compute simultaneously the two bounds that characterize the exponential stability rate of the solution.     

Design of planar articulated mechanisms using branch and bound

This paper considers an optimization model and a solution method for the design of two-dimensional mechanical mechanisms. The mechanism design problem is modeled as a nonconvex mixed integer program which allows the optimal topology and geometry of the mechanism to be determined simultaneously. The underlying mechanical analysis model is based on a truss representation allowing for large displacements. For mechanisms undergoing large displacements elastic stability is of major concern. We derive conditions, modeled by nonlinear matrix inequalities, which guarantee that a stable equilibrium is found and that buckling is prevented. The feasible set of the design problem is described by nonlinear differentiable and non-differentiable constraints as well as nonlinear matrix inequalities.To solve the mechanism design problem a branch and bound method based on convex relaxations is developed. To guarantee convergence of the method, two different types of convex relaxations are derived. The relaxations are strengthened by adding valid inequalities to the feasible set and by solving bound contraction sub-problems. Encouraging computational results indicate that the branch and bound method can reliably solve mechanism design problems of realistic size to global optimality.     

Robust least squares solution of linear inequalities

Least squares solution of linear inequalities appears in many disciplines such as linear separability problems and inconsistency correction. In this paper we consider this problem with uncertainty in its data. Then we prove that its robust counterpart is equivalent to a second order conic linear optimization problem, which can be efficiently solved using interior point methods.     

Solving Standard Quadratic Optimization Problems via Linear, Semidefinite and Copositive Programming

The problem of minimizing a (non-convex) quadratic function over the simplex (the standard quadratic optimization problem) has an exact convex reformulation as a copositive programming problem. In this paper we show how to approximate the optimal solution by approximating the cone of copositive matrices via systems of linear inequalities, and, more refined, linear matrix inequalities (LMI's). In particular, we show that our approach leads to a polynomial-time approximation scheme for the standard quadratic optimzation problem. This is an improvement on the previous complexity result by Nesterov who showed that a 2/3-approximation is always possible. Numerical examples from various applications are provided to illustrate our approach.     

On approximating the nearest Ω‐stable matrix

In this paper, we consider the problem of approximating a given matrix with a matrix whose eigenvalues lie in some specific region Ω of the complex plane. More precisely, we consider three types of regions and their intersections: conic sectors, vertical strips, and disks. We refer to this problem as the nearest Ω‐stable matrix problem. This includes as special cases the stable matrices for continuous and discrete time linear time‐invariant systems. In order to achieve this goal, we parameterize this problem using dissipative Hamiltonian matrices and linear matrix inequalities. This leads to a reformulation of the problem with a convex feasible set. By applying a block coordinate descent method on this reformulation, we are able to compute solutions to the approximation problem, which is illustrated on some examples.     

Preconditioning projection methods for solving algebraic linear systems

Numerical experiments have shown that projection methods are robust for solving the problem of finding a point satisfying a linear system of n variables and m equations; however, their qualities of convergence depend on certain parameters: an n × n symmetric positive definite matrix M, and a vector u with m components. We are concerned here with the choice of M. Through a link with Conjugate Gradient methods we determine an expedient M. Preliminary numerical results on a hard 3D partial differential equation are highly promising. We solve a discretized system that could not be solved by conventional methods. We also give hints on how to adapt our findings to the solution of a linear system of inequalities. This is the first stage of a forthcoming research. This revised version was published online in June 2006 with corrections to the Cover Date.     

Robust distributed state estimation for genetic regulatory networks with markovian jumping parameters

In this paper, the robust distributed state estimation problem is dealt with for the delayed genetic regulatory networks (GRNs) with SUM logic and multiple sensors. The system parameters are time-varying, norm-bounded, and controlled by a Markov Chain. Time delays here are assumed to be time-varying and belong to the given intervals. The genetic regulatory functions are supposed to satisfy the sector-like condition. We aim to design a distributed state estimator which approximates the genetic states through the measurements of the sensors, i.e., the estimation error system is robustly asymptotically stable in the mean square. Based on the Lyapunov functional method and the stochastic analysis technique, it is shown that if a set of linear matrix inequalities (LMIs) are feasible, the desired distributed state estimator does exist. A numerical example is constructed in the end of the paper to demonstrate the effectiveness of the obtained criteria.     

A numerically stable least squares solution to the quadratic programming problem

The strictly convex quadratic programming problem is transformed to the least distance problem — finding the solution of minimum norm to the system of linear inequalities. This problem is equivalent to the linear least squares problem on the positive orthant. It is solved using orthogonal transformations, which are memorized as products. Like in the revised simplex method, an auxiliary matrix is used for computations. Compared to the modified-simplex type methods, the presented dual algorithm QPLS requires less storage and solves ill-conditioned problems more precisely. The algorithm is illustrated by some difficult problems.      

On Generalizations of the Frank-Wolfe Theorem to Convex and Quasi-Convex Programmes

In this paper we are concerned with the problem of boundedness and the existence of optimal solutions to the constrained optimization problem. We present necessary and sufficient conditions for boundedness of either a faithfully convex or a quasi-convex polynomial function over the feasible set defined by a system of faithfully convex inequality constraints and/or quasi-convex polynomial inequalities, where the faithfully convex functions satisfy some mild assumption. The conditions are provided in the form of an algorithm, terminating after a finite number of iterations, the implementation of which requires the identification of implicit equality constraints in a homogeneous linear system. We prove that the optimal solution set of the considered problem is nonempty, this way extending the attainability result well known as the so-called Frank-Wolfe theorem. Finally we show that our extension of the Frank-Wolfe theorem immediately implies continuity of the solution set defined by the considered system of (quasi)convex inequalities.     

Robust stabilization of a class of state-dependent jump linear systems

In this article, we consider a continuous-time state-dependent jump linear system (SDJLS), a kind of stochastic hybrid system, with the presence of uncertainties in system parameters. In SDJLS, we consider that the transition rates of the underlying random jump process depend on the state variable. In particular, we assume the transition rates to have different values across suitably defined sets to which the state of the system belongs, and address a problem of robust stability and stabilization analysis. We obtain sufficient conditions for robust stability and state-feedback stabilization in terms of linear matrix inequalities (LMIs). We validate the obtained sufficient robust stability and stabilization conditions with numerical examples.