A Note on the Calculation of Step-Lengths in Interior-Point Methods for Semidefinite Programming

In each iteration of an interior-point method for semidefinite programming, the maximum step-length that can be taken by the iterate while maintaining the positive semidefiniteness constraint needs to be estimated. In this note, we show how the maximum step-length can be estimated via the Lanczos iteration, a standard iterative method for estimating the extremal eigenvalues of a matrix. We also give a posteriori error bounds for the estimate. Numerical results on the performance of the proposed method against two commonly used methods for calculating step-lengths (backtracking via Cholesky factorizations and exact eigenvalues computations) are included.     

New Sequential Quadratically-Constrained Quadratic Programming Method of Feasible Directions and Its Convergence Rate

This paper discusses optimization problems with nonlinear inequality constraints and presents a new sequential quadratically-constrained quadratic programming (NSQCQP) method of feasible directions for solving such problems. At each iteration. the NSQCQP method solves only one subproblem which consists of a convex quadratic objective function, convex quadratic equality constraints, as well as a perturbation variable and yields a feasible direction of descent (improved direction). The following results on the NSQCQP are obtained: the subproblem solved at each iteration is feasible and solvable: the NSQCQP is globally convergent under the Mangasarian-Fromovitz constraint qualification (MFCQ); the improved direction can avoid the Maratos effect without the assumption of strict complementarity; the NSQCQP is superlinearly and quasiquadratically convergent under some weak assumptions without thestrict complementarity assumption and the linear independence constraint qualification (LICQ). Research supported by the National Natural Science Foundation of China Project 10261001 and Guangxi Science Foundation Projects 0236001 and 0249003. The author thanks two anonymous referees for valuable comments and suggestions on the original version of this paper.     

On modified block SSOR iteration methods for linear systems from steady incompressible viscous flow problems

In order to solve the large sparse systems of linear equations arising from numerical solutions of two-dimensional steady incompressible viscous flow problems in primitive variable formulation, we present block SSOR and modified block SSOR iteration methods based on the special structures of the coefficient matrices. In each step of the block SSOR iteration, we employ the block LU factorization to solve the sub-systems of linear equations. We show that the block LU factorization is existent and stable when the coefficient matrices are block diagonally dominant of type-II by columns. Under suitable conditions, we establish convergence theorems for both block SSOR and modified block SSOR iteration methods. In addition, the block SSOR iteration and AF-ADI method are considered as preconditioners for the nonsymmetric systems of linear equations. Numerical experiments show that both block SSOR and modified block SSOR iterations are feasible iterative solvers and they are also effective for preconditioning Krylov subspace methods such as GMRES and BiCGSTAB when used to solve this class of systems of linear equations.     

Implicit representation of generalized variable upper bounds in linear programming

In certain linear programs, especially those derived from integer programs, large numbers of constraints may have very simple form. Examples are:x _ij 1 (simple upper bounds [SUB]), _i x _ij = 1 (generalized upper bounds [GUB]) andx _ij y _i (variable upper bounds [VUB]). A class of constraints called generalized VUB [GVUB] is introduced which includes GUB and VUB as special cases. Also introduced is a method for representing GVUB constraints implicitly within the mechanics of the simplex method.Research supported in part by the Mobil Oil Corporation.     

Using Constraint-Based Operators to Solve the Vehicle Routing Problem with Time Windows

This paper presents operators searching large neighborhoods in order to solve the vehicle routing problem. They make use of the pruning and propagation techniques of constraint programming which allow an efficient search of such neighborhoods. The advantages of using a large neighborhood are not only the increased probability of finding a better solution at each iteration but also the reduction of the need to invoke specially-designed methods to avoid local minima. These operators are combined in a variable neighborhood descent in order to take advantage of the different neighborhood structures they generate.     

Reduced Functions, Gradients and Hessians from Fixed-Point Iterations for State Equations

In design optimization and parameter identification, the objective, or response function(s) are typically linked to the actually independent variables through equality constraints, which we will refer to as state equations. Our key assumption is that it is impossible to form and factor the corresponding constraint Jacobian, but one has instead some fixed-point algorithm for computing a feasible state, given any reasonable value of the independent variables. Assuming that this iteration is eventually contractive, we will show how reduced gradients (Jacobians) and Hessians (in other words, the total derivatives) of the response(s) with respect to the independent variables can be obtained via algorithmic, or automatic, differentiation (AD). In our approach the actual application of the so-called reverse, or adjoint differentiation mode is kept local to each iteration step. Consequently, the memory requirement is typically not unduly enlarged. The resulting approximating Lagrange multipliers are used to compute estimates of the reduced function values that can be shown to converge twice as fast as the underlying state space iteration. By a combination with the forward mode of AD, one can also obtain extra-accurate directional derivatives of the reduced functions as well as feasible state space directions and the corresponding reduced or projected Hessians of the Lagrangian. Our approach is verified by test calculations on an aircraft wing with two responses, namely, the lift and drag coefficient, and two variables, namely, the angle of attack and the Mach number. The state is a 2-dimensional flow field defined as solution of the discretized Euler equation under transonic conditions.     

求解Nash均衡子问题的一个算法

n人有限博弈的混合策略组合（p1^*,…,pn^*)为Nash均衡,如果其中每一策略pi^*都是参与人i(i=1,2,…,n),对其它n-1个参与人策略组合（p1^*,…,pi 1^*,pi-1^*,…,pn^*)的最优反应,即存在n个概率向量p1^*,…,pn^*使得对i=1,2,…,n及任意k1维概率向量pi恒有vi(p1^*,…,pn^*…)小于vi(pi^*,…,pi-1^*,pi 1^*,…pn^*),其中vi为参与人i的支付函数,pi=(pil,…,piki)）为ki维概率向量,即满足条件,pij大于等于0,∑kij=1pij=1,ki是参与人i的策略空间中策略个数,i=1,2,…,n,由此,Nash均衡的求解可化为下列优化问题：求n个概率向量pi^*,…,pn^8,使得对i=1,2,…,n及任意ki维的概率向量pi满足maxxvi(P1^*,…,pi-1^*,pi,Pi 1^*,…,pn^*)=vi(P1^*,,…,Pn^*)。     

On the Integrability of a Generalized Variable‐Coefficient Forced Korteweg‐de Vries Equation in Fluids

With the inhomogeneities of media taken into account, under investigation is hereby a generalized variable‐coefficient forced Korteweg‐de Vries (vc‐fKdV) equation, which describes shallow‐water waves, internal gravity waves, etc. Under an integrable constraint condition on the variable coefficients, in this paper, the complete integrability of the generalized vc‐fKdV equation is proposed. By virtue of a generalization of Bells polynomials, we systematically present its bilinear representations, Bäcklund transformations, Lax pairs and Darboux covariant Lax pairs, which can be reduced to the ones of some integrable models, such as vcKdV model, cylindrical KdV equation, and an analytical model of tsunami generation. It is very interesting that its bilinear formulism is free for the integrable constraint condition. Besides, researching the Lax equations yield its infinitely conservation laws, all conserved densities and fluxes of them are obtained by explicit recursion formulas. Furthermore, by considering its bilinear formulism with an extra auxiliary variable, we present the soliton solutions and Riemann theta function periodic wave solutions of the equation. According to the constraint among the nonlinear, dispersive, and line‐damping coefficients, we further discuss the solitonic structures and interaction properties by some graphic analysis. Finally, the relationships between the periodic wave solutions and soliton solutions are presented in detail by a limiting procedure.     

A Schwarz domain decomposition method with gradient projection for optimal control governed by elliptic partial differential equations

A domain decomposition method (DDM) is presented to solve the distributed optimal control problem. The optimal control problem essentially couples an elliptic partial differential equation with respect to the state variable and a variational inequality with respect to the constrained control variable. The proposed algorithm, called SA-GP algorithm, consists of two iterative stages. In the inner loops, the Schwarz alternating method (SA) is applied to solve the state and co-state variables, and in the outer loops the gradient projection algorithm (GP) is adopted to obtain the control variable. Convergence of iterations depends on both the outer and the inner loops, which are coupled and affected by each other. In the classical iteration algorithms, a given tolerance would be reached after sufficiently many iteration steps, but more iterations lead to huge computational cost. For solving constrained optimal control problems, most of the computational cost is used to solve PDEs. In this paper, a proposed iterative number independent of the tolerance is used in the inner loops so as to save a lot of computational cost. The convergence rate of L²-error of control variable is derived. Also the analysis on how to choose the proposed iteration number in the inner loops is given. Some numerical experiments are performed to verify the theoretical results.     

Copulas with maximum entropy

We shall find a multi-dimensional checkerboard copula of maximum entropy that matches an observed set of grade correlation coefficients. This problem is formulated as the maximization of a concave function on a convex polytope. Under mild constraint qualifications we show that a unique solution exists in the core of the feasible region. The theory of Fenchel duality is used to reformulate the problem as an unconstrained minimization which is well solved numerically using a Newton iteration. Finally, we discuss the numerical calculations for some hypothetical examples and describe how this work can be applied to the modelling and simulation of monthly rainfall.     

Strong convergence of LAD estimates in a censored regression model

A regression model with a nonnegativity constraint on the dependent variable, known as censored median regression model, is considered. Under some mild conditions, the LAD estimate of the regression coefficient is shown to be strongly consistent. Furthermore, its convergence rate and Bahadur strong representation are also obtained.     

Reflected forward–backward stochastic differential equations with continuous monotone coefficients

In this work, we prove that there exists at least one solution for the reflected forward–backward stochastic differential equations satisfying the obstacle constraint with continuous monotone coefficients. The distinct character of our result is that the coefficient of the forward SDEs contains the solution variable of the reflected BSDEs.     

接触问题中的快速凝缩消元法

用分离解法求解弹性接触问题时，在增量加载和迭代过程中，由于接触区某些节点的状态发生改变而导致方程组的系数矩阵某些行和列元素随之变化。根据此特点，本推导了一种新的自适应迭代算法-快速凝缩消元法，并给出具体的迭代步骤，避免了系数矩阵变化时必须重新形成矩阵的重复计算。     

Geometrical nonlinear analysis based on optimization technique

In this paper, two triangular shapes are used to formulate iteration procedures required for nonlinear analysis. These triangles are formed by the structural load–displacement curve. The areas of these shapes are considered as two variables objective functions. To find the optimal solutions, these functions are minimized with respect to each variable. As a result, two new constraint equations are obtained, which can be utilized as the nonlinear solver. To demonstrate the merit of authors’ scheme, some geometric nonlinear analyses of shells, frames and trusses are performed. Furthermore, present formulations are compared with the cylindrical arc-length method.     

A gradient descent method for solving an inverse coefficient heat conduction problem

An iterative gradient descent method is applied to solve an inverse coefficient heat conduction problem with overdetermined boundary conditions. Theoretical estimates are derived showing how the target functional varies with varying the coefficient. These estimates are used to construct an approximation for a target functional gradient. In numerical experiments, iteration convergence rates are compared for different descent parameters.     

具有带状系数矩阵的无限维线性规划的解法

研究一类每个约束条件有两个变量且每个变量出现在两个约束条件中的无限维线性规划.引入松弛变量后,得到约束方程组的系数矩阵为无限阶带状矩阵,用它的左逆以及属于零的特征向量可以表示这类问题的最优解.获得目标函数值收敛的一个充分条件.     

基于Gristensen算法的砂岩储层横波速度计算方法

由于横波测量成本高,大部分油田测井资料中仅有少部分横波数据,则依据常规测井资料准确构建横波曲线已成为关键.考虑到横波构建理论方法更多地依赖实验室分析资料,提出在Gristensen经验公式基础上,以研究区横波测量曲线为约束,通过优化反演确立公式系数是一种好的研究思路.优化方法实现中采用阻尼型高斯牛顿法,保障了多参数优化迭代的收敛性和精度.将研究方法用于卫星油田横波数据构建中,取得好的计算结果.     

Constraint satisfaction problems: Algorithms and applications

A constraint satisfaction problem (CSP) requires a value, selected from a given finite domain, to be assigned to each variable in the problem, so that all constraints relating the variables are satisfied. Many combinatorial problems in operational research, such as scheduling and timetabling, can be formulated as CSPs. Researchers in artificial intelligence (AI) usually adopt a constraint satisfaction approach as their preferred method when tackling such problems. However, constraint satisfaction approaches are not widely known amongst operational researchers. The aim of this paper is to introduce constraint satisfaction to the operational researcher. We start by defining CSPs, and describing the basic techniques for solving them. We then show how various combinatorial optimization problems are solved using a constraint satisfaction approach. Based on computational experience in the literature, constraint satisfaction approaches are compared with well-known operational research (OR) techniques such as integer programming, branch and bound, and simulated annealing.     

A tearing-based hybrid parallel sparse linear system solver

We propose a hybrid sparse system solver for handling linear systems using algebraic domain decomposition-based techniques. The solver consists of several stages. The first stage uses a reordering scheme that brings as many of the largest matrix elements as possible closest to the main diagonal. This is followed by partitioning the coefficient matrix into a set of overlapped diagonal blocks that contain most of the largest elements of the coefficient matrix. The only constraint here is to minimize the size of each overlap. Separating these blocks into independent linear systems with the constraint of matching the solution parts of neighboring blocks that correspond to the overlaps, we obtain a balance system. This balance system is not formed explicitly and has a size that is much smaller than the original system. Our novel solver requires only a one-time factorization of each diagonal block, and in each outer iteration, obtaining only the upper and lower tips of a solution vector where the size of each tip is equal to that of the individual overlap. This scheme proves to be scalable on clusters of nodes in which each node has a multicore architecture. Numerical experiments comparing the scalability of our solver with direct and preconditioned iterative methods are also presented.     

逃逸时间法生成M集中控制变量B的确定

逃逸时间算法是生成Mandelbrot集(简称M集)最常用的算法,本文针对非线性复映射f(z)=zm c为迭代函数的情形进行讨论.首先,根据逃逸时间算法的基本原理给出相应的算法步骤;然后,对迭代函数f(z)=zm c进行了详细研究,从而合理地确定了算法中需要控制的变量B(参数值c0的取值范围)的取值,这样就大大地减少了迭代次数,从而提高了算法的运算效率.