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.     

THE NECESSARY AND SUFFICIENT CONDITIONS FOR THE SOLVABILITY OF A CLASS OF THE MATRIX INVERSE PROBLEM

Censider the solutions of the matrix inverse problem, which are symmetric positive semide finite on a subspace. Necessary and sufficient conditions for the solvability, as well as the general solution are obtained. The best approximate solution by the above solution set is given. Thus the open problem in [1] is solved.     

On differential equations with interval coefficients

In this study, a new approach is developed to solve the initial value problem for interval linear differential equations. In the considered problem, the coefficients and the initial values are constant intervals. In the developed approach, there is no need to define a derivative for interval-valued functions. All derivatives used in the approach are classical derivatives of real functions. The reason for this is that the solution of the problem is defined as a bunch of real functions. Such a solution concept is compatible also with the robust stability concept. Sufficient conditions are provided for the solution to be expressed analytically. In addition, on a numerical example, the solution obtained by the proposed approach is compared with the solution obtained by the generalized Hukuhara differentiability. It is shown that the proposed approach gives a new type of solution. The main advantage of the proposed approach is that the solution to the considered interval initial value problem exists and is unique, as in the real case.     

拓扑向量空间中非光滑向量极值问题的最优性条件与对偶

本文提出了向量值函数的锥D-s凸，锥D-s拟凸，s右导数及锥D-s伪凸等新概念，探讨了锥D-s凸函数的有关性质，建立了带约束非光滑向量极值问题(VP)的最优性必要条件与涉及锥D-s凸(拟凸，伪凸)函数的约束极值问题(VP)的最优性充分条件，给出了原问题(VP)与其Mond-Weir型对偶问题的弱对偶与强对偶结论，揭示了(VP)的局部锥D-(弱)有效解与整体锥D-(弱)有效解，(VP)的锥D-弱有效解与锥D-有效解的关系，所得结果拓广了凸规划及部分广义凸规划的有关结论．     

On the use of Kronecker's algorithm in the generalized rational interpolation problem

Kronecker's algorithm can be used to solve the generalized rational interpolation problem. In order to present the algorithm, rational forms are used here instead of too restrictive rational fractions. The proposed algorithm is reliable as soon as the functionals that characterize the problem satisfy two precise conditions. These conditions are fulfilled in the modified Hermite rational interpolation problem and, as a consequence, in the special case of the Cauchy problem and of the Padé approximation problem. This reliability covers two properties: on one hand, every rational form resulting from the algorithm is a solution of the problem whereas, on the other hand, every solution of the problem is found by the algorithm (with the exception of a possible reduction of the rational form). However, if the algorithm yields a non-reduced rational form, then the corresponding rational fraction is not a solution of the problem.     

由三个特征对构造正定Jacobi矩阵

本文研究了由三个特征对构造正定Jacobi矩阵的问题,给出了这个问题有唯一解的充要条件及解的表达式,并给出了问题的数值算法.     

Real-Time Solution of Bi-Level Optimal Control Problems

Bi-level optimal control problems are presented as an extension to classical optimal control problems. Hereby, additional constraints for the primary problem are considered, which depend on the optimal solution of a secondary optimal control problem. A demanding problem is the numerical complexity, since at any point in time the solution of the optimal control problem as well as a complete solution of the secondary problem have to be determined. Hence we deal with two dependent variables in time. The numerical solution of the bi-level problem is illustrated by an application of a container crane. Jerk and energy optimal trajectories with free final time are calculated under the terminal condition that the crane system comes to be at rest at a predefined location. In enlargement additional constraints are investigated to ensure that the crane system can be brought to a rest position by a safety stop at a free but admissible location in minimal time from any state of the trajectory. (© 2005 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Solving the CLSP by a Tabu Search Heuristic

The multi-item, single-level, capacitated, dynamic lot-sizing problem, commonly abbreviated as CLSP, is considered. The problem is cast in a tight mixed-integer programming model (MIP); tight in the sense that the gap between the optimal value of MIP and that of its linear programming relaxation (LP) is small. The LP relaxation of MIP is then solved by column generation. The resulting feasible solution is further improved by adopting the corresponding set-up schedule and re-optimizing variable costs by solving a minimum-cost network flow (trans-shipment) problem. Subsequently, the improved solution is used as a starting solution for a tabu search procedure, with the worth of moves assessed using the same trans-shipment problem. Results of computational testing of benchmark problem instances are presented. They show that the heuristic solutions obtained are effective, in that they are extremely close to the best known solutions. The computational efficiency makes it possible to solve realistically large problem instances routinely on a personal computer; in particular, the solution procedure is most effective, in terms of solution quality, for larger problem instances.     

Characterizations of optimal solution sets of convex infinite programs

In this paper, several Lagrange multiplier characterizations of the solution set of a convex infinite programming problem are given. Characterizations of solution sets of cone-constrained convex programs are derived as well. The procedure is then adopted to a semi-convex problem with convex constraints. For this problem, we present firstly a necessary and sufficient condition for optimality and secondly a characterization of its optimal solution set, based on a Lagrange multiplier associated with a given solution and on directional derivatives of the objective function.      

Nonclassical pseudospectral method for the solution of brachistochrone problem

In this paper, nonclassical pseudospectral method is proposed for solving the classic brachistochrone problem. The brachistochrone problem is first formulated as a nonlinear optimal control problem. Properties of nonclassical pseudospectral method are presented, these properties are then utilized to reduce the computation of brachistochrone problem to the solution of algebraic equations. Using this method, the solution to the brachistochrone problem is compared with those in the literature.     

Study on a Cross Diffusion Parabolic System

This paper considers a kind of strongly coupled cross diffusion parabolic system,which can be usedas the multi-dimensional Lyumkis energy transport model in semiconductor science.The global existence andlarge time behavior are obtained for smooth solution to the initial boundary value problem.When the initialdata are a small perturbation of an isothermal stationary solution,the smooth solution of the problem under theinsulating boundary condition,converges to that stationary solution exponentially fast as time goes to infinity.     

Inverse problems of reconstructing parameters of the Navier-Stokes system

An inverse problem of reconstructing parameters not known a priori of the dynamical system described by the boundary-value problem for the Navier-Stokes system is considered. The reconstruction is based on one piece of admissible information or another about the motion of the dynamical system (solution of the corresponding boundary-value problem). In particular, one of the problems considered is the inverse problem consisting of reconstruction of the a priori unknown right-hand side of the Navier-Stokes system. The right-hand side characterizes the density of exterior mass forces acting on the system. This problem, as well as many other similar problems, is ill-posed. Two methods are proposed for its solution: the statistical method and the dynamical method. These methods use different initial information. In solving the problem by using the statistical method, initial information for the solution is the results of approximate measurement (in one sense or another) of the motion of the dynamical system on a given interval of time. Here, the reconstruction is performed after the corresponding interval of time. For solution of the problem by this method, the concepts and constructions of open-loop control theory are used. In solving the problem by using the dynamical method, initial information for its solution is the results of approximate (in one sense or another) measurements of the current states of the system, which are dynamically obtained by the observer. Here, the reconstruction is dynamically performed during the process. For solution of the problem by the dynamical method, the concepts and constructions of the dynamical regularization method based on positional control theory are used. Also, the author considers various modifications and regularizations of the methods for solution of problems proposed that are based on one piece of a priori information or another about the desired solution and solvability conditions of the problem. __________ Translated from Sovremennaya Matematika i Ee Prilozheniya (Contemporary Mathematics and Its Applications), Vol. 26, Nonlinear Dynamics, 2005.     

Aggregation bounds in stochastic linear programming

Stochastic linear programs become extremely large and complex as additional uncertainties and possible future outcomes are included in their formulation. Row and column aggregation can significantly reduce this complexity, but the solutions of the aggregated problem only provide an approximation of the true solution. In this paper, error bounds on the value of the optimal solution of the original problem are obtained from the solution of the aggregated problem. These bounds apply for aggregation of both random variables and time periods.     

Differential and Difference Boundary Value Problem for Loaded Third-Order Pseudo-Parabolic Differential Equations and Difference Methods for Their Numerical Solution

Boundary value problems for loaded third-order pseudo-parabolic equations with variable coefficients are considered. A priori estimates for the solutions of the problems in the differential and difference formulations are obtained. These a priori estimates imply the uniqueness and stability of the solution with respect to the initial data and the right-hand side on a layer, as well as the convergence of the solution of each difference problem to the solution of the corresponding differential problem.     

拟线性对称双曲型方程组的某些整体解及其渐近性质

<正> 1.引言 近年来,人们采用了不定常气流方程来计算定常的跨音速气流,取得了一定的成效.在这种计算中,混合型方程组的解被看成为多一个自变量的双曲型方程组解的极限.这启发我们去研究系数和t无关的双曲型方程组的解当t趋向无限时的渐近行为.在本文中,我们利用[2]中的结果,先考虑拟线性对称双曲型方程组,以方程组的充分正为代价,对初始条件作了某些限制以后,证明了这种方程组的混合问题的整体解的存在性.然     

A bifurcation phenomenon in a singularly perturbed two-phase free boundary problem of phase transition

In this paper, we prove a bifurcation phenomenon in a two-phase, singularly perturbed, free boundary problem of phase transition. We show that the uniqueness of the solution for the two-phase problem breaks down as the boundary data decreases through a threshold value. For boundary values below the threshold, there are at least three solutions, namely, the harmonic solution which is treated as a trivial solution in the absence of a free boundary, a nontrivial minimizer of the functional under consideration, and a third solution of the mountain-pass type. We classify these solutions according to the stability through evolution. The evolution with initial data near a stable solution, such as the trivial harmonic solution or a minimizer of the functional, converges to the stable solution. On the other hand, the evolution deviates away from a non-minimal solution of the free boundary problem.     

Bounds for the solution set of linear complementarity problems

We give here bounds for the feasible domain and the solution norm of Linear Complementarity Problems (LCP). These bounds are motivated by formulating the LCP as a global quadratic optimization problem and are characterized by the eigenstructure of the corresponding matrix. We prove boundedness of the feasible domain when the quadratic problem is concave, and give easily computable bounds for the solution norm for the convex case. We also obtain lower and upper bounds for the solution norm of the general nonconvex problem.     

Test-assignment: a quadratic coloring problem

We consider the problem of assigning the test variants of a written exam to the desks of a classroom in such a way that desks that are close-by receive different variants. The problem is a generalization of the Vertex Coloring and we model it as a binary quadratic problem. Exact solution methods based on reformulating the problem in a convex way and applying a general-purpose solver are discussed as well as a Tabu Search algorithm. The methods are extensively evaluated through computational experiments on real-world instances. The problem arises from a real need at the Faculty of Engineering of the University of Bologna where the solution method is now implemented.     

A fuzzy preference relation in the vector maximum problem

A new approach to the compromise solution concept for the vector maximum problem is considered. It is assumed in this approach that one may specify a fuzzy preference relation in the alternative space reflecting the objective functions and the decision maker's preferences. The maximal nondominated alternative for this relation is proposed as a compromise solution to the initial problem. Properties of the compromise solution are analysed under different assumptions concerning the initial problem as well as the accepted fuzzy preference relation.     

Analysis of Properties of the Solutions to Parametric Time-Optimal Problems

We consider a linear time-optimal problem in which initial state values depend on a parameter and study the problem of the solution structure identification for small parameter perturbations. Properties of the time-optimal function and a point-set mapping, defined by optimal Lagrange vectors, are studied as well as the dependence of the solution on the parameter. Special attention is paid to the solution properties in irregular points.