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 l...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.展开更多
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 inv...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.展开更多
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...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.展开更多
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 con...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.展开更多
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 m...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.展开更多
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 wi...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.展开更多
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 H...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.展开更多
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 con...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.展开更多
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 fo...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.展开更多
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 emplo...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.展开更多
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-s...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.展开更多
文摘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.
基金the Foundation for Innovative Research Groups of the National Natural Science Foundation of China(Grant No.51521003)the National Natural Science Foundation of China(Grant No.61803341)the Self-planned Task of State Key Laboratory of Robotics and System(Harbin Institute of Technology)(Grant No.SKLRS202009B).No conflicts of interest exist in this paper.
文摘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.
基金Research partially supported by Chinese NSF grants 19525101, 19731010 and State key project 96-221-04-02-02.
文摘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.
基金the National Natural Science Foundation of China (Grant No.10471062)the Natural Science Foundation of Jiangsu Province (Grant No. BK2006184)
文摘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.
基金supported by the National Natural Science Foundation of China(Nos.11201304,11371253)the Innovation Program of Shanghai Municipal Education Commission(No.12YZ174)the Group of Accounting and Governance Disciplines(No.10kq03)
文摘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.
基金supported by National Natural Science Foundation of China(Grant Nos.11471052,11171040,11001030 and 61375066)the Grant of China Scholarship Council
文摘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.
基金supported by the startup grants for doctoral research and the school grants for mathematical research of Beijing University of Technologythe National Natural Science Foundation of China(Grant No.10401038).
文摘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.
基金supported in part by the National Natural Foundation of China(Nos.11801087 and 12171100).
文摘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.
基金Project partly supported by the National Natural Science Foundation of China.
文摘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.
文摘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.
基金The authors would like to thank the anonymous referees for their careful reading and comments. This work of the first author was supported in part by the National Natural Science Foundation of China （Grant Nos. 11671246, 91730303, 11371102） and the work of the second author was supported in part by the National Natural Science Foundation of China （Grant Nos. 91730304, 11371102, 91330201）.
文摘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.
