Since the origin of linear programming, theoreticians and practionners
have developed and used transformations of optimization problems,
for example to reduce a given problem to one for which an algorithm
is available, or to embed one class of optimization problems in another.
These transformations range from simple, such as
introducing nonnegative slack variables to represent linear inequality
constraints, to sophisticated ones involving second-order
and semidefinite cone representations.
In 2004, Grant and Boyd developed disciplined convex programming (DCP),
a method for constructing convex optimization problems in a simple
language,
from a small set of atoms and using combination rules that derive from
basic
convex analysis. Problems expressed in DCP form are easily parsed,
and can be automatically transformed to a target problem form, as in
the widely used CVX and YALMIP packages, which target cone solvers.
DCP-style descriptions allow many other tasks to be automated, including
automatic dualization, relaxation, and generation of extremely efficient
code for solving instances of the particular problem family.
After covering the basic ideas and examples, I will describe some
recent work
on code generation.
We describe new models for problems of group decision making, aggregate
ranking and clustering techniques for data mining. The problems are
modeled as integer programs on MONOTONE INEQUALITIES and therefore can be
set as graph problems. One of these problems we call the inverse equal
paths problem. This problem as well as all problems studied here have
convex objective function representing penalties for deviating from
specified a-priori comparison/ranking beliefs. These problems are shown
to be solvable in polynomial time using network flow techniques.
One application of the aggregate ranking problem is to determine the
ranking of sports teams based on the outcomes of games played. Current
techniques are based on finding a maximum eigenvector. Our alternative
model has a number of advantages including the ability to differentiate
between games based on some measure of significance. Further, the
problem is stated as a combinatorial graph problem. This problem is
shown to be solved in polynomial time even with a convex objective
function, using flow techniques.
A closely related area that addresses various forms of rankings is
data mining with applications to customer segmentation, patient
diagnosis and assessment of bankrupcy risk. We demonstrate new models
for these problems and how to solve them with flow techniques.
Similarly, the models and solution methodoloies are applicable to
multi-criteria decision making.
Uncertainty quantification is an emerging field that aims to provide precise information about the uncertainty in computed solutions to complex problems, often involving partial differential equations. The uncertainty may originate in lack of information about the environment in which the phenomenon modeled by the partial differential equation takes place, or it may originate from uncertainty in constitutive laws, boundary conditions, etc. Quantifying uncertainty is vastly more demanding than just producing a "solution", both theoretically and computationally. Homogenization theory, which is now more than thirty years old, provides some clues as to how this complexity can be reduced in what at first appear to be very complicated problems, ones that involve randomness on small scales, which are effectively unobservable. I will discuss how homogenization theory can help in reducing some of the complexities in uncertainty quantification.
Computational research transforms the sciences (physical, mathematical, life or social) not just by empowering them analytically, but mainly by providing a novel and powerful perspective and body of metaphors, which often leads to unforeseen insights. Examples abound: quantum computation provides the right forum for questioning and testing some f the most basic tenets of quantum physics, while statistical mechanics has found in the efficiency of randomized algorithms a powerful metaphor for phase transitions. In mathematics, the P vs. NP problem has joined the list of the most profound and consequential problems, and in economics considerations of computational complexity revise predictions of economic behavior and affect the design of economic mechanisms such as auctions. Finally, in biology some of the most fundamental problems, such as understanding the brain and evolution, can be productively recast in computational terms. My talk is structured around several vignettes exemplifying this pattern.