******* 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*(*n*log(*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.

_______________________________________________________________________________

¡@

***** ALL ARE WELCOME *****

Host : Prof. Shuzhong Zhang

Tel : 2609 8240

Email : zhang@se.cuhk.edu.hk

For more information please

refer to http://www.se.cuhk.edu.hk/~seg5810/

¡@