非线性特征值问题的二次近似方法

本文研究求解非线性特征值问题的数值方法.基于矩阵值函数的二次近似,将非线性特征值问题转化为二次特征值问题,提出了求解非线性特征值问题的逐次二次近似方法,分析了该方法的收敛性.结合求解二次特征值问题的Arnoldi方法和Jacobi-Davidson方法,给出求解非线性特征值问题的一些二次近似方法.数值结果表明本文所给算法是有效的.     

Differential sensitivity of solutions of convex constrained optimal control problems for discrete systems

A family of optimal control problems for discrete systems that depend on a real parameter is considered. The problems are strongly convex and subject to state and control constraints. Some regularity conditions are imposed on the constraints.The control problems are reformulated as mathematical programming problems. It is shown that both the primal and dual optimal variables for these problems are right-differentiable functions of a parameter. The right-derivatives are characterized as solutions to auxiliary quadratic control problems. Conditions of continuous differentiability are discussed, and some estimates of the rate of convergence of the difference quotients to the respective derivatives are given.     

Quasi-Newton Methods for Nonlinear Least Squares Focusing on Curvatures

A new quasi-Newton method for nonlinear least squares problems is proposed. Two advantages of the method are accomplished by utilizing special geometrical properties in the problem class. First, fast convergence is established for well-conditioned problems by interpolating both the current and the previous step in each iteration. Second, high accuracy is achieved for certain difficult problems, such as ill-conditioned problems and problems with large curvatures in the tangent space. Numerical results for artificial problems and standard test problems are presented and discussed.     

The solution existence of general variational inclusion problems

We propose general variational inclusion problems which are slightly different from corresponding problems considered in several recent papers in the literature and show that they are advantageous. Sufficient conditions for the solution existence are established. As applications we derive consequences for several special cases of variational inclusion problems, quasioptimization problems, equilibrium problems and implicit variational inequalities and show that they improve the results of some recent existing papers.     

Necessary optimality conditions for Stackelberg problems

First-order necessary optimality conditions are derived for a class of two-level Stackelberg problems in which the followers' lower-level problems are convex programs with unique solutions. To this purpose, generalized Jacobians of the marginal maps corresponding to followers' problems are estimated. As illustrative examples, two discretized optimum design problems with elliptic variational inequalities are investigated. The theoretical results may be used also for the numerical solution of the Stackelberg problems considered by nondifferentiable optimization methods.Communicated by M. Simaan     

A range-space implementation for large quadratic programs with small active sets

Large and sparse convex quadratic programming problems are often generated in the course of solving large-scale optimization problems. An important class of these problems has the property that only a small number of constraints are at their bounds at a solution. We describe an implementation of a range-space method designed for efficient solution of these small-active-set problems. The implementation is oriented toward the application area of multidimensional data fitting subject to constraints. Test results are presented for several data-fitting problems.The authors are indebted to the referees for several valuable contributions     

Towards global bilevel dynamic optimization

The global solution of bilevel dynamic optimization problems is discussed. An overview of a deterministic algorithm for bilevel programs with nonconvex functions participating is given, followed by a summary of deterministic algorithms for the global solution of optimization problems with nonlinear ordinary differential equations embedded. Improved formulations for scenario-integrated optimization are proposed as bilevel dynamic optimization problems. Solution procedures for some of the problems are given, while for others open challenges are discussed. Illustrative examples are given.     

凸二次规划问题逆问题的模型与解法

本文分别考虑带非负约束和不带大量负约束凸二次规划问题逆问题。首先得到各个逆问题的数学模型,然后对不同的模型给出不同的求解方法。     

半无限规划问题的一个有效解法

1．引言在计算机辅助设计和工程设计中,经常遇到下面的两类优化问题1,2］．1．无约束半无限极大极小问题．其中外x）二——x。。Im。x。。。Yi夕（x;N）这里J二（】,2,·,｝对任何7E八岁：R－xR”。＋R是连续可微的函数,X是R”。中的一个紧子集,且VYj）一O,这里问h）表示X体积．2．约束半无限代化问题．其中I一（1,2,·．小记L二《0｝UI对任何jCL冲’（x）一max。。。Yi夕（x,yi）·这里拉：PX＊n＋R是连续可微函数,X是”。中的一个紧子集,且NU）一0·注．设Y（Z,一二切EyW一叫卜4．今后对本文用到的紧子集地做…     

一类混合似变分不等式问题解的存在唯一性

本文中,我们首先给出了一类混合似变分不等式问题．接着,在Banach空间中研究了它的解的存在性和唯一性．最后,讨论了混合似变分不等式问题的扰动问题,并证明了扰动问题的解的存在唯一性定理．     

Helly’s Principle and Its Application to an Infinite-Horizon Optimal Control Problem

In this paper, a numerical method is presented to solve singularly-perturbed two-point boundary-value problems for second-order ordinary differential equations with a discontinuous source term. First, an asymptotic expansion approximation of the solution of the boundary-value problem is constructed using the basic ideas of the well-known WKB perturbation method. Then, some initial-value problems and terminal-value problems are constructed such that their solutions are the terms of this asymptotic expansion. These initial-value problems and terminal-value problems are singularly-perturbed problems and therefore fitted mesh method (Shishkin mesh) are used to solve these problems. Necessary error estimates are derived and examples are provided to illustrate the method.     

Sensitivity analysis for multivalued quasiequilibrium problems in metric spaces: Hölder continuity of solutions

Hölder continuity and uniqueness of the solutions of general multivalued vector quasiequilibrium problems in metric spaces are established. The results are shown to be extensions of recent ones for equilibrium problems with some improvements. Applications in quasivariational inequalities, vector quasioptimization and traffic network problems are provided as examples for others in various optimization—related problems.     

Global and Local Search Algorithms for Concave Cost Transshipment Problems

Traditionally, the minimum cost transshipment problems have been simplified as linear cost problems, which are not practical in real applications. Recently, some advanced local search algorithms have been developed that can directly solve concave cost bipartite network problems. However, they are not applicable to general transshipment problems. Moreover, the effectiveness of these modified local search algorithms for solving general concave cost transshipment problems is doubtful. In this research, we propose a global search algorithm for solving concave cost transshipment problems. Effecient methods for encoding, generating initial populations, selection, crossover and mutation are proposed, according to the problem characteristics. To evaluate the effectiveness of the proposed global search algorithm, four advanced local search algorithms based on the threshold accepting algorithm, the great deluge algorithm, and the tabu search algorithm, are also developed and are used for comparison purpose. To assist with the comparison of the proposed algorithms, a randomized network generator is designed to produce test problems. All the tests are performed on a personal computer. The results indicate that the proposed global search algorithm is more effective than the four advanced local algorithms, for solving concave cost transshipment problems.     

Estimates for Solutions to Model Problems Connected with Quasistationary Approximation for the Stefan Problem

Model problems for elliptic equations are considered. The time-derivative of a solution can be contained in the boundary condition or in the conjugation condition. Suich problems appear, for example, in the study of free boundary problems for elliptic equations that can be considered as quasistationary approximations to free boundary problems for parabolic equations. Estimates for solutions to the model problems are obtained. Bibliography: 11 titles.     

Optimal Path Planning Based on Visibility

Various problems associated with optimal path planning for mobile observers such as mobile robots equipped with cameras to obtain maximum visual coverage of a surface in the three-dimensional Euclidean space are considered. The existence of solutions to these problems is discussed first. Then, optimality conditions are derived by considering local path perturbations. Numerical algorithms for solving the corresponding approximate problems are proposed. Detailed solutions to the optimal path planning problems for a few examples are given.     

Linear programming in tector criterion markov and semi-Markov decision processes

Optimality problems in infinite horizon, discrete time, vector criterion Markov and semi-Markov decision processes are expressed as standard problems of multiobjective linear programming. Processes with discounting, absorbing processes and completely ergodie processes without discounting are investigated. The common properties and special structure of derived multiobjective linear programming problems are overviewed. Computational simplicities associated with these problems in comparison with general multiobjective linear programming problems are discussed. Methods for solving these problems are overviewed and simple numerical examples are given.     

On certain optimization methods with finite-step inner algorithms for convex finite-dimensional problems with inequality constraints

Numerical methods are proposed for solving finite-dimensional convex problems with inequality constraints satisfying the Slater condition. A method based on solving the dual to the original regularized problem is proposed and justified for problems having a strictly uniformly convex sum of the objective function and the constraint functions. Conditions for the convergence of this method are derived, and convergence rate estimates are obtained for convergence with respect to the functional, convergence with respect to the argument to the set of optimizers, and convergence to the g-normal solution. For more general convex finite-dimensional minimization problems with inequality constraints, two methods with finite-step inner algorithms are proposed. The methods are based on the projected gradient and conditional gradient algorithms. The paper is focused on finite-dimensional problems obtained by approximating infinite-dimensional problems, in particular, optimal control problems for systems with lumped or distributed parameters.     

Isomorphic scheduling problems

We consider general properties of isomorphic scheduling problems that constitute a new class of pairs of mutually related scheduling problems. Any such a pair is composed of a scheduling problem with fixed job processing times and its time-dependent counterpart with processing times that are proportional-linear functions of the job starting times. In order to introduce the class formally, first we formulate a generic scheduling problem with fixed job processing times and define isomorphic problems by a one-to-one transformation of instances of the generic problem into instances of time-dependent scheduling problems with proportional-linear job processing times. Next, we prove basic properties of isomorphic scheduling problems and show how to convert polynomial algorithms for scheduling problems with fixed job processing times into polynomial algorithms for proportional-linear counterparts of the original problems. Finally, we show how are related approximation algorithms for isomorphic problems. Applying the results, we establish new worst-case results for time-dependent parallel-machine scheduling problems and prove that many single- and dedicated-machine time-dependent scheduling problems with proportional-linear job processing times are polynomially solvable.     

Optimality conditions and newton-type methods for mathematical programs with vanishing constraints

A new class of optimization problems is discussed in which some constraints must hold in certain regions of the corresponding space rather than everywhere. In particular, the optimal design of topologies for mechanical structures can be reduced to problems of this kind. Problems in this class are difficult to analyze and solve numerically because their constraints are usually irregular. Some known first- and second-order necessary conditions for local optimality are refined for problems with vanishing constraints, and special Newton-type methods are developed for solving such problems.     

Unified solutions to some classical problems in rarefied gas dynamics based on the one-dimensional linearized S-model equations

An analytical version of the discrete-ordinates method is used to derive solutions for a class of problems defined in terms of the S-model kinetic equations. In addition to a general derivation, which is common to all the problems, specific analytical and computational aspects for each one of the problems are presented. In particular, numerical results for velocity profile, heat-flow profile and flow rates are obtained with high accuracy for the plane channel problems. In the case of half-space problems, the thermal and viscous-slip coefficients are also listed. Received: September 20, 2004; revised: March 31, 2005