Multiple reduced gradient method for multiobjective optimization problems

Multiobjective optimization has a large number of real-life applications. Under this motivation, in this paper, we present a new method for solving multiobjective optimization problems with both linear constraints and bound constraints on the variables. This method extends, to the multiobjective setting, the classical reduced gradient method for scalar-valued optimization. The proposed algorithm generates a feasible descent direction by solving an appropriate quadratic subproblem, without the use of any scalarization approaches. We prove that the sequence generated by the algorithm converges to Pareto-critical points of the problem. We also present some numerical results to show the efficiency of the proposed method.     

An algorithm for solving new trust region subproblem with conic model

The new trust region subproblem with the conic model was proposed in 2005, and was divided into three different cases. The first two cases can be converted into a quadratic model or a convex problem with quadratic constraints, while the third one is a nonconvex problem. In this paper, first we analyze the nonconvex problem, and reduce it to two convex problems. Then we discuss some dual properties of these problems and give an algorithm for solving them. At last, we present an algorithm for solving the new trust region subproblem with the conic model and report some numerical examples to illustrate the efficiency of the algorithm.     

Smoothed penalty algorithms for optimization of nonlinear models

We introduce an algorithm for solving nonlinear optimization problems with general equality and box constraints. The proposed algorithm is based on smoothing of the exact l ₁-penalty function and solving the resulting problem by any box-constraint optimization method. We introduce a general algorithm and present theoretical results for updating the penalty and smoothing parameter. We apply the algorithm to optimization problems for nonlinear traffic network models and report on numerical results for a variety of network problems and different solvers for the subproblems.     

An improved sequential quadratic programming algorithm for solving general nonlinear programming problems

In this paper, a class of general nonlinear programming problems with inequality and equality constraints is discussed. Firstly, the original problem is transformed into an associated simpler equivalent problem with only inequality constraints. Then, inspired by the ideals of the sequential quadratic programming (SQP) method and the method of system of linear equations (SLE), a new type of SQP algorithm for solving the original problem is proposed. At each iteration, the search direction is generated by the combination of two directions, which are obtained by solving an always feasible quadratic programming (QP) subproblem and a SLE, respectively. Moreover, in order to overcome the Maratos effect, the higher-order correction direction is obtained by solving another SLE. The two SLEs have the same coefficient matrices, and we only need to solve the one of them after a finite number of iterations. By a new line search technique, the proposed algorithm possesses global and superlinear convergence under some suitable assumptions without the strict complementarity. Finally, some comparative numerical results are reported to show that the proposed algorithm is effective and promising.     

Solving Variational Inequality Problems with Linear Constraints by a Proximal Decomposition Algorithm

The alternating direction method solves large scale variational inequality problems with linear constraints via solving a series of small scale variational inequality problems with simple constraints. The algorithm is attractive if the subproblems can be solved efficiently and exactly. However, the subproblem is itself variational inequality problem, which is structurally also difficult to solve. In this paper, we develop a new decomposition algorithm, which, at each iteration, just solves a system of well-conditioned linear equations and performs a line search. We allow to solve the subproblem approximately and the accuracy criterion is the constructive one developed recently by Solodov and Svaiter. Under mild assumptions on the problem's data, the algorithm is proved to converge globally. Some preliminary computational results are also reported to illustrate the efficiency of the algorithm.     

A New Decomposition Method for Variational Inequalities with Linear Constraints

We propose a new decomposition method for solving a class of monotone variational inequalities with linear constraints. The proposed method needs only to solve a well-conditioned system of nonlinear equations, which is much easier than a variational inequality, the subproblem in the classic alternating direction methods. To make the method more flexible and practical, we solve the sub-problems approximately. We adopt a self-adaptive rule to adjust the parameter, which can improve the numerical performance of the algorithm. Under mild conditions, the underlying mapping be monotone and the solution set of the problem be nonempty, we prove the global convergence of the proposed algorithm. Finally, we report some preliminary computational results, which demonstrate the promising performance of the new algorithm.     

An interior affine scaling projective algorithm for nonlinear equality and linear inequality constrained optimization

In this paper, we propose a new nonmonotonic interior point backtracking strategy to modify the reduced projective affine scaling trust region algorithm for solving optimization subject to nonlinear equality and linear inequality constraints. The general full trust region subproblem for solving the nonlinear equality and linear inequality constrained optimization is decomposed to a pair of trust region subproblems in horizontal and vertical subspaces of linearize equality constraints and extended affine scaling equality constraints. The horizontal subproblem in the proposed algorithm is defined by minimizing a quadratic projective reduced Hessian function subject only to an ellipsoidal trust region constraint in a null subspace of the tangential space, while the vertical subproblem is also defined by the least squares subproblem subject only to an ellipsoidal trust region constraint. By introducing the Fletcher's penalty function as the merit function, trust region strategy with interior point backtracking technique will switch to strictly feasible interior point step generated by a component direction of the two trust region subproblems. The global convergence of the proposed algorithm while maintaining fast local convergence rate of the proposed algorithm are established under some reasonable conditions. A nonmonotonic criterion should bring about speeding up the convergence progress in some high nonlinear function conditioned cases.     

求解带线性约束的凸优化的一类自适应不定线性化增广拉格朗日方法

增广拉格朗日方法是求解带线性约束的凸优化问题的有效算法.线性化增广拉格朗日方法通过线性化增广拉格朗日函数的二次罚项并加上一个临近正则项,使得子问题容易求解,其中正则项系数的恰当选取对算法的收敛性和收敛速度至关重要.较大的系数可保证算法收敛性,但容易导致小步长.较小的系数允许迭代步长增大,但容易导致算法不收敛.本文考虑求解带线性等式或不等式约束的凸优化问题.我们利用自适应技术设计了一类不定线性化增广拉格朗日方法,即利用当前迭代点的信息自适应选取合适的正则项系数,在保证收敛性的前提下尽量使得子问题步长选择范围更大,从而提高算法收敛速度.我们从理论上证明了算法的全局收敛性,并利用数值实验说明了算法的有效性.     

求线性比式和问题全局解的输出空间分枝定界算法

基于对p-1维输出空间进行剖分的思想,提出了一种求解线性比式和问题的分枝定界算法.通过一种两阶段转换方法得到原问题的一个等价问题,该问题的非凸性主要体现在新增加的p-1个非线性等式约束上.利用双线性函数的凹凸包络对这些非线性约束进行凸化,这就为等价问题构造了凸松弛子问题.将凸松弛子问题中的冗余约束去掉并进行等价转换,从而获得了一个比凸松弛子问题规模更小、约束更少的线性规划问题.证明了算法的理论收敛性和计算复杂性.数值实验表明该算法是有效可行的.     

不可分离凸背包问题的拉格朗日分解和区域分割方法

本文对线性约束不可分离凸背包问题给出了一种精确算法．该算法是拉格朗日分解和区域分割结合起来的一种分枝定界算法．利用拉格朗日分解方法可以得到每个子问题的一个可行解，一个不可行解，一个下界和一个上界．区域分割可以把一个整数箱子分割成几个互不相交的整数子箱子的并集，每个整数子箱子对应一个子问题．通过区域分割可以逐步减小对偶间隙并最终经过有限步迭代找到原问题的最优解．数值结果表明该算法对不可分离凸背包问题是有效的．     

A SELF-ADAPTIVE ALGORITHM FOR NONLINEAR LEAST SQUARES WITH LINEAR CONSTRAINTS

An algorithm for solving nonlinear least squares problems with general linear inequality constraints is described.At each step,the problem is reduced to an unconstrained linear least squares problem in a subs pace defined by the active constraints,which is solved using the quasi-Newton method.The major update formula is similar to the one given by Dennis,Gay and Welsch (1981).In this paper,we state the detailed implement of the algorithm,such as the choice of active set,the solution of subproblem and the avoidance of zigzagging.We also prove the globally convergent property of the algorithm.     

Navier-Stokes方程的最佳有限元非线性Galerkin算法

1．引言对于Navier－Stokes方程有限元数值求解方面的研究已有很多的文章和专著,多数是采用有限元Galerkin算法,例见文献[1-4]．然而,由于Navier-Stokes方程在大雷诺数时有其强的非线性性和对时间土的长期依赖性,用计算机求解Navier－Stokes方程在速度和容量方面是难以承受的．为了克服这些困难,最近人们提出了有限元非线性Galerkin算法,见文献卜8］,然而这种算法只是在某一有限时刻之后具有好的收敛速度,在初始时刻的某一区间不能达到好的收敛速度．本文应用Taylor展开技术导出了数值求解二维非定常Navier－Stokes方程的最佳…     

An Algorithm for Strictly Convex Quadratic Programming with Box Constraints

1IntroductionWeconsiderastrictlyconvex(i.e.,positivedefinite)quadraticprogrammingproblemsubjecttoboxconstraints:t-iereA=[aij]isannxnsymmetricpositivedefinitematrix,andb,canddaren-vectors.Letg(x)bethegradient,Ax b,off(x)atx.Withoutlossofgeneralityweassumebothcianddiarefinitenumbers,ci相似文献   

解新锥模型信赖域子问题的折线法

本文以新锥模型信赖域子问题的最优性条件为理论基础,认真讨论了新子问题的锥函数性质,分析了此函数在梯度方向及与牛顿方向连线上的单调性.在此基础上本文提出了一个求解新锥模型信赖域子问题折线法,并证明了这一子算法保证解无约束优化问题信赖域法全局收敛性要满足的下降条件.本文获得的数值实验表明该算法是有效的.     

Split Common Fixed Point Problem of Nonexpansive Semigroup

In this paper, we first introduce a new algorithm with a viscosity iteration method for solving the split common fixed point problem (SCFP) for a finite family of nonexpansive semigroups. We also present a new algorithm for solving the SCFP for an infinite family of quasi-nonexpansive mappings. We establish strong convergence of these algorithms in an infinite-dimensional Hilbert spaces. As application, we obtain strong convergence theorems for split variational inequality problems and split common null point problems. Our results improve and extend the related results in the literature.     

A norm-relaxed method of feasible directions for finely discretized problems from semi-infinite programming

In this paper, a class of finely discretized Semi-Infinite Programming (SIP) problems is discussed. Combining the idea of the norm-relaxed Method of Feasible Directions (MFD) and the technique of updating discretization index set, we present a new algorithm for solving the Discretized Semi-Infinite (DSI) problems from SIP. At each iteration, the iteration point is feasible for the discretized problem and an improved search direction is computed by solving only one direction finding subproblem, i.e., a quadratic program, and some appropriate constraints are chosen to reduce the computational cost. A high-order correction direction can be obtained by solving another quadratic programming subproblem with only equality constraints. Under weak conditions such as Mangasarian–Fromovitz Constraint Qualification (MFCQ), the proposed algorithm possesses weak global convergence. Moreover, the superlinear convergence is obtained under Linearly Independent Constraint Qualification (LICQ) and other assumptions. In the end, some elementary numerical experiments are reported.     

Spectral projected gradient and variable metric methods for optimization with linear inequalities

A family of variable metric methods for convex constrained optimizationwas introduced recently by Birgin, Martínez and Raydan.One of the members of this family is the inexact spectral projectedgradient (ISPG) method for minimization with convex constraints.At each iteration of these methods a strictly convex quadraticfunction with convex constraints must be (inexactly) minimized.In the case of the ISPG method it was shown that, in some importantapplications, iterative projection methods can be used for thisminimization. In this paper the particular case in which theconvex domain is a polytope described by a finite set of linearinequalities is considered. For solving the linearly constrainedconvex quadratic subproblem a dual approach is adopted, by meansof which subproblems become (not necessarily strictly) convexquadratic minimization problems with box constraints. Thesesubproblems are solved by means of an active-set box-constraintquadratic optimizer with a proximal-point type unconstrainedalgorithm for minimization within the current faces. Convergenceresults and numerical experiments are presented.     

A method combining norm-relaxed QP subproblems with systems of linear equations for constrained optimization

Based on the ideas of norm-relaxed sequential quadratic programming (SQP) method and the strongly sub-feasible direction method, we propose a new SQP algorithm for the solution of nonlinear inequality constrained optimization. Unlike the previous work, at each iteration, the norm-relaxed quadratic programming subproblem (NRQPS) in our algorithm only consists of the constraints corresponding to an estimate of the active set, and the high-order correction direction (used to avoid the Maratos effect) is obtained by solving a system of linear equations (SLE) which also only consists of such a subset of constraints and gradients. Moreover, the line search technique can effectively combine the initialization process with the optimization process, and therefore (if the starting point is not feasible) the iteration points always get into the feasible set after a finite number of iterations. The global convergence is proved under the Mangasarian–Fromovitz constraint qualification (MFCQ), and the superlinear convergence is obtained without assuming the strict complementarity. Finally, the numerical experiments show that the proposed algorithm is effective and promising for the test problems.     

A partitioning and bounded variable algorithm for linear programming

An interesting new partitioning and bounded variable algorithm (PBVA) is proposed for solving linear programming problems. The PBVA is a variant of the simplex algorithm which uses a modified form of the simplex method followed by the dual simplex method for bounded variables. In contrast to the two-phase method and the big M method, the PBVA does not introduce artificial variables. In the PBVA, a reduced linear program is formed by eliminating as many variables as there are equality constraints. A subproblem containing one ‘less than or equal to’ constraint is solved by executing the simplex method modified such that an upper bound is placed on an unbounded entering variable. The remaining constraints of the reduced problem are added to the optimal tableau of the subproblem to form an augmented tableau, which is solved by applying the dual simplex method for bounded variables. Lastly, the variables that were eliminated are restored by substitution. Differences between the PBVA and two other variants of the simplex method are identified. The PBVA is applied to solve an example problem with five decision variables, two equality constraints, and two inequality constraints. In addition, three other types of linear programming problems are solved to justify the advantages of the PBVA.