FoCM 2014 conference
Workshop B3 - Continuous Optimization
December 17, 15:00 ~ 15:30 - Room A21
Toward a Broader View of Theory of Computing -- Part 3
Narendra Karmarkar
Indian Institute of Technology, Bombay, India - narendrakarmarkar@yahoo.com
Beginning with the projectively invariant method for linear programming, interior point methods have led to powerful algorithms for many difficult computing problems, in combinatorial optimization, logic, number theory and non-convex optimization. Algorithms for convex optimization benefitted from many pre-established ideas from classical mathematics, but non-convex problems require new concepts. This three part series outlines some of these concepts In this session, we extend the Riemannian geometry underlying projective method for linear programming to more general metric g(x), to solve non-convex optimization problems. A number of computational methods in optimization and solving equations use locally approximate linear or quadratic models based on Taylor expansion of the functions at a point . We introduce a method of creating locally exact models by defining appropriate space curvature adapted to the function(s) under consideration. We introduce concepts of degree and algebraicity relative to a metric or an affine connection. If all covariant derivatives of the function except for a finite number vanish, zero set of the function is considered to be algebraic w.r.t. that affine connection. The metric is adapted to the input instance in such a way as to make the objective function “relatively algebraic” with low degree
A property of more fundamental significance than convexity is path-wise connectivity of the level sets of the objective function. We introduce graded version of this property. A connected subset is ( k, l ) -- connected if any pair of points in the set can be joined by segment of a curve of degree not exceeding k, dimension of the affine space spanned by points on the segment not exceeding l, and lying entirely in the subset. Convex sets have the simplest type of connectivity – they are (1,1) – connected .A simple example of non-convex set is the set of m by n matrices of rank not exceeding k. This set is ( 2,3 ) – connected. Sets of higher connectivity indices are important in going beyond convex optimization. In case a curved space is introduced as above, the degree is relative to the affine connection and dimension is that of the geodesic submanifold spanned by points on the segment. Geodesically convex sets have (1,1)-connectivity relative to the metric.