******* NOTE SPECIAL DATE AND TIME ************

******************************************************************************

                                    Seminar


       Department of Systems Engineering and Engineering Management,

                    The Chinese University of Hong Kong

Title:
A Full-Newton Step O(n) Infeasible Interior-Point Algorithm
for Linear Optimization

Speaker:
Prof. Dr. Ir. Cornelis Roos
Faculty of Electrical Engineering, Computer Science and Mathematics
Delft University of Technology

Date : March 1, 2006 (Wednesday)

Time : 5:30 p.m. - 6:30 p.m.

Venue : Room 513, William M.W. Mong Engineering Building

(Engineering Building Complex Phase 2), CUHK

Abstract:
We present a primal-dual infeasible interior-point algorithm. As usual, the
algorithm decreases the duality gap and the feasibility residuals at the same
rate. Assuming that an optimal solution exists it is shown that at most O(n)
iterations suffice to reduce the duality gap and the residuals by the factor
1/ε. This implies an O(nlog(n/ε)) iteration bound for getting an ε-solution of
the problem at hand, which coincides with the best known bound for infeasible
interior-point algorithms. The algorithm constructs strictly feasible iterates
for a sequence of perturbations of the given problem and its dual problem. A
special feature of the algorithm is that it uses only full-Newton steps. Two
types of full-Newton steps are used, so-called feasibility steps and usual
(centering) steps. Starting at strictly feasible iterates of a perturbed pair,
(very) close to its central path, feasibility steps serve to generate strictly
feasible iterates for the next perturbed pair. By accomplishing a few
centering steps for the new perturbed pair we obtain strictly feasible
iterates close enough to the central path of the new perturbed pair. The
algorithm finds an optimal solution or detects infeasibility or unboundedness
of the given problem. It is conjectured that further investigations may
improve the above bound to O ().

Bio:
Kees Roos holds a chair on Optimization at Delft University of Technology. The
past 15 years his research concentrated on interior-point methods for linear
and convex optimization, at present with emphasis on semi-definite
optimization and its applications. He is the (co-)author of several books and
more than hundred papers in refereed journals and member of the editorial
board of several journals, among them the SIAM Journal on Optimization.
Currently he is secretary/treasurer of the of SIAM Activity Group on
Optimization. He supervised a large number of research projects, among them
the Dutch nationwide NWO-project High Performance Methods for Mathematical
Optimization, and currently the project Discrete Mathematics and Optimization
of the (Dutch) Stieltjes Institute.

Note : Cookies and drinks will be available at 5:15 pm.

 _______________________________________________________________________________