A dual perturbation view of linear programming

Solving standard-form linear prograrns via perturbation of the primal objective function has received much attention recently. In this paper, we investigate a new perturbation scheme which obtains a dual optimal solution by perturbing the dual feasible domain under different norms. A dual-to-primal conversion formula is also provided. We show that this new perturbation scheme actually generalizes the primal entropic perturbation approach to linear programming.Partially sponsored by the North Carolina Supercomputing Center 1994 Cray Research Grant and the National Textile Center Research Grant.     

Controllability and observability of a class of linear impulsive systems

This paper studies the controllability and observability of a class of linear piecewise constant impulsive systems. Necessary and sufficient criteria for reachability and controllability are established, respectively. It is proved that the reachability is equivalent to the controllability under some mild conditions. Then, necessary and sufficient criteria for observability and determinability of such systems are established, respectively. It is also proved that the observability is equivalent to the determinability under some mild conditions. Our criteria are of geometric type, they can be transformed into algebraic type conveniently. Finally, a numerical example is given to illustrate the utility of our criteria.     

Qualitative properties and stabilizability of a model for blood thrombin formation

We perform a qualitative analysis of a differential equation that was originally introduced by Stortelder, Hemker and Hemker to model the formation of thrombin, and discuss issues of controllability and stabilizability. Results include a general proof of convergence to equilibrium, and of local exponential stabilizability.     

Solving the subproblem in the lagrangian dual of separable discrete programs with linear constraints

This note presents an efficient method for the routine solution of the subproblem associated with the Lagrangian dual of discrete programming problems having separable non-linear objective function and linear constraints. An additional advantage for subgradient methods is described.     

Control and Stabilization Properties for a Singular Heat Equation with an Inverse-Square Potential

The goal of this article is to analyze control properties of parabolic equations with a singular potential ? μ/|x|², where μ is a real number. When μ ≤ (N ? 2)²/4, it was proved in [19 Vancostenoble , J. , Zuazua , E. ( 2008 ). Null controllability for the heat equation with singular inverse-square potentials . J. Funct. Anal. 254 : 1864 – 1902 .[Crossref], [Web of Science ®] , [Google Scholar]] that the equation can be controlled to zero with a distributed control which surrounds the singularity. In the present work, using Carleman estimates, we will prove that this assumption is not necessary, and that we can control the equation from any open subset as for the heat equation. Then we will study the case μ > (N ? 2)²/4, and prove that the situation changes completely: indeed, we will consider a sequence of regularized potentials μ/(|x|² + ?²), and prove that we cannot stabilize the corresponding systems uniformly with respect to ? > 0, due to the presence of explosive modes which concentrate around the singularity.     

The controllability of a system of two bank-to-turn airborne vehicles

This letter deals with the controllability of the motion of a system of two bank-to-turn airborne vehicles. It is shown that the smooth manifold on which the system is controllable, is not unique.     

On solving a primal geometric program by partial dual optimization

The several published methods for mapping a dual solution estimate to a primal solution estimate in posynomial geometric programming provide no criteria for deciding how much deviation from primal feasibility, or discrepancy between the primal and dual objective function values, should be permitted before the primal solution estimate is accepted by the designer. This paper presents a new and simple dual-to-primal conversion method that uses the cost coefficients to provide a sound economic criterion for determining when to accept a primal solution estimate. The primal solution estimate generated is the exact solution to a modified primal obtained from the given primal by modifying the cost coefficients, with the exponent matrix left unchanged. The method is shown to have desirable properties when coupled with a convergent dual algorithm.     

Closed-form solutions to the nonhomogeneous Yakubovich-conjugate matrix equation

Some closed-form solutions are provided for the nonhomogeneous Yakubovich-conjugate matrix equation with X and Y being unknown matrices. The presented solutions can offer all the degrees of freedom which is represented by an arbitrarily chosen parameter matrix. The primary feature of the solutions is that the matrices F and R are not restricted to be in any canonical form, or may be even unknown a priori. One of the solutions is neatly expressed in terms of controllability matrices and observability matrices.     

The dual quasisemigroup and controllability of evolution equations

We study the notion of dual quasisemigroups of bounded linear operators as a generalization of that for strongly continuous semigroup and prove some properties similar to the dual of a semigroup, among other things we prove that for reflexive Banach spaces the dual quasisemigroup is strongly continuous on (0,+∞). This allows us to extend some recent criteria of controllability to a general class of evolution equations in reflexive Banach spaces.     

Controllability and observability of a heat equation with hyperbolic memory kernel

The exact controllability and observability for a heat equation with hyperbolic memory kernel in anisotropic and nonhomogeneous media are considered. Due to the appearance of such a kind of memory, the speed of propagation for solutions to the heat equation is finite and the corresponding controllability property has a certain nature similar to hyperbolic equations, and is significantly different from that of the usual parabolic equations. By means of Carleman estimate, we establish a positive controllability and observability result under some geometric condition. On the other hand, by a careful construction of highly concentrated approximate solutions to hyperbolic equations with memory, we present a negative controllability and observability result when the geometric condition is not satisfied.     

Computational complexity of a piecewise linear homotopy algorithm

We give a bound on the number of steps required by the piecewise linear algorithm based on component wise homotopy (proposed by the author for structured problems) when solving a linear problem. When the coefficient matrix is symmetric and positive definite, this bound is polynomial inn and linear in the condition number of the matrix. We also investigate the expected value of the bound for a particular distribution of such matrices. This research has been partially supported by the grant MCS 80-05154 from the National Science Foundation.     

Bounding a class of nonconvex linearly-constrained resource allocation problems via the surrogate dual

We consider a class of problems of resource allocation under economies of scale, namely that of minimizing a lower semicontinuous, isotone, and explicitly quasiconcave cost function subject to linear constraints. An important class of algorithms for the linearly constrained minimization of nonconvex cost functions utilize the branch and bound approach, using convex underestimating cost functions to compute the lower bounds.We suggest instead the use of the surrogate dual problem to bound subproblems. We show that the success of the surrogate dual in fathoming subproblems in a branch and bound algorithm may be determined without directly solving the surrogate dual itself, but that a simple test of the feasibility of a certain linear system of inequalities will suffice. This test is interpreted geometrically and used to characterize the extreme points and extreme rays of the optimal value function's level sets.Research partially supported by NSF under grant # ENG77-06555.     

A dual strategy for solving the linear programming relaxation of a driver scheduling system

A Mathematical Programming model of a driver scheduling system is described. This consists of set covering and partitioning constraints, possibly user-supplied side constraints, and two pre-emptively ordered objectives. The previous solution strategy addressed the two objectives using separate Primal Simplex optimisations; a new strategy uses a single weighted objective function and a Dual Simplex algorithm initiated by a specially developed heuristic. Computational results are reported.     

A homotopy perturbation algorithm to solve a system of Fredholm–Volterra type integral equations

In this paper, an application of He’s homotopy perturbation (HPM) method is applied to solve the system of Fredholm and Volterra type integral equations, the results revealing that the HPM is very effective and simple.     

Combining a path method and parametric linear programming for the computation of competitive equilibria

A path-following philosophy (continuation method, global Newton method) is used to compute equilibria for piecewise linear economies while taking advantage of the linear structure of the model. The existence of a path leading through certain faces of a polyhedral set to an equilibrium point is demonstrated. Computational experience is reported which indicates that this method is promising for models dealing with many commodities and relatively few consumers.Most of this paper has been extracted from the author's doctoral dissertation for the Department of Operations Research at Stanford University; the author would like to express indebtedness to his advisor, R. Wilson. Major revisions were made while the author was at Bell Laboratories in Whippany, New Jersey.     

Determining dimension of the solution component that contains a computed zero of a polynomial system

When the Jacobian of a computed numerical solution of a polynomial system in Cn allows very small singular values, the solution could be isolated with a multiple multiplicity or may belong to a solution component with positive dimension. The algorithm constructed in this article intends to differentiate those cases by determining the dimension of the solution component M in which the solution lies. Of particular interest is the case when dim(M)=0, then the solution is of course isolated. While the proposed algorithm is experimental, it has been tested successfully on the class of problems with the solution in question belonging to a reduced component. Numerical results are provided to illustrate the accuracy of the algorithm.     

Two suggestions of how to define a stochastic stress-strength system

In this paper we suggest how to generalize a stress-strength system treated in Ebrahimi (1984) at a fixed point of time to a dynamic situation in two ways. In the first approach we assume that a stress factor starts and stops to influence the system and different stress factors add up to total system stress at any time. In the second approach we assume that a stress factors starts and stops to influence the system and stress factors do not accumulate additively.