We investigate the reasons for the observed performance of interior-point methods on optimization problems that arise in practice. In the past decade a new complexity theory has been developed for a large class of convex optimization problems using an extension of condition number theory (of numerical analysis) to constrained optimization. We aim to assess the extent to which this condition number theory has practical explanatory power when applied to linear and nonlinear programming problems that arise in practice.
For example, one of our results shows that roughly 40% of the variance in iteration counts to solve LPs in the NETLIB suite is accounted for by the log of the condition number. This result gives practical evidence to theoretical results on the complexity of IPMs in terms of the condition number. We are exploring also its significance when solving SDPs.
My work experience in optimization modeling and computation before arriving at USC was in areas such as energy production planning, large-scale systems reliability, structural design, and pattern recognition. These projects exposed me to many different modeling techniques and solution methods that are used in current research and applications. Below I provide brief descriptions for some of the current applications I'm involved in.
Current work on using non-linear optimization models to study the theoretical limits of wireless sensor networks (WSN). This research provides the means to design WSN tailored for specific applications and to benchmark the performance of implementable heuristics against the theoretical best performance.
Another line of research comes from the computer science artificial intelligence community. In this group, and important problem is how to coordinate teams of agents under resource constraints. Think of mars rovers which have to accomplish a task under limited resources (that could be replenished or not). In this setting we've shown that optimal policies of the Markov Decision Processes that control the interaction have to be randomized policies, and that these policies can be obtained from convex programs with non-convex quadratic equality constraints. We devise a scalable solution procedure which although is not theoretically polynomial can solve real sized problems.
The problem of routing a fleet of vehicles from a depot to service a geographically dispersed set of customers is common to many industries such as courier services and demand responsive transportation services.
The optimal vehicle routing solution can be significantly inefficient, due to the uncertainty that is present in the actual operating conditions (random travel times, demand, and service times). This research aims at obtaining a routing solution that performs well for all possible uncertainty scenarios and, therefore, is a better solution in practice. These robust solutions have the potential to reduce real operating costs for the broad range of industries which face routing problems daily. NSF CMS 0409887
We devise a procedure to construct scaling laws of physical phenomena automatically from statistical data. The procedure integrates dimensional analysis with the backward elimination of multivariate linear regessions to find the simplest linear regression on the log of the data that still statistically represents the dependent variable. The scaling laws obtained consider rounded, phisically meaningful coefficients. Experiments on different problem domains have shown that given experimental data, our procedure can identify a representative scaling law with simple structure and statistical significance without expert knowledge of the problem.
SLAW is the name of our procedure for Scaling LAWs. It is
coded in 6 Matlab .m files, which can be executed within Matlab or from
a Java interface we provide for SLAW. The software is available from
SLAW's webpage