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.展开更多
This paper proposes an arlene scaling derivative-free trust region method with interior backtracking technique for bounded-constrained nonlinear programming. This method is designed to get a stationary point for such ...This paper proposes an arlene scaling derivative-free trust region method with interior backtracking technique for bounded-constrained nonlinear programming. This method is designed to get a stationary point for such a problem with polynomial interpolation models instead of the objective function in trust region subproblem. Combined with both trust region strategy and line search technique, at each iteration, the affine scaling derivative-free trust region subproblem generates a backtracking direction in order to obtain a new accepted interior feasible step. Global convergence and fast local convergence properties are established under some reasonable conditions. Some numerical results are also given to show the effectiveness of the proposed algorithm.展开更多
Grapiglia et al.(2013) proved subspace properties for the Celis-Dennis-Tapia(CDT) problem. If a subspace with lower dimension is appropriately chosen to satisfy subspace properties, then one can solve the CDT problem ...Grapiglia et al.(2013) proved subspace properties for the Celis-Dennis-Tapia(CDT) problem. If a subspace with lower dimension is appropriately chosen to satisfy subspace properties, then one can solve the CDT problem in that subspace so that the computational cost can be reduced. We show how to find subspaces that satisfy subspace properties for the CDT problem, by using the eigendecomposition of the Hessian matrix of the objection function. The dimensions of the subspaces are investigated. We also apply the subspace technologies to the trust region subproblem and the quadratic optimization with two quadratic constraints.展开更多
基金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 National Science Foundation of China under Grant No.11371253
文摘This paper proposes an arlene scaling derivative-free trust region method with interior backtracking technique for bounded-constrained nonlinear programming. This method is designed to get a stationary point for such a problem with polynomial interpolation models instead of the objective function in trust region subproblem. Combined with both trust region strategy and line search technique, at each iteration, the affine scaling derivative-free trust region subproblem generates a backtracking direction in order to obtain a new accepted interior feasible step. Global convergence and fast local convergence properties are established under some reasonable conditions. Some numerical results are also given to show the effectiveness of the proposed algorithm.
基金supported by National Natural Science Foundation of China(Grant Nos.11171217 and 11571234)
文摘Grapiglia et al.(2013) proved subspace properties for the Celis-Dennis-Tapia(CDT) problem. If a subspace with lower dimension is appropriately chosen to satisfy subspace properties, then one can solve the CDT problem in that subspace so that the computational cost can be reduced. We show how to find subspaces that satisfy subspace properties for the CDT problem, by using the eigendecomposition of the Hessian matrix of the objection function. The dimensions of the subspaces are investigated. We also apply the subspace technologies to the trust region subproblem and the quadratic optimization with two quadratic constraints.
