Source author record

Bahman Kalantari

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Catalog footprint

Research overview

19works
11topics
4close collaborators

Published work

19 publications

preprint2023arXiv

Approximating Bimatrix Nash Equilibrium Via Trilinear Minimax

The Bimatrix Nash Equilibrium (NE) for m×nm \times n real matrices RR and CC, denoted as the {\it Row} and {\it Column} players, is characterized as follows: Let Δ=Sm×SnΔ=S_m \times S_n, where SkS_k denotes the unit simplex in Rk\mathbb{R}^k. For a given point p=(x,y)∈Δp=(x,y) \in Δ, define R[p]=xTRyR[p]=x^TRy and C[p]=xTCyC[p]=x^TCy. Consequently, there exists a subset Δ∗⊂ΔΔ_* \subset Δ such that for any p∗=(x∗,y∗)∈Δ∗p_*=(x_*,y_*) \in Δ_*, max⁡p∈Δ,y=y∗R[p]=R[p∗]\max_{p \in Δ, y=y_*}R[p]=R[p_*] and max⁡p∈Δ,x=x∗C[p]=C[p∗]\max_{p \in Δ, x=x_* } C[p]=C[p_*]. The computational complexity of bimatrix NE falls within the class of {\it PPAD-complete}. Although the von Neumann Minimax Theorem is a special case of bimatrix NE, we introduce a novel extension termed {\it Trilinear Minimax Relaxation} (TMR) with the following implications: Let λ∗=min⁡α∈S2max⁡p∈Δ(α1R[p]+α2C[p])λ^*=\min_{α\in S_{2}} \max_{p \in Δ} (α_1 R[p]+ α_2C[p]) and λ∗=max⁡p∈Δmin⁡α∈S2(α1R[p]+α2C[p])λ_*=\max_{p \in Δ} \min_{α\in S_{2}} (α_1 R[p]+ α_2C[p]). λ∗≥λ∗λ^* \geq λ_*. λ∗λ^* is computable as a linear programming in O(mn)O(mn) time, ensuring max⁡p∗∈Δ∗min⁡{R[p∗],C[p∗]}≤λ∗\max_{p_* \in Δ_*}\min \{R[p_*], C[p_*]\} \leq λ^*, meaning that in any Nash Equilibrium it is not possible to have both players' payoffs to exceed λ∗λ^*. λ∗=λ∗λ^*=λ_* if and only if there exists p∗∈Δp^* \in Δ such that λ∗=min⁡{R[p∗],C[p∗]}λ^*= \min\{R[p^*], C[p^*]\}. Such a p∗p^* serves as an approximate Nash Equilibrium. We analyze the cases where such p∗p^* exists and is computable. Even when λ∗>λ∗λ^* > λ_*, we derive approximate Nash Equilibria. In summary, the aforementioned properties of TMR and its efficient computational aspects underscore its significance and relevance for Nash Equilibrium, irrespective of the computational complexity associated with bimatrix Nash Equilibrium. Finally, we extend TMR to scenarios involving three or more players.

preprint2023arXiv

Approximating Nash Equilibrium Via Multilinear Minimax

Nash equilibrium} (NE) can be stated as a formal theorem on a multilinear form, free of game theory terminology. On the other hand, inspired by this formalism, we state and prove a {\it multilinear minimax theorem}, a generalization of von Neumann's bilinear minimax theorem. As in the bilinear case, the proof is based on relating the underlying optimizations to a primal-dual pair of linear programming problems, albeit more complicated LPs. The theorem together with its proof is of independent interest. Next, we use the theorem to associate to a multilinear form in NE a {\it multilinear minimax relaxation} (MMR), where the primal-dual pair of solutions induce an approximate equilibrium point that provides a nontrivial upper bound on a convex combination of {\it expected payoffs} in any NE solution. In fact we show any positive probability vector associated to the players induces a corresponding {\it diagonally-scaled} MMR approximate equilibrium with its associated upper bound. By virtue of the proof of the multilinear minimax theorem, MMR solution can be computed in polynomial-time. On the other hand, it is known that even in bimatrix games NE is {\it PPAD-complete}, a complexity class in NP not known to be in P. The quality of MMR solution and the efficiency of solving the underlying LPs are the subject of further investigation. However, as shown in a separate article, for a large set of test problems in bimatrix games, not only the MMR payoffs for both players are better than any NE payoffs, so is the computing time of MMR in contrast with that of Lemke-Howsen algorithm. In large size problems the latter algorithm even fails to produce a Nash equilibrium. In summary, solving MMR provides a worthy approximation even if Nash equilibrium is shown to be computable in polynomial-time.

preprint2022arXiv

On Tusi's Classification of Cubic Equations and its Connections to Cardano's Formula and Khayyam's Geometric Solution

Omar Khayyam's studies on cubic equations inspired the 12th century Persian mathematician Sharaf al-Din Tusi to investigate the number of positive roots. According to the noted mathematical historian Rashed, Tusi analyzed the problem for five different types of equations. In fact all cubic equations are reducible to a form {\it Tusi form} x2−x3=cx^2-x^3=c. Tusi determined that the maximum of x2−x3x^2-x^3 on (0,1)(0,1) occurs at 23\frac{2}{3} and concluded when c=427δc=\frac{4}{27} δ, δ∈(0,1)δ\in (0,1), there are roots in (0,23)(0, \frac{2}{3}) and (23,1)(\frac{2}{3},1), ignoring the root in (−13,0)(-\frac{1}{3},0). Given a {\it reduced form} x3+px+q=0x^3+px+q=0, when p<0p <0, we show it is reducible to a Tusi form with δ=12+33q/4−p3δ= \frac{1}{2} + {3\sqrt{3} q}/{4\sqrt{-p^3}}. It follows there are three real roots if and only if Δ=−(q24+p327)Δ=-(\frac{q^2}{4}+\frac{p^3}{27}) is positive. This gives an explicit connection between δδ in Tusi form and ΔΔ in Cardano's formula. Thus when δ∈(0,1)δ\in (0,1), rather than using Cardano's formula in complex numbers one can approximate the roots iteratively. On the other hand, for a reduced form with p>0p >0 we give a novel proof of Cardono's formula. While Rashed attributes Tusi's computation of the maximum to the use of derivatives, according to Hogendijk, Tusi was probably influenced by Euclid. Here we show the maximizer in Tusi form is computable via elementary algebraic manipulations. Indeed for a {\it quadratic Tusi form}, x−x2=δ/4x-x^2=δ/4, Tusi's approach results in a simple derivation of the quadratic formula, comparable with the pedagogical approach of Po-Shen Loh. Moreover, we derive analogous results for the {\it general Tusi form}. Finally, we present a novel derivation of Khayyam's geometric solution. The results complement previous findings on Tusi's work and reveal further facts on history, mathematics and pedagogy in solving cubic equations.

preprint2020arXiv

A Geometric Algorithm for Solving Linear Systems

Based on the geometric {\it Triangle Algorithm} for testing membership of a point in a convex set, we present a novel iterative algorithm for testing the solvability of a real linear system Ax=bAx=b, where AA is an m×nm \times n matrix of arbitrary rank. Let CA,rC_{A,r} be the ellipsoid determined as the image of the Euclidean ball of radius rr under the linear map AA. The basic procedure in our algorithm computes a point in CA,rC_{A,r} that is either within ε\varepsilon distance to bb, or acts as a certificate proving b∉CA,rb \not \in C_{A,r}. Each iteration takes O(mn)O(mn) operations and when bb is well-situated in CA,rC_{A,r}, the number of iterations is proportional to log⁡(1/ε)\log{(1/\varepsilon)}. If Ax=bAx=b is solvable the algorithm computes an approximate solution or the minimum-norm solution. Otherwise, it computes a certificate to unsolvability, or the minimum-norm least-squares solution. It is also applicable to complex input. In a computational comparison with the state-of-the-art algorithm BiCGSTAB ({\it Bi-conjugate gradient method stabilized}), the Triangle Algorithm is very competitive. In fact, when the iterates of BiCGSTAB do not converge, our algorithm can verify Ax=bAx=b is unsolvable and approximate the minimum-norm least-squares solution. The Triangle Algorithm is robust, simple to implement, and requires no preconditioner, making it attractive to practitioners, as well as researchers and educators.

preprint2020arXiv

A Globally Convergent Newton Method for Polynomials

Newton's method for polynomial root finding is one of mathematics' most well-known algorithms. The method also has its shortcomings: it is undefined at critical points, it could exhibit chaotic behavior and is only guaranteed to converge locally. Based on the {\it Geometric Modulus Principle} for a complex polynomial p(z)p(z), together with a {\it Modulus Reduction Theorem} proved here, we develop the {\it Robust Newton's method} (RNM), defined everywhere with a step-size that guarantees an {\it a priori} reduction in polynomial modulus in each iteration. Furthermore, we prove RNM iterates converge globally, either to a root or a critical point. Specifically, given ε\varepsilon and any seed z0z_0, in t=O(1/ε2)t=O(1/\varepsilon^{2}) iterations of RNM, independent of degree of p(z)p(z), either ∣p(zt)∣≤ε|p(z_t)| \leq \varepsilon or ∣p(zt)p′(zt)∣≤ε|p(z_t) p'(z_t)| \leq \varepsilon. By adjusting the iterates at {\it near-critical points}, we describe a {\it modified} RNM that necessarily convergence to a root. In combination with Smale's point estimation, RNM results in a globally convergent Newton's method having a locally quadratic rate. We present sample polynomiographs that demonstrate how in contrast with Newton's method RNM smooths out the fractal boundaries of basins of attraction of roots. RNM also finds potentials in computing all roots of arbitrary degree polynomials. A particular consequence of RNM is a simple algorithm for solving cubic equations.

preprint2020arXiv

Collatz polynomials: an introduction with bounds on their zeros

The Collatz Conjecture (also known as the 3x+1 Problem) proposes that the following algorithm will, after a certain number of iterations, always yield the number 1: given a natural number, multiply by three and add one if the number is odd, halve the resulting number, then repeat. In this article, for each NN for which the Collatz Conjecture holds we define the NthN^{th} Collatz polynomial to be the monic polynomial with constant term NN and kthk^{th} term (for k>1k > 1) the kthk^{th} iterate of NN under the Collatz function. In particular, we bound the moduli of the roots of these polynomials, prove theorems on when they have rational integer roots, and suggest further applications and avenues of research.

preprint2020arXiv

On the Equivalence of SDP Feasibility and a Convex Hull Relaxation for System of Quadratic Equations

We show {\it semidefinite programming} (SDP) feasibility problem is equivalent to solving a {\it convex hull relaxation} (CHR) for a finite system of quadratic equations. On the one hand, this offers a simple description of SDP. On the other hand, this equivalence makes it possible to describe a version of the {\it Triangle Algorithm} for SDP feasibility based on solving CHR. Specifically, the Triangle Algorithm either computes an approximation to the least-norm feasible solution of SDP, or using its {\it distance duality}, provides a separation when no solution within a prescribed norm exists. The worst-case complexity of each iteration is computing the largest eigenvalue of a symmetric matrix arising in that iteration. Alternate complexity bounds on the total number of iterations can be derived. The Triangle Algorithm thus provides an alternative to the existing interior-point algorithms for SDP feasibility and SDP optimization. In particular, based on a preliminary computational result, we can efficiently solve SDP relaxation of {\it binary quadratic} feasibility via the Triangle Algorithm. This finds application in solving SDP relaxation of MAX-CUT. We also show in the case of testing the feasibility of a system of convex quadratic inequalities, the problem is reducible to a corresponding CHR, where the worst-case complexity of each iteration via the Triangle Algorithm is solving a {\it trust region subproblem}. Gaining from these results, we discuss potential extension of CHR and the Triangle Algorithm to solving general system of polynomial equations.

preprint2016arXiv

A Comparison of the Triangle Algorithm and SMO for Solving the Hard Margin Problem

In this article we consider the problem of testing, for two finite sets of points in the Euclidean space, if their convex hulls are disjoint and computing an optimal supporting hyperplane if so. This is a fundamental problem of classification in machine learning known as the hard-margin SVM. The problem can be formulated as a quadratic programming problem. The SMO algorithm is the current state of art algorithm for solving it, but it does not answer the question of separability. An alternative to solving both problems is the Triangle Algorithm, a geometrically inspired algorithm, initially described for the convex hull membership problem, a fundamental problem in linear programming. First, we describe the experimental performance of the Triangle Algorithm for testing the intersection of two convex hulls. Next, we compare the performance of Triangle Algorithm with SMO for finding the optimal supporting hyperplane. Based on experimental results ranging up to 5000 points in each set in dimensions up to 10000, the Triangle Algorithm outperforms SMO.

preprint2016arXiv

A Necessary and Sufficient Condition for Local Maxima of Polynomial Modulus Over Unit Disc

An important quantity associated with a complex polynomial p(z)p(z) is ∥p∥∞\Vert p \Vert_\infty, the maximum of its modulus over the unit disc DD. We prove, z∗∈Dz_* \in D is a local maximum of ∣p(z)∣|p(z)| if and only if a∗a_* satisfies, z∗=p(z∗)∣p′(z∗)∣/p′(z∗)∣p(z∗)∣z_*=p(z_*)|p'(z_*)|/p'(z_*)|p(z_*)|, i.e. it is proportional to its corresponding Newton direction. This explicit formula gives rise to novel iterative algorithms for computing ∥p∥∞\Vert p \Vert_\infty. We describe two such algorithms, including a Newton-like method and present some visualization of their performance.

preprint2016arXiv

An Algorithmic Separating Hyperplane Theorem and Its Applications

We first prove a new separating hyperplane theorem characterizing when a pair of compact convex subsets K,K′K, K' of the Euclidean space intersect, and when they are disjoint. The theorem is distinct from classical separation theorems. It generalizes the {\it distance duality} proved in our earlier work for testing the membership of a distinguished point in the convex hull of a finite point set. Next by utilizing the theorem, we develop a substantially generalized and stronger version of the {\it Triangle Algorithm} introduced in the previous work to perform any of the following three tasks: (1) To compute a pair (p,p′)∈K×K′(p,p') \in K \times K', where either the Euclidean distance d(p,p′)d(p,p') is to within a prescribed tolerance, or the orthogonal bisecting hyperplane of the line segment pp′pp' separates the two sets; (2) When KK and K′K' are disjoint, to compute (p,p′)∈K×K′(p,p') \in K \times K' so that d(p,p′)d(p,p') approximates d(K,K′)d(K,K') to within a prescribed tolerance; (3) When KK and K′K' are disjoint, to compute a pair of parallel supporting hyperplanes H,H′H,H' so that d(H,H′)d(H,H') is to within a prescribed tolerance of the optimal margin. The worst-case complexity of each iteration is solving a linear objective over KK or K′K'. The resulting algorithm is a fully polynomial-time approximation scheme for such important special cases as when KK and K′K' are convex hulls of finite points sets, or the intersection of a finite number of halfspaces. The results find many theoretical and practical applications, such as in machine learning, statistics, linear, quadratic and convex programming. In particular, in a separate article we report on a comparison of the Triangle Algorithm and SMO for solving the hard margin problem. In future work we extend the applications to combinatorial and NP-complete problems.

preprint2014arXiv

A One-Line Proof of the Fundamental Theorem of Algebra with Newton's Method as a Consequence

Many proofs of the fundamental theorem of algebra rely on the fact that the minimum of the modulus of a complex polynomial over the complex plane is attained at some complex number. The proof then follows by arguing the minimum value is zero. This can be done by proving that at any complex number that is not a zero of the polynomial we can exhibit a direction of descent for the modulus. In this note we present a very short and simple proof of the existence of such descent direction. In particular, our descent direction gives rise to Newton's method for solving a polynomial equation via modulus minimization and also makes the iterates definable at any critical point.

preprint2014arXiv

Algorithms and Polynomiography for Solving Quaternion Quadratic Equations

Solving a quadratic equation P(x)=ax2+bx+c=0P(x)=ax^2+bx+c=0 with real coefficients is known to middle school students. Solving the equation over the quaternions is not straightforward. Huang and So \cite{Huang} give a complete set of formulas, breaking it into several cases depending on the coefficients. From a result of the second author in \cite{kalQ}, zeros of P(x)P(x) can be expressed in terms of the zeros of a real quartic equation. This drastically simplifies solving a quadratic equation. Here we also consider solving P(x)=0P(x)=0 iteratively via Newton and Halley methods developed in \cite{kalQ}. We prove a property of the Jacobian of Newton and Halley methods and describe several 2D polynomiography based on these methods. The images not only encode the outcome of the iterative process, but by measuring the time taken to render them we find the relative speed of convergence for the methods.

preprint2014arXiv

Fast Approximation and Randomized Algorithms for Diameter

We consider approximation of diameter of a set SS of nn points in dimension mm. Eg~\tilde{g}eciog~\tilde{g}lu and Kalantari \cite{kal} have shown that given any p∈Sp \in S, by computing its farthest in SS, say qq, and in turn the farthest point of qq, say q′q', we have diam(S)≤3d(q,q′){\rm diam}(S) \leq \sqrt{3} d(q,q'). Furthermore, iteratively replacing pp with an appropriately selected point on the line segment pqpq, in at most t≤nt \leq n additional iterations, the constant bound factor is improved to c∗=5−23≈1.24c_*=\sqrt{5-2\sqrt{3}} \approx 1.24. Here we prove when m=2m=2, t=1t=1. This suggests in practice a few iterations may produce good solutions in any dimension. Here we also propose a randomized version and present large scale computational results with these algorithm for arbitrary mm. The algorithms outperform many existing algorithms. On sets of data as large as 1,000,0001,000,000 points, the proposed algorithms compute solutions to within an absolute error of 10−410^{-4}.

preprint2014arXiv

Newton-Ellipsoid Method and its Polynomiography

We introduce a new iterative root-finding method for complex polynomials, dubbed {\it Newton-Ellipsoid} method. It is inspired by the Ellipsoid method, a classical method in optimization, and a property of Newton's Method derived in \cite{kalFTA}, according to which at each complex number a half-space can be found containing a root. Newton-Ellipsoid method combines this property, bounds on zeros, together with the plane-cutting properties of the Ellipsoid Method. We present computational results for several examples, as well as corresponding polynomiography. Polynomiography refers to algorithmic visualization of root-finding. Newton's method is the first member of the infinite family of iterations, the {\it basic family}. We also consider general versions of this ellipsoid approach where Newton's method is replaced by a higher-order member of the family such as Halley's method.

preprint2014arXiv

Randomized Triangle Algorithms for Convex Hull Membership

We present randomized versions of the {\it triangle algorithm} introduced in \cite{kal14}. The triangle algorithm tests membership of a distinguished point p∈Rmp \in \mathbb{R} ^m in the convex hull of a given set SS of nn points in Rm\mathbb{R}^m. Given any {\it iterate} p′∈conv(S)p' \in conv(S), it searches for a {\it pivot}, a point v∈Sv \in S so that d(p′,v)≥d(p,v)d(p',v) \geq d(p,v). It replaces p′p' with the point on the line segment p′vp'v closest to pp and repeats this process. If a pivot does not exist, p′p' certifies that p∉conv(S)p \not \in conv(S). Here we propose two random variations of the triangle algorithm that allow relaxed steps so as to take more effective steps possible in subsequent iterations. One is inspired by the {\it chaos game} known to result in the Sierpinski triangle. The incentive is that randomized iterates together with a property of Sierpinski triangle would result in effective pivots. Bounds on their expected complexity coincides with those of the deterministic version derived in \cite{kal14}.

preprint2014arXiv

Solving Cubic Equations By the Quadratic Formula

Let p(z)p(z) be a monic cubic complex polynomial with distinct roots and distinct critical points. We say a critical point has the {\it Voronoi property} if it lies in the Voronoi cell of a root θθ, V(θ)V(θ), i.e. the set of points that are closer to θθ than to the other roots. We prove at least one critical point has the Voronoi property and characterize the cases when both satisfy this property. It is known that for any ξ∈V(θ)ξ\in V(θ), the sequence Bm(ξ)=ξ−p(ξ)dm−2/dm−1B_m(ξ) =ξ- p(ξ) d_{m-2}/d_{m-1} converges to θθ, where dmd_m satisfies the recurrence dm=p′(ξ)dm−1−0.5p(ξ)p′′(ξ)dm−2+p2(ξ)dm−3d_m =p'(ξ)d_{m-1}-0.5 p(ξ)p''(ξ)d_{m-2} +p^2(ξ)d_{m-3}, d0=1,d−1=d−2=0d_0 =1, d_{-1}=d_{-2}=0. Thus by the Voronoi property, there is a solution cc of p′(z)=0p'(z)=0 where Bm(c)B_m(c) converges to a root of p(z)p(z). The speed of convergence is dependent on the ratio of the distances between cc and the closest and the second closest roots of p(z)p(z). This results in a different algorithm for solving a cubic equation than the classical methods. We give polynomiography for an example.

preprint2013arXiv

A Characterization Theorem and An Algorithm for A Convex Hull Problem

Given S={v1,…,vn}⊂RmS= \{v_1, \dots, v_n\} \subset \mathbb{R} ^m and p∈Rmp \in \mathbb{R} ^m, testing if p∈conv(S)p \in conv(S), the convex hull of SS, is a fundamental problem in computational geometry and linear programming. First, we prove a Euclidean {\it distance duality}, distinct from classical separation theorems such as Farkas Lemma: pp lies in conv(S)conv(S) if and only if for each p′∈conv(S)p' \in conv(S) there exists a {\it pivot}, vj∈Sv_j \in S satisfying d(p′,vj)≥d(p,vj)d(p',v_j) \geq d(p,v_j). Equivalently, p∉conv(S)p \not \in conv(S) if and only if there exists a {\it witness}, p′∈conv(S)p' \in conv(S) whose Voronoi cell relative to pp contains SS. A witness separates pp from conv(S)conv(S) and approximate d(p,conv(S))d(p, conv(S)) to within a factor of two. Next, we describe the {\it Triangle Algorithm}: given ε∈(0,1)ε\in (0,1), an {\it iterate}, p′∈conv(S)p' \in conv(S), and v∈Sv \in S, if d(p,p′)<εd(p,v)d(p, p') < εd(p,v), it stops. Otherwise, if there exists a pivot vjv_j, it replace vv with vjv_j and p′p' with the projection of pp onto the line p′vjp'v_j. Repeating this process, the algorithm terminates in O(mnmin⁡{ε−2,c−1ln⁡ε−1})O(mn \min \{ε^{-2}, c^{-1}\ln ε^{-1} \}) arithmetic operations, where cc is the {\it visibility factor}, a constant satisfying c≥ε2c \geq ε^2 and sin⁡(∠pp′vj)≤1/1+c\sin (\angle pp'v_j) \leq 1/\sqrt{1+c}, over all iterates p′p'. Additionally, (i) we prove a {\it strict distance duality} and a related minimax theorem, resulting in more effective pivots; (ii) describe O(mnln⁡ε−1)O(mn \ln ε^{-1})-time algorithms that may compute a witness or a good approximate solution; (iii) prove {\it generalized distance duality} and describe a corresponding generalized Triangle Algorithm; (iv) prove a {\it sensitivity theorem} to analyze the complexity of solving LP feasibility via the Triangle Algorithm. The Triangle Algorithm is practical and competitive with the simplex method, sparse greedy approximation and first-order methods.

preprint2012arXiv

Solving Linear System of Equations Via A Convex Hull Algorithm

We present new iterative algorithms for solving a square linear system Ax=bAx=b in dimension nn by employing the {\it Triangle Algorithm} \cite{kal12}, a fully polynomial-time approximation scheme for testing if the convex hull of a finite set of points in a Euclidean space contains a given point. By converting Ax=bAx=b into a convex hull problem and solving via the Triangle Algorithm, together with a {\it sensitivity theorem}, we compute in O(n2ε−2)O(n^2ε^{-2}) arithmetic operations an approximate solution satisfying ∥Axε−b∥≤ερ\Vert Ax_ε- b \Vert \leq ερ, where ρ=max⁡{∥a1∥,...,∥an∥,∥b∥}ρ= \max \{\Vert a_1 \Vert,..., \Vert a_n \Vert, \Vert b \Vert \}, and aia_i is the ii-th column of AA. In another approach we apply the Triangle Algorithm incrementally, solving a sequence of convex hull problems while repeatedly employing a {\it distance duality}. The simplicity and theoretical complexity bounds of the proposed algorithms, requiring no structural restrictions on the matrix AA, suggest their potential practicality, offering alternatives to the existing exact and iterative methods, especially for large scale linear systems. The assessment of computational performance however is the subject of future experimentations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.