Title: Variable selection: tractable upper bounds on the restricted isometry constant.
Abstract: We use recent semidefinite relaxation results to produce tractable upper bounds on sparse eigenvalues. We then test the performance of these bounds on various random matrices from compressed sensing, for which asymptotic estimates are known.
Joint work with Francis Bach (ENS Ulm) and Laurent El Ghaoui (U.C. Berkeley).
Tamon Stephen, SFU, Canada
Title: The Colourful Feasibility Problem
Abstract: A colourful version of the linear programming feasibility problem is to find a feasible basis that respects a given colouring (partition) of the vertices. This problem was presented by Barany and Onn in 1997, it is still not known if a polynomial time algorithm exists.
We compare the methods introduced by Barany and Onn with new methods. We perform benchmarking on generic and ill-conditioned problems, as well as recently introduced highly structured problems. We show that some algorithms can lead to cycling or slow convergence, but we provide numerical experiments which show that others perform much better than predicted by complexity arguments. We conclude that an effective method in practice is a proposed multi-update algorithm.
This is joint work with A. Deza, S. Huang and T. Terlaky.
Donald Goldfarb, Columbia University, Paretment of IEOR, 500 W 120th Street, New York, NY 10027, USA.
Title: Bregman Iterative Algorithms for Compressed Sensing and Matrix Rank Minimization
Abstract: We propose efficient methods for solving the Basis Pursuit problem, $\min\{\|u\|_1 : Au=f, u \in R^n\}$, based on Bregman iterative regularization, that obtain an accurate solution after solving only a very small number of instances of the unconstrained problem $\min\{\|u\|_1 + \frac{1}{2}\| Au-f \|^2 : u \in R^n\}$. We prove that an exact solution is obtained in a finite number of steps, and present numerical results on huge compressed sensing applications where matrix-vector operations involving $A$ and $A^T$ can be computed by fast transforms. We also describe extensions to matrix rank minimization.
Title: Robust Optimization in Asset Allocation
Abstract: In this talk I will survey recent work on using robust optimization techniques in asset management. I will discuss examples from equity portfolio management, pension-fund management, and credit portfolio management. Parts of this talk are joint work with Emre Erdogan, Don Goldfarb, Ka Chun Ma, and Victor De Miguel.
M.J. Todd Cornell University
Title: First-Order Methods for Matrix Optimization Problems
Abstract: First-order methods can be very effective for certain matrix optimization problems arising in data analysis and statistics, because rank-one updates make each iteration very cheap. We survey the theory available for such algorithms and provide computational results for minimum-volume containing ellipsoid, minimum-area enclosing cylinder, and max-cut problems
Title: Algorithms for Sparse Optimization
Abstract: In many modern applications of optimization, users seek not exact solutions but rather approximate solutions that are simple, in the sense of being sparse (i.e. having relatively few nonzero components) in some representation. Sparsity can be imposed explicitly in the formulation, or induced with the help of a nonsmooth regularization term or a dual formulation. We review a number of applications in which sparse optimization problems arise. We then focus on an algorithmic framework that generates steps by solving a proximal linearized subproblem, possibly enhanced by line-search strategies and second-order information. Global and local properties of methods in this framework are described, along with results obtained by using practical methods in this framework to solve problems from compressed sensing and variable selection.
This talk covers joint work with A. Lewis, M. Figueiredo, R. Nowak, G. Wahba, and W. Shi.
Title: T-algebras and linear optimization over symmetric cones
Abstract: The first target-following algorithm was given by Shinji Mizuno in 1992 for linear complementarity problems, using the notion of delta sequences. A delta sequence is a sequence of targets that leads the primal-dual solutions towards optimality. This target-following paradigm was successfully generalized to semidefinite programming by the speaker in a recent work. In this talk, the target-following framework is further generalized to symmetric cone programming via $T$-algebra.
Adrian Lewis ORIE, Cornell
Title: Metric Regularity illustrated
Abstract: Metric regularity sits at the heart of variational analysis, capturing the idea of a posteriori error bounds for constraint systems. Two simple examples - alternating projections and matrix pseudospectra - nicely illustrate the interplay between metric regularity and computation. For both convex and nonconvex sets, the method of alternating projections exemplifies a theme emphasized by Demmel, relating conditioning, the distance to ill-posedness, and algorithmic speed (and incidentally proves a fundamental extremal principle of Mordukhovich). The pseudospectral mapping from a square matrix to the eigenvalues of all nearby matrices is a robust and practical numerical tool: its Lipschitz behavior follows from a striking recent semi-algebraic Sard-type result of Ioffe, describing the prevalence of metric regularity.
This talk describes joint work with J. Bolte, J.V. Burke, A. Daniilidis, A.L. Dontchev, D.R. Luke, J. Malick, M.J. Overton, C.H.J. Pang, R.T. Rockafellar, M. Shiota.
Robert M. Freund, MIT
Title: Equivalence of Complexity and Geometric Properties of the Convex
Feasibility Problem, in the Separation Oracle Model
Abstract: We examine the problem of computing a point in a convex set S
given only by a separation oracle, with no further information (i.e., no
bounding ball, etc.). Using an extension of the ellipsoid algorithm, we
show that the complexity of this problem depends only on three geometric
quantities involving a ball of radius r contained in S and at a distance R
from a reference point. This shows that ``good geometry implies good
computational complexity.'' Furthermore, the converse of this result:
``good complexity implies good geometry'' is true for families of problem
instances with the same values of R and r. These results also yield lower
bounds on complexity in condition measure theory for convex optimization.
This is joint work with Jorge Vera.
Title: Numerical experiments with universal barrier functions
Abstract:
We present the results of extensive numerical experiments for path-following
algorithms based on universal barrier functions. The corresponding optimization
problems involve cones generated by Chebyshev systems. We consider approaches
for approximation of Hessians based on corresponding approximations
of continuous Chebyshev systems by discrete ones. The comparison is given to
analytic solutions, semidefinite programming and linear programming solutions
(where it is possible). The results show the reduction in number of Newton-like
steps for algorithms based on universal barriers. Possible generalizations for
other cones are briefly discussed.
Javier Pena, Carnegie Mellon University
Title: Algorithms for computing Nash equilibria of large sequential games
Abstract:
Finding a Nash equilibrium of an extensive form game is a central
problem in computational game theory. For a two-person, zero-sum
game this problem can be formulated as a linear program, which in
principle is solvable via standard algorithms such as the simplex
or interior-point methods. However, most interesting games lead
to enormous linear programs that are beyond today's computational
capabilities. We propose specialized algorithms that tailor modern
smoothing techniques to the highly structured polytopes that arise
in the Nash equilibrium formulation. We discuss computational
results with instances of poker, whose Nash equilibrium
formulation has about 108 variables and 108 constraints.
This is joint work with Sam Hoda, Andrew Gilpin, and Tuomas Sandholm at
Carnegie Mellon University.
Title: A FPTAS for Computing a Symmetric Leontief Competitive Economy Equilibrium
Abstract:
We consider a linear complementarity problem (LCP) arisen from the
Arrow-Debreu-Leontief competitive economy equilibrium where the LCP
coefficient matrix is symmetric. We prove that the decision problem,
to decide whether or not there exists a complementary solution, is
NP-complete. Under certain conditions, an LCP solution is guaranteed
to exist and we present a fully polynomial-time approximation scheme
(FPTAS) for computing such a solution, although the LCP solution set
can be non-convex or non-connected. Our method is based on solving a
quadratic social utility optimization problem (QP) and showing that
a certain KKT point of the QP problem is an LCP solution. Then, we
further show that such a KKT point can be approximated with running
time $\mathcal{O}((\frac{1}{\epsilon})\log(\frac{1}{\epsilon}))$ in
accuracy $\epsilon \in (0,1)$ and a polynomial in problem dimensions.
We also report preliminary computational results which show that the
method is highly effective. Joint work with Zhisu Zhu.
Title: Matrix Decomposition and Its Applications in Nonconvex Quadratic
Optimization
Abstract: In this talk we shall discuss some new results regarding the
decomposition of a positive semidefinite matrix into the sum of rank-one
matrices, with some desirable properties. Such matrix decomposition is
useful in solving nonconvex quadratic optimization problems. It also has
connections with the study of the joint numerical range, and the
solutions for quadratic equations, among others. We will discuss how to
compute such rank-one decompositions. The talk is based on joint work
with Wenbao Ai and Yongwei Huang.
T. Coleman, University of Waterloo, Canada
Title: Fast (Structured) Newton Computations
Abstract:
L.Q. Qi, Hong Kong Polytechnic University
Title:
A Random Global Line Search Method for The Quartic Spherical Optimization Problem
Abstract:
The quartic spherical optimization problem arises
from the best rank-one approximation to a fourth order symmetric
tensor and the positive definiteness identification of a quartic
form. It minimizes a quartic homogeneous function over the unit
sphere and has extensive engineering and statistical applications.
Mathematically, it is NP-hard. In this paper, we present a
sufficient and necessary condition for a second-order stationary
point to be a global minimizer of this problem. Based upon this
condition, we propose a random global line search method for
solving this problem. We show that an approximate global optimizer
can be found within a given error bound with a given probability.
TBA
Jerome Malick (CNRS, Grenoble, France)
Title: Projection methods in semidefinite programming
Abstract:
There exists an explicit expression for the projection of a symmetric
matrix onto the cone of positive semidefinite matrices. The
projections on the subsets of this cone are not explicit in general,
but still easy to compute using techniques of convex optimization. In
this presentation, I will first review these numerical methods,
insisting on the dual method that I recently introduced, and that has
then opened the way for further developments. Next I will explain how
these projections allow to set up a new family of algorithms for
solving semidefinite programs. I will give numerical illustrations on
standard problems, like computing the nearest correlation matrix and
computing the Lovasz theta number of big graphs.
Jorge Nocedal, Northwestern University
Title: Analyzing the Behavior of Nonlinear Optimization Algorithms
on Infeasible Problems
Abstract:
For many years, the primary focus in the design of nonlinear
optimization methods has been the efficient solution in cases where a
feasible and optimal point exists, with only minor emphasis on the
detection of infeasibility. In fact, most of the popular optimization
methods are inefficient when confronted with nonconvex infeasible problems.
In this talk we discuss active-set identification, global convergence
and rate of convergence properties of optimization algorithms on
infeasible problems. We advocate a penalty method, involving a single
optimization strategy, and show that it is effective for finding an
optimal feasible solution (when it exists) or minimizing violation of
infeasibility (when no solution exists).
Kim-Chuan Toh
Department of Mathematics and
Singapore-MIT Alliance, National
University of Singapore
Title: A Newton-CG Augmented Lagrangian Method for
Semidefinite Programming
Abstract:
We consider a Newton-CG augmented Lagrangian
(NCGAL) method for solving semidefinite programming (SDP) problems
from the perspective of approximate semismooth Newton methods. In
order to analyze the rate of convergence of the method, we
characterize the Lipschitz continuity of the corresponding
solution mapping at the origin. For the inner problems in the
NCGAL method, we show that the positive definiteness of the
generalized Hessian of the objective function in these inner
problems, a key property for ensuring the efficiency of using an
inexact semismooth Newton-CG method to solve the inner problems,
is equivalent to the constraint nondegeneracy of the corresponding
dual problems. Numerical experiments on a variety of large scale
SDPs with matrix dimensions up to ${1,600}$ and the number of equality
constraints up to a million show that the proposed method is
very efficient.
Join work with Defeng Sun, Department of Mathematics and Risk Management Institute,
National University of Singapore, and Xin-Yuan Zhao,
Department of Mathematics, National University of
Singapore
Alper Yildirim,
Bilkent University, Department of Industrial Engineering, 06800
Bilkent, Ankara, Turkey
Title: Recent Progress in Core Sets
Abstract: Recently, many studies have centered around developing
algorithms for
large-scale optimization problems by identifying a small subset of the
constraints and/or variables and solving the resulting smaller optimization
problem. Such small subsets are known as {\em core sets}. For a
certain class of optimization problems, one can
explicitly compute such a small subset with the property that the
resulting optimal solution is a close approximation of the optimal
solution of the original problem. Such problems mainly include
geometric optimization problems such as minimum containment,
clustering, and classification. In this talk, we review the recent
results in this area and provide a unifying framework. In particular
we discuss how the existence of small core sets forms a basis for the
design of efficient algorithms for large-scale optimization problems.
Title: Regularization as an alternative to lineserach and trustregions for
nonlinear optimization
Abstract: The talk will review a new class of regularization techniques
resulting from the convergence of various ideas by Griewank, Weiser,
Deuflhard and Erdmann and Nesterov, and recently analyzed by Cartis,
Gould and the author. Three algorithms will be discussed. The first is
for unconstrained optimization and uses a cubic regularization term, the
second is for optimization with convex constraints and uses the same
regularization in a different context, and the third is for
least-squares computations and solution of systems of nonlinear
equations, and uses a prox regularization of the unsquared Euclidean
norm. Theoretical properties of these algorithms will be reviewed, as
well as algorithmic tools for the solution of the relevant
subsproblems. Some numerical evidence will also be presented,
indicating a strong potential for this approach.