A New Technique for Estimating the Lower Bound of the Trust-Region Subproblem

Trust-region methods are popular for nonlinear optimization problems. How to determine the predicted reduction of the trust-region subproblem is a key issue for trust-region methods. Powell gave an estimation of the lower bound of the trust-region subproblem by considering the negative gradient direction. In this article, we give an alternate way to estimate the same lower bound of the trust-region subproblem.

General closed-form inverse kinematics for arbitrary three-joint subproblems based on the product of exponential model

The inverse kinematics problems of robots are usually decomposed into several Paden–Kahan subproblems based on the product of exponential model. However, the simple combination of subproblems cannot solve all the inverse kinematics problems, and there is no common approach to solve arbitrary three-joint subproblems in an arbitrary postural relationship. The novel algebraic geometric (NAG) methods that obtain the general closed-form inverse kinematics for all types of three-joint subproblems are presented in this paper. The geometric and algebraic constraints are used as the conditions precedent to solve the inverse kinematics of three-joint subproblems. The NAG methods can be applied in the inverse kinematics of three-joint subproblems in an arbitrary postural relationship. The inverse kinematics simulations of all three-joint subproblems are implemented, and simulation results indicating that the inverse solutions are consistent with the given joint angles validate the general closed-form inverse kinematics. Huaque III minimally invasive surgical robot is used as the experimental platform for the simulation, and a master–slave tracking experiment is conducted to verify the NAG methods. The simulation result shows the inverse solutions and six sets given joint angles are consistent. Additionally, the mean and maximum of the master–slave tracking experiment for the closed-form solution are 0.1486 and 0.4777 mm, respectively, while the mean and maximum of the master–slave tracking experiment for the compensation method are 0.3188 and 0.6394 mm, respectively. The experiments results demonstrate that the closed-form solution is superior to the compensation method. The results verify the proposed general closed-form inverse kinematics based on the NAG methods.

ON MAXIMA OF DUAL FUNCTION OF THE CDT SUBPROBLEM

Focuses on a study which determined the geometry meaning of the maxima of the CDT mathematical subproblem's dual function. Properties of trust region subproblem; Approximation of the CDT feasible region; Relations between the CDT problem and the trust region problem; Illustration of the geometry meaning of the jump parameter.

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.

A Dwindling Filter Algorithm with a Modified Subproblem for Nonlinear Inequality Constrained Optimization

The authors propose a dwindling filter algorithm with Zhou's modified subproblem for nonlinear inequality constrained optimization.The feasibility restoration phase,which is always used in the traditional filter method,is not needed.Under mild conditions,global convergence and local superlinear convergence rates are obtained.Numerical results demonstrate that the new algorithm is effective.

A necessary and sufficient condition of convexity for SOC reformulation of trust-region subproblem with two intersecting cuts

We consider the extended trust-region subproblem with two linear inequalities. In the "nonintersecting" case of this problem, Burer and Yang(2015) have proved that its semi-definite programming relaxation with second-order-cone reformulation(SDPR-SOCR) is a tight relaxation. In the more complicated "intersecting" case, which is discussed in this paper, so far there is no result except for a counterexample for the SDPR-SOCR. We present a necessary and sufficient condition for the SDPR-SOCR to be a tight relaxation in both the "nonintersecting" and "intersecting" cases. As an application of this condition, it is verified easily that the "nonintersecting" SDPR-SOCR is a tight relaxation indeed. Furthermore, as another application of the condition, we prove that there exist at least three regions among the four regions in the trust-region ball divided by the two intersecting linear cuts, on which the SDPR-SOCR must be a tight relaxation. Finally, the results of numerical experiments show that the SDPR-SOCR can work efficiently in decreasing or even eliminating the duality gap of the nonconvex extended trust-region subproblem with two intersecting linear inequalities indeed.

On KKT points of Celis-Dennis-Tapia subproblem

The Celis-Dennis-Tapia(CDT) problem is a subproblem of the trust region algorithms for the constrained optimization. CDT subproblem is studied in this paper. It is shown that there exists the KKT point such that the Hessian matrix of the Lagrangian is positive semidefinite,if the multipliers at the global solution are not unique. Next the second order optimality conditions are also given, when the Hessian matrix of Lagrange at the solution has one negative eigenvalue.And furthermore, it is proved that all feasible KKT points satisfying that the corresponding Hessian matrices of Lagrange have one negative eigenvalue are the local optimal solutions of the CDT subproblem.

Cubic Regularization Methods with Second-Order Complexity Guarantee Based on a New Subproblem Reformulation

The cubic regularization(CR)algorithm has attracted a lot of attentions in the literature in recent years.We propose a new reformulation of the cubic regularization subproblem.The reformulation is an unconstrained convex problem that requires computing the minimum eigenvalue of the Hessian.Then,based on this reformulation,we derive a variant of the(non-adaptive)CR provided a known Lipschitz constant for the Hessian and a variant of adaptive regularization with cubics(ARC).We show that the iteration complexity of our variants matches the best-known bounds for unconstrained minimization algorithms using first-and second-order information.Moreover,we show that the operation complexity of both of our variants also matches the state-of-the-art bounds in the literature.Numerical experiments on test problems from CUTEst collection show that the ARC based on our new subproblem reformulation is comparable to the existing algorithms.

New sequential quadratic programming algorithm with consistent subproblems

One of the most interesting topics related to sequential quadratic programming algorithms is how to guarantee the consistence of all quadratic programming subproblems. In this decade, much work trying to change the form of constraints to obtain the consistence of the subproblems has been done The method proposed by De O. Panto-ja J F A and coworkers solves the consistent problem of SQP method, and is the best to the authors’ knowledge. However, the scale and complexity of the subproblems in De O. Pantoja’s work will be increased greatly since all equality constraints have to be changed into absolute form A new sequential quadratic programming type algorithm is presented by means of a special ε-active set scheme and a special penalty function. Subproblems of the new algorithm are all consistent, and the form of constraints of the subproblems is as simple as one of the general SQP type algorithms. It can be proved that the new method keeps global convergence and local superhnear convergence.

A BLOCK LANCZOS METHOD FOR THE CDT SUBPROBLEM

In this paper, we present a block Lanczos met hod for solving the large-scale CDT subproblem. During the algorithm, the original CDT subproblem is projected to a smallscale one, and then some classical method is employed to solve this small-scale CDT subproblem to get a solution, which can be used to derive an approximate solution of the original CDT subproblem. Theoretical analysis of the error bounds for both the optimal value and the optimal solution is also proposed. Numerical experiments are carried out, and it is demonstrated that the block Lanczos method is effective and can achieve high accuracy for large-scale CDT subproblems.

Error bounds of Lanczos approach for trust-region subproblem

Because of its vital role of the trust-region subproblem （TRS） in various applications, for example, in optimization and in ill-posed problems, there are several factorization-free algorithms for solving the large-scale sparse TRS. The truncated Lanczos approach proposed by N. I. M. Gould, S. Lucidi, M. Roma, and P. L. Toint [SIAM J. Optim., 1999, 9： 504-525] is a natural extension of the classical Lanczos method for the symmetric linear system and eigenvalue problem and, indeed follows the classical Rayleigh-Ritz procedure for eigenvalue computations. It consists of 1） projecting the original TRS to the Krylov subspa^es to yield smaller size TRS＇s and then 2） solving the resulted TRS＇s to get the approximates of the original TRS. This paper presents a posterior error bounds for both the global optimal value and the optimal solution between the original TRS and their projected counterparts. Our error bounds mainly rely on the factors from the Lanczos process as well as the data of the original TRS and, could be helpful in designing certain stopping criteria for the truncated Lanczos approach.

基于新几何子问题的6R机械臂逆运动学分析

针对已有几何子问题对工业机械臂逆运动学分析通用性差且计算效率低的问题,提出了一种全新的几何子问题,并基于此开展了6R机械臂逆运动学分析研究。首先,简要叙述了已有的经典Paden-Kahan子问题;然后,在总结已有子问题不足的基础上,提出了用于求解通用6R工业机械臂逆运动学的新几何子问题,即单点绕3个轴线顺序旋转,并给出子问题的求解步骤;进一步,基于旋量理论及所提出的子问题,给出了求解工业机械臂逆运动学解的流程;最后,通过仿真和物理实验,验证所提子问题对于不同类型的6R机械臂逆运动学求解的适用性,并与文献中的已有方法进行了对比分析。研究结果表明,与已有基于旋量理论的方法相比,对于含有/不含有肩部偏移、前两个关节轴线相交/不相交的各类工业机械臂逆运动学求解问题,所提方法在通用性及计算效率上更加优良,且能够有效应用于实际机械臂的实时轨迹控制。

未知发射机位置的闭式解椭圆定位方法

研究了发射机位置未知时的椭圆定位问题,提出了一种低复杂度的目标和发射机位置联合估计的三步闭式求解方法。首先,利用直接路径测量值构造一个广义信赖域子问题(Generalized Trust Region Subproblem,GTRS)以得到发射机的估计位置;然后,将所估计的发射机位置代入间接路径模型,以此构造另外一个GTRS估计目标位置;最后,通过构造线性加权最小二乘问题联合估计目标和发射机的误差项,同时补偿前两步的估计误差,从而进一步提高了定位精度。所提算法的三个步骤均存在闭式解,且具有极低的计算复杂度。理论性能分析和仿真验证表明,所提方法的均方误差在大噪声时能够趋近于克拉美-罗下界(Cramer-Rao lower bound,CRLB),在特定环境下与现有方法相比具有更优的性能。

可重构机器人封闭形式的运动学逆解计算

由于可重构机器人构型的多样性,其运动学逆解的自动生成是应用中的关键问题。采用旋量和指数积公式建立可重构机器人的运动学模型,系统地分析了指数积公式的化简方法、子问题的分类和计算方法并加以实现,为可重构机器人封闭形式的运动学逆解提供了一种通用的可分解的计算方法,降低了求解的复杂性。通过一个典型实例验证了算法的有效性与可重用性。

解信赖域子问题的隐式分段折线算法

在Hessian矩阵正定的前提下,建立了一种最优曲线的微分方程模型.针对此微分方程模型,构造了一条隐式分段折线,从而提出了一种求解信赖域子问题的隐式分段折线算法,并且分析和证明了隐式分段折线路径的合理性.数值结果表明新算法是有效且可行的.

一种求解二次模型信赖域子问题的新算法

在Hessian矩阵正定的前提下,首先根据信赖域子问题精确求解方法的思想,得到了最优曲线的参数方程,进而建立了一种最优曲线的微分方程模型.针对此微分方程模型,运用中点公式构造了一条折线.从而用该折线代替最优曲线,提出了一种求解二次模型信赖域子问题的新算法.数值结果表明新算法比切线单折线法具有明显的优势.

动态邻域的分解多目标进化算法

多目标优化问题是进化算法领域的研究热点与难点.基于分解的多目标进化算法(MOEA/D)在求解多目标优化问题时有着较强的搜索能力、高效的适应度评价、良好的收敛性等优点.然而,不同的子问题使用相同大小的邻域统一优化,减缓算法搜索全局最优解的速率.为解决以上问题,提出一种动态邻域设置策略,针对不同的子问题设置不同的邻域.首先,分析子问题差异处理的原因;其次,根据子问题与边界的距离,提出边界子问题与靠边界子问题的邻域减小,其他子问题邻域增大策略并将以上策略应用在MOEA/D中,提出一种动态邻域的分解多目标进化算法,进一步分析改进算法中参数的敏感性.将该算法在经典测试函数ZDT系列,WFG系列上进行仿真实验,并采用反向世代距离(IGD)和超体积(HV)指标对算法性能对比分析.结果表明,与MOEA/D对比,改进算法的收敛性明显提高,求出的解集相比MOEA/D,NSGA-II,MOEA/D-DU同类典型的算法求出解集的质量更高,算法在求解前端为凸面的情况效果甚好.

求解信赖域子问题的一个光滑牛顿法

信赖域子问题的有效求解是实现信赖域算法的关键.利用光滑Fischer-Bermeister NCP函数提出了一个求解信赖域子问题的光滑牛顿法.数值实验表明所提出的算法是有效的.

基于差异化邻域策略的分解多目标进化算法

子问题邻域对基于分解的多目标进化算法性能影响较大.当邻域过大时,种群繁殖产生的新解偏离Pareto解集,在更新子问题时,新解与邻域内旧解的比较次数增多,算法的计算复杂度增加;当邻域过小时,算法容易陷入局部最优.为了解决上述问题,文中提出基于差异化邻域策略的分解多目标进化算法(MOEA/D-DN),通过分析不同大小的邻域对算法性能的影响,选择合适的参数.并根据每个子问题的权重向量与中心向量的偏角,为各子问题设置不同大小的邻域,合理分配算法资源,提高算法搜索全局最优解的速率.在2维ZDT系列和3维、5维DTLZ系列测试函数上的实验表明,MOEA/D-DN的收敛速度与收敛性能均有明显提高,算法的计算资源分配更合理,所获解集整体质量更优.

蜂窝型C/SiC椭圆反射镜镜坯的优化设计

进行了蜂窝型C/SiC椭圆反射镜镜坯的最小质量优化.首先确定了优化参量及相应的变化范围.其次进行了双设计参量的零阶近似优化和一阶优化.结果表明,零阶近似优化优于一阶优化且更适合于反射镜最小质量的优化.最后进行了不同初始设计参量值下的零阶近似优化,结果表明,零阶近似优化得到的解接近最优设计,虽然初始设计参量值对最优结果的影响较小,但小的初始M值和适中的初始TP值更倾向于得到较优结果.优化的机理可能是较大的设计参量M的单位变形变化造成的质量变化率.