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 present a full-Newton step interior-point method for solving monotone Weighted Linear Complementarity Problem. We use the technique of algebraic equivalent transformation (AET) of the nonlinear equation of the system which defines the central path. The AET is based on the square root function which plays an important role in computing the new search directions. The algorithm uses only full-Newton steps at each iteration, and hence, line searches are no longer needed. We prove that the algorithm has a quadratic rate of convergence to the target point on the central path. The obtained iteration bound coincides with the best known iteration bound for these types of problems. [ABSTRACT FROM AUTHOR]

In this paper, we present a polynomial primal-dual interior-point algorithm for linear optimization based on a modified logarithmic barrier kernel function. Iteration bounds for the large-update interior-point method and the small-update interior-point method are derived. It is shown that the large-update interior-point method has the same polynomial complexity as the small-update interior-point method, which is the best known iteration bounds. Our result closes a long-existing gap in the theoretical complexity bounds for large-update interior-point method and small-update interior-point method. [ABSTRACT FROM AUTHOR]

In this paper, we suggest a new infeasible interior-point method (IIPM) for P ∗ (κ) -linear complementarity problem ( P ∗ (κ) -LCP) based on a new class of kernel functions with full-Newton steps. Each iteration of the algorithm consists of a feasible step and a few centering steps. The feasible step is defined by the newly proposed kernel functions, while the centering step is determined by using Newton's method. New class of kernel functions includes a logarithmic kernel function in Roos (SIAM J Optim 16:1110–1136, 2006) and a trigonometric kernel function in Moslemi and Kheirfam (Optim Lett 13:127–157, 2019), Kheirfam and Haghighi (Commun Comb Optim 3:51–70, 2018), Fathi-Hafshejani et al. (J Appl Math Comput 48:111–128, 2015) as special cases. And we show that the proposed algorithm has the best known complexity for P ∗ (κ) -LCP for such a method and present some numerical results. [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 reduce the logarithmic Sarnak conjecture to the $\{0,1\}$ -symbolic systems with polynomial mean complexity. By showing that the logarithmic Sarnak conjecture holds for any topologically dynamical system with sublinear complexity, we provide a variant of the $1$ -Fourier uniformity conjecture, where the frequencies are restricted to any subset of $[0,1]$ with packing dimension less than one. [ABSTRACT FROM AUTHOR]

The "common agency" model, introduced by Bernheim and Whinston in 1986 combines the fundamental challenge of the principal–agent model with the challenges of coordinating multiple principals. In "Incomplete information VCG contracts for common agency," Alon, Talgam-Cohen, Lavi, and Shamash show that the class of common agency settings for which there exists a contract that guarantees truthfulness of all principals, welfare maximization, and the two standard properties from contract theory—limited liability for the agent and individual rationality for the principals—is identifiable by a polynomial-time algorithm. Furthermore, for these settings, the authors design a polynomial-time computable contract: given valuation reports from the principals, it returns, if possible for the setting, a payment scheme for the agent that constitutes a contract with all desired properties. We study contract design for welfare maximization in the well-known "common agency" model introduced in 1986 by Bernheim and Whinston. This model combines the challenges of coordinating multiple principals with the fundamental challenge of contract design: that principals have incomplete information of the agent's choice of action. Our goal is to design contracts that satisfy truthfulness of the principals, welfare maximization by the agent, and two fundamental properties of individual rationality (IR) for the principals and limited liability (LL) for the agent. Our results reveal an inherent impossibility. Whereas for every common agency setting there exists a truthful and welfare-maximizing contract, which we refer to as "incomplete information Vickrey–Clarke–Groves contracts," there is no such contract that also satisfies IR and LL for all settings. As our main results, we show that the class of settings for which there exists a contract that satisfies truthfulness, welfare maximization, LL, and IR is identifiable by a polynomial-time algorithm. Furthermore, for these settings, we design a polynomial-time computable contract: given valuation reports from the principals, it returns, if possible for the setting, a payment scheme for the agent that constitutes a contract with all desired properties. We also give a sufficient graph-theoretic condition on the population of principals that ensures the existence of such a contract and two truthful and welfare-maximizing contracts, in which one satisfies LL and the other one satisfies IR. Funding: Funding is by the European Union (ERC, ALGOCONTRACT) [Grant 101077862]. [ABSTRACT FROM AUTHOR]

In this paper, we propose a new method of applying the XOR and XNOR gates on exponentially large superpositions in Instantaneous Noise-Based Logic. These new gates are repeatable, and they can achieve an exponential speedup in computation with polynomial hardware complexity. [ABSTRACT FROM AUTHOR]

In this paper, we present a predictor-corrector interior-point algorithm for $ P_{*}(\kappa) $-weighted linear complementarity problems. Based on the kernel function $ \varphi(t) = \sqrt{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.

This paper considers the approximation problem of global optimal control of max-plus linear systems with real affine equality constrains. The approximate model that makes feasible values closest to the greatest lower bound is set up by introducing the distance between max-plus vectors. The existence of approximately optimal solutions is proved, and a criterion for the uniqueness of such solutions is presented. A general formula with polynomial time complexity is given to compute all the approximately optimal solutions. Furthermore, the proposed approximation technique is used to minimise the overall completion time of a distributed system without accurate optimal solution. The examples and simulations are provided to demonstrate the applicability of the results. [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 work, we investigate a full Newton step infeasible interior-point method for linear optimization based on a new search direction which is obtained from an algebraic equivalent transformation of the central path system. Furthermore, we prove that the proposed method obtains an ε-optimal solution to the original problem in polynomial time.

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]

In this paper, we present a new corrector-predictor interior-point method for solving semidefinite optimization. We use an algebraic equivalent transformation of the centering equation of the system which defines the central path. The algebraic transformation plays an essential role in the calculation of the new search directions. We prove that the iteration complexity of the algorithm coincides with the best known ones for interior-point methods (IPMs). To the best of our knowledge, this is the first corrector-predictor interior-point algorithm that uses the search directions obtained from the desired algebraic transformation for semidefinite optimization. Finally, some numerical experiments are provided to demonstrate the efficiency of our new algorithm. [ABSTRACT FROM AUTHOR]

In this paper, based on Darvay et al.'s strategy for linear optimization (LO) (Z. Darvay and P.R. Takács, Optim. Lett.12 (2018) 1099–1116.), we extend Kheirfam et al.'s feasible primal-dual path-following interior point algorithm for LO (B. Kheirfam and A. Nasrollahi, Asian-Eur. J. Math.1 (2020) 2050014.) to semidefinite optimization (SDO) problems in order to define a class of new search directions. The algorithm uses only full Nesterov-Todd (NT) step at each iteration to find an ε-approximated solution to SDO. Polynomial complexity of the proposed algorithm is established which is as good as the LO analogue. Finally, we present some numerical results to prove the efficiency of the proposed 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]

Nonlinear functional-integral equations contain the unknown function nonlinearly, occurring extensively in theory developed to a certain extent toward different applied problems and solutions thereof. Nonlinear science serves to reveal the nonlinear descriptions of widely different systems, has had a fundamental impact on complex dynamics. Accordingly, this study provides the basic definitions and results regarding Banach spaces with the proof as well as applications. Besides, proving the existence and uniqueness of the solutions by the Banach theorem is carried out. The existence results of the equations are generally obtained based on fundamental methods by which the fixed-point theorems are frequently applied. Subsequently, the definition of the measure pertaining to noncompactness on Banach space along with properties is presented. Hence, the aim is to study nonlinear functional-integral equations in the Banach space B C (R +) using the measure of noncompactness. In addition, the proof of the existence of global attractors and asymptotic stabilities, having at least one solution which pertains to B C (R +) is looked into. As the last stage, the definitions of global attractivity and asymptotical stability for equations on Banach space B C (R +) are given while proving the existence of solutions and global attractivity. Besides these, the existence and asymptotical stability are proven. Furthermore, the proof of the existence of global attractors and asymptotic stabilities, having at least one solution which pertains to B C (R +) for an example nonlinear integral equation has been demonstrated by one example premediated and the existence of blow-up point has been examined in one and more than one points regarding the nonlinear integral equation. The example nonlinear integral equation as addressed in this study has been examined in terms of its blow-up point and asymptotic stability with computational complexity for the first time. By doing so, it has been demonstrated that the existence of blow-up point has been the case in one and more than one points and besides this, the examination of its asymptotic stability has shown that it is asymptotically stable at least in one point, yet has no blow-up point pertaining to B C (R +). This has enabled thorough analysis of computational complexity of the related nonlinear functional-integral equations within the example both addressing dimension of input in Banach space and that of dataset with N dimension. This applicable approach assures the accurate transformation of the complex problems towards optimized solutions through the generation of advanced mathematical models in nonlinear dynamic settings characterized by complexity. [ABSTRACT FROM AUTHOR]

We propose a feasible primal-dual path-following interior-point algorithm for semidefinite least squares problems (SDLS). At each iteration, the algorithm uses only full Nesterov-Todd steps with the advantage that no line search is required. Under new appropriate choices of the parameter β which defines the size of the neighborhood of the central-path and of the parameter θ which determines the rate of decrease of the barrier parameter, we show that the proposed algorithm is well defined and converges to the optimal solution of SDLS. Moreover, we obtain the currently best known iteration bound for the algorithm with a short-update method, namely, O (n log (n / ε)) . Finally, we report some numerical results to illustrate the efficiency of our proposed algorithm. [ABSTRACT FROM AUTHOR]

In this paper, a wide neighborhood arc-search interior-point algorithm for convex quadratic programming with box constrains and linear constraints (BLCQP) is presented. The algorithm searches the optimizers along the ellipses that approximate the entire central path. Assuming a strictly feasible initial point is available, we show that the algorithm has O (n 3 4 log (x 0 - l) T s 0 + (w - x 0) T t 0 ε) iteration complexity bound, which is the best known complexity result for such methods. The numerical results show that our algorithm is effective and promising. [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]

By using a new search direction, we propose an infeasible interior-point method for monotone linear complementarity problem. The algorithm uses only one feasibility step in each iteration, and we prove that it suffices in order to obtain a polynomial-time method. The iteration bound coincides with the currently best iteration bound for linear complementarity problems. Moreover, the numerical results show that the new algorithm has a good performance.

The article investigates the problems of reduction (decomposition) of multidimensional data models in terms of hypercube OLAP-structures. Describes the case when a data structure is defined by the array that slices and dices the hypercube into the odd number of subcubes, and this set of subcube structures becomes decomposed. Defines an exact upper bound for increasing a computational performance of methods to analyze OLAP-data on subcubes, which determines the decomposition approach efficiency in comparison with the OLAP-data analysis on a complete unreduced hypercube. A compared efficiency of the hypercube decomposition into two subcubes on the sets consisting of the even and odd number of subcube structures has shown that with considerable data partitioning for methods of a polynomial complexity degree the decomposition efficiency essentially is independent on this factor and rises with increasing complexity degree of methods applied.When using the mathematical methods to study decomposition (reduction) of large hyper-cubes of multidimensional data of analytical OLAP systems into subcube components, there is a need to find conditions for minimising the computational complexity of methods to solve the problems of the OLAP hyper-cube analysis during data decomposition in comparison with using these methods for analyzing large amounts of information that is accumulated directly in the hyper-cubes of multidimensional OLAP-data to establish the criteria for decreasing or increasing computational performance when applying methods on the subcube components (reduction methods) as compared to applying these methods on a hypercube (non-reduction or traditional methods), depending on one or another degree of complexity of complex methods.The article provides an accurate quantitative estimate of decreasing computational complexity of reduction methods for analyzing OLAP-cubes as compared to the non-reduction methods in the case when said methods have the polynomial complexity and the original hypercube array of data comprises the odd number of subcubes.

In this paper, we present a new predictor-corrector interior-point algorithm based on a wide neighborhood for semidefinite optimization. The proposed algorithm is a Mizuno-Todd-Ye predictor-corrector type and uses the Nesterov-Todd (NT) search direction in predictor step and a commutative class of search directions involving Helmberg-Kojima-Monteiro and NT directions in corrector step. We show that the proposed algorithm at every both predictor and corrector steps reduces the duality gap. The method enjoys the iteration complexity of O (n κ ∞ L) , which matching to the currently best known iteration bound for wide neighborhood algorithms. Numerical results also confirm the algorithm is reliable and promising. [ABSTRACT FROM AUTHOR]

This paper studies the local optimality condition for the widely applied concave piecewise linear network flow problem (CPLNFP). Traditionally, for CPLNFP the complexity of checking the local optimality condition is exponentially related to the number of active arcs (i.e., arcs in which the flow is at the breakpoints). When the scale of CPLNFP is large, even local optimality is unverifiable and the corresponding local algorithms are inefficient. To overcome this shortcoming, a new local optimality condition is given. This new condition is based on the concavity and piecewise linearity of the cost function and makes full use of the network structure. It is proven that the complexity of the new condition is polynomial. Therefore, using the new condition to verify the local optimality is far superior to using the traditional condition, especially when there are many active arcs.

In this paper, we present a second-order corrector infeasible interior-point method for linear optimization in a large neighborhood of the central path. The innovation of our method is to calculate the predictor directions using a specific kernel function instead of the logarithmic barrier function. We decompose the predictor direction induced by the kernel function to two orthogonal directions of the corresponding to the negative and positive component of the right-hand side vector of the centering equation. The method then considers the new point as a linear combination of these directions along with a second-order corrector direction. The convergence analysis of the proposed method is investigated and it is proved that the complexity bound is O(n 5/4 logs ε-1). [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]

In this paper, we propose an arc-search infeasible interior-point algorithm with infeasible central path wide neighborhood for semidefinite optimization. In every iteration, the algorithm uses an analytic expression of an ellipse and searches an ε -approximation solution of the problem along an ellipsoidal approximation of the infeasible central path. Based on the commutative class of scaling matrices at an iterate (X , S) ≻ (0 , 0) , we show that the algorithm has the complexity order O (n 3 2 L) to Nesterov-Todd (NT) search directions, which coincides with the results for the corresponding algorithm for linear optimization. Then, we present a simplified version of the algorithm and show that the iteration complexity bound of the algorithm is the same as the best iteration bound for feasible interior-point algorithms. [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, an improved Interior-Point Method (IPM) for solving symmetric optimization problems is presented. Symmetric optimization (SO) problems are linear optimization problems over symmetric cones. In particular, the method can be efficiently applied to an important instance of SO, a Controlled Tabular Adjustment (CTA) problem which is a method used for Statistical Disclosure Limitation (SDL) of tabular data. The presented method is a full Nesterov-Todd step infeasible IPM for SO. The algorithm converges to ε-approximate solution from any starting point whether feasible or infeasible. Each iteration consists of the feasibility step and several centering steps, however, the iterates are obtained in the wider neighborhood of the central path in comparison to the similar algorithms of this type which is the main improvement of the method. However, the currently best known iteration bound known for infeasible short-step methods is still achieved. [ABSTRACT FROM AUTHOR]

An infeasible interior-point algorithm for mixed symmetric cone linear complementarity problems is proposed. Using the machinery of Euclidean Jordan algebras and Nesterov-Todd search direction, the convergence analysis of the algorithm is shown and proved. Moreover, we obtain a polynomial time complexity bound which matches the currently best known iteration bound for infeasible interior-point methods.

Abstract In this paper, a variant of Mehrotra-type predictor–corrector algorithm is proposed for P∗(κ) $P_{*}(\kappa )$ linear complementarity problems. In this algorithm, a safeguard step is used to avoid small step sizes and a new corrector direction is adopted. The algorithm has polynomial iteration complexity and the iteration bound is O((14κ+11)(1+4κ)(1+2κ)nlog(x0)Ts0ε) $O ((14\kappa +11)\sqrt{(1+4 \kappa )(1+2\kappa )}~n\log \frac{(x^{0})^{T}s^{0}}{\varepsilon } )$. Some numerical results are reported as well.

We present a short-step interior-point algorithm (IPA) for sufficient linear complementarity problems (LCPs) based on a new search direction. An algebraic equivalent transformation (AET) is used on the centrality equation of the central path system and Newton's method is applied on this modified system. This technique was offered by Zsolt Darvay for linear optimization in 2002. Darvay first used the square root function as AET and in 2012 Darvay et al. applied this technique with an other transformation formed by the difference of the identity map and the square root function. We apply the AET technique with the new function to transform the central path equation of the sufficient LCPs. This technique leads to new search directions for the problem. We introduce an IPA with full Newton steps and prove that the iteration bound of the algorithm coincides with the best known one for sufficient LCPs. We present some numerical results to illustrate performance of the proposed IPA on two significantly different sets of test problems and compare it, with related, quite similar variants of IPAs. [ABSTRACT FROM AUTHOR]

In this paper, we propose a new predictor–corrector interior-point algorithm for semidefinite optimization based on a wide neighbourhood of the central path. We show that, in addition to the predictor step, each corrector step decreases the duality gap as well. We also prove that the iteration complexity of the proposed algorithm coincides with the best iteration bound for small neighbourhood algorithms that use the Nesterov–Todd direction. Finally, some numerical results are provided as well. [ABSTRACT FROM AUTHOR]

This paper proposes a second-order corrector infeasible interior-point method for semidefinite optimization in a large neighborhood of the central path. Our algorithm uses the Nesterov–Todd search directions as a Newton direction. We make use of the scaled Newton directions for symmetric search directions. Based on Ai and Zhang idea, we decompose the Newton directions into two orthogonal directions corresponding to positive and negative parts of the right-hand side of the Newton equation. In such a way, we use different step lengths for each of them and the corrector step is multiplied by the square of the step length of the infeasible directions in the expression of the new iterate. Starting with a point (X 0 , y 0 , S 0) in the neighborhood in terms of Frobenius norm, we show that the algorithm terminates after at most O (n 5 4 log ε - 1) iterations, improving by a factor n 1 4 results on these kinds of algorithms. We believe that this is the first infeasible interior-point algorithm in a large neighborhood, which uses a Newton direction decomposition and a second-order corrector step to improve the iteration complexity. The main difference of the proposed method comparing with the existing methods in literature is the strategy for generating corrector directions. Some preliminary numerical results are given to verify the efficiency of the algorithm. [ABSTRACT FROM AUTHOR]

In this paper, we propose a theoretical framework of a predictor-corrector interior-point method for linear optimization based on the one-norm wide neighborhood of the central path, focusing on infeasible corrector steps. Here, we call the predictor-infeasible corrector algorithm. At each iteration, the proposed algorithm computes an infeasible corrector step in addition to the Ai-Zhang search directions and considers the Newton direction as a linear combination of these directions. We represent the complexity analysis of the algorithm and conclude that its iteration bound is O (n log ε - 1) . To our knowledge, this is the best complexity result up to now for infeasible interior-point methods based on these kinds of search directions. The complexity bound obtained here is the same as small neighborhood infeasible interior point algorithms. [ABSTRACT FROM AUTHOR]

In this paper, a feasible primal-dual path-following interior-point algorithm for monotone semidefinite linear complementarity problems is proposed. At each iteration, the algorithm uses only full Nesterov-Todd feasible steps for tracing approximately the central-path and getting an approximated solution of this problem. Under a new appropriate choices of the threshold \(\tau\) which defines the size of the neighborhood of the central-path and of the update barrier parameter \(\theta\), we show that the algorithm is well-defined and enjoys the locally quadratically convergence. Moreover, we prove that the short-step algorithm deserves the best known iteration bound, namely, \(\O(\sqrt{n} log \frac{n}{\epsilon}))\). Finally, some numerical results are reported to show the practical performance of the algorithm

We present a full Nesterov-Todd (NT) step infeasible interior-point algorithm for second-order cone optimization based on a different way to calculate feasibility direction. In each iteration of the algorithm we use the largest possible barrier parameter value θ. Moreover, each main iteration of the algorithm consists of a feasibility step and a few centering steps. The feasibility step differs from the feasibility step of the other existing methods. We derive the complexity bound which coincides with the best known bound for infeasible interior point methods.

In this paper, a wide neighborhood path-following interior point algorithm for linear optimization (LO) is proposed that uses a trigonometric kernel function to get search directions. The method treats the Newton direction as the sum of two other directions, according to the negative and positive parts of the right-hand-side based on the kernel function. By choosing different and appropriate step sizes for these two directions, the iterates stop in the Ai–Zhang's wide neighborhood. By an elegant analysis, we show that the method enjoys the low iteration bound of O (n log (x 0) T s 0 ε) , where n is the dimension of the problem and (x 0 , s 0) the initial interior point with ε the required precision. In our knowledge, this result is the first instance of a wide neighborhood interior point method for LO which involving the trigonometric kernel function. [ABSTRACT FROM AUTHOR]

We propose a new large-step primal-dual second-order corrector interior-point method for linear optimization. At each iteration, our method uses the new wide neighborhood introduced by Darvay and Takács (Cent Eur J Oper Res 26(3):551–563, 2018. https://doi.org/10.1007/s10100-018-0524-0). In this paper we would like to improve the directions proposed by Darvay and Takács by adding a second-order corrector direction. The corrector step is multiplied by the square of the step length in the expression of the new iterate. To our best knowledge, this is the first primal-dual second-order corrector interior-point algorithm based on Darvay–Takács's new wide neighborhood, which has the same complexity as the best short-step algorithms for linear optimization. Finally, numerical experiments show that the proposed algorithm is efficient and reliable. [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.)