An improved infeasible SSLE method for constrained optimization without strict complementarity

In this paper, using “working set” technique for determining the active set, a new SSLE-Type algorithm with arbitrary initial point for constrained optimization is presented. At each iteration, we first introduce a new working set based on a multiplier function, then an improved direction is obtained by three systems of linear equations with the same coefficient matrix and possess small scale, and to avoid the Maratos effect, another correction direction is yielded by a simple explicit formula. Under some mild conditions, the algorithm is proved to be globally and strongly convergent, and the superlinear or even quadratic convergence can be obtained without the strict complementarity. Finally, some interesting numerical results are reported.     

A feasible direction algorithm for general nonlinear semidefinite programming

This paper deals with nonlinear smooth optimization problems with equality and inequality constraints, as well as semidefinite constraints on nonlinear symmetric matrix-valued functions. A new semidefinite programming algorithm that takes advantage of the structure of the matrix constraints is presented. This one is relevant in applications where the matrices have a favorable structure, as in the case when finite element models are employed. FDIPA_GSDP is then obtained by integration of this new method with the well known Feasible Direction Interior Point Algorithm for nonlinear smooth optimization, FDIPA. FDIPA_GSDP makes iterations in the primal and dual variables to solve the first order optimality conditions. Given an initial feasible point with respect to the inequality constraints, FDIPA_GSDP generates a feasible descent sequence, converging to a local solution of the problem. At each iteration a feasible descent direction is computed by merely solving two linear systems with the same matrix. A line search along this direction looks for a new feasible point with a lower objective. Global convergence to stationary points is proved. Some structural optimization test problems were solved very efficiently, without need of parameters tuning.     

On the computer implementation of feasible direction interior point algorithms for nonlinear optimization

The paper discusses the computer implementation of a class of interior point algorithms for the minimization of nonlinear functions with equality and inequality constraints. These algorithms consist of fixed point iterations to solve KKT firstorder optimality conditions. At each iteration a descent direction is defined by solving a linear system. Then, the linear system is perturbed in such a way as to deflect the descent direction and obtain a feasible descent direction. A line search is finally performed to obtain a new interior point with a lower objective. Newton, quasi-Newton, or first-order versions of the algorithm can be obtained. This paper is mainly concerned with the solution of the internal linear systems, the algorithms that are employed for the constrained line search and also with the quasi-Newton matrix updating. Some numerical results obtained with a quasi Newton algorithm are also presented. A set of test problems were solved very efficiently with the same values of the internal parameters.     

求解互补支持向量机的非单调信赖域算法

求解支持向量机的核心问题是对一个大规模凸二次规划问题进行求解。基于支持向量机的修正模型,得到一个与之等价的互补问题,利用Fischer-Burmeister互补函数,从一个新的角度提出了求解互补支持向量机的非单调信赖域算法。新算法避免了求解Hesse矩阵或矩阵求逆运算,减少了工作量,提高了运算效率。在不需要任何假设的情况下,证明算法具有全局收敛性。数值实验结果表明,对于大规模非线性分类问题,该算法的运行速度比LSVM算法和下降法快,为求解SVM优化问题提供了一种新的可行方法。     

On the globalization of Wilson-type optimization methods by means of generalized reduced gradient methods

For solving nonlinear optimization problems, i.e. for the determination of Kuhn-Tucker points a numerical method is proposed. The considerations continue investigations of Best/ Bräuninger/Ritter/Robinson and Kleinmichel/Richter/Schönefeld. In these papers (published in this journal) different local methods are combined with a penalty method in such a way that global convergence can be guaranteed. In order to show that the basic principle of coupling is applicable to a number of further globally convergent methods a local Wilson-type method is now initialized by a feasible direction method that uses reduced gradients. In both phases of the method similar subproblems (special quadratic programs) occur. Therefore, in contrast to the papers mentioned above systems of linear equations have to be solved exclusively. Under usual assumptions the algorithm is shown to be globally and superlinearly convergent.     

Two modified spectral conjugate gradient methods and their global convergence for unconstrained optimization

In this paper, two modified spectral conjugate gradient methods which satisfy sufficient descent property are developed for unconstrained optimization problems. For uniformly convex problems, the first modified spectral type of conjugate gradient algorithm is proposed under the Wolfe line search rule. Moreover, the search direction of the modified spectral conjugate gradient method is sufficiently descent for uniformly convex functions. Furthermore, according to the Dai–Liao's conjugate condition, the second spectral type of conjugate gradient algorithm can generate some sufficient decent direction at each iteration for general functions. Therefore, the second method could be considered as a modification version of the Dai–Liao's algorithm. Under the suitable conditions, the proposed algorithms are globally convergent for uniformly convex functions and general functions. The numerical results show that the approaches presented in this paper are feasible and efficient.     

An efficient sequential linear quadratic algorithm for solving nonlinear optimal control problems

We develop a numerically efficient algorithm for computing controls for nonlinear systems that minimize a quadratic performance measure. We formulate the optimal control problem in discrete-time, but many continuous-time problems can be also solved after discretization. Our approach is similar to sequential quadratic programming for finite-dimensional optimization problems in that we solve the nonlinear optimal control problem using sequence of linear quadratic subproblems. Each subproblem is solved efficiently using the Riccati difference equation. We show that each iteration produces a descent direction for the performance measure, and that the sequence of controls converges to a solution that satisfies the well-known necessary conditions for the optimal control.     

Quasidifferential Optimization Algorithms in a Parallel Computation Environment

In this paper some parallel algorithms for the minimization of a quasidifferentiable function in the sense of Dem'yanov are considered. In particular a new parallel method for the search of a descent direction of a subdifferentiable function is presented. Such a method is based on the approximation of the subdifferential by a simplex which is related to the directional derivatives of the function at the current point; the direction of descent is found by solving in parallel some quadratic programming problems on the simplex. Some ideas about the possibility of reducing the number of constraints are also presented. Based on this new method, an algorithm for quasidifferentiable functions is sketched.     

稀疏盲源信号分离的新算法

针对以往通常采用线性规划或最短路径法计算相对复杂这一稀疏盲信号分离瓶颈,提出了一种新的算法,通过方向投影合理设置迭代初始值,结合最速下降法寻优估计源信号。新算法容易实现,分离速度快,能够很好地满足盲分离对速度的要求。     

A feasible directions algorithm for nonlinear complementarity problems and applications in mechanics

Complementarity problems are involved in mathematical models of several applications in engineering, economy and different branches of physics. We mention contact problems and dynamics of multiple bodies systems in solid mechanics. In this paper we present a new feasible direction algorithm for nonlinear complementarity problems. This one begins at an interior point, strictly satisfying the inequality conditions, and generates a sequence of interior points that converges to a solution of the problem. At each iteration, a feasible direction is obtained and a line search performed, looking for a new interior point with a lower value of an appropriate potential function. We prove global convergence of the present algorithm and present a theoretical study about the asymptotic convergence. Results obtained with several numerical test problems, and also application in mechanics, are described and compared with other well known techniques. All the examples were solved very efficiently with the present algorithm, employing always the same set of parameters.     

An improved electromagnetism-like mechanism algorithm for constrained optimization

Many problems in scientific research and engineering applications can be decomposed into the constrained optimization problems. Most of them are the nonlinear programming problems which are very hard to be solved by the traditional methods. In this paper, an electromagnetism-like mechanism (EM) algorithm, which is a meta-heuristic algorithm, has been improved for these problems. Firstly, some modifications are made for improving the performance of EM algorithm. The process of calculating the total force is simplified and an improved total force formula is adopted to accelerate the searching for optimal solution. In order to improve the accuracy of EM algorithm, a parameter called as move probability is introduced into the move formula where an elitist strategy is also adopted. And then, to handle the constraints, the feasibility and dominance rules are introduced and the corresponding charge formula is used for biasing feasible solutions over infeasible ones. Finally, 13 classical functions, three engineering design problems and 22 benchmark functions in CEC’06 are tested to illustrate the performance of proposed algorithm. Numerical results show that, compared with other versions of EM algorithm and other state-of-art algorithms, the improved EM algorithm has the advantage of higher accuracy and efficiency for constrained optimization problems.     

A hybrid LQP-based method for structured variational inequalities

This paper proposes a hybrid LQP-based method (LQP, logarithmic-quadratic proximal) to solve a class of structured variational inequalities. In this method, an intermediate point is produced by solving a nonlinear equation system based on the LQP method; a descent direction is constructed using this iterate and the new iterate is obtained by a convex combination of the previous point and the one generated by a projection-type method along this descent direction. Global convergence of the new method is proved under mild assumptions. Preliminary numerical results for traffic equilibrium problems verify the computational preferences of the new method.     

On the existence of affine invariant descent directions

This paper begins with a brief review of affine invariance and its significance for iterative algorithms. It then explores the existence of affine invariant descent directions for unconstrained minimization. While there may exist several affine invariant descent directions for smooth functions at a given point, it is shown that for quadratic functions, there exists exactly one invariant descent direction in the strictly convex case and generally none in the case where the Hessian is singular or indefinite. These results can be generalized to smooth nonlinear functions and have implications regarding the initialization of minimization algorithms. They stand in contrast to recent works on constrained convex and nonconvex optimization for which there may exist an affine invariant ‘frame’ that depends on the feasible set and that can be used to define an affine invariant descent direction.     

大规模优化问题的一个具有充分下降性的共轭梯度算法

本文基于修正的共轭梯度公式,提出了一个具有充分下降性的共轭梯度算法,该算法不需要线搜索,其步长由固定的公式给出．某种程度上,该算法利用了目标函数的二次信息,对目标函数的(近似)二次模型采取了精确线搜索,每步都只需要计算一次梯度值,特别适合大规模优化计算．本文还给出了该算法的全局收敛性分析,并得到强收敛结果．数值实验表明这种算法是很有应用前景的．     

矩阵方程AXB+CYD=E最佳逼近自反解的迭代算法

利用复合最速下降法的迭代算法能够求出矩阵方程[AXB+CYD=E]的最佳逼近自反解,但其收敛速度很慢。针对这一问题,提出一种利用共轭方向法的迭代算法。对于任给初始自反矩阵[X1]和[Y1],无论矩阵方程[AXB+CYD=E]是否相容,该算法都可以经过有限次迭代计算出其最佳逼近自反解。两个数值例子表明该算法是可行的,且收敛速度更快。     

Buckling analysis of nonlinear structures using Lanczos method

An improved Lanczos algorithm is proposed for solving ill-conditioned or singular (but inconsistent) systems of linear equations, especially those resulting from nonlinear finite element problems. Using the new algorithm, the limit range(s) of the buckling response of a nonlinear structure can be handled effectively by the full Newton-Raphson iteration which possesses a quadratic convergence property.     

Solving nonlinear optimal control problems using a hybrid IPSO-SQP algorithm

A hybrid algorithm by integrating an improved particle swarm optimization (IPSO) with successive quadratic programming (SQP), namely IPSO-SQP, is proposed for solving nonlinear optimal control problems. The particle swarm optimization (PSO) is showed to converge rapidly to a near optimum solution, but the search process will become very slow around global optimum. On the contrary, the ability of SQP is weak to escape local optimum but can achieve faster convergent speed around global optimum and the convergent accuracy can be higher. Hence, in the proposed method, at the beginning stage of search process, a PSO algorithm is employed to find a near optimum solution. In this case, an improved PSO (IPSO) algorithm is used to enhance global search ability and convergence speed of algorithm. When the change in fitness value is smaller than a predefined value, the searching process is switched to SQP to accelerate the search process and find an accurate solution. In this way, this hybrid algorithm may find an optimum solution more accurately. To validate the performance of the proposed IPSO-SQP approach, it is evaluated on two optimal control problems. Results show that the performance of the proposed algorithm is satisfactory.     

无约束图像分割模型的快速数值算法

针对无约束图像分割模型的实现问题,提出一种基于分块协调下降方法的快速数值算法.该算法将模型的对偶问题转化为一组约束一元或二元二次极值问题,不仅避免了原问题求解时局部不可微性和高非线性性等难点,使得求解过程简单并易于实现:而且与现有的基于梯度下降的算法相比,具有无条件全局收敛性并显著地提高了收敛速度.仿真实验结果表明了所提出算法的有效性和在分割效率上的优越性.     

方块脉冲函数应用于线性时变二次型最优控制的动态规划解法

本文通过应用方块脉冲函数的一些基本性质，将线性时变二次型最优控制问题化成多段动态规划问题，通过求解得到的动态规划问题，可得原问题的分段常值解。文中给出了形式简单且易于计算机求解的递推算法，与参考文献中的方法比较，本文得到的递推算法简单，明了，且计算时间及存储空间极大地减少，文中给出了算法的具体算例，具有明显的优越性。