Search

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 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.

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]

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]

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.

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]

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.

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.

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, we present a full-Newton step feasible interior-point algorithm for a P∗(κ) linear complementarity problem based on a new search direction. We apply a vector-valued function generated by a univariate function on nonlinear equations of the system which defines the central path. Furthermore, we derive the iteration bound for the algorithm, which coincides with the best-known iteration bound for these types of algorithms. Numerical results show that the proposed algorithm is competitive and reliable.

An arc search interior-point algorithm for monotone symmetric cone linear complementarity problem is presented. The algorithm estimates the central path by an ellipse and follows an ellipsoidal approximation of the central path to reach an ε-approximate solution of the problem in a wide neighborhood of the central path. The convergence analysis of the algorithm is derived. Furthermore, we prove that the algorithm has the complexity bound O (√rL) using Nesterov-Todd search direction and O (√rL) by the xs and sx search directions. The obtained iteration complexities coincide with the best-known ones obtained by any proposed interior-point algorithm for this class of mathematical problems.

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.

In this paper, we propose a large-update interior-point algorithm for linear optimization based on a new kernel function. New search directions and proximity measure are defined based on this kernel function. We show that if a strictly feasible starting point is available, then the new algorithm has O(3/4log n/ε) iteration complexity.

An arc search interior-point algorithm for monotone symmetric cone linear complementarity problem is presented. The algorithm estimates the central path by an ellipse and follows an ellipsoidal approximation of the central path to reach an "-approximate solution of the problem in a wide neighborhood of the central path. The convergence analysis of the algorithm is derived. Furthermore, we prove that the algorithm has the complexity bound O √rL) using Nesterov-Todd search direction and O (rL) by the xs and sx search directions. The obtained iteration complexities coincide with the best-known ones obtained by any proposed interior-point algorithm for this class of mathematical problems. [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 o(√rlogrμ/ε), where r is the rank of Euclidean Jordan algebra.

In this paper, we propose an infeasible interior-point algorithm for linear complementarity problems. In every iteration, the algorithm constructs an ellipse and searches an $$\varepsilon $$ -approximate solution of the problem along the ellipsoidal approximation of the central path. The theoretical iteration-complexity of the algorithm is derived and the algorithm is proved to be polynomial with the complexity bound $$O\left(n\log \varepsilon ^{-1}\right)$$ which coincides with the best known iteration bound for infeasible interior-point methods. [ABSTRACT FROM AUTHOR]

This paper proposes a second-order Mehrotra-type predictor-corrector feasible interior-point algorithm for semidefinite optimization problems. In each iteration, the algorithm computes the Newton search directions through a new form of combination of the predictor and corrector directions. Using the Ai-Zhang wide neighborhood for linear complementarity problems, it is shown that the complexity bound of the algorithm is O (√n log ∈-1) for the Nesterov-Todd search direction and O (n log ∈-1) for the Helmberg-Kojima-Monteiro search directions. [ABSTRACT FROM AUTHOR]

We present an improved version of a full Nesterov-Todd step infeasible interior-point method for linear complementarity problem over symmetric cone (Bull. Iranian Math. Soc., 40, (2014), no. 3, 541-564). In the earlier version, each iteration consisted of one so-called feasibility step and a few -at most three - centering steps. Here, each iteration consists of only a feasibility step. Thus, the new algorithm demands less work in each iteration and admits a simple analysis of complexity bound. The complexity result coincides with the best-known iteration bound for infeasible interior-point methods. [ABSTRACT FROM AUTHOR]

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

We present an interior point method for Cartesian P*(k)-Linear Complementarity Problems over Symmetric Cones (SCLCPs). The Cartesian P*(k)-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 function 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 leads to a very good complexity results for the method. For some specific eligilbe 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.

We show that Sleptsov place–transition nets (that allow transition firing in multiple instances at a step) run fast by implementing multiplication and division operations in polynomial time. In comparison, Petri nets (PNs) implement the mentioned operations in exponential time. Moreover, PNs are obtained as a special case of Sleptsov nets (SNs) using loops with places having unit marking attached to each transition. In addition, we develop basics of an SN programming technology including basic operations and program composition rules. We provide examples of programs written in SN language for encryption/decryption with the RSA algorithm, calculation of fuzzy logic functions, and parallel calculation of the solutions to Laplace equations. SN computers promise hyper-performance because of a concurrent programming style consisting of a concise graphical language and small granulation of parallel processes on the level of separate events. [ABSTRACT FROM PUBLISHER]

Inspector problem represents an economic duel of inspector and law violator and is formulated as a bimatrix game. In general, bimatrix game is NP-complete problem. The inspector problem is a special case where the equilibrium can be found in polynomial time. In this paper, a generalized version of the Inspector Problem is described with the aim to represent broader family of applied problems, including the optimization of security systems. The explicit solution is provided and the Modified Strategy Elimination algorithm is introduced.

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 paper, we present a new full step infeasible interior- point algorithm for the Cartesian P*(κ) linear complementarity problem over second-order cones. The algorithm uses only full Nesterov and Todd steps. Each (main) iteration of the algorithm consists of one so-called feasibility step and only one centering step. The algorithm starts with a strictly feasible point of a perturbed problem, after an iteration, the new iterate is still strictly feasible of the new perturbed problem. The algorithm has the same complexity as the best known infeasible interior- point methods. [ABSTRACT FROM AUTHOR]

Coupled tasks are two-operation tasks, where the two operations are separated by a time interval of fixed duration. Coupled task scheduling problems refer then to the scheduling of a set of coupled tasks on a single machine. Applications of these problems, reported in the literature, arise in connection with radar systems, robotic cells, and in manufacturing. Most of the complexity issues for scheduling coupled tasks have been settled. However, the complexity status has been unknown for the identical coupled task problem, where multiple copies of a single coupled task are to be processed. The purpose of the article is to solve this open problem in the cyclic case, for which we prove the polynomial complexity. [ABSTRACT FROM AUTHOR]

A P*-Nonlinear Complementarity Problem as a generalization of the P*-Linear Complementarity Problem is considered. We show that the long-step version of the homogeneous self-dual interior-point algorithm could be used to solve such a problem. The algorithm achieves linear global convergence and quadratic local convergence under the following assumptions: the function satisfies a modified scaled Lipschitz condition, the problem has a strictly complementary solution, and certain submatrix of the Jacobian is nonsingular on some compact set.

Recently, Roos proposed a full-Newton step infeasible interior- point method (IIPM) for solving linear optimization (LO) problems. Later on, more variants of this algorithm were published. However, each main step of these methods is composed of one feasibility step and several centering steps. The purpose of this paper is to prove that by using a new search direction it is enough to take only one centering step in order to ob- tain a polynomial-time method. This algorithm has the same complexity as the best known IIPMs. [ABSTRACT FROM AUTHOR]

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]

A novel primal-dual path-following interior-point algorithm for the Cartesian P*(κ)-linear complementarity problem over symmetric cones is presented. The algorithm is based on a reformulation of the central path for finding the search directions. For a full Nesterov-Todd step feasible interior-point algorithm based on the new search directions, the complexity bound of the algorithm with small-update approach is the best-available bound. [ABSTRACT FROM AUTHOR]