A homogeneous interior-point algorithm for solving nonsymmetric convex conic optimization problems is presented. Starting each iteration from the vicinity of the central path, the method steps in the approximate tange...
详细信息
A homogeneous interior-point algorithm for solving nonsymmetric convex conic optimization problems is presented. Starting each iteration from the vicinity of the central path, the method steps in the approximate tangent direction and then applies a correction phase to locate the next well-centered primal-dual point. Features of the algorithm include that it makes use only of the primal barrier function, that it is able to detect infeasibilities in the problem and that no phase-I method is needed. We prove convergence to -accuracy in iterations. To improve performance, the algorithm employs a new Runge-Kutta type second order search direction suitable for the general nonsymmetric conic problem. Moreover, quasi-Newton updating is used to reduce the number of factorizations needed, implemented so that data sparsity can still be exploited. Extensive and promising computational results are presented for the -cone problem, the facility location problem, entropy maximization problems and geometric programs;all formulated as nonsymmetric convex conic optimization problems.
This article presents a polynomial predictor-corrector interior-point algorithm for convex quadratic programming based on a modified predictor-corrector interior-point algorithm. In this algorithm, there is only one c...
详细信息
This article presents a polynomial predictor-corrector interior-point algorithm for convex quadratic programming based on a modified predictor-corrector interior-point algorithm. In this algorithm, there is only one corrector step after each predictor step, where Step 2 is a predictor step and Step 4 is a corrector step in the algorithm. In the algorithm, the predictor step decreases the dual gap as much as possible in a wider neighborhood of the central path and the corrector step draws iteration points back to a narrower neighborhood and make a reduction for the dual gap. It is shown that the algorithm has O（√nL） iteration complexity which is the best result for convex quadratic programming so far.
This paper provides an analysis of the iterative complexity of a predictor-corrector type interior-point algorithm for a class of non-monotone nonlinear complementarity problems, i.e., the nonlinear P*-complementarity...
详细信息
This paper provides an analysis of the iterative complexity of a predictor-corrector type interior-point algorithm for a class of non-monotone nonlinear complementarity problems, i.e., the nonlinear P*-complementarity problems, which is quite general because it includes as a special case the monotone complementarity problem. At each corrector step, one has to compute an approximate solution of a nonlinear system such that a certain accuracy requirement is satisfied. The proof of the iterative complexity of the proposed algorithm requires that the mapping associated the problem satisfies a scaled Lipschitz condition.
In this paper, we propose a short-step feasible full-Newton step path-following interior-point algorithm (IPA) for monotone linear complementarity problems (LCPs). The proposed IPA uses the technique of algebraic equi...
详细信息
In this paper, we propose a short-step feasible full-Newton step path-following interior-point algorithm (IPA) for monotone linear complementarity problems (LCPs). The proposed IPA uses the technique of algebraic equivalent transformation (AET) induced by an univariate function to transform the centering equations which defines the central-path. By applying Newton's method to the modified system of the central-path of LCP, a new Newton search direction is obtained. Under new appropriate defaults of the threshold t which defines the size of the neighborhood of the central-path and of ? which determines the decrease in the barrier parameter, we prove that the IPA is well-defined and converges locally quadratically to a solution of the monotone LCPs. Moreover, we derive its iteration bound, namely, O(vnlogn/c) which coincides with the best-known iteration bound for such algorithms. Finally, some numerical results are presented to show its efficiency.
In this paper we propose a primal-dual path-following interior-point algorithm for second-order cone optimization. The algorithm is based on a new technique for finding the search directions and the strategy of the ce...
详细信息
In this paper we propose a primal-dual path-following interior-point algorithm for second-order cone optimization. The algorithm is based on a new technique for finding the search directions and the strategy of the central path. At each iteration, we use only full Nesterov-Todd step. Moreover, we derive the currently best known iteration bound for the algorithm with small-update method, namely, O(root N log N/epsilon), where N denotes the number of second-order cones in the problem formulation and epsilon the desired accuracy. (C) 2009 Elsevier Inc. All rights reserved.
The central path plays a very important role in interior-point methods. By an equivalent reformulation of the central path, we obtain a new search direction which targets at a small neighborhood of the central path. F...
详细信息
The central path plays a very important role in interior-point methods. By an equivalent reformulation of the central path, we obtain a new search direction which targets at a small neighborhood of the central path. For a full-Newton step interior-point algorithm based on this search direction, the complexity bound of the algorithm is the best known for linear optimization. (C) 2011 Elsevier B.V. All rights reserved.
In this paper, we present a new polynomial interior-point algorithm for the monotone linear complementarity problem over symmetric cones by employing the framework of Euclidean Jordan algebras. At each iteration, we u...
详细信息
In this paper, we present a new polynomial interior-point algorithm for the monotone linear complementarity problem over symmetric cones by employing the framework of Euclidean Jordan algebras. At each iteration, we use only full Nesterov and Todd steps. The currently best known iteration bound for small-update method, namely, O(root r log r/epsilon), is obtained, where r denotes the rank of the associated Euclidean Jordan algebra and e the desired accuracy.
In this paper, we consider a kernel-based full-Newton step feasible interior-point method (IPM) for P & lowast;(K)-Weighted Linear Complementarity Problem (WLCP). The specific eligible kernel function is used to d...
详细信息
In this paper, we consider a kernel-based full-Newton step feasible interior-point method (IPM) for P & lowast;(K)-Weighted Linear Complementarity Problem (WLCP). The specific eligible kernel function is used to define an equivalent form of the central path, the proximity measure, and to obtain search directions. Full-Newton steps are adopted to avoid the line search at each iteration. It is shown that with appropriate choices of the parameters, and a certain condition on the starting point, the iterations always lie in the defined neighborhood of the central path. Assuming strict feasibility of P & lowast;(K)-WLCP, it is shown that the IPM converges to the epsilon-approximate solution of P & lowast;(K)-WLCP in a polynomial number of iterations. Few numerical results are provided to indicate the computational performance of the algorithm.
We present a long-step predictor-corrector interior-point algorithm for the monotone semidefinite linear complementarity problems using the Monteiro-Zhang unified search directions. Our algorithm is based on the long-...
详细信息
We present a long-step predictor-corrector interior-point algorithm for the monotone semidefinite linear complementarity problems using the Monteiro-Zhang unified search directions. Our algorithm is based on the long-step predictor-corrector interior-point algorithm proposed by Kojima, Shida and Shindoh using the Alizadeh-Haeberly-Overton search direction, though the AHO search direction does not belong to the MZ unified search directions in general.
We propose a wide neighborhood interior-point algorithm with arc-search for P-*(kappa) linear complementarity problem (LCP). Along the ellipsoidal approximation of the central path, the algorithm searches optimizers i...
详细信息
We propose a wide neighborhood interior-point algorithm with arc-search for P-*(kappa) linear complementarity problem (LCP). Along the ellipsoidal approximation of the central path, the algorithm searches optimizers in every iteration. Assuming a strictly starting point is available, we show that the algorithm has O((1 + 2 kappa)(1 + 18 kappa)(2)n log (x(0))(T)s(0)/epsilon) iteration complexity. It matches the currently best known iteration bound for P-*(K) LCP. Some preliminary numerical results show that the proposed algorithm is efficient and reliable. (C) 2018 IMACS. Published by Elsevier B.V. All rights reserved.
暂无评论