Search

In this article, we present a corrector-predictor path-following interior-point algorithm forP∗(κ)-horizontal linear complementarity problem over Cartesian product of symmetric cones, using Euclidean Jordan algebras. This comprehensive problem is a newly introduced problem in the context of interior-point methods. The algorithm takes damped Nesterov-Todd steps in the predictor (affine-scaling) stage while maintaining a certain neighborhood of the central path. Moreover, at each corrector stage, we use only full-Nesterov-Todd steps. Furthermore, we derive the currently best known iteration bound for the algorithm with small updates, namely,, whereris the rank of the associated Euclidean Jordan algebra and𝜀is a prescribed tolerance. [ABSTRACT FROM AUTHOR]

In this paper, we present an improved version of the infeasible-interior-point method for linear optimization introduced by Roos (SIAM J Optim 16(4):1110-1136, ). Each main step of Roos's algorithm is composed of one feasibility step and several centering steps. By using a new search direction, we prove that it is enough to take only one step in order to obtain a polynomial-time method. The iteration bound coincides with the currently best iteration bound for linear optimization problems. [ABSTRACT FROM AUTHOR]

After a brief introduction to Jordan algebras, we present a primal-dual interior-point algorithm for second-order conic optimization that uses full Nesterov-Todd steps; no line searches are required. The number of iterations of the algorithm coincides with the currently best iteration bound for second-order conic optimization. We also generalize an infeasible interior-point method for linear optimization to second-order conic optimization. As usual for infeasible interior-point methods, the starting point depends on a positive number. The algorithm either finds a solution in a finite number of iterations or determines that the primal-dual problem pair has no optimal solution with vanishing duality gap. [ABSTRACT FROM AUTHOR]

We present a modified version of the infeasible-interior-point algorithm for monotone linear complementary problems introduced by Mansouri et al. (Nonlinear Anal. Real World Appl. 12(2011) 545{561). Each main step of the algorithm consists of a feasibility step and several centering steps. We use a different feasibility step, which targets at the μ+-center. It results a better iteration bound. [ABSTRACT FROM AUTHOR]

In [H. Mansouri and C. Roos, Numer. Algorithms 52 (2009) 225-255.], Mansouri and Ross presented a primal-dual infeasible interior-point algorithm with full-Newton steps whose iteration bound coincides with the best known bound for infeasible interior-point methods. Here, we introduce a slightly different algorithm with a different search direction and show that the same complexity result is obtained using a simpler analysis. [ABSTRACT FROM AUTHOR]

Abstract: This paper consists of two parts. In the first part we present a new primal-dual feasible interior-point algorithm for solving monotone linear complementarity problems (LCP). Since the algorithm uses only full-Newton steps, it has the advantage that no line-searches are needed. It is proven that the number of iterations of the algorithm is , which coincides with the well-known best iteration bound for LCP. In the second part, we generalize an infeasible interior-point method for linear optimization introduced by Roos (2006)  to LCP. Two types of full-Newton steps are used, feasibility steps and (ordinary) centering steps, respectively. The algorithm starts from strictly feasible iterates of a perturbed problem, on its central path, and feasibility steps find strictly feasible iterates for the next perturbed problem. By using centering steps for the new perturbed problem, we obtain strictly feasible iterates close enough to the central path of the new perturbed problem. The starting point depends on two positive numbers and . The algorithm terminates either by finding an -solution or detecting that the LCP problem has no optimal solution with vanishing duality gap satisfying a condition in terms of and . The iteration bound coincides with the currently best iteration bound for linear complementarity problems. [Copyright &y& Elsevier]

In this paper, we propose an infeasible interior-point algorithm for symmetric optimization problems using a new wide neighborhood and estimating the central path by an ellipse. In contrast of most interior-point algorithms for symmetric optimization which search an ε-optimal solution of the problem in a small neighborhood of the central path, our algorithm searches for optimizers in a new wide neighborhood of the ellipsoidal approximation of central path. The convergence analysis of the algorithm is shown and it is proved that the iteration bound of the algorithm is O(rlogε−1) which improves the complexity bound of the recent proposed algorithm by Liu et al. (J. Optim. Theory Appl., 2013, 10.1007/s10957-013-0303-y) for symmetric optimization by the factor r12 and matches the currently best-known iteration bound for infeasible interior-point methods. [ABSTRACT FROM AUTHOR]

We present a primal-dual predictor-corrector interior-point method for symmetric cone optimization. The proposed algorithm is based on the Nesterov-Todd search directions and a wide neighborhood, which is an even wider neighborhood than a given negative infinity neighborhood. At each iteration, the method computes two corrector directions in addition to the Ai and Zhang directions (SIAM J. Optim. 16, 400-417, 2005), in order to improve performance. Moreover, we derive the complexity bound of the wide neighborhood predictor-corrector interior-point method for symmetric cone optimization that coincides with the currently best known theoretical complexity bounds for the short step algorithm. Finally, some numerical experiments are provided to reveal the effectiveness of the proposed method. [ABSTRACT FROM AUTHOR]

In this paper, we propose an arc-search infeasible-interior-point method based on the wide neighbourhoodfor linear complementarity problems over symmetric cones with the Cartesian-property (-SCLCP). The algorithm searches the optimizers along the ellipses that approximate the central path. Moreover, we derive the complexity bound of the algorithm which coincides with the currently best known theoretical complexity bounds for the short step path-following algorithm. Some numerical results are provided to demonstrate the computational performance of the proposed algorithm. [ABSTRACT FROM PUBLISHER]

In this paper,we propose a new predictor–corrector interior-point method for symmetric cone programming. This algorithm is based on a wide neighbourhood and the Nesterov–Todd direction. We prove that, besides the predictor steps, each corrector step also reduces the duality gap by a rate of, whereris the rank of the associated Euclidean Jordan algebras. In particular, the complexity bound is, whereis a given tolerance. To our knowledge, this is the best complexity result obtained so far for interior-point methods with a wide neighbourhood over symmetric cones. The numerical results show that the proposed algorithm is effective. [ABSTRACT FROM AUTHOR]

In this paper, we present a predictor-corrector infeasible-interior-point method for symmetric cone linear complementarity problem (SCLCP) with the Cartesian-property (-SCLCP). This method is based on a wide neighbourhood, which is an even wider neighbourhood than the negative infinity neighbourhood. We show that the iteration-complexity bound of the proposed algorithm for a commutative class of search directions is, whereis the condition number of matrixG,is the handicap of the problem,ris the rank of the associated Euclidean Jordan algebra andis a given tolerance. To our knowledge, this is the best complexity result obtained so far for the wide neighbourhood infeasible-interior-point methods for the Cartesian-SCLCPs. [ABSTRACT FROM PUBLISHER]

In this paper, we propose a feasible interior-point method for convex quadratic programming over symmetric cones. The proposed algorithm relaxes the accuracy requirements in the solution of the Newton equation system, by using an inexact Newton direction. Furthermore, we obtain an acceptable level of error in the inexact algorithm on convex quadratic symmetric cone programming (CQSCP). We also prove that the iteration bound for the feasible short-step method is O(√n log 1 ε), and O(n log 1 ε) for the large-step method which coincide with the currently best known iteration bounds for CQSCPs. [ABSTRACT FROM AUTHOR]

In this paper, we propose a new predictor-corrector interior-point algorithm for linear programming based on a wide neighbourhood. In each iteration, the algorithm computes the Ai-Zhang's predictor direction (SIAM J. Optim. 16(2):400-417, ) and a new corrector direction, in an attempt to improve its performance. We drive that the duality gap reduces in both predictor and corrector steps. Moreover, we also prove that the complexity of the algorithm coincides with the best iteration bound for small neighbourhood algorithms. Finally, some numerical experiments are provided which reveal capability and effectiveness of the proposed method. [ABSTRACT FROM AUTHOR]

In this article, we present a new predictor-corrector interior-point method, based on a wide neighborhood of the central path, for linear programming problems. In the corrector step ofthe proposed method, we derive the step size and corrector directions that guarantee that each iteration lies in a wide neighborhood of the central path. We also prove that the algorithm hasiteration complexity, which coincides with the best bound derived for linear programming problems. [ABSTRACT FROM PUBLISHER]

Euclidean Jordan algebra is a commonly used tool in designing interior-point algorithms for symmetric cone programs. In this paper, we present a full Nesterov–Todd (NT) step infeasible interior-point algorithm for horizontal linear complementarity problems over Cartesian product of symmetric cones. Since the algorithm uses only full-NT feasibility and centring steps, it has the advantage that no line searches are needed. The complexity result obtained here for symmetric cones using NT directions coincides with the best bound obtained for horizontal linear complementarity problems. [ABSTRACT FROM AUTHOR]

We present several improvements of the full-Newton step infeasible interior-point method for linear optimization introduced by Roos (SIAM J. Optim. 16(4):1110-1136, ). Each main step of the method consists of a feasibility step and several centering steps. We use a more natural feasibility step, which targets the μ-center of the next pair of perturbed problems. As for the centering steps, we apply a sharper quadratic convergence result, which leads to a slightly wider neighborhood for the feasibility steps. Moreover, the analysis is much simplified and the iteration bound is slightly better. [ABSTRACT FROM AUTHOR]

In this paper, we present a feasible predictor-corrector interior-point method for symmetric cone optimization problem in the large neighbourhood of the central path. The method is generalization of Ai-Zhang's predictor-corrector algorithm to the symmetric cone optimization problem. Starting with a feasible point in given large neighbourhood of the central path, the algorithm still terminates in at most iterations. This matches the best known iteration bound that is usually achieved by short-step methods, thereby, closing the complexity gap between long- and short-step interior-point methods for symmetric cone optimization. The preliminary numerical results on a selected set of NETLIB problems show advantage of the method in comparison with the version of the algorithm that is not based on the predictor-corrector scheme. [ABSTRACT FROM AUTHOR]

In this paper, we present a feasible interior-point algorithm for Cartesian horizontal linear complementarity problems in a new large neighbourhood of the central path. The new large neighbourhood is based on the infinity norm, and it is wider than the well-known neighbourhood based on negative infinity pseudonorm as well as the recently introduced large neighbourhood by Liu et al. [A new wide neighborhood primal-dual infeasible-interior-point method for symmetric cone programming. J Optim Theory Appl. 2013;158:796-815] which is based on Frobenius norm. The iterates are calculated by taking the largest possible step along the Nesterov-Todd search directions. Nevertheless, we show that the algorithm is globally convergent with the favourable polynomial iteration bound. Furthermore, the preliminary numerical results indicate that our method preforms quite well and outperforms the large-step Liu et al.'s method. [ABSTRACT FROM AUTHOR]

The aim of this paper is to extend the theoretical framework of thehorizontal linear complementarity problem over Cartesian product of symmetric cones (Cartesian-SCHLCP). The concepts of column and row sufficiency are defined for a linear operator on a Euclidean Jordan algebra. Some connections between theproperty of a linear operator on a Euclidean Jordan algebra and itsproperty as well as its column sufficiency are presented. Then these definitions and connections are generalized to a pair of linear operators determining the Cartesian-SCHLCP. It is also demonstrated that the Cartesian-SCHLCP can be equivalent with alinear complementarity problem over Cartesian product of symmetric cones (Cartesian-SCLCP), in a certain sense. Finally, based on some obtained results and using a suitable potential function, the main task of the paper is done, which is to show that the central trajectory of the Cartesian-SCHLCP exists and is unique. Therefore, we open the way for presenting and extending the interior-point methods for the Cartesian-SCHLCP. [ABSTRACT FROM AUTHOR]