Search

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]

This paper proposes an infeasible interior-point algorithm for linear complementarity problem with full-Newton steps. The main iteration consists of a feasibility step and several centrality steps. No more than O( nlog( n/ ɛ)) iterations are required for getting an ɛ-solution of the problem at hand, which coincides with the best-known bound for infeasible interior-point algorithms. [ABSTRACT FROM AUTHOR]

In this paper, we propose an interior-point algorithm for monotone linear complementarity problems. The algorithm is based on a new technique for finding the search direction and the strategy of the central path. At each iteration, we use only full-Newton steps. Moreover, it is proven that the number of iterations of the algorithm coincides with the well-known best iteration bound for monotone linear complementarity problems. [ABSTRACT FROM AUTHOR]

Abstract: We establish a (novel for desingularization algorithms) a priori bound on the length of resolution of singularities by means of the compositions of the normalizations with Nash blowings up, albeit that only for affine binomial varieties of (essential) dimension 2. Contrary to a common belief the latter algorithm turns out to be of a very small complexity (in fact polynomial). To that end we prove a structure theorem for binomial varieties and, consequently, the equivalence of the Nash algorithm to a combinatorial algorithm that resembles Euclidean division in dimension ≥2 and, perhaps, makes the Nash termination conjecture of the Nash algorithm particularly interesting. A bound on the length of the normalized Nash resolution of a minimal surface singularity via the size of the dual graph of its minimal desingularization is in the Appendix (by M. Spivakovsky). [Copyright &y& Elsevier]

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]

In recent years, convex optimization solved very large practical engineering problems reliably and efficiently. In this paper, we present an extension of an algorithm for convex quadratic programming using a new technique for finding a class of search directions and the strategy of the central path, for convex optimization under linear constraints. To solve the initialization problem, we have introduced a weighted vector with the property that starting from an initial feasible centred point, it generates iterates that simultaneously, gets closer to optimality and closer to centrality. Finally, the favorable polynomial complexity bound for the algorithm is deserved namely, O (√n log(xtz/∈)) iterations. [ABSTRACT FROM AUTHOR]

Mehrotra-type predictor-corrector algorithm is one of the most effective primal-dual interiorpoint methods. This paper presents an extension of the recent variant of second order Mehrotra-type predictor-corrector algorithm that was proposed by Salahi, et al. (2006) for linear optimization. Based on the NT direction as Newton search direction, it is shown that the iteration-complexity bound of the algorithm for semidefinite optimization is {ie1108-1}, which is similar to that of the corresponding algorithm for linear optimization. [ABSTRACT FROM AUTHOR]

This paper presents an extension of the variant of Mehrotra's predictor-corrector algorithm which was proposed by Salahi and Mahdavi-Amiri (Appl. Math. Comput. 183:646-658, ) for linear programming to symmetric cones. This algorithm incorporates a safeguard in Mehrotra's original predictor-corrector algorithm, which keeps the iterates in the prescribed neighborhood and allows us to get a reasonably large step size. In our algorithm, the safeguard strategy is not necessarily used when the affine scaling step behaves poorly, which is different from the algorithm of Salahi and Mahdavi-Amiri. We slightly modify the maximum step size in the affine scaling step and extend the algorithm to symmetric cones using the machinery of Euclidean Jordan algebras. Based on the Nesterov-Todd direction, we show that the iteration-complexity bound of the proposed algorithm is $\mathcal{O}(r\log\varepsilon^{-1})$, where r is the rank of the associated Euclidean Jordan algebras and ε>0 is the required precision. [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]

An interior-point method (IPM) for Cartesian P *(κ)- linear complementarity problems over symmetric cones (SCLCP) is analysed and the complexity results are presented. The Cartesian P *(κ)- SCLCPs have been recently introduced as the generalization of the more commonly known and more widely used monotone-SCLCPs. The IPM is based on the barrier functions that are defined by a large class of univariate functions called eligible kernel functions, which have recently been successfully used to design new IPMs for various optimization problems. Eligible barrier (kernel) functions are used in calculating the Nesterov–Todd search directions and the default step-size which lead to very good complexity results for the method. For some specific eligible kernel functions, we match the best-known iteration bound for the long-step methods while for the short-step methods the best iteration bound is matched for all cases. [ABSTRACT FROM PUBLISHER]

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]

Abstract: Partial words are sequences over a finite alphabet that may contain wildcard symbols, called holes, which match, or are compatible with, all letters in the alphabet ((full) words are just partial words without holes). The subword complexity function of a partial word over a finite alphabet assigns to each positive integer, , the number, , of distinct full words over that are compatible with factors of length of . In this paper, with the help of our so-called hole functions, we construct infinite partial words such that for any real number . In addition, these partial words have the property that there exist infinitely many non-negative integers satisfying . Combining these results with earlier ones on full words, we show that this represents a class of subword complexity functions not achievable by full words. We also construct infinite partial words with intermediate subword complexity, that is, between polynomial and exponential. [Copyright &y& Elsevier]

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 design a primal-dual interior-point algorithm for linear optimization. Search directions and proximity function are proposed based on a new kernel function which includes neither growth term nor barrier term. Iteration bounds both for large- and small-update methods are derived, namely, O( nlog( n/ɛ)) and $O(\sqrt n \log (n/\varepsilon ))$. This new kernel function has simple algebraic expression and the proximity function has not been used before. Analogous to the classical logarithmic kernel function, our complexity analysis is easier than the other primal-dual interior-point methods based on logarithmic barrier functions and recent kernel functions. [ABSTRACT FROM AUTHOR]

This paper establishes the polynomial convergence of a new class of path-following methods for linear complementarity problems (LCP) whose search directions are obtained by applying Newton's method to the central path equation Xz = μe; Mx - c = z: Specifically, we show that the short-step path-following methods based on the L∞ norm neighborhood and the semilong-step path-following methods based on the L∞ seminorm neighborhood have the iteration-complexity bounds of O(n), respectively. [ABSTRACT FROM AUTHOR]

In the paper, the equivalence checking problem for program schemas in balanced semigroup models of programs is studied. A method for constructing algorithms to resolve this problem is proposed in the case where a semigroup model of programs possesses the left cancellation property h h = h h ⟹ h = h. The equivalence checking problem is shown to be decidable in time that polynomially depends on size of the schema being checked if the balanced semigroup model of programs possesses additionally the right cancellation property h h = h h ⟹ h = h. [ABSTRACT FROM AUTHOR]

In this paper, we propose a primal-dual second-order corrector interior point algorithm for linear programming problems. At each iteration, the method computes a corrector direction in addition to the Ai-Zhang direction [Ai and Zhang in SIAM J Optim 16:400-417 (2005)], in an attempt to improve performance. The corrector is multiplied by the square of the step-size in the expression of the new iterate. We prove that the use of the corrector step does not cause any loss in the worst-case complexity of the algorithm. To our best knowledge, this is the first wide neighborhood second-order corrector algorithm enjoyed the low iteration bound of $${O(\sqrt{n}L)}$$, the same as the best known complexity results for interior point methods. [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]

We present an interior-point method for monotone linear complementarity problems over symmetric cones (SCLCP) that is based on barrier functions which are defined by a large class of univariate functions, called eligible kernel functions. This class is fairly general and includes the classical logarithmic function, the self-regular functions, as well as many non-self-regular functions as special cases. We provide a unified analysis of the method and give a general scheme on how to calculate the iteration bounds for the entire class. We also calculate the iteration bounds of both large-step and short-step versions of the method for ten frequently used eligible kernel functions. For some of them we match the best known iteration bound for large-step methods, while for short-step methods the best iteration bound is matched for all cases. The paper generalizes results of Lesaja and Roos (SIAM J. Optim. 20(6):3014-3039, ) from P( κ)-LCP over the non-negative orthant to monotone LCPs over symmetric cones. [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]

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 a second order interior point algorithm for symmetric cone programming using a wide neighborhood of the central path. The convergence is shown for commutative class of search directions. The complexity bound is $${O(r^{3/2}\,\log\epsilon^{-1})}$$ for the NT methods, and $${O(r^{2}\,\log\epsilon^{-1})}$$ for the XS and SX methods, where r is the rank of the associated Euclidean Jordan algebra and $${\epsilon\,{ > }\,0}$$ is a given tolerance. If the staring point is strictly feasible, then the corresponding bounds can be reduced by a factor of r. The theory of Euclidean Jordan algebras is a basic tool in our analysis. [ABSTRACT FROM AUTHOR]

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]

In this paper, motivated by the complexity results of Interior Point Methods (IPMs) for Linear Optimization (LO) based on kernel functions, we present a polynomial time IPM for solving P*( κ)-linear complementarity problem, using a new class of kernel functions. The special case of our new class was considered earlier for LO by Y. Q. Bai et al. in 2004. Using some appealing properties of the new class, we show that the iteration bound for IPMs matches the so far best known theoretical iteration bound for both large and small updates by choosing special values for the parameters of the new class. [ABSTRACT FROM AUTHOR]

Abstract: In this paper we deal with the study of the polynomial complexity and numerical implementation for a short-step primal-dual interior point algorithm for monotone linear complementarity problems LCP. The analysis is based on a new class of search directions used by the author for convex quadratic programming (CQP) [M. Achache, A new primal-dual path-following method for convex quadratic programming, Computational and Applied Mathematics 25 (1) (2006) 97–110]. Here, we show that this algorithm enjoys the best theoretical polynomial complexity namely , iteration bound. For its numerical performances some strategies are used. Finally, we have tested this algorithm on some monotone linear complementarity problems. [Copyright &y& Elsevier]

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]

In this paper a primal-infeasible interior point algorithm is proposed for linearly constrained convex programming. A positive primal-infeasible dual-feasible point can be taken as the starting point of this algorithm in a large region. At each iterates it requires to solve approximately a nonlinear system. The polynomial complexity of the algorithm is obtained. It is shown that, after finite iterations a sufficiently good approximation to the optimal point is found, or there is no optimal point in a large region. [ABSTRACT FROM AUTHOR]

Abstract: Recently new classes of directed, acyclic graphs with vertices, namely -orders where is a larger than 1 integer, have been presented. These classes contain the interval orders, but are incomparable to trees. Here it is shown that the complexity of recognizing the -order class is , hence independent of . However, recognizing if a graph is in -orders for all might be done in time. These classes have an application in the preemptive multiprocessor scheduling problem. This problem is NP-hard if the number of processors is arbitrary but open for a fixed number of processors . When the task graph is an -order, the problem is polynomial on processors. Hence it is interesting to recognize such task graphs in a polynomial, independent of time, especially when the number of processors is large, for instance on a computation grid. [Copyright &y& Elsevier]

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]

Abstract: The one-in-three SAT problem is known to be NP-complete even in the absence of negated variables [T.J. Schaefer, The complexity of satisfiability problems, in: Proceedings of the 10th Annual ACM Symposium on Theory of Computing, ACM, New York, 1978, pp. 216–226], a variant known as positive (or monotone) one-in-three SAT. In this note, we use clausal graphs to investigate a further restriction: -bounded positive one-in-three SAT (BP one-in-three SAT), in which each variable occurs in no more than clauses. We show that for , BP one-in-three SAT is in the polynomial complexity class , while for all , it is NP-complete, providing another way of exploring the boundary between classes and NP. [Copyright &y& Elsevier]

Recently, using the framework of self-regularity, Salahi in his Ph.D. thesis proposed an adaptive single step algorithm which takes advantage of the current iterate information to find an appropriate barrier parameter rather than using a fixed fraction of the current duality gap. However, his algorithm might do at most one bad step after each good step in order to keep the iterate in a certain neighborhood of the central path. In this paper, using the same framework, we propose a hybrid adaptive algorithm. Depending on the position of the current iterate, our new algorithm uses either the classical Newton search direction or a self-regular search direction. The larger the distance from the central path, the larger the barrier degree of the self-regular search direction is. Unlike the classical approach, here we control the iterates by guaranteeing certain reduction of the proximity measure. This itself leads to a one dimensional equation which determines the target barrier parameter at each iteration. This allows us to have a large update algorithm without any need for safeguard or special steps. Finally, we prove that our hybrid adaptive algorithm has an O (n 71/100 log on χ0Ts0/ϵ) worst case iteration complexity. [ABSTRACT FROM AUTHOR]

A polynomial interior-point algorithm is presented for monotone linear complementarity problem (MLCP) based on a class of kernel functions with the general barrier term, which are called general kernel functions. Under the mild conditions for the barrier term, the complexity bound of algorithm in terms of such kernel function and its derivatives is obtained. The approach is actually an extension of the existing work which only used the specific kernel functions for the MLCP. [ABSTRACT FROM AUTHOR]

Abstract: Interior-point methods not only are the most effective methods in practice but also have polynomial-time complexity. The large update interior-point methods perform in practice much better than the small update methods which have the best known theoretical complexity. In this paper, motivated by the complexity results for linear optimization based on kernel functions, we extend a generic primal-dual interior-point algorithm based on a new kernel function to solve linear complementarity problems. By using some elegant and simple tools and having interior-point condition, we show that the large update primal-dual interior-point methods for solving linear complementarity problems enjoys iteration bound which becomes with special choices of the parameter q. This bound is much better than the classical primal-dual interior-point methods based on logarithmic barrier function and recent kernel functions introduced by some authors in optimization field. Some computational results have been provided. [Copyright &y& Elsevier]

We consider a primal-dual short-step interior-point method for conic convex optimization problems for which exact evaluation of the gradient and Hessian of the primal and dual barrier functions is either impossible or prohibitively expensive. As our main contribution, we show that if approximate gradients and Hessians of the primal barrier function can be computed, and the relative errors in such quantities are not too large, then the method has polynomial worst-case iteration complexity. (In particular, polynomial iteration complexity ensues when the gradient and Hessian are evaluated exactly.) In addition, the algorithm requires no evaluation--or even approximate evaluation--of quantities related to the barrier function for the dual cone, even for problems in which the underlying cone is not self-dual. [ABSTRACT FROM AUTHOR]

Even for a simple automated manufacturing system (AMS), such as a general single-unit resource allocation system, the computation of an optimal or maximally permissive dead- lock-avoidance policy (DAP) is NP-hard. Based on its Petri-net model, this paper addresses the deadlock-avoidance problem in AMSs, which can be modeled by systems of simple sequential processes with resources. First, deadlock is characterized as a perfect resource-transition circuit that is saturated at a reachable state. Second, for AMSs that do not have one-unit resources shared by two or more perfect resource-transition circuits that do not contain each other, it is proved that there are only two kinds of reachable states: safe states and deadlock. An algorithm for determining the safety of a new state resulting from a safe one is then presented, which has polynomial complexity. Hence, the optimal DAP with polynomial complexity can be obtained by a one-step look-ahead method, and the deadlock-avoidance problem is polynomially solved with Petri nets for the first time. Finally, by reducing a Petri-net model and applying the design of optimal DAP to the reduced one, a suboptimal DAP for a general AMS is synthesized, and its computation is of polynomial complexity. [ABSTRACT FROM AUTHOR]