Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.mccme.ru/ium/postscript/f12/nesterov-PublicBM.pdf Дата изменения: Fri Sep 7 23:12:32 2012 Дата индексирования: Mon Feb 4 19:07:37 2013 Кодировка: Поисковые слова: туманность андромеды

Complexity and Simplicity of Optimization Problems
Yurii Nesterov, CORE/INMA (UCL)

September 4, 2012 (Moscow)


Developments in Computer Sciences
Age of Revolutions: Revolution of Personal Computers: 1980 ­ 2000. Revolution of Internet an Telecommunications: 1990 ­ 2010. Algorithmic Revolution: 2000 - now. NB Advances of the last years are based on algorithmic Know How Examples Numerical TV, ADSL Google (search, maps, video maps) , Netflix (E-Shops), etc. GPS navigators (intelligent routes, positioning, data), etc. Main design to ol: Optimization Methods.


Introductory Lecture (September 4, 2012)

Algorithmic Challenges in Optimization: Mathematical Point of View Main topics: What can be interesting in Optimization for mathematicians? Main directions for the research. Advertising of the main course.


Genealogy

Mathematics

Engineering

Computational Mathematics

...

Optimization

...


Mathematics
Objects: Abstract notions, axioms and theorems. Metho ds: Logical proofs. Results: Perfectly correct statements. (Monopoly for the absolute truth.) Definition Mathematics is an art of discovering the real facts about imaginary objects. Behavioral rules Any question has a right to be answered. The older is the question, the more prestigious is finding the answer (e.g. Great Fermat Theorem; Jackpot principle?). Many important problems remain unsolved.


Engineering
Objects: Exist in the real nature. Metho ds: Experience, modeling, physical sciences. Results: Reliable constructions (under normal conditions). Definition Engineering is an art of constructing the real objects based on imaginary facts. Behavioral rules Open questions: importance is measured by practical consequences. Old problems quickly loose the relevance (Philosopher's stone, Perpetual motion). Alexandrian solution for Gordian knot? All really important problems are solvable. (Life still goes on!)


Computational Mathematics: A Child of Two Extremes?

Objects: Mathematical models. Metho ds: Iterative procedures implemented on computers. Results: Numbers. Too much of ambiguity in the input and output? Definition (?) Computational mathematics is an art of producing imaginary facts about imaginary objects. Other suggestions? Difficult to find ...


Computational Mathematics: Hope for true respect?
(Do not mix with mathematical computations!)

Observations Position of the International Union of Mathematicians. Very often, engineers prefer their homebred algorithms. Books on Computational Mathematics (fuzzy questions, many assumptions, fuzzy answers). Usually very thick! In view of the fast progress in computers, the computational experience becomes obsolete very quickly. Accumulation of knowledge?


Optimization Fields
Mathematical Optimization Optimality conditions and Nonlinear Analysis. Optimal Control. Semi-infinite optimization. Optimization in Banach spaces. Quantum Computing (???) Engineering Optimization Genetic algorithms, ants, etc. Surrogate Optimization, Tabu Search. Neural Networks, Simulated Annealing, etc. Time to introduce Algorithmic Optimization?


Comparing theoretical goals ...
Mathematics The more general is the statement, the more powerful it is. Problem classes should be as abstract as possible. Algorithmic Optimization Statements proved for all numerical schemes are usually silly. We have already enough troubles with problems formed by the simplest functions. The main goal is the selection of the best scheme applicable to a particular problem. All possible efforts should be spent for exploiting the structure of a particular problem instance in the numerical scheme.


Main declarations

Our claim: In Computational Mathematics, there exist research directions interesting both for mathematicians and engineers. For these developments, we need new mathematical tools. The new schemes have good chances to become the most efficient in practice. Our field: Our goals: Optimization Methods with full Complexity Analysis. No gap between Theory and Practice. Nonlinear Optimization


Underwater rocks

Data size. Dimension. Accuracy. Discreteness. Main goal: Cut off unsolvable problem keeping a significant number of real-life applications.


Complexity issues

Example: Goal: Solve equation x 2 + 2ax + b = 0 with integer a, b . Answer: x = -a ± a2 - b . What is the complexity of this problem? Naive answer: 4 a.o. + 1 sqrt. Works well when a2 - b = If not, we need to introduce a lot of details: Computational tools. Required accuracy, etc. Note: for some variants, the problem is unsolvable.
m2 n2

.

Representation of input, output and intermediate results.


Algorithmic complexity

Meta-Theorem. Assume that in our problem class P : Complexity of the problems is an increasing unbounded function of the data size. Speed of computers is finite. Then there exists a problem in P , which cannot be solved during the time of existence of Universe. Corollary: The majority of problem classes, solvable from mathematical point of view, contain numerically unsolvable instances. How to distinguish solvable and unsolvable problems?


Scale for complexity measures

Engineering scale: Time of Human Life. Observation: Before solving the problem, we need to pose it. (collecting the data, coding it, etc.) Fair goal: Solve any problem, which we can pose. Example Pose the problem write down its formulation by hand. Complexity measure: Number of digits in the data set. Polynomial-time methods: performance is proportional to the data length.


Small and big numbers (by Engineering Scale)

Small numbers Number of production items for a time period. Total length of highways in Europe (in km). Big number Orders in a pack of 52 cards: 52! 8.05 · 10 Compare: 65 years = 2 · 109 sec. Cumulative Human Population of Earth: 1011 . Mathematician: Practical experience is too limited. Engineer: Practical experience is extraordinary selective.
67

variants.


NP-hard problems: price for universality?
Example: find Boolean solution xi = ±1 to the following equation:
n

()
i =1

ai xi = 0,

where all ai > 0 are integer. Full search: 2n variants (exponential in the dimension n). For n = 100, we have 2n 1030 . Closed form solution: 2n ·
2 0

f (t ) =

def

n

cos(ai t ) · dt = 2 · (# of solutions to (*))
i =1

Can we compute this integral? Yes! Since f (t ) is a
n

trigonometric polynomial of degree N =
i =1

ai , we need O (nN )

a.o. If all ai have a "real-life origin", then N is reasonably small.


Artificial coefficients
Problem: Find a Boolean solution of the system
n

() :
i =1

aij xi

= 0,

j = 1, . . . , m,
n

where all aij are integer. Denote M = max
m

1j m i =1

|aij |.

Define bi =

(M + 1)
j =1

j -1 a j i

, i = 1, . . . , n.
n

Lemma: Boolean x satisfies (**) if and only if
i =1

bi xi = 0.

Note: Physical sense of the residuals is lost. (Same for accuracy.) Extreme NP-hard problem instance: for given , Z find x, y Z : x 2 = y + .


Reducibility of the problems
NP-hard problems: are mutually reducible with polynomial growth of coefficients. Old Mathematical Principle The problem is solved if it can be reduced to another problem with known solution. (Or, with known method for finding its solution.) Combinatorial Optimization: this works (?) since we are looking for exact solutions. Nonlinear Optimization: We are able to compute only approximate solutions. Transformation of problems changes the quality of approximations and the residuals. Be careful!


Continuity and Discreteness

Main principle: Avoid discrete variables by all possible means. Example "To be or not to be?" (Hamlet, Shakespeare, 1601) Discrete choice is difficult for human beings. It is also difficult for numerical methods. Any compromise solution must be feasible: {x , y } [x , y ]. Thus, we always work with convex objects (sets, functions, etc.).


Golden Rules

1

Try to find an unsolved and easy problem. Try to keep the physical sense of the components (hoping to avoid big numbers). New optimization scheme must be supported by complexity analysis. The first encouraging numerical experiments must be performed by the author.

2

3

4


Lecture 1: Intrinsic complexity of Black-Box Optimization
Negative results. All problems below are NP-hard Finding a descent direction for nonsmooth nonconvex function. Optimal control problems with nonlinear ODE. Minimization of cubic polynomial on a Euclidean sphere. Lower b ounds: analytic complexity for finding -solution Nonconvex optimization: O ( 1 ). n Nonsmooth convex optimization: O ( 1 ). 2
1 Nonsmooth strongly convex optimization: O ( µ ).

System of linear equations: O ( 1 ). Smooth convex optimization: O (
1
1/2

).

To ols: Resisting oracle, worst functions in the world.


Lecture 2: Looking into the Black Box (Structural Optim.)

Smoothing technique Minimax representation of nonsmooth function. Smoothing by prox functions. Solving the smoothed problems by Fast Gradient Methods. Self-concordant barriers Polar set. Geometric origin of self-concordant barriers. Barrier parameter. How to construct self-concordant barriers. Polynomial-time path-following method.


Lecture 3: Huge-scale optimization problems

Main features Even the simplest vector operations are difficult. Acceptable cost of one iteration: logarithmic in dimension. Available technique:
1 2

Coordinate descent methods for smooth functions. Subgradient methods for nonsmooth functions with sparse subgradients. Finite-element schemes. Problems with PDE-constraints. Google problem.

Applications:


Lecture 4: Nonlinear analysis of combinatorial problems

Boolean Quadratic Optimization Simple polyhedral and eigenvalue bounds. Semidefinite relaxation.
2

-approximation.

Counting technique for NP-hard problems Generating functions. Polynomials on unit circle. Counting problems. Fast computations by FFT.


Lecture 5: Algorithmic models of human behavior
Main obstacles for the rational choice: For nonsmooth functions, marginal utilities do not work. Dimension. Impossibility of massive computations. Conscious/Subconscious behavioral patters. Example of sub conscious adjustment
I'$ @ s After projection: contraction @s ) @r s &%

Initial positions (space of characteristics)

Mode

New shift of the Mode: decrease of distances again

Limiting pattern: points stick all together. Topics: 1. Random intuitive search as a basis of rational behavior. 2. Algorithms of rational consumption.


Thank you for your attention!