General formulation

Some necessary or\and sufficient conditions are known (See Optimality conditions. KKT and Convex optimization problem)

  • In fact, there might be very challenging to recognize the convenient form of optimization problem.
  • Analytical solution of KKT could be inviable

Iterative methods

Typically, the methods generate an infinite sequence of approximate solutions

which for a finite number of steps (or better - time) converges to an optimal (at least one of the optimal) solution .

def GeneralScheme(x, epsilon):
    while not StopCriterion(x, epsilon):
        OracleResponse = RequestOracle(x)
        x = NextPoint(x, OracleResponse)
    return x

Oracle conception

Complexity

Challenges

Unsolvability

In general, optimization problems are unsolvable. ¯\(ツ)

Consider the following simple optimization problem of a function over unit cube:

We assume, that the objective function is Lipschitz continuous on :

with some constant (Lipschitz constant). Here - the - dimensional unit cube .

Our goal is to find such for some positive . Here is the global minimizer of the problem. Uniform grid with points on each dimension guarantees at least this quality

which means, that

Our goal is to find the for some . So, we need to sample points, since we need to measure function in points. Doesn’t look scary, but if we’ll take , computations on the modern personal computers will take 31,250,000 years.

Stopping rules

  • Argument closeness:
  • Function value closeness:
  • Closeness to a critical point

But and are unknown!

Sometimes, we can use the trick:

Note: it’s better to use relative changing of these values, i.e. .

Local nature of the methods

Problem classifications

Methods classifications

Speed of convergence

  • Sublinear

    where and

  • Linear

    where and

  • Superlinear

    where or ,

  • Quadratic

    where and

Root test

Пусть — последовательность неотрицательных чисел, сходящаяся к нулю, и пусть

  • Если , то имеет линейную сходимость с константной .
  • В частности, если , то имеет сверхлинейную сходимость.
  • Если , то имеет сублинейную сходимость.
  • Случай невозможен.

Ratio test

Пусть — последовательность строго положительных чисел, сходящаяся к нулю. Пусть

  • Если существует и при этом , то имеет линейную сходимость с константой
  • В частности, если , то имеет сверхлинейную сходимость
  • Если не существует, но при этом , то имеет линейную сходимость с константой, не превосходящей .
  • Если , то имеет сублинейную сходимость.
  • Ситуация невозможна.
  • Во всех остальных случаях (т. е. когда ) нельзя утверждать что-либо конкретное о скорости сходимости

References


Table of contents