In this paper we prove that a class of trust region methods presented in part I is superlinearly convergent. Numerical tests are reported thereafter. Results by solving a set of typical problems selected from literatu...In this paper we prove that a class of trust region methods presented in part I is superlinearly convergent. Numerical tests are reported thereafter. Results by solving a set of typical problems selected from literatures have demonstrated that our algorithm is effective.展开更多
The sparse nonlinear programming(SNP) is to minimize a general continuously differentiable function subject to sparsity, nonlinear equality and inequality constraints. We first define two restricted constraint qualifi...The sparse nonlinear programming(SNP) is to minimize a general continuously differentiable function subject to sparsity, nonlinear equality and inequality constraints. We first define two restricted constraint qualifications and show how these constraint qualifications can be applied to obtain the decomposition properties of the Fréchet, Mordukhovich and Clarke normal cones to the sparsity constrained feasible set. Based on the decomposition properties of the normal cones, we then present and analyze three classes of Karush-KuhnTucker(KKT) conditions for the SNP. At last, we establish the second-order necessary optimality condition and sufficient optimality condition for the SNP.展开更多
In this paper, we establish a theoretical framework of path-following interior point al- gorithms for the linear complementarity problems over symmetric cones (SCLCP) with the Cartesian P*(κ)-property, a weaker condi...In this paper, we establish a theoretical framework of path-following interior point al- gorithms for the linear complementarity problems over symmetric cones (SCLCP) with the Cartesian P*(κ)-property, a weaker condition than the monotonicity. Based on the Nesterov-Todd, xy and yx directions employed as commutative search directions for semidefinite programming, we extend the variants of the short-, semilong-, and long-step path-following algorithms for symmetric conic linear programming proposed by Schmieta and Alizadeh to the Cartesian P*(κ)-SCLCP, and particularly show the global convergence and the iteration complexities of the proposed algorithms.展开更多
The semidefinite matrix completion(SMC) problem is to recover a low-rank positive semidefinite matrix from a small subset of its entries. It is well known but NP-hard in general. We first show that under some cases, S...The semidefinite matrix completion(SMC) problem is to recover a low-rank positive semidefinite matrix from a small subset of its entries. It is well known but NP-hard in general. We first show that under some cases, SMC problem and S1/2relaxation model share a unique solution. Then we prove that the global optimal solutions of S1/2regularization model are fixed points of a symmetric matrix half thresholding operator. We give an iterative scheme for solving S1/2regularization model and state convergence analysis of the iterative sequence.Through the optimal regularization parameter setting together with truncation techniques, we develop an HTE algorithm for S1/2regularization model, and numerical experiments confirm the efficiency and robustness of the proposed algorithm.展开更多
We study the generalizedk-median version of the warehouse-retailer network design problem(kWRND).We formulate the k-WRND as a binary integer program and propose a 6-approximation randomized algorithm based on Lagrangi...We study the generalizedk-median version of the warehouse-retailer network design problem(kWRND).We formulate the k-WRND as a binary integer program and propose a 6-approximation randomized algorithm based on Lagrangian relaxation.展开更多
文摘In this paper we prove that a class of trust region methods presented in part I is superlinearly convergent. Numerical tests are reported thereafter. Results by solving a set of typical problems selected from literatures have demonstrated that our algorithm is effective.
基金supported by National Natural Science Foundation of China(Grant No.11431002)Shandong Province Natural Science Foundation(Grant No.ZR2016AM07)
文摘The sparse nonlinear programming(SNP) is to minimize a general continuously differentiable function subject to sparsity, nonlinear equality and inequality constraints. We first define two restricted constraint qualifications and show how these constraint qualifications can be applied to obtain the decomposition properties of the Fréchet, Mordukhovich and Clarke normal cones to the sparsity constrained feasible set. Based on the decomposition properties of the normal cones, we then present and analyze three classes of Karush-KuhnTucker(KKT) conditions for the SNP. At last, we establish the second-order necessary optimality condition and sufficient optimality condition for the SNP.
基金supported by National Natural Science Foundation of China (Grant Nos. 10671010, 70841008)
文摘In this paper, we establish a theoretical framework of path-following interior point al- gorithms for the linear complementarity problems over symmetric cones (SCLCP) with the Cartesian P*(κ)-property, a weaker condition than the monotonicity. Based on the Nesterov-Todd, xy and yx directions employed as commutative search directions for semidefinite programming, we extend the variants of the short-, semilong-, and long-step path-following algorithms for symmetric conic linear programming proposed by Schmieta and Alizadeh to the Cartesian P*(κ)-SCLCP, and particularly show the global convergence and the iteration complexities of the proposed algorithms.
基金supported by National Natural Science Foundation of China(Grant Nos.11431002,71271021 and 11301022)the Fundamental Research Funds for the Central Universities of China(Grant No.2012YJS118)
文摘The semidefinite matrix completion(SMC) problem is to recover a low-rank positive semidefinite matrix from a small subset of its entries. It is well known but NP-hard in general. We first show that under some cases, SMC problem and S1/2relaxation model share a unique solution. Then we prove that the global optimal solutions of S1/2regularization model are fixed points of a symmetric matrix half thresholding operator. We give an iterative scheme for solving S1/2regularization model and state convergence analysis of the iterative sequence.Through the optimal regularization parameter setting together with truncation techniques, we develop an HTE algorithm for S1/2regularization model, and numerical experiments confirm the efficiency and robustness of the proposed algorithm.
基金supported by National Basic Research Program of China(973 Program)(Grant No.2010CB732501)National Natural Science Foundation of China(Grant No.11071268)China Scholarship Council Scientific Research Common Program of Beijing Municipal Commission of Education(Grant No.KM201210005033)
文摘We study the generalizedk-median version of the warehouse-retailer network design problem(kWRND).We formulate the k-WRND as a binary integer program and propose a 6-approximation randomized algorithm based on Lagrangian relaxation.
