Banach空间一类H-增生算子的混合拟变分包含的邻近算子方程

本文在Banach空间中引入一类H-增生算子的混合拟变分包含,并提出求该变分包含问题解的邻近点法.通过H-增生算子的预解算子技术,建立了混合拟变分包含问题与邻近算子方程的等价关系,由这个等价关系得到求解邻近算子方程的迭代算法,该算法收敛于上述混合拟变分包含问题的解.     

一般单调变分不等式的近似邻近外梯度算法

近似邻近点算法是求解单调变分不等式的一个有效方法,该算法通过解决一系列强单调子问题,产生近似邻近点序列来逼近变分不等式的解,而外梯度算法则通过每次迭代中增加一个投影来克服一般投影算法限制太强的缺点,但它们均未能改变迭代步骤中不规则闭凸区域上投影难计算的问题.于是,本文结合外梯度算法的迭代格式,构造包含原投影区域的半空间,将投影建立在半空间上,简化了投影的求解过程,并对新的邻近点序列作相应限制,使得改进的算法具有较好的收敛性.     

一种求解半定规划的邻近外梯度算法

本文提出了一种求解半定规划的邻近外梯度算法.通过转化半定规划的最优性条件为变分不等式,在变分不等式满足单调性和Lipschitz连续的前提下,构造包含原投影区域的半空间,产生邻近点序列来逼近变分不等式的解,简化了投影的求解过程.将该算法应用到教育测评问题中,数值实验结果表明,该方法是解大规模半定规划问题的一种可行方法.     

求解凸规划及鞍点问题定制的PPA 算法及其收敛速率

线性约束的凸优化问题和鞍点问题的一阶最优性条件是一个单调变分不等式. 在变分不等式框架下求解这些问题, 选取适当的矩阵G, 采用G- 模下的PPA 算法, 会使迭代过程中的子问题求解变得相当容易. 本文证明这类定制的PPA 算法的误差界有1/k 的收敛速率.     

求解单调包含问题的惯性混合非精确邻近点算法

本文提出了求解单调包含问题的一类新的惯性混合非精确邻近点算法(简记为iHIPPA)在适当的参数假设下,我们证明了求解单调包含问题的iHIPPA所产生点列的弱收敛性,获得了iHIPPA的非渐近收敛率为■及iHIPPA的遍历迭代复杂性为O(1/k).作为应用,我们还建立了求解单调变分包含问题的惯性邻近收缩算法,求解广义变分不等式问题的惯性投影邻近点算法,及求解原始一对偶问题的惯性非精确调比部分逆算法产生点列的收敛性及相应算法的非渐近收敛率及遍历迭代复杂性.本文结果推广和改进了文献中的相应结论.最后,本文应用新的惯性交替方向乘子法用以求解LASSO问题,而且一些初步的试验结果表明了新的算法的优越性.     

非凸非光滑不可分离优化的线性对称邻近ADMM收敛性分析

交替方向乘子法(ADMM)是一种求解可分离优化问题的简单有效的方法,相关研究已经较为完善.然而,当目标函数存在耦合项时,对ADMM算法收敛性的研究还处于初期.文章针对非凸非光滑不可分离优化问题,基于对称交替方向乘子法(SADMM),结合线性化技术,提出了一种新的线性对称邻近ADMM.在一定的假设条件下,证明了算法生成的序列有界并收敛至增广拉格朗日函数的稳定点.其次,当辅助函数满足Kurdyka-Lojasiewicz性质时,证明了算法的强收敛性.最后,数值实验的结果表明了算法的有效性.     

一种混合算法求解可分离带线性约束的变分不等式问题

本文研究了大规模的可分离带线性约束的变分不等式问题,提出了基于对数二次临近点法的交替方向法,新算法的每步用一个非线性方程组来代替变分不等式子问题.通过有效求解非线性方程组,使得新算法简单易行而且一定程度上提高了计算的效率.同时,在映射单调和原问题解集非空的条件下,证明了此算法具有全局收敛性,最后通过数值实验说明了此算法是有效可行的.     

解变分不等式的一种二次投影迭代算法

本文研究了一类新的求解伪单调变分不等式的二次投影迭代算法.利用Armijo型线性搜寻程序,建立了一类新的超平面,他们严格分离当前迭代点与变分不等式的解集.运用超平面的这种分离性质,在较弱的条件下证明了该算法生成的无穷序列是全局收敛的.数值实验证明该算法是有效的.     

仿射变换内点信赖域方法求解变分不等式问题

本文研究了求解非线性约束变分不等式问题(VIP)的一个新的算法.利用KKT条件的非光滑方程形式,得到了与VIP等价的简单约束优化问题.提出了求解VIP的一类结合回代线搜索技巧的仿射变换内点信赖域算法.在较弱的条件下证明了算法具有整体收敛性,进一步在某些正则条件下,证明了算法具有超线性收敛速度.     

求解单调变分不等式的近似邻近点算法的收敛性分析

为了求解单调变分不等式,建立了一个新的误差准则,并且在不需要增加诸如投影,外梯度等步骤的情况下证明了邻近点算法的收敛性.     

The convergence of subspace trust region methods

The trust region method is an effective approach for solving optimization problems due to its robustness and strong convergence. However, the subproblem in the trust region method is difficult or time-consuming to solve in practical computation, especially in large-scale problems. In this paper we consider a new class of trust region methods, specifically subspace trust region methods. The subproblem in these methods has an adequate initial trust region radius and can be solved in a simple subspace. It is easier to solve than the original subproblem because the dimension of the subproblem in the subspace is reduced substantially. We investigate the global convergence and convergence rate of these methods.     

卫星舱布局的半无限优化模型及最优性条件

本文以人造卫星仪器舱布局问题为背景，建立了一个半无限优化模型。应用图论、群对集合的作用、轨道等，把该问题分解为有限多个子问题，在每个子问题中克服了关于优化变量的时断时续性质。针对每个子问题分析了模型中各函数的性质，并构造了一个局部等价于子问题的极大极小问题。利用这个极大极小问题及子问题中各函数的方向可微性给出了子问题的一阶最优性条件。     

The layout problem of two kinds of graph elements with performance constraints and its optimality conditions

This paper presents an optimization model with performance constraints for two kinds of graph elements layout problem. The layout problem is partitioned into finite subproblems by using graph theory and group theory, such that each subproblem overcomes its on-off nature about optimal variable. Furthermore each subproblem is relaxed and the continuity about optimal variable doesn’t change. We construct a min-max problem which is locally equivalent to the relaxed subproblem and develop the first order necessary and sufficient conditions for the relaxed subproblem by virtue of the min-max problem and the theories of convex analysis and nonsmooth optimization. The global optimal solution can be obtained through the first order optimality conditions.     

David G. Luenberger,Linear and nonlinear programming, 2nd edition,Addison-Wesley,Reading (1984), xv + 492 pages, $35.50

This paper considers a stochastic version of the linear continuous type knapsack problem in which the cost coefficients are random variables. The problem is to find an optimal solution and an optimal probability level of the chance constraint. This problem P₀ is first transformed into a deterministic equivalent problem P. Then a subproblem with a positive parameter is introduced and a close relation between P and its subproblem is shown. Further, an auxiliary problem of the subproblem is introduced and a direct relation between P and the auxiliary problem is derived through a relation connecting the subproblem and its auxiliary problem. Fully utilizing these relations, an efficient algorithm is proposed that finds an optimal solution of P in at most O(n⁴) computational time where n is the number of decision variables. Finally, further research problems are discussed.     

The Model for Two-dimensional Layout Optimization Problem with Performance Constraints and Its Optimality Function

This paper studies the two-dimensional layout optimization problem.An optimization model withperformance constraints is presented.The layout problem is partitioned into finite subproblems in terms ofgraph theory,in such a way of that each subproblem overcomes its on-off nature optimal variable.A minimaxproblem is constructed that is locally equivalent to each subproblem.By using this minimax problem,we presentthe optimality function for every subproblem and prove that the first order necessary optimality condition issatisfied at a point if and only if this point is a zero of optimality function.     

Constraint programming-based column generation

This paper surveys recent applications and advances of the constraint programming-based column generation framework, where the master subproblem is solved by traditional OR techniques, while the pricing subproblem is solved by constraint programming (CP). This framework has been introduced to solve crew assignment problems, where complex regulations make the pricing subproblem demanding for traditional techniques, and then it has been applied to other contexts. The main benefits of using CP are the expressiveness of its modeling language and the flexibility of its solvers. Recently, the CP-based column generation framework has been applied to many other problems, ranging from classical combinatorial problems such as graph coloring and two dimensional bin packing, to application oriented problems, such as airline planning and resource allocation in wireless ad hoc networks.      

Constraint Programming-based Column Generation

This paper surveys recent applications and advances of the Constraint Programming-based Column Generation framework, where the master subproblem is solved by traditional OR techniques, while the pricing subproblem is solved by Constraint Programming. This framework has been introduced to solve crew assignment problems, where complex regulations make the pricing subproblem demanding for traditional techniques, and then it has been applied to other contexts. The main benefits of using Constraint Programming are the expressiveness of its modeling language and the flexibility of its solvers. Recently, the Constraint Programming-based Column Generation framework has been applied to many other problems, ranging from classical combinatorial problems such as graph coloring and two dimensional bin packing, to application oriented problems, such as airline planning and resource allocation in wireless ad-hoc networks.     

Sequential Linear-Quadratic Method for Differential Games with Air Combat Applications

We present a numerical method for computing a local Nash (saddle-point) solution to a zero-sum differential game for a nonlinear system. Given a solution estimate to the game, we define a subproblem, which is obtained from the original problem by linearizing its system dynamics around the solution estimate and expanding its payoff function to quadratic terms around the same solution estimate. We then apply the standard Riccati equation method to the linear-quadratic subproblem and compute its saddle solution. We then update the current solution estimate by adding the computed saddle solution of the subproblem multiplied by a small positive constant (a step size) to the current solution estimate for the original game. We repeat this process and successively generate better solution estimates. Our applications of this sequential method to air combat simulations demonstrate experimentally that the solution estimates converge to a local Nash (saddle) solution of the original game.     

Exact two steps SOCP/SDP formulation for a modified conic trust region subproblem

In this paper, we study a modified version of the conic trust region subproblem which arises within a class of nonlinear programming algorithms. First using a variant of S-Lemma, we give an SOCP/SDP formulation which gives its optimal objective value. Then using the parametrization approach of Dinkelbach and the known exact SOCP/SDP relaxation of the extended trust region subproblem, we find its optimal solution. Finally, some preliminary numerical results are given.     

A convergence proof for linear mean value cross decomposition

The mean value cross decomposition method for linear programming problems is a modification of ordinary cross decomposition that eliminates the need for using the Benders or Dantzig-Wolfe master problem. It is a generalization of the Brown-Robinson method for a finite matrix game and can also be considered as a generalization of the Kornai-Liptak method. It is based on the subproblem phase in cross decomposition, where we iterate between the dual subproblem and the primal subproblem. As input to the dual subproblem we use the average of a part of all dual solutions of the primal subproblem, and as input to the primal subproblem we use the average of a part of all primal solutions of the dual subproblem. In this paper we give a new proof of convergence for this procedure. Previously convergence has only been shown for the application to a special separable case (which covers the Kornai-Liptak method), by showing equivalence to the Brown-Robinson method.