This is the 17th day of my participation in the Novembermore Challenge.The final text challenge in 2021

title: date: 2020-12-15 23:51:25 tags: [Machine_Learning] categories: [Machine_Learning] mathjax: true

After determining the type of quadratic that can be optimized, the optimization method of quadratic is discussed in this paper.

The current problem

  • Solving equations Ax = b \ bf = \ bf {b} {Ax} Ax = b

  • Where A\bf{A}A is A semidefinite matrix

  • The rank of A\bf{A}A is equal to that of its augmented matrix Ab\bf{Ab}Ab

An optimization method

Algebraic method

Gaussian elimination

  • When the determinant of A\bf{A}A is not 0, the half-side coefficients can be eliminated term by term to get the triangular matrix, xnx_nxn can be calculated and then the other unknowns can be calculated step by step to get the calculation result.
\begin{equation} \begin{split} {a_{11}}{x_1} + {a_{12}}{x_2} + \cdots {a_{1n}}{x_n} = {b_1}\\\\ {a_{22}}{x_2} + \cdots {a_{2n}}{x_n} = {b_2}\\\\ \vdots \\\\ {a_{nn}}{x_n} = {b_n} \end{split} \end{equation}
  • Other algebraic methods are improved on the basis of Gaussian elimination method

Gauss principal element elimination method

  • In order to solve the problem that the accuracy is not enough when the principal element is 0 or the absolute value of the principal element is too small, the principal element elimination is proposed
  • The core idea is to select the row with the largest absolute value of coefficient as the benchmark for elimination, which can effectively alleviate the above problems

Matrix inversion

  • For the case of invertible matrix A\bf{A}A, the inverse matrix of A\bf{A}A can be directly calculated, then:

x = A – 1 b {\bf{x}} = {\bf{A^{-1}}}{\bf{b}}

Iterative method

The time complexity of algebraic methods is on the order of O(N3)O(N ^3)O(N3), which is unacceptable in practice.

The idea of iterative method is that the local optimal solution can be calculated greedy each time, and gradually approach the global optimal solution

Steepest descent method/gradient method

  • Proceed in the opposite direction of the current gradient until the directional gradient is 0, recalculate the current gradient, and start again
  • The process is repeated until the desired accuracy is met

Conjugate gradient method

  • The magnitude of the component of the conjugate base advancing along the conjugate gradient
  • The global optimal solution can be obtained by repeating the above operations on all conjugate bases

Then we will focus on the iterative method