Logic-Based Modeling and Solution of Nonlinear Discrete/Continuous Optimization Problems

This paper presents a review of advances in the mathematical programming approach to discrete/continuous optimization problems. We first present a brief review of MILP and MINLP for the case when these problems are modeled with algebraic equations and inequalities. Since algebraic representations have some limitations such as difficulty of formulation and numerical singularities for the nonlinear case, we consider logic-based modeling as an alternative approach, particularly Generalized Disjunctive Programming (GDP), which the authors have extensively investigated over the last few years. Solution strategies for GDP models are reviewed, including the continuous relaxation of the disjunctive constraints. Also, we briefly review a hybrid model that integrates disjunctive programming and mixed-integer programming. Finally, the global optimization of nonconvex GDP problems is discussed through a two-level branch and bound procedure.     

The Discrete Linear One-sided Chebyshev Approximation

A simplex algorithm for the one-sided Chebyshev solution fromabove of overdetermined systems of linear equations is described.In this algorithm minimum storage is required, no artificialvariables are needed and no conditions are imposed on the coefficientmatrix. The described algorithm applies as well for the one-sidedChebyshev solution from below. The algorithm is a simple andfast one. Numerical results are given.     

Linear Complexity of the Discrete Logarithm

We obtain new lower bounds on the linear complexity of several consecutive values of the discrete logarithm modulo a prime p. These bounds generalize and improve several previous results.     

Linear Optimization

Journal of the Operational Research Society -     

Linear Complexity,k-Error Linear Complexity,and the Discrete Fourier Transform

Complexity measures for sequences of elements of a finite field play an important role in cryptology. We focus first on the linear complexity of periodic sequences. By means of the discrete Fourier transform, we determine the number of periodic sequences S with given prime period length N and linear complexity L_N, 0(S)=c as well as the expected value of the linear complexity of N-periodic sequences. Cryptographically strong sequences should not only have a large linear complexity, but also the change of a few terms should not cause a significant decrease of the linear complexity. This requirement leads to the concept of the k-error linear complexity L_N, k(S) of sequences S with period length N. For some k and c we determine the number of periodic sequences S with given period length N and L_N, k(S)=c. For prime N we establish a lower bound on the expected value of the k-error linear complexity.     

Discrete Filled Function Method for Discrete Global Optimization

A discrete filled function method is developed in this paper to solve discrete global optimization problems over strictly pathwise connected domains. Theoretical properties of the proposed discrete filled function are investigated and a solution algorithm is proposed. Numerical experiments reported in this paper on several test problems with up to 200 variables have demonstrated the applicability and efficiency of the proposed method.     

线性离散系统的部分稳定性

In this paper, we study the partial stability of linear discrete systems by means of Liapunov's functions of quadratic form . We obtain a necessary and sufficient condition for the system being stable with respect to part of variables and generalize Liapunov's equation to the partial stability of linear discrete systems . A method of constructing Liapunov's function of quadratic form for the stability of the systems is given.     

Problems of Linear Discrete Games of Pursuit

In this paper, we consider two problems of linear discrete games of pursuit. In each of them, the terms of the sequence defining the pursuer’s control are bounded by some positive number. In the first problem, the terms of the sequence defining the quarry’s control are bounded by some positive number and, in the second problem, the sum of the pth powers of the terms of this sequence is bounded by a given number. For each problem, we obtain a necessary and sufficient condition for the termination of pursuit from all points in space.__________Translated from Matematicheskie Zametki, vol. 77, no. 5, 2005, pp. 707–718.Original Russian Text Copyright ©2005 by G. I. Ibragimov.     

Linear Optimization Queries

Let Γ₀ be a set of n halfspaces in E^d (where the dimension d is fixed) and let m be a parameter, n ≤ m ≤ n^d/2. We show that Γ₀ can be preprocessed in time and space O(m^1+δ) (for any fixed δ > 0) so that given a vector c E^d and another set Γ_q of additional halfspaces, the function c · x can be optimized over the intersection of the halfspaces of Γ₀ Γ_q in time O((n/m^1/d/2 + |Γ_q|)log^4d+3n). The algorithm uses a multidimensional version of Megiddo′s parametric search technique and recent results on halfspace range reporting. Applications include an improved algorithm for computing the extreme points of an n-point set P in E^d, improved output-sensitive computation of convex hulls and Voronoi diagrams, and a Monte-Carlo algorithm for estimating the volume of a convex polyhedron given by the set of its vertices (in a fixed dimension).     

Conjugate Duality and the Control of Linear Discrete Systems

In this paper we deal with the minimization of a convex function over the solution set of a range inclusion problem determined by a multivalued operator with convex graph. We attach a dual problem to it, provide regularity conditions guaranteeing strong duality and derive for the resulting primal–dual pair necessary and sufficient optimality conditions. We also discuss the existence of optimal solutions for the primal and dual problems by using duality arguments. The theoretical results are applied in the context of the control of linear discrete systems.     

Min-Max Optimization of Several Classical Discrete Optimization Problems

In this paper, we study discrete optimization problems with min-max objective functions. This type of problems has direct applications in the recent development of robust optimization. The following well-known classes of problems are discussed: minimum spanning tree problem, resource allocation problem with separable cost functions, and production control problem. Computational complexities of the corresponding min-max version of the above-mentioned problems are analyzed. Pseudopolynomial algorithms for these problems are provided under certain conditions.     

Discrete Optimization and Control in the Market

Multistage discrete dynamical systems are investigated in finite space of state variables. Optimal control of several levels orders in the market is presented. Discrete optimal control model is used for the investigation of several levels orders in the market. Dynamic programming equations are used for the approximation of optimal control.     

Discrete Approximations and Optimization of Evolution Inclusions

The paper studies discrete approximations of nonconvex valued evolution inclusions with the right-hand side satisfying Kamke condition which is more general than the Lipschitz one and more convenient than the variant of the one-sided Lipschitz condition used in Donchev et al. (J Differ Equ 243:301–328, 2007). We extend an interesting previous result of Mordukhovich to a large class of evolution systems appearing in the theory of parabolic partial differential equations. Examples of control systems governed by partial differential equations are provided.     

Approximating Reachable Sets for n-dimensional Linear Discrete Systems

We present a technique for approximating the reachable set fromthe origin for n-dimensional discrete-time linear systems subjectto bounded control, where the state matrix is stable and diagonalizable.The procedure is based on decomposing the system into one- andtwo-dimensional subsystems for which the reachable set of eachof the subsystems can be over-estimated by a polygon. Thesepolygons are then used to create an n-dimensional polyhedronwhich contains the reachable set of the original system     

Uniform Stability for Time-Varying Infinite-Dimensional Discrete Linear Systems

Stability for time-varying discrete linear systems in a Banachspace is investigated. On the one hand is established a fairlycomplete collection of necessary and sufficient conditions foruniform asymptotic equistability for input-free systems. Thisincludes uniform and strong power equistability, and uniformand strong l_p-equistability, among other technical conditionswhich also play an essential role in stability theory. On theother hand, it is shown that uniform asymptotic equistabilityfor input-free systems is equivalent to each of the followingconcepts of uniform stability for forced systems: l_p-input l_p-state,e_o-input e_o-state, bounded-input bounded-state, l_p-input bounded-state(with p>1), e_o-input bounded-state, and convergent-inputbounded-state; these are also equivalent to their nonuniformcounterparts. For time-varying convergent systems, the aboveis also equivalent to convergent-input convergent-state stability.The proofs presented here are all ‘lementary’ inthe sense that they are based essentially only on the Banach–Steinhaustheorem.     

线性空间中的一种S凸映射及其不等式性质

本文讨论了一类定义在线性空间中的新的凸性概念－S凸映射，并给该类凸映射的部分性质。     

Transfer Operators and State Spaces for Discrete Multidimensional Linear Systems

This paper treats multidimensional discrete input-output systems from the constructive point of view. We adapt and improve recursive algorithms, derived earlier by E. Zerz and the second author from standard Gröbner basis algorithms, for the solution of the canonical Cauchy problem for linear systems of partial difference equations with constant coefficients on the lattices N = ^r1 × ^r2. These recursive algorithms, in turn, furnish four other solution methods for the initial value problem, namely by transfer operators, by canonical Kalman global state equations, by parametrizations of controllable systems and, for systems with proper transfer matrix and left bounded input signals, by convolution with the transfer matrix. In the 2D-case N = ² the last method was studied by S. Zampieri. Minimally embedded systems are studied and give rise to especially simple Kalman equations. The latter also imply a useful characterization of the characteristic or polar variety of the system by eigenvalue spectra. For N = ^r we define reachability of a system and prove that controllability implies reachability, but not conversely. Moreover we solve, in full generality, the modelling problem which was introduced and partially solved by F. Pauer and S. Zampieri. Various algorithms have been implemented by the first author in axiom, and examples are demonstrated by means of computer generated pictures. Related work on state space representations has been done by the Padovian and Groningian system theory schools.     

Modeling Discrete Event Systems With Faults Using a Rules-based Modeling Formalism

Obtaining accurate models of systems which are prone to failures and breakdowns is a difficult task. In this paper we present a methodology which makes the task of modeling failure prone discrete event systems (DESs) considerably less cumbersome, less error prone, and more user-friendly. The task of obtaining commonly used automata models for DESs is non-trivial for most practical systems, owing to the fact that the number of states in the commonly used automata models is exponential in the number of signals and faults. In contrast a model of a discrete event system, in the rules based modeling formalism proposed by the co-authors of this paper, is of size polynomial in the number of signals and faults. In order to model failures, we augment the signals set of the rules based formalism to include binary valued fault signals, the values representing either a non-faulty or a faulty state of a certain failure type. Addition of new fault signals requires introduction of new rules for the added fault signal events, and also modification of the existing rules for non-fault events. The rules based modeling formalism is further extended to model real-time systems, and we apply it to model delay-faults of the system as well. The model of a failure prone DES in the rules based can automatically be converted into an equivalent (timed)-automaton model for a failure analysis in the automaton model framework.