16周 Lec8 LP InteriorPoint

2020-03-01 57浏览

  • 1.
  • 2.
  • 3.
  • 4.
  • 5.
  • 6.
  • 7.min .. cT x Ax x max bT y . . AT y = ≤ = , ..., = ≥ b ≤ c ≥ = =
  • 8.min .. cT x Ax x max bT y . . AT y = ≥ b ≤ c = ≥ +σ = σ ≥ σ = + +
  • 9.⎛ ⎞ ⎛ σ ⎠, Σ = ⎝ =⎝ ⎛ σ Σ =⎝ σ ⎞⎛ ⎞ σ σ ⎛ ⎞ ⎞ ⎠ ⎞ σ ⎠⎝ ⎠ = ⎝ ⎠ = ⎝ σ ⎠ σ σ = ≥ +σ = σ ≥ Σ = ( , , σ) > ( , , σ) σ> ⎛
  • 10.(¯, ¯, σ̄) ¯ = ,¯ > ¯ + σ̄ = , σ̄ > ( ∗, (∆ , ∆ , ∆σ) ∗, σ∗) (¯, ¯, σ̄) (¯ + ∆ , ¯ + ∆ , σ̄ + ∆σ) (¯ + ∆ , ¯ + ∆ , σ̄ + ∆σ) ¯+∆ = ¯+∆ ≥ (¯ + ∆ ) + (σ̄ + ∆σ) = σ̄ + ∆σ ≥ ( ¯ + ∆ )(Σ̄ + ∆Σ) =
  • 11.(¯, ¯, σ̄) ¯ = ,¯ > ¯ + σ̄ = , σ̄ > ∆ = ¯+∆ ≥ ∆ + ∆σ = σ̄ + ∆σ ≥ ¯ ∆Σ + Σ̄∆ = − ¯ Σ̄ − ∆ ∆Σ ∆ ∆σ −∆ ∆Σ ∆ = ¯+∆ ≥ ∆ + ∆σ = σ̄ + ∆σ ≥ ¯ ∆Σ + Σ̄∆ = − ¯ Σ̄ − ¯ Σ̄ ∆σ = ¯ − (− ¯ Σ̄ − Σ̄∆ ) = −σ̄ − ¯ − Σ̄∆ % &% & % & − ¯ − Σ̄ ∆ σ̄ = ∆
  • 12.¯ ¯, σ̄ % − ¯ − Σ̄ ¯= &% ¯> ¯ + σ̄ = ∆ ∆ & = σ̄ > % & σ̄ ∆σ = ¯ − (− ¯ Σ̄ − Σ̄∆ ) = −σ̄ − ¯ − Σ̄∆ ¯ + θ∆ ≥ θ σ̄ + θ∆σ ≥ ¯ = ¯ + θ∆ ¯ = ¯ + θ∆ σ̄ = σ̄ + θ∆σ σ ≤ϵ = , ..., ( , , σ)
  • 13.min .. + . + + + ≥ ≥ ≥ ≤ ≤ ≥ ≥
  • 14.=( , =( , ) )
  • 15.
  • 16.
  • 17.
  • 18.
  • 19.Σ = Σ = ( > )
  • 20.=( , =( , ) )
  • 21.Σ = min cT x − .. ( > ) ' = log Ax = b x ≥
  • 22.min .. ( ) ( ) ( ) Ax = b ( )≤
  • 23.min .. Ax∗ = b ( P AT A 0 Px + Q x + r Ax = b P x + Q + AT λ = x∗ )( x∗ λ ) = ( −Q b )
  • 24.( ) ( ) min ( ) . . Ax = b ˜( + ∆ ) = ( ) + ▽ ( ) + ∆ ▽ ( )∆ ˜( ) min . . A(x + ∆x) = b ( ▽2 ( ) A ∆x∗ )( ) ( ) ∆x∗ −▽ ( ) = 0 λ b ( ) AT
  • 25.( ) min .. ( ) ( ) ( ) Ax = b ( )≤
  • 26.
  • 27.min .. ( ) ( ) min .. ( )= ( ) Ax = b ( )≤ * ∞ ( )+ ≤ ( ( )) Ax = b
  • 28.min .. ( ) ( ) min .. − log(− ) ( ) Ax = b ( )≤ ( )− log(− ( )) Ax = b →∞
  • 29.− log(− ) →∞
  • 30.min .. > ( )− log(− ( )) Ax = b ∗( { ∗ ( ) > } )
  • 31.min cT x . . Ax ≤ x ≥
  • 32.∗( > min .. ∗( ) ) ( )− log(− ( )) Ax = b
  • 33.