Maximum network flows with concave gains

This paper deals with a generalized maximum flow problem with concave gains, which is a nonlinear network optimization problem. Optimality conditions and an algorithm for this problem are presented. The optimality conditions are extended from the corresponding results for the linear gain case. The algorithm is based on the scaled piecewise linear approximation and on the fat path algorithm described by Goldberg, Plotkin and Tardos for linear gain cases. The proposed algorithm solves a problem with piecewise linear concave gains faster than the naive solution by adding parallel arcs. Supported by a Grant-in-Aid for Scientific Research (No. 13780351 and No.14380188) from The Ministry of Education, Culture, Sports, Science and Technology of Japan.     

Suboptimal security solution of a linear-quadratic pursuit-evasion game with mixed noises

The discrete-time, linear-quadratic pursuit-evasion game is considered in this paper. The difference system contains the state-dependent, control-dependent, and additive noises. In addition, each player has additive noises in his own measurement vector, and he is restricted to implement a linear estimator based on his measurements. Each player's philosophy is not to run a risk but to adopt a security control policy. Because of the linear estimation restriction, the security solution is suboptimal, which is found to be the closed-loop controls which are linear in the best estimate of the state. Equations for calculating the state estimation are derived. An algorithm for off-line computing the filter gain is also given.     

Fractional order adaptive high-gain controllers for a class of linear systems

In this paper we show that a fractional adaptive controller based on high gain output feedback can always be found to stabilize any given linear, time-invariant, minimum phase, siso systems of relative degree one. We generalize the stability theorem of integer order controllers to the fractional order case, and we introduce a new tuning parameter for the performance behaviour of the controlled plant. A simulation example is given to illustrate the effectiveness of the proposed algorithm.     

Intelligent control of chaos using linear feedback controller and neural network identifier

A method for controlling chaos when the mathematical model of the system is unknown is presented in this paper. The controller is designed by the pole placement algorithm which provides a linear feedback control method. For calculating the feedback gain, a neural network is used for identification of the system from which the Jacobian of the system in its fixed point can be approximated. The weights of the neural network are adjusted online by the gradient descent algorithm in which the difference between the system output and the network output is considered as the error to be decreased. The method is applied on both discrete-time and continuous-time systems. For continuous-time systems, equivalent discrete-time systems are constructed by using the Poincare map concept. Two discrete-time systems and one continuous-time system are tested as examples for simulation and the results show good functionality of the proposed method. It can be concluded that the chaos in systems with unknown dynamics may be eliminated by the presented intelligent control system based on pole placement and neural network.     

Primal and dual multi-objective linear programming algorithms for linear multiplicative programmes

Multiplicative programming problems (MPPs) are global optimization problems known to be NP-hard. In this paper, we employ algorithms developed to compute the entire set of nondominated points of multi-objective linear programmes (MOLPs) to solve linear MPPs. First, we improve our own objective space cut and bound algorithm for convex MPPs in the special case of linear MPPs by only solving one linear programme in each iteration, instead of two as the previous version indicates. We call this algorithm, which is based on Benson’s outer approximation algorithm for MOLPs, the primal objective space algorithm. Then, based on the dual variant of Benson’s algorithm, we propose a dual objective space algorithm for solving linear MPPs. The dual algorithm also requires solving only one linear programme in each iteration. We prove the correctness of the dual algorithm and use computational experiments comparing our algorithms to a recent global optimization algorithm for linear MPPs from the literature as well as two general global optimization solvers to demonstrate the superiority of the new algorithms in terms of computation time. Thus, we demonstrate that the use of multi-objective optimization techniques can be beneficial to solve difficult single objective global optimization problems.     

A level set algorithm for a class of reverse convex programs

A new algorithm is presented for minimizing a linear function subject to a set of linear inequalities and one additional reverse convex constraint. The algorithm utilizes a conical partition of the convex polytope in conjuction with its facets in order to remain on the level surface of the reverse convex constraint. The algorithm does not need to solve linear programs on a set of cones which converges to a line segment.     

一类含参数的分块对称矩阵的正定性及应用

首先给出一种判断分块对称矩阵正定的方法,提供了确定一组尽可能小的参数,使一类含参数的分块对称矩阵正定的简单算法,然后,将其结果用于研究线性定常大系统的分散镇定性,得到了一类可分散镇定的线性大系统,并给出了相应的分散镇定算法,同文献中提供的方法相比,该算法不仅扩大了所考虑的系统范围,而且不会引起过高的反馈增益,同时还简单易算。     

Implementation and Test of Auction Methods for Solving Generalized Network Flow Problems with Separable Convex Cost

We describe the implementation and testing of two methods, based on the auction approach, for solving the problem of minimizing a separable convex cost subject to generalized network flow conservation constraints. The first method is the -relaxation method of Ref. 1; the second is an extension of the auction sequential/shortest path algorithm for ordinary network flow to generalized network flow. We report test results on a large set of randomly generated problems with varying topology, arc gains, and cost function. Comparison with the commercial code CPLEX on linear/quadratic cost problems and with the public-domain code PPRN on nonlinear cost ordinary network problems are also made. The test results show that the auction sequential/shortest path algorithm is generally fastest for solving quadratic cost problems and mixed linear/nonlinear cost problems with arc gain range near 1. The -relaxation method is generally fastest for solving nonlinear cost ordinary network problems and mixed linear/nonlinear cost problems with arc gain range away from 1. CPLEX is generally fastest for solving linear cost and mixed linear/quadratic cost problems with arc gain range near 1.     

Guaranteed Cost Control of a Markov Jump Linear Uncertain System Using a Time-Multiplied Cost Function

This paper addresses the guaranteed cost control problem of jump linear systems with norm-bounded uncertain parameters. A time-multiplied performance index is considered. The performance is calculated first and an LMI-based algorithm is developed to design a state feedback control law with constant gain matrices which robustly stabilizes the system in the mean-square quadratically stable sense.     

Formulation of linear problems and solution by a universal machine

Using the predicate language for ordered fields a class of problems referred to aslinear problems is defined. This class contains, for example, all systems of linear equations and inequalities, all linear programming problems, all integer programming problems with bounded variables, all linear complementarity problems, the testing of whether sets that are defined by linear inequalities are semilattices, all satisfiability problems in sentenial logic, the rank-computation of matrices, the computation of row-reduced echelon forms of matrices, and all quadratic programming problems with bounded variables. A single, one, algorithm, to which we refer as theUniversal Linear Machine, is described. It solves any instance of any linear problem. The Universal Linear Machine runs in two phases. Given a linear problem, in the first phase a Compiler running on a Turing Machine generates alinear algorithm for the problem. Then, given an instance of the linear problem, in the second phase the linear algorithm solves the particular instance of the linear problem. The linear algorithm is finite, deterministic, loopless and executes only the five ordered field operations — additions, multiplications, subtractions, divisions and comparisons. Conversely, we show that for each linear algorithm there is a linear problem which the linear algorithm solves uniquely. Finally, it is shown that with a linear algorithm for a linear problem, one can solve certain parametric instances of the linear problem.Research was supported in part by the National Science Foundation Grant DMS 92-07409, by the Department of Energy Grant DE-FG03-87-ER-25028, by the United States—Israel Binational Science Foundation Grant 90-00434 and by ONR Grant N00014-92-J1142.Corresponding author.     

不等式约束优化一个新型可行QP-free算法

本文对非线性不等式约束优化问题提出了一个新的可行 QP-free 算法. 新算法保存了现有算法的优点, 并具有以下特性: (1) 算法每次迭代只需求解三个具有相同系数矩阵的线性方程组, 计算量小; (2) 可行下降方向只需通过求解一个线性方程组即可获得, 克服了以往分别求解两个线性方程组获得下降方向和可行方向, 然后再做凸组合的困难;(3) 迭代点均为可行点, 并不要求是严格内点; (4) 算法中采用了试探性线搜索,可以进一步减少计算量; (5) 算法中参数很少,数值试验表明算法具有较好的数值效果和较强的稳定性.     

The out-of-kilter algorithm applied to traffic congestion

The out-of-kilter algorithm finds a minimum cost assignment of flows to a network defined in terms of one-way arcs, each with upper and lower bounds on flow, and a cost. It is a mathematical programming algorithm which exploits the network structure of the data. The objective function, being the sum taken over all the arcs of the products, cost×flow, is linear. The algorithm is applied in a new way to minimise a series of linear functions in a heuristic method to reduce the value of a non-convex quadratic function which is a measure of traffic congestion. The coefficients in these linear functions are chosen in a way which avoids one of the pitfalls occurring when Beale's method is applied to such a quadratic function. The method does not guarantee optimality but has produced optimal results with networks small enough for an integer linear programming method to be feasible.     

Further Improvements in High Gain Observer Design for Systems with Structured Nonlinearities

Due to their simple implementation based on a constant gain matrix, high gain observers are very common in practical applications. We consider systems whose dynamics can be decomposed into a linear and a nonlinear part, where the nonlinear part meets some Lipschitz condition. In many cases there exists a finite bound on the maximum feasible Lipschitz constant for which the error dynamics can be stabilized. Necessary and in some sense sufficient conditions for this maximum Lipschitz constant are given in [1]. These results has been improved in [2,3] by taking the structure of the linear part into account. Having a system with one single nonlinearity, the results given in [2,3] are strict. If multiple nonlinearities occur, even this approach tends to be to conservative. In this case, one could additionally take the internal structure of the nonlinearities into account which leads to a larger set of systems for which convergence of the observer error can be guaranteed. Our new approach is based on an approximation of the structured singular value [4] which yields existence conditions in terms of linear matrix inequalities (LMIs). These LMIs may as well be used for the numerical computation of the observer gain. We demonstrate the advantage of our method on an example. (© 2016 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Minimization of the sum of three linear fractional functions

In this paper, we will propose an efficient and reliable heuristic algorithm for minimizing and maximizing the sum of three linear fractional functions over a polytope. These problems are typical nonconvex minimization problems of practical as well as theoretical importance. This algorithm uses a primal-dual parametric simplex algorithm to solve a subproblem in which the value of one linear function is fixed. A subdivision scheme is employed in the space of this linear function to obtain an approximate optimal solution of the original problem. It turns out that this algorithm is much more efficient and usually generates a better solution than existing algorithms. Also, we will develop a similar algorithm for minimizing the product of three linear fractional functions.     

Nonsmooth nonconvex optimization approach to clusterwise linear regression problems

Clusterwise regression consists of finding a number of regression functions each approximating a subset of the data. In this paper, a new approach for solving the clusterwise linear regression problems is proposed based on a nonsmooth nonconvex formulation. We present an algorithm for minimizing this nonsmooth nonconvex function. This algorithm incrementally divides the whole data set into groups which can be easily approximated by one linear regression function. A special procedure is introduced to generate a good starting point for solving global optimization problems at each iteration of the incremental algorithm. Such an approach allows one to find global or near global solution to the problem when the data sets are sufficiently dense. The algorithm is compared with the multistart Späth algorithm on several publicly available data sets for regression analysis.     

Solving real-world linear ordering problems using a primal-dual interior point cutting plane method

Cutting plane methods require the solution of a sequence of linear programs, where the solution to one provides a warm start to the next. A cutting plane algorithm for solving the linear ordering problem is described. This algorithm uses the primaldual interior point method to solve the linear programming relaxations. A point which is a good warm start for a simplex-based cutting plane algorithm is generally not a good starting point for an interior point method. Techniques used to improve the warm start include attempting to identify cutting planes early and storing an old feasible point, which is used to help recenter when cutting planes are added. Computational results are described for some real-world problems; the algorithm appears to be competitive with a simplex-based cutting plane algorithm.Research partially supported by ONR Grant number N00014-90-J-1714.     

Use of a nonquadratic model in a conjugate-gradient method of optimization with inexact line searches

An algorithm for unconstrained minimization is developed which uses a rational function model, rather than a quadratic, as a basis for conjugate directions. The algorithm is similar to one previously proposed by the authors, but inexact linear searches are investigated in the present paper.     

Links Between Linear Bilevel and Mixed 0–1 Programming Problems

We study links between the linear bilevel and linear mixed 0–1 programming problems. A new reformulation of the linear mixed 0–1 programming problem into a linear bilevel programming one, which does not require the introduction of a large finite constant, is presented. We show that solving a linear mixed 0–1 problem by a classical branch-and-bound algorithm is equivalent in a strong sense to solving its bilevel reformulation by a bilevel branch-and-bound algorithm. The mixed 0–1 algorithm is embedded in the bilevel algorithm through the aforementioned reformulation; i.e., when applied to any mixed 0–1 instance and its bilevel reformulation, they generate sequences of subproblems which are identical via the reformulation.     

A ROBUST SUPERLINEARLY CONVERGENT ALGORITHM FOR LINEARLY CONSTRAINED OPTIMIZATION PROBLEMS UNDER DEGENERACY

1.IntroductionTheproblemconsideredinthispaperiswhereX={xER"laTx5hi,jEI={l,.'.,m}},ajeR"(jEI)areallcolumn*ThisresearchissupportedbytheNationalNaturalSciencesFoundationofChinaandNaturalSciencesFoundationofHunanProvince.vectors,hiERI(j6I)areallscalars,andf:R"-- Risacontinuouslydifferentiablefunction.Weonlyconsiderinequalityconstraintsheresinceanyequalitycanbeexpressedastwoinequalities.Withoutassumingregularityofthelinearconstraints,thereisnotanydifficultyinextendingtheresultstothegenera…     

Parameter-dependent H∞ filter design for LPV systems and an autopilot application

This paper considers the design problem of parameter dependent H_∞ filters for linear parameter varying (LPV) systems whose parameters are measurable. Conditions for existence of parameter-dependent Lyapunov function are proposed via parametrical linear matrix inequality (LMI) constraints. Based on the solutions to the LMIs, an algorithm for the gain matrices of LPV filter is presented. The design method is applied to a missile system to demonstrate the effectiveness.