Books

Here are some books I read or currently reading.

ThePrincetonCompanionToMathematics.jpg OptimizationByVectorSpaceMethods.jpg TheoryOfGamesAndEconomicBehavior.jpg PlayingForReal.webp
ComputationalComplexity.webp ComputationalComplexityAModernApproach.jpg ElementsOfStatisticalLearning.jpg DistributedOptimizationAndStatisticalLearning.jpg
ConvexOptimization.jpg ReinforcementLearning.jpg A MATHEMATICIAN'S APOLOGY BY PROF. G. H. Hardy logicomix.png

Here are the ones I would like to read:

BookOfProof.jpg MathematicalThoughtAndItsObjects.jpg    

Examples to kindle your mathematics enthusiasm

  • The following sets have equal cardinality \(|\mathbb{N}| = |\mathbb{Z}| = |\mathbb{Q}|\)
  • Deciding whether a diophantine equation has solutions reduces to the halting problem.
  • \(\sum_{n=1}^\infty \frac{1}{n}\) diverges, but \(\sum_{n=1}^\infty \frac{1}{n^2}\) converges.
  • The triangle shaped by the North Pole as one of the vertices, together with a point on the equator, and a third quarter of the way around the equator from the first has three right angles! (the flatter it becomes, the closer the sum of the angles is to \(180^\circ\))

Optimization

Tricks

Dual problems

  • LP

    (P) LP-SEF: \(\min_x \langle c, x \rangle: A x = b, x \geq 0\) (D) LP-SEF: \(\max_y \langle b, y \rangle: ( A y + \lambda = c, \lambda \geq 0) \equiv Ay \leq c\)

  • QP
    • primal problem

      \(\min_x \frac{1}{2} x^T H x + c^T x: A x \leq b, H \succeq 0\)

    • dual problem

      \(\max_{\lambda, z} - \frac{1}{2} z^T H z - b^T \lambda : H z = - (c + A^T \lambda), \lambda \geq 0\)

  • QCQP
    • primal problem

      \(\min \frac{1}{2} x^T P_0 x + c_0^T x : \frac{1}{2} x^T P_i x + c_i^T + d_i \leq 0; i \in \{1, \cdots, m \}, m \in \mathbb{N}\)

    • dual problem (\(P\) invertible)

      \(\max -(1/2) q(\lambda)^T P(\lambda)^{-1} q(\lambda) + r(\lambda) : \lambda \succeq 0\)

    • dual problem (\(P\) not invertible)

      \(\max_{\gamma, \lambda} - \gamma + d^T \lambda : \begin{pmatrix} P_0 + \sum_{i=1}^m \lambda_i P_i & c_0 + \sum_{i=1}^m \lambda_i c_i \\ c_0^T + \sum_{i=1}^m \lambda_i c_i^T & \gamma \end{pmatrix} \succeq 0\)

  • SOCP
    • primal problem

      \(\min_x c^T x : A x = b, x \in C_2^{k_1} \times \cdots \times C_2^{k_n}\)

      linear objective, equality constraints, single second order cone constraint.

  • SDP
    • primal problem

      SDP: \(\min_X \langle C, X \rangle: \langle A_i, X \rangle= b_i, X \in \mathbb{S}^n_+, C_, A_i \in \mathbb{S}^n, b \in \mathbb{R}^n\)

  • SCF
    • primal problem

      \(\min_x c^T x : A x = b; x \in K\)
      \(\left(\text{SOCP: } K = C_2^{k_1} \times \cdots \times C_2^{k_n}; \text{SDP: }K = \mathbb{S}^n_+ \right)\)

    • dual problem

      \(\max_{y} - b^T \nu : c - \lambda + A^T \nu = 0, \lambda \succeq_{K^\ast} 0 \equiv c - A^Ty \succeq_{K^\ast} 0\) or (\(y = -\nu\)) \(\max_{y} b^T y : c - A^T y \succeq_{K^\ast} 0\) (\(X \in \mathbb{S}^n_+\) can be rewritten \(X \in \mathbb{S}^n \wedge \lambda_{\max} (-X) \leq 0\))

Formulation

\[LP \subseteq QP \subseteq QCQP \subseteq SOCP \subseteq SDP\]

  • QP \(\to\) LP: \(H = 0\).
  • QCQP \(\to\) QP: \(P_i = 0\)
  • QCQP \(\to\) SOCP

    \(\left\lVert \begin{pmatrix} \frac{1}{\sqrt{2}} G x \\ d - \langle p, x \rangle \\ \frac{1}{2} \end{pmatrix} \right\lVert \leq d - \langle p, x \rangle+ \frac{1}{2}\),

    e.g., \(||u - u_0||^2 \leq s \Leftrightarrow \left\lVert\begin{pmatrix} u - u_0 \\ s \\ 1/2 \end{pmatrix}\right\lVert \leq s + 1/2\)

  • SOCP \(\to\) SDP

    \(||x|| \leq t \Leftrightarrow \begin{pmatrix} t & x^T \\ x & t I_n \end{pmatrix} \succeq 0\)

Game Theory

History

2005-Present

  • 2007: “The Sveriges Riksbank Prize in Economic Sciences in Memory of Alfred Nobel 2007 was awarded jointly to Leonid Hurwicz, Eric S. Maskin and Roger B. Myerson ‘for having laid the foundations of mechanism design theory’.”
  • 2012: “The Sveriges Riksbank Prize in Economic Sciences in Memory of Alfred Nobel 2012 was awarded jointly to Alvin E. Roth and Lloyd S. Shapley ‘for the theory of stable allocations and the practice of market design’.”

Combinatorial Game Theory

Why Mathematica?

Table 1: The cyclic projections algorithm applied to a bundle of hyperplanes, where all pass through a common point.
hyperplanes1.png hyperplanes2.png hyperplanes3.png
hyperplanes4.png hyperplanes5.png hyperplanes6.png

♚

I maintain this webpage using Org mode version 9.7.1 and magit version 20241126.1900 (commit id #1ba074f) on Emacs 29 and gnu/linux