4
the worst-case computational effort to solve this problem within absolute inaccuracy 0.5 by all known optimization
metho ds is about 2
n
op erations; for n = 256 (just 256 design variables corresponding to the “alphabet of bytes”),
the quantity 2
n
≈ 10
77
, for all practical purposes, is the same as +∞. In contrast to this, the second problem is
quite “computationally tractable”. E.g., for k = 6 (6 loads of interest) and m = 100 (100 degrees of freedom of
the construction) the problem has about 600 variables (twice the one of the “byte” version of (A)); however, it
can be reliably solved within 6 accuracy digits in a couple of minutes. The dramatic difference in computational
effort required to solve (A) and (B) finally comes from the fact that (A) is a non-convex optimization problem,
while (B) is convex.
Note that realizing what is easy and what is difficult in Optimization is, aside of theoretical
importance, extremely important methodologically. Indeed, mathematical models of real world
situations in any case are incomplete and therefore are flexible to some extent. When you know in
advance what you can process efficiently, you p erhaps can use this flexibility to build a tractable
(in our context – a convex) model. The “traditional” Optimization did not pay much attention
to complexity and focused on easy-to-analyze purely asymptotical “rate of convergence” results.
From this viewpoint, the most desirable property of f and g
i
is smoothness (plus, perhaps,
certain “nondegeneracy” at the optimal solution), and not their convexity; choosing between
the above problems (A) and (B), a “traditional” optimizer would, perhaps, prefer the first of
them. We suspect that a non-negligible part of “applied failures” of Mathematical Programming
came from the traditional (we would say, heavily misleading) “order of preferences” in model-
building. Surprisingly, some advanced users (primarily in Control) have realized the crucial role
of convexity much earlier than some members of the Optimization community. Here is a real
story. About 7 years ago, we were working on certain Convex Optimization method, and one of
us sent an e-mail to people maintaining CUTE (a benchmark of test problems for constrained
continuous optimization) requesting for the list of convex programs from their collection. The
answer was: “We do not care which of our problems are convex, and this be a lesson for those
developing Convex Optimization techniques.” In their opinion, the question is stupid; in our
opinion, they are obsolete. Who is right, this we do not know...
♠ Discovery of interior-point polynomial time methods for “well-structured” generic convex
programs and throughout investigation of these programs.
By itself, the “efficient solvability” of generic convex programs is a theoretical rather than
a practical phenomenon. Indeed, assume that all we know about (P) is that the program is
convex, its objective is called f , the constraints are called g
j
and that we can compute f and g
i
,
along with their derivatives, at any given point at the cost of M arithmetic operations. In this
case the computational effort for finding an ϵ-solution turns out to be at least O(1)nM ln(
1
ϵ
).
Note that this is a lower complexity bound, and the best known so far upper bound is much
worse: O(1)n(n
3
+ M) ln(
1
ϵ
). Although the bounds grow “moderately” – polynomially – with
the design dimension n of the program and the required number ln(
1
ϵ
) of accuracy digits, from
the practical viewpoint the upper bound becomes prohibitively large already for n like 1000.
This is in striking contrast with Linear Programming, where one can solve routinely problems
with tens and hundreds of thousands of variables and constraints. The reasons for this huge
difference come from the fact that
When solving an LP program, our a priory knowledge is far beyond the fact that the
objective is called f , the constraints are called g
i
, that they are convex and we can
compute their values at derivatives at any given point. In LP, we know in advance
what is the analytical structure of f and g
i
, and we heavily exploit this knowledge
when processing the problem. In fact, all successful LP methods never never compute
the values and the derivatives of f and g
i
– they do something completely different.
simoney2012-12-292012年9月的书，内容很新
