Search

In this paper, we consider a kernel-based full-Newton step feasible interior-point method (IPM) for P ∗ (κ) -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 ∗ (κ) -WLCP, it is shown that the IPM converges to the ε -approximate solution of P ∗ (κ) -WLCP in a polynomial number of iterations. Few numerical results are provided to indicate the computational performance of the algorithm. [ABSTRACT FROM AUTHOR]

In this paper, we proposed a new primal-dual second-order corrector interior-point algorithm for semidefinite optimization. The algorithm is based on Darvay–Takács neighbourhood of the central path. In the new algorithm, the search directions are determined by the Darvay–Takács's direction and a second-order corrector direction in each iteration. The iteration complexity bound is $ O(\sqrt {n}L) $ O (n L) for the Nesterov–Todd scaling direction, which coincides with the best-known complexity results for semidefinite optimization. Finally, numerical experiments show that the proposed algorithm is promising. [ABSTRACT FROM AUTHOR]

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 τ 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(√nlog n\ϵ) O n log n ε $ \mathcal{O}\left(\sqrt{n}\mathrm{log}\frac{n}{\epsilon }\right)$ which coincides with the best-known iteration bound for such algorithms. Finally, some numerical results are presented to show its efficiency. [ABSTRACT FROM AUTHOR]

In this paper, we present a predictor-corrector interior-point algorithm for P*(K)-weighted linear complementarity problems. Based on the kernel function φ(t) = √t, the search direction of the algorithm is obtained. By choosing appropriate parameters, we prove that the algorithm is feasible and convergent. It is shown that the proposed algorithm has polynomial iteration complexity. Numerical results illustrate the effectiveness of the algorithm. [ABSTRACT FROM AUTHOR]

This paper presents a path-following full-Newton step interior-point algorithm for solving monotone linear complementarity problems. Under new choices of the defaults of the updating barrier parameter and the threshold τ which defines the size of the neighborhood of the central-path, we show that the short-step algorithm has the best-known polynomial complexity, namely, (n log n ). Finally, some numerical results are reported to show the efficiency of our algorithm. [ABSTRACT FROM AUTHOR]

Getting a perfectly centered initial point for feasible path-following interior-point algorithms is a hard practical task. Therefore, it is worth to analyze other cases when the starting point is not necessarily centered. In this paper, we propose a short-step weighted-path following interior-point algorithm (IPA) for solving convex quadratic optimization (CQO). The latter is based on a modified search direction which is obtained by using the technique of algebraically equivalent transformation (AET) introduced by a new univariate function to the Newton system which defines the weighted-path. At each iteration, the algorithm uses only full-Newton steps and the strategy of the central-path for tracing approximately the weighted-path. We show that the algorithm is well-defined and converges locally quadratically to an optimal solution of CQO. Moreover, we obtain the currently best known iteration bound, namely, O v n log n which is as good as the bound for linear optimization analogue. Some numerical results are given to evaluate the efficiency of the algorithm. [ABSTRACT FROM AUTHOR]

We present an arc-search infeasible interior-point algorithm for semidefinite optimization using the Nesterov-Todd search directions. The algorithm is based on the negative infinity neighborhood of the central path. The algorithm searches an ε-approximate solution of the problem along the ellipsoidal approximation of the entire central path. The convergence analysis of the algorithm is presented and shows that the algorithm has the iteration complexity bound O n 3 / 2 log ε − 1 . Here, n is the dimension of the problem and ε is the required precision. The numerical results show that our algorithm is efficient and promising. [ABSTRACT FROM AUTHOR]

As an extension of the complementarity problem (CP), the weighted complementarity problem (wCP) is a large class of equilibrium problems with wide applications in science, economics, and engineering. If the weight vector is zero, the wCP reduces to a CP. In this paper, we present a full-Newton step infeasible interior-point method (IIPM) for the special weighted linear complementarity problem over the nonnegative orthant. One iteration of the algorithm consists of one feasibility step followed by a few centering steps. All of them are full-Newton steps, and hence, no calculation of the step size is necessary. The iteration bound of the algorithm is as good as the best-known polynomial complexity of IIPMs for linear optimization. [ABSTRACT FROM AUTHOR]

In this paper, we propose a Mizuno-Todd-Ye type predictor-corrector infeasible interior-point method for linear optimization based on a wide neighborhood of the central path. According to Ai-Zhang's original idea, we use two directions of distinct and orthogonal corresponding to the negative and positive parts of the right side vector of the centering equation of the central path. In the predictor stage, the step size along the corresponded infeasible directions to the negative part is chosen. In the corrector stage by modifying the positive directions system a full-Newton step is removed. We show that, in addition to the predictor step, our method reduces the duality gap in the corrector step and this can be a prominent feature of our method. We prove that the iteration complexity of the new algorithm is (n log ɛ−1), which coincides with the best known complexity result for infeasible interior-point methods, where ɛ > 0 is the required precision. Due to the positive direction new system, we improve the theoretical complexity bound for this kind of infeasible interior-point method [1] by a factor of n . Numerical results are also provided to demonstrate the performance of the proposed algorithm. [ABSTRACT FROM AUTHOR]

An efficient algorithm for determining the equivalence of two deterministic multitape finite automata is suggested. It is based on an already published proof of solvability for this problem. It is shown that the suggested algorithm has polynomial complexity. The asymptotic running time of the algorithm is bounded by k ⁎ s n + 1 , where k is some constant, n is the number of tapes and s is the sum of the number of states for the considered automata. [ABSTRACT FROM AUTHOR]

In this paper, a full-Newton step infeasible interior-point method for solving linear optimization problems is presented. In each iteration, the algorithm uses only one so-called feasibility step and computes the feasibility search directions by using a trigonometric kernel function with a double barrier term. Convergence of the algorithm is proved and it is shown that the complexity bound of the algorithm matches the currently best known iteration bound for infeasible interior-point methods. Finally, some numerical results are provided to illustrate the performance of the proposed algorithm. [ABSTRACT FROM AUTHOR]

We introduce a feasible corrector–predictor interior-point algorithm (CP IPA) for solving linear optimization problems which is based on a new search direction. The search directions are obtained by using the algebraic equivalent transformation (AET) of the Newton system which defines the central path. The AET of the Newton system is based on the map that is a difference of the identity function and square root function. We prove global convergence of the method and derive the iteration bound that matches best iteration bounds known for these types of methods. Furthermore, we prove the practical efficiency of the new algorithm by presenting numerical results. This is the first CP IPA which is based on the above mentioned search direction. [ABSTRACT FROM AUTHOR]

An image overlapping algorithm, taking into account certain properties of objects identified in the images (average intensity, movement speed, etc) is proposed. The algorithm minimizes both memory and time complexity and it can be used in various applications, especially in medical imaging analysis. The idea behind the proposed algorithm is surface merging and interpolation. [ABSTRACT FROM AUTHOR]

Copyright of Control Theory & Applications / Kongzhi Lilun Yu Yinyong is the property of Editorial Department of Control Theory & Applications and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

In this article, we present a second-order corrector infeasible interior-point method based on one-norm large neighborhood for symmetric optimization. We consider the classical Newton direction as the sum of two other directions associated with the negative and positive parts of the right-hand side of the centrality equation. In addition to equipping them with different step lengths, we add a corrector step that is multiplied by the square of the step length in the expression of the new iterate. The convergence analysis of the algorithm is discussed and it is proved that the new algorithm has the same complexity as small neighborhood infeasible interiorpoint algorithms for the Nesterov-Todd (NT) direction, and the xs and sx directions. [ABSTRACT FROM AUTHOR]

Recently, Mansouri et al. (J. Optim. Theory Appl. 166: 605-618, 2015) presented an improved infeasible interior-point algorithm for linear optimization. Their algorithm has the shortcoming that the proximity measure may be still large when the duality gap approaches to zero. In this paper, we propose an infeasible interior-point algorithm for semidefinite optimization with a modified search direction. This modification is an attempt to decrease the value of the proximity measure, which is important to determine whether or not to perform centreing steps in the classical infeasible interior-point algorithms. Some preliminary numerical results show the benefit of the proposed algorithm as well. [ABSTRACT FROM AUTHOR]

We introduce an interior-point method for symmetric optimization based on a new method for determining search directions. In order to accomplish this, we use a new equivalent algebraic transformation on the centring equation of the system which characterizes the central path. In this way, we obtain a new class of directions. We analyse a special case of this class, which leads to the new interior-point algorithm mentioned before. Another way to find the search directions is using barriers derived from kernel functions. We show that in our case the corresponding direction cannot be deduced from a usual kernel function. In spite of this fact, we prove the polynomial complexity of the proposed algorithm. [ABSTRACT FROM AUTHOR]

In this paper, we propose a new primal-dual path-following interior-point method for semidefinite optimization based on a new reformulation of the nonlinear equation of the system which defines the central path. The proposed algorithm takes only full Nesterov and Todd steps and therefore no line-searches are needed for generating the new iterations. The convergence of the algorithm is established and the complexity result coincides with the best-known iteration bound for semidefinite optimization problems. [ABSTRACT FROM AUTHOR]

In this paper, we propose a primal-dual interior-point method for semidefinite optimization problems. The algorithm is based on a new class of search directions and the Ai-Zhang's wide neighborhood for monotone linear complementarity problems. The theoretical complexity of the new algorithm is calculated. It is investigated that the proposed algorithm has polynomial iteration complexity $$O(\sqrt{n}L)$$ and coincides with the best known iteration bound for semidefinite optimization problems. [ABSTRACT FROM AUTHOR]

We present a global algorithm for indefinite knapsack separable quadratic programs with bound constraints. The upper bounds on variables with nonconvex terms are assumed to be infinite in the algorithmic development. By characterizing optimal solutions of the problem, we enumerate a subset of KKT points to determine a global optimum. The enumeration is made efficient by developing a theory for shrinking and partitioning the search domain of KKT multipliers. The global algorithmic procedure is developed based on interval and point testing techniques that have roots in solving strictly convex problems. Our algorithm has quadratic (worst-case) complexity and its performance is demonstrated on a broad range of randomly generated problem instances and comparisons with existing global and local solvers. It turns out that our method can solve these nonconvex problems of extremely large size in a fraction of the time (relative to commercial software such as CPLEX 12.6) on a desktop computer. Furthermore, a feasible upper bounding scheme is developed for the case when the variables with nonconvex terms are allowed to have finite upper limits, using an iterative application of the above global algorithm, and the computational experience is presented. [ABSTRACT FROM AUTHOR]

We propose a new primal-dual interior-point predictor-corrector algorithm in Ai and Zhang's wide neighborhood for solving monotone linear complementarity problems (LCP). Based on the understanding of this neighborhood, we use two new directions in the predictor step and in the corrector step, respectively. Especially, the use of new corrector direction also reduces the duality gap in the corrector step, which has good effects on the algorithm's convergence. We prove that the new algorithm has a polynomial complexity of , which is the best complexity result so far. In the paper, we also prove a key result for searching for the best step size along some direction. Considering local convergence, we revise the algorithm to be a variant, which enjoys both complexity of and Q-quadratical convergence. Finally, numerical result shows the effectiveness and superiority of the two new algorithms for monotone LCPs. [ABSTRACT FROM AUTHOR]

In this article, we present a new full Nesterov-Todd step infeasible interior-point method for second-order cone optimization based on a non-coercive kernel function. The main iteration consists of a so-called feasibility step and one centering step, whereas the earlier versions, in [4, 21], needed two additional centering steps. We use a kernel function to induce the feasibility step. The new algorithm reduces the searching steps in each iteration and tenders an interesting analysis for complexity bound. [ABSTRACT FROM PUBLISHER]

Many systems of real word are modeled by retrial queuing system with batch arrivals. Analytical formulas for this class of systems are complicated and address only particular cases. The paper presents a study approach for this kind of systems, based on discrete event simulation. It is shown that the given algorithm has a polynomial complexity. Also, the object-oriented design we used for implementation is sketched. [ABSTRACT FROM AUTHOR]

After a brief introduction to Euclidean Jordan algebra, we present a new corrector-predictor path-following interior-point algorithm for convex, quadratic, and symmetric cone optimization. In each iteration, the algorithm involves two kind of steps: a predictor (affine-scaling) step and a full Nesterov and Todd (centring) step. Moreover, we derive the complexity for the algorithm, and we obtain the best-known iteration bound for the small-update method. [ABSTRACT FROM AUTHOR]

We present an improved version of an infeasible interior-point method for linear optimization published in 2006. In the earlier version each iteration consisted of one so-called feasibility step and a few--at most three--centering steps. In this paper each iteration consists of only a feasibility step, whereas the iteration bound improves the earlier bound by a factor 2 √2. The improvements are due to a new lemma that gives a much tighter upper bound for the proximity after the feasibility step. [ABSTRACT FROM AUTHOR]

A 2nd-order Mehrotra-type predictor-corrector interior-point method was proposed for linear programming, in which the predictor direction and corrector direction were computed with the Newton method and the search direction was obtained through a new form of combination of the predictor direction and corrector direction. At each step of the iteration, the step size parameter was calculated with the iteration restricted to a wide neighborhood of the central path. Analysis indicates the proposed algorithm converges to the optimal solution after finite times of iteration and has the polynomial iteration complexity O(√nL), which is the best complexity result for the current interior-point methods. Numerical experiment proves the high efficiency of the proposed algorithm. [ABSTRACT FROM AUTHOR]

We propose an infeasible Mehrotra-type predictor-corrector algorithm with a new center parameter updating scheme for CartesianP*(κ)-linear complementarity problem over symmetric cones. Based on the Nesterov-Todd direction, we show that the iteration-complexity bound of the proposed algorithm is 𝒪((1 + κ)3r2log ε−1), whereris the rank of the associated Euclidean Jordan algebras and κ is the handicap of the problem and ε > 0 is the required precision. Some numerical results are reported as well. [ABSTRACT FROM PUBLISHER]

In this paper, a full-Newton step feasible interior-point algorithm is proposed for solving $$P_*(\kappa )$$ -linear complementarity problems. We prove that the full-Newton step to the central path is local quadratically convergent and the proposed algorithm has polynomial iteration complexity, namely, $$O\left( (1+4\kappa )\sqrt{n}\log {\frac{n}{\varepsilon }}\right) $$ , which matches the currently best known iteration bound for $$P_*(\kappa )$$ -linear complementarity problems. Some preliminary numerical results are provided to demonstrate the computational performance of the proposed algorithm. [ABSTRACT FROM AUTHOR]

In this paper, we present a predictor-corrector path-following interior-point algorithm for symmetric cone optimization based on Darvay's technique. Each iteration of the algorithm contains a predictor step and a corrector step based on a modification of the Nesterov and Todd directions. Moreover, we show that the algorithm is well defined and that the obtained iteration bound is ...(√r log rµ0/ε), where r is the rank of Euclidean Jordan algebra. [ABSTRACT FROM AUTHOR]

We present a new infeasible-interior-point method, based on a wide neighborhood, for symmetric cone programming. The convergence is shown for a commutative class of search directions, which includes the Nesterov-Todd direction and the xs and sx directions. Moreover, we derive the complexity bound of the wide neighborhood infeasible interior-point methods that coincides with the currently best known theoretical complexity bounds for the short step path-following algorithm. [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]

Many systems of real word are modeled by retrial queuing system. Analytical formulas for this class of systems are complicated and address only particular cases. By algorithmic approach one studies through simulation the cases that are not studied analytically. It is shown that the given algorithm has a polynomial complexity. [ABSTRACT FROM AUTHOR]

In this paper we propose primal-dual interior-point algorithms for semidefinite optimization problems based on a new kernel function with a trigonometric barrier term. We show that the iteration bounds are $O(\sqrt{n}\log(\frac{n}{\epsilon}))$ for small-update methods and $O(n^{\frac{3}{4}}\log(\frac{n}{\epsilon}))$ for large-update, respectively. The resulting bound is better than the classical kernel function. For small-update, the iteration complexity is the best known bound for such methods. [ABSTRACT FROM AUTHOR]

Abstract: Two Mehrotra-type predictor–corrector algorithms are proposed for solving sufficient linear complementarity problems. Both algorithms are independent on the handicap χ of the problems. The first version of the Mehrotra-type algorithm is a generalization of the safeguard based Mehrotra-type algorithm for linear programming, that was proposed by Salahi et al. [M. Salahi, J. Peng, T. Terlaky, On Mehrotra-type predictor–corrector algorithms, SIAM J. Optim. 18 (2007) 1377–1397]. We also present a new variant of Mehrotra-type predictor–corrector algorithm using a new adaptive updating strategy of the centering parameter. We show that both algorithms enjoy iteration complexity. Some numerical results are reported as well. [Copyright &y& Elsevier]

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]

We introduce a full NT-step infeasible interior-point algorithm for semidefinite optimization based on a self-regular function to provide the feasibility step and to measure proximity to the central path. The result of polynomial complexity coincides with the best known iteration bound for infeasible interior-point methods. [ABSTRACT FROM AUTHOR]

Recently an infeasible interior-point algorithm for linear programming (LP) was presented by Liu and Sun. By using similar predictor steps, we give a (feasible) predictor-corrector algorithm for convex quadratic programming (QP). We introduce a (scaled) proximity measure and a dynamical forcing factor (centering parameter). The latter is used to force the duality gap to decrease. The algorithm can decrease the duality gap monotonically. Polynomial complexity can be proved and the result coincides with the best one for LP, namely, $O(\sqrt{n}\log n\mu^{0}/\varepsilon)$. [ABSTRACT FROM AUTHOR]

Interior-point methods for semidefinite optimization problems have been studied frequently, due to their polynomial complexity and practical implications. In this paper we propose a primal-dual infeasible interior-point algorithm that uses full Nesterov-Todd (NT) steps with a different feasibility step. We obtain the currently best known iteration bound for semidefinite optimization problems. [ABSTRACT FROM AUTHOR]

In this paper, we propose a second-order corrector interior-point algorithm for semidefinite programming (SDP). This algorithm is based on the wide neighborhood. The complexity bound is $${O(\sqrt{n}L)}$$ for the Nesterov-Todd direction, which coincides with the best known complexity results for SDP. To our best knowledge, this is the first wide neighborhood second-order corrector algorithm with the same complexity as small neighborhood interior-point methods for SDP. Some numerical results are provided as well. [ABSTRACT FROM AUTHOR]

In this paper we propose a class of new large-update primal-dual interior-point algorithms for P( κ) nonlinear complementarity problem (NCP), which are based on a class of kernel functions investigated by Bai et al. in their recent work for linear optimization (LO). The arguments for the algorithms are followed as Peng et al.'s for P( κ) complementarity problem based on the self-regular functions [Peng, J., Roos, C., Terlaky, T.: Self-Regularity: A New Paradigm for Primal-Dual Interior-Point Algorithms, Princeton University Press, Princeton, 2002]. It is worth mentioning that since this class of kernel functions includes a class of non-self-regular functions as special case, so our algorithms are different from Peng et al.'s and the corresponding analysis is simpler than theirs. The ultimate goal of the paper is to show that the algorithms based on these functions have favorable polynomial complexity. [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]

Abstract: This paper proposes an infeasible interior-point algorithm with full Nesterov–Todd (NT) steps for semidefinite programming (SDP). The main iteration consists of a feasibility step and several centrality steps. First we present a full NT step infeasible interior-point algorithm based on the classic logarithmical barrier function. After that a specific kernel function is introduced. The feasibility step is induced by this kernel function instead of the classic logarithmical barrier function. This kernel function has a finite value on the boundary. The result of polynomial complexity, , coincides with the best known one for infeasible interior-point methods. [ABSTRACT FROM AUTHOR]

This article proposes a class of infeasible interior point algorithms for convex quadratic programming, and analyzes its complexity. It is shown that this algorithm has the polynomial complexity. Its best complexity is O(nL). [ABSTRACT FROM AUTHOR]

It has been shown in various papers that most interior-point algorithms and their analysis can be generalized to semidefinite optimization. This paper presents an extension of the recent variant of Mehrotra's predictor-corrector algorithm that was proposed by Salahi et al. [M. Salahi, J. Peng, and T. Terlaky, On Mehrotra-type predictor-corrector algorithms, SIAM J. Optim. 18 (2007), pp. 1377-1397] for linear optimization (LO) problems. Based on the NT [Y.E. Nesterov and M.J. Todd, Self-scaled barriers and interior-point methods for convex programming, Math. Oper. Res. 22 (1997), pp. 1-42] directions which are Newton search directions, we show that the iteration-complexity bound of the algorithm is of the same order as that of the corresponding algorithm for LO. [ABSTRACT FROM AUTHOR]

Kernel functions play an important role in defining new search directions for primal-dual interior-point algorithm for solving linear optimization problems. In this paper we present a new kernel function which yields an algorithm with the best known complexity bound for both large- and small-update methods. [ABSTRACT FROM AUTHOR]

This paper proposes an infeasible interior-point algorithm with full-Newton step for linear programming, which is an extension of the work of Roos (SIAM J. Optim. 16(4):1110–1136, ). The main iteration of the algorithm consists of a feasibility step and several centrality steps. We introduce a kernel function in the algorithm to induce the feasibility step. For parameter p∈[0,1], the polynomial complexity can be proved and the result coincides with the best result for infeasible interior-point methods, that is, O( nlog n/ ε). [ABSTRACT FROM AUTHOR]

In this paper, using the framework of self-regularity, we propose a hybrid adaptive algorithm for the linear optimization problem. If the current iterates are far from a central path, the algorithm employs a self-regular search direction, otherwise the classical Newton search direction is employed. This feature of the algorithm allows us to prove a worst case iteration bound. Our result matches the best iteration bound obtained by the pure self-regular approach and improves on the worst case iteration bound of the classical algorithm. [ABSTRACT FROM AUTHOR]

Kernel functions play an important role in interior point methods (IPMs) for solving linear optimization (LO) problems to define a new search direction. In this paper, we consider primal-dual algorithms for solving Semidefinite Optimization (SDO) problems based on a new class of kernel functions defined on the positive definite cone S++n×n. Using some appealing and mild conditions of the new class, we prove with simple analysis that the new class-based large-update primal-dual IPMs enjoy an O(√n log n log n/ϵ) iteration bound to solve SDO problems with special choice of the parameters of the new class. [ABSTRACT FROM AUTHOR]

Abstract: We present primal–dual interior-point algorithms for second-order cone optimization based on a wide variety of kernel functions. This class of kernel functions has been investigated earlier for the case of linear optimization. In this paper we derive the iteration bounds for large- and for small-update methods, respectively. Here denotes the number of second-order cones in the problem formulation and the desired accuracy. These iteration bounds are currently the best known bounds for such methods. Numerical results show that the algorithms are efficient. [Copyright &y& Elsevier]