US-Mexico Workshop on Optimization and its Applications

ABSTRACTS

MONDAY

9:00

Title: An improvement to NEWUOA?
Speaker: M. J. D. Powell
Affiliation: University of Cambridge
Abstract: The NEWUOA software was developed by the author about 3 years ago for unconstrained minimization without derivatives. Changes to the variables are derived by trust region methods using quadratic models of the objective function, or alternatively some steps are made in the space of the variables to improve the robustness of the model near the trust region. Each new model interpolates the objective function at about 2n+1 points, where n is the number of variables, which leaves nearly n*n/2 degrees of freedom. When the quadratic model is updated, the freedom is taken up by minimizing the Frobenius norm of the change to the second derivative matrix of the quadratic model. The software has been applied successfully to test problems having up to 160 variables.

Recently the author has investigated an extension to NEWUOA that allows simple bounds on the variables. That work suggests strongly that the efficiency of NEWUOA in the unconstrained case can be increased by taking advantage of the following remark. If three of the interpolation points of a new model lie on a straight line, then on that line no errors are inherited from the previous quadratic model. Thus 2n+1 points may be sufficient to give much better accuracy than before in first derivative estimates at the starting points of trust region subproblems. Attempts by the author to take advantage of this idea will be reported. The opportunity to do so comes from the freedom that is available in the steps to improve robustness that have been mentioned.

9:40

Title: FilMINT: A New Mixed Integer Nonlinear Optimization Solver
Speaker: Sven Leyffer
Affiliation: Argonne National Laboratory
Abstract: We describe a new solver for mixed integer nonlinear programs (MINLPs) that implements a linearization-based algorithm in a branch-and-cut framework. The framework includes cutting planes, primal heuristics, and other well-known techniques for solving mixed integer linear programs (MILPs). The solver FilMINT (Filter-Mixed INTeger optimizer) combines the MINTO branch-and-cut framework for MILP with filterSQP used to solve the nonlinear programs that arise as subproblems in the algorithm. We present detailed computational experiments that show the benefit of introducing advanced MILP techniques into such a framework. Further, we demonstrate how to use the framework to add and manage linearizations that arise in the algorithm. Comparisons to existing solvers for MINLPs are presented, highlighting the effectiveness of FilMINT.

Joint work with Kumar Abhishek (Lehigh University), Sven Leyffer, and Jeffrey T. Linderoth (Lehigh University)

10:05

Title: Spline Interpolation of Zero Curves
Speaker: Zeferino Parada
Affiliation: Instituto Tecnológico Autónomo de México (ITAM)
Abstract: In Finance, the zero curve is interpolated for a wide range of techniques, in particular for cubic splines (natural, complete and financial spline). Practitioners in finance prefer to use each of these splines in the following order: financial, natural and complete. They refuse to use the complete spline based in numerical results.

In this talk we present a mathematical condition that separates the financial (or the natural) spline to the complete spline. Basically, we propose a family of cubic splines generated by the three splines. In this family, it is not possible to move continuously from the financial (or natural) spline to the complete spline. Due to the finite precision on computers, the separation is not fully appreciated in practice.

10:50

Title: Solution Recovery via L1 minimization: What are possible and Why?
Speaker: Yin Zhang
Affiliation: Rice University
Abstract: We introduce some recent results related to cone programming (more precisely, linear L1-minimization), which state, roughly speaking, that to recover sufficiently sparse (or sparsely corrupted) signals one only needs a "small" number of "good" measurements. We present simple ideas for proofs and discuss some computational issues.

11:15

Title: New concepts of active constraints and Nurnberger’s type theorems
Speaker: Maxim I. Todorov
Affiliation: UDLA
Abstract: In the context of semi-infinite optimization it can happen that on the whole boundary of the feasible set there are not active constraints. We propose new definitions of active constraints and using them, we have generalized the theorem of Nurenberg, characterizing the interior of the set of uniquely solvable problems. We show the limits of such kind of theorems as a tool to obtain generic results in linear semi-infinite optimization.

11:40

Title: Optimization of Noisy Functions: Application to Simulations
Speaker: Michael Ferris
Affiliation: UW Madison
Abstract: In many real-world optimization problems, the objective function may come from a simulation evaluation so that it is (a) subject to various levels of noise, (b) not neccesarily differentiable, and (c) computationally hard to evaluate.

We propose a two-phase approach for optimization of such functions.
Phase I uses classification tools to facilitate the global search process. By learning a surrogate from existing data the approach identifies promising regions for optimization. Additional features of the method are: (a) more reliable predictions obtained using a voting scheme combining the options of multiple classifiers, (b) a data pre-processing step that copes with imbalanced training data and (c) a nonparametric statistical method to determine regions for multistart optimizations.

Phase II is a collection of local trust region derivative free optimizations. Our methods apply Bayesian techniques to guide appropriate sampling strategies, while simultaneously enhancing algorithmic efficiency to obtain solutions of a desired accuracy. The statistically accurate scheme determines the number of simulation runs, and guarantees the global convergence of the algorithm.

We present results on two practical simulations: a Wisconsin breast cancer simulation and the robust design for a floating sleeve coaxial antenna for hepatic microwave ablation. Joint work with Geng Deng.

16:00

Title:Robust methods for the fast and approximate solution of mixed LCPs
Speaker: Jose-Luis Morales
Abstract:In this talk we present new algorithms for solving mixed linear complementarity problems. The LCP matrix is sparse symmetric positive definite, but may be arbitrarily ill-conditioned. The proposed methods interleave steps of the projected SOR method (PSOR) with subspace minimization on the free variables. We also present different mechanisms to effectively improve robustness in our methods. Experimental results, based on a set of test problems that arise in computer games, indicate that the new methods are very promising when the computational resources are limited. Joint work with Jorge Nocedal (Northwestern University) and Mikhail Smelyanskiy (Intel Corporation).

16:40

Title: Exact Penalty Methods and Regularization
Speaker: Richard Byrd
Affiliation: University of Colorado
Abstract: Nondifferentiable exact penalty methods were originally proposed as a way to turn constrained optimization problems into unconstrained problems. However, we argue that their principle advantage is that they provide subproblems that are feasible and well-conditioned. This is useful in trust region methods and provides a way for dealing with problems that lack regularity. For this to work the issue of penalty parameter choice must be dealt with.

Recently some new guidelines have been proposed for automatic penalty parameter choice that are intuitive and have performed well in experiments. In this talk we show how these guidelines can be used in a classic SQP line search method. We prove that this approach is globally convergent without regularity assumptions, and give examples of good performance on problems where regularity fails.

17:05

Title: A new algorithm for equality constrained optimization
Speaker: Philippe Toint
Affiliation: The University of Namur (FUNDP)
Abstract: A new algorithm will be presented for solving the nonlinear constrained optimization problem that has the interesting feature that it does not use any penalty/barrier parameter but does not use a filter either. Moreover, global convergence of the associated sequence of iterates to a first order critical point can be proved without any constraint qualification assumption. A variant of this algorithm will also be discussed that incorporates a filter mechanism for improved efficiency, and for which a new strong filter convergence theorem will be given.

17:50

Title: Nonlinear programming formulations for on-line applications
Speaker: L. T. Biegler
Affiliation: Carnegie Mellon University
Abstract: The development of powerful NLP solvers allows the formulation and on-line solution of large-scale first principle plant models for system identification, control and real-time optimization. The to these time-critical applications is the incorporation of more detailed models with greater process scope, while still maintaining fast execution. This talk describes a real-time iteration approach originally due to Bock and coworkers that is adapted to Newton-based interior point methods. Problem formulations for this approach led to an extension of IPOPT to incorporate an NLP sensitivity function. The resulting approach has the potential to include very large process models with significant savings in on-line computational cost. Nonlinear state estimation and model predictive control will be demonstrated on a real-world polymerization process. Joint work with C. D. Laird and V. M. Zavala-Tejeda.

18:15

Title: Formulating Fano's Method as an Optimization Problem to obtain
Broadband Tuning Limits on UWB Antennas
Speaker: Cristina Villalobos
Affiliation: Department of Mathematics, The University of Texas-Pan American
Abstract: Modern broadband communications requires antennas with greatly improved frequency range and reduced size. It has been known since 1948 that there are basic physical limitations on the bandwidth that can be obtained for a given size antenna; however, the numerical results that have been available were until recently based entirely on a second-order model for the antenna that was (a) an approximation, and (b) only strictly applicable to relatively narrowband cases. In the last few years, a new approach based on "Fano's formulation" has been used which can apply over any bandwidth. We have reformulated Fano's method as an optimization problem and as a result have been able to obtain fundamental bandwidth limits that can in principle be calculated for any radiation mode. This means that one can now find the ultimate possible bandwidth performance for directional antennas, a result with immediate practical significance for designers of ultra-wideband antennas. Graphs of numerical limits on the in-band reflection coefficient tolerance versus electrical size for high-pass and band-pass tuning are presented. Joint work with Heinrich Foltz (UT-Pan American) and Jim S. McLean (TDK Corporation)

18:40

Title: Interior-Point Methods for Nonconvex Nonlinear Programming: Regularization and Warmstarts
Speaker: Hande Y. Benson
Affiliation: Drexel University
Abstract: In this talk, we investigate the use of an exact primal-dual penalty approach within the framework of an interior-point method for nonconvex nonlinear programming. This approach provides regularization and relaxation, which can aid in solving ill-behaved problems and in warmstarting the algorithm. We present details of our implementation within the LOQO algorithm and provide extensive encouraging numerical results.

TUESDAY

9:00

Title: A New Open Source Solver for MINLP
Speaker: Andreas Waechter
Institution: IBM Watson Center
Abstraact: We present our work related to developing an open-source solver for Mixed Integer Nonlinear Programming (Bonmin).  It currently implements three
algorithms for solving convex MINLPs: a branch-and-bound method, an outer
approximation scheme, and a novel hybrid approach.  Recent improvements
and numerical results will be discussed.

9:40

Title: Simultaneous Scheduling and Control of Polymer Grade Transition Operations
Speaker: Antonio Flores-Tlacuahuac
Affiliation: Carnegie-Mellon University
Abstract: Traditionally, scheduling and control problems in chemical processes have been addressed in a separate way. From a pure scheduling point of view, the interest lies in determining optimal production sequences, production times for each product, switching times, leading to designs featuring maximum profit. Commonly, during this task, features related to the dynamic behavior of the underlying process are not taken into account. Similarly, when computing optimal transition trajectories (i.e. optimal values of the manipulated and controlled variables) between different set of products, one of the major objectives lies in determining the transition trajectory featuring minimum transition time. When addressing pure optimal control problems, it is normally assumed that the best production sequence has been determined in some way. Hence, normally scheduling features are neglected in optimal control formulations. In pure scheduling problems, normally the transition times between the different product combinations is fixed. On the other hand, in pure optimal control formulations, the best production sequence is normally assumed to be known. However, it has been recognized that scheduling and control problems are closely related problems and that, ideally, they should be addressed simultaneously rather than sequentially or, even more simply, solved separately without taking account the respective parts (i.e. pure scheduling and pure control problems). In a simultaneous approach, the interactions between scheduling and control problems are explicitly taken into account potentially leading to improved operation in terms of the objective function that is selected. In this work we propose a simultaneous approach to address scheduling and control problems, particularly those emerging during grade transition operations in polymerization reactors. We take advantage of the rich knowledge of pure scheduling and optimal control formulations and we merge them so the final result is a formulation able to solve simultaneous scheduling and control problems. The simultaneous scheduling and control formulation is applied to a Methyl-Methacrylate CSTR where four different types of grades are manufactured. It is shown that the proposed methodology provides the best grade scheduling policy and optimal transition trajectories leading to maximum process profit.
Joint work with Ignacio E. Grossmann

10:05

Title: Random Variables, an AMPL Extension for Stochastic Programming
Speaker: David M. Gay
Affiliation: Sandia National Labs
Abstract: The AMPL modeling language facilitates stating, solving, analyzing and generally manipulating mathematical programming problems. Hitherto the only way to deal with stochastic programming problems in AMPL has been to state deterministic equivalents, which is only feasible for a few, coarsely discretized random variables. The introduction to AMPL of "random variables" will permit suitable solvers to do their own sampling, adaptively deciding where and when to sample, which may permit handling some problems with more randomness than is feasible with straightforward deterministic equivalents. Random variable declarations mention "random" and are otherwise similar to declarations of deterministic variables. A distribution may be specified in a random variable's declaration, or may be assigned later by a "let" command. As a special case, "let" can assign constant values to some random variables, giving simplified problems, which may help one to find suitable formulations.

10:50

Title: Inexact Primal-Dual Methods for Constrained Optimization
Speaker: Jorge Nocedal
Affiliation: Northwestern University
Abstract: Very large constrained optimization problems, such as those arising in PDE-constrained optimization, can be solved using inexact methods in which the search direction is computed using iterative linear algebra techniques. To make such an approach robust for nonlinear problems, it is necessary to know when an approximate solution of the primal-dual system makes sufficient progress toward optimality. In this talk we consider conditions that ensure global convergence using models of an exact penalty function.

11:15

Title: Inexact SQP Methods for Equality Constrained Optimization
Speaker: Frank Curtis
Affiliation: Northwestern University
Abstract: We develop a globally convergent inexact SQP framework for equality constrained optimization problems. Inexact SQP methods are needed for large-scale applications for which the iteration matrix cannot be explicitly formed or factored and the arising linear systems must be solved by means of iterative linear algebra techniques. Extensions to the framework include methods for establishing inertia control and handling (near)-singularities of the constraint Jacobian.

11:40

Title: Large-Scale Numerical Optimization with Simple Bounds
Speaker: Liang “Linda” Xu
Affiliation: University of Washington
Abstract: An algorithm for solving large nonlinear optimization problems with simple bounds is described. The convergence theory is discussed and numerical performance is illustrated. The algorithm is in the framework of a Quasi-Newton trust-region method where the trust-region is the intersection of the constraints and sup-norm ball. The Projected Gradient is used to determine the local active set and the trust-region subproblem is solved with respect to the current active set. A restart strategy is used to ensure the algorithm identifies the optimal constraints in a finite number of iterations. When a Limited memory BFGS update is used we show an efficient implementation based Interior-Point methodology.

16:00

Title: Algorithms for Nonsmooth, Nonconvex Optimization
Speaker: Michael Overton
Affiliation: NYU
Abstract: Nonsmooth, nonconvex optimization problems abound in many applications.We describe two simple algorithmic approaches:BFGS (a new look at an old method), and Gradient Sampling(a method that, although computationally intensive,has solved various previously unsolved problemsand has a very satisfactory convergence theory).Both methods require the user to provide a routine that computesthe function value and, if it exists, the gradient at a given point,the idea being that the function is virtually never evaluatedat a point where it is not differentiable, even though it istypically not differentiable at local optimizers.These methods are combined in a new publicly available code, HANSO (Hybrid Algorithm for Nonsmooth Optimization). Joint work with James Burke and Adrian Lewis.

16:40

17:05

Title: Algorithmic Behavior of KNITRO on Application Problems
Speaker: Todd Plantenga
Affiliation: Ziena Optimization, Inc.
Abstract: The KNITRO nonlinear solver features 3 state-of-the-art algorithms: Interior Point / Direct, Interior Point / CG, and Active Set. KNITRO has been available commercially for more than five years, providing considerable experience in "real world" problems. Modeling deficiencies such as degenerate constraints, infeasible problems, and nonsmoothness are relatively common. The talk will focus on techniques to improve performance and robustness, including choice of algorithm, barrier penalty update rules, regularization techniques, and more.

17:50

Title: Modulus of concavity of critical value functions
Speaker: Francisco Guerra-Vázquez
Affiliation: UDLA
Abstract: A smooth finite dimensional parametric optimization
problem $P(y)$ with objective function $f(x,y)$ is considered. Here, $x$ and $y$ denote the state variable and the parameter, respectively. In the case that $\bar{x}$ is a strongly stable Karush-Kuhn-Tucker point for $P(\bar{y})$, a neighborhood of $\bar{x}$ contains a unique Karush-Kuhn-Tucker point $x(y)$ for $P(y)$, provided that $y$ is sufficiently close to $\bar{y}$. This gives rise to the critical value function$ y \mapsto \phi(y):=f(x,y)$. Under the additional assumption that the Mangasarian-Fromovitz constraint qualification is satisfied at $\bar{x}$, it is shown that $\phi$ has finite modulus of concavity. That means $\phi$ becomes convex in a neighborhood of $\bar{y}$ by adding to it the function $y \mapsto (?/2)??y-\bar{y}?^2$ for some $?>0$.

18:15

Title: Primal-dual techniques in image restoration
Speaker: Michael Hintermueller
Affiliation: University of Graz
Abstract: The focus of this talk is on nonsmooth models in image restoration based on total variation regularization.Utilizing a Fenchel (pre)-duality calculus it is demonstrated that the TV-problem is equivalent to a linear complementarity problem in function space. For its numerical solution primal-dual active set techniques are proposed. Local convergence in function space is briefly addressed and numerical results are discussed. In a second part of the talk, the special case of binary images is considered. In this case, an 'exact' relaxation concept is introduced and a numerical solution scheme is proposed. The talk ends by a report on numerical results.

18:40

Title: An adaptive finite volume method for non-smooth parameter identification
Speaker: Eldad Haber
Affiliation: Emory University
Abstract: In this work we develop a finite volume adaptive grid refinement method for the solution of a constrained optimization problem which arises from distributed parameter estimation problems with almost discontinuous coefficients. We discuss discretization on locally refined grids as well as optimization and refinement criteria. We show that local refinement can significantly reduce the computational effort of solving the problem.

THURSDAY

9:00

Title: Solving Applications Problems with l-1 Norm Objective Terms
Speaker: Stephen J Wright
Affiliation: University of Wisconsin Madison
Abstract: We discuss problems in which the objective consists of a smooth term added to a weighted l-1 norm of the variables. It is well understood how such problems can be formulated and solved as bound-constrained optimization problems, but the properties and requirements of each individual application make some approaches more useful than others. We examine applications in statistics and in signal and image processing, describe the approaches that have proved to be most useful in each case, and present computational results. Joint work with Grace Wahba, Rob Nowak, Mario Figuerido, and others.

9:40

Title: A first-order convergence analysis of a trust-region algorithm with inexact Jacobians
Speaker: Andrea Walther
Affiliation: Institute of Scientific Computing, TU Dresden
Abstract: We present and analyze in this paper a class of trust-region SQP algorithms for the solution of minimization problems with nonlinear equality constraints. The proposed approach does not require the exact evaluation of the constraint Jacobian or an iterative solution of a linear system with a system matrix that involves the constraint Jacobian. Instead the algorithm presented here works only with an approximation of the constraint Jacobian. Hence, it is well suited for optimization problems of moderate size but with a special structure of the constraint Jacobian. The corresponding applications cover the wide range of periodic adsorption processes including for example the purification of hydrogen. In these cases, the Jacobian of the equality constraints is dense due to the periodicity of the underlying chemical process. As a consequence, the run-time needed for the optimization process may be dominated significantly by the computation of the dense Jacobian and its factorization.
The accuracy requirements for the presented first-order global convergence result are based on the feasibility and the optimality of the iterates. The corresponding criteria can be verified easily during the optimization process to adjust the approximation quality of the constraint Jacobian. Numerical results for various test problems are presented. Furthermore, possible extensions for the handling of inequality constraints are discussed.

10:05

Title: Fast algorithms for the inverse medium problem
Speaker: George Biros
Affiliation: University of Pennsylvania
Abstract: In this talk I consider the inverse medium problem, a case of distributed parameter estimation, for elliptic, parabolic, and hyperbolic PDEs. I will present three representative examples, for a Helmholtz, a reaction-diffusion, and an acoustic wave propagation PDE. I will present the formulation, the inverse operator, and discuss the spectral properties and their implications with respect ill-posedness, ill-conditioning. I will conclude with a description of recently proposed multilevel algorithms that are robust as the regularization is reduced, achieve optimal algorithmic complexity, and can scale to parallel computing architectures.

10:50

Title: Image Registration and Lung Cancer
Speaker: Richard Tapia
Affiliation: Rice University
Abstract: A group of researchers at Rice University and MD Anderson Cancer Center are developing a new method for accurate image registration of 4D CT lung images. The objective is to facilitate radiation therapies that do not damage healthy lung tissue. The new method takes into account the compressible nature of the lungs, the extreme noise in the images, and the high computational workload required to register these image sets. The resulting large linear system is solved using a preconditioned conjugate gradient algorithm.

11:15

Title: Good-Quality Structured Grids on Irregular Regions
Speaker: Francisco Domínguez-Mota
Affiliation: U.M.S.N.H.
Abstract: In this talk we will review the development on discrete variational grid generation procedures, concerning the particular case of structured grids on very irregular regions in both, the practical implementation issues and the theory to understand when the problem is ill-posed and how we can deal with it, in order to obtain a good-quality grid regarding some geometrical properties.
Joint work with Pablo Barrera-Sánchez, Guilmer F. González Flores, Longina Castellanos Noda, Angel Pérez Domínguez, Francisco Domínguez-Mota.

11:40

Title: On convergence of Wedge derivative free algorithm
Speaker: Katya Scheinberg
Affiliation:
Abstract: All existing derivative free algorithms based on polynomial interpolation have to balance the quality of the geometry of the interpolation set and the number of objective function evaluations. Derivative free optimization (DFO) algorithm proposed by Conn, Scheinberg and Toint generates special geometry improving sample points when the model is suspected to be poor. This algorithm was shown to have global convergence property. Wedge derivative free algorithm, proposed by Marazzi and Nocedal, has a different approach to geometry handling. It imposes the geometry constraints on iterates, which are otherwise generated solely to improve the objective function. Thus the algorithm attempts to maintain the quality of the polynomial models at all times. So far this algorithm, although successful numerically, was lacking convergence theory. We will use our recently developed general framework for convergence proofs for DFO algorithms to show how to modify Wedge algorithm so that we can obtain global convergence results.

16:00

Title: An interior-point, piecewise linear $ell_2$ penalty method for nonlinear programming
Speaker: Don Goldfarb
Affiliation: Columbia University
Abstract: An interior-point method is proposed that forces eventual satisfaction of any nonlinear equality constraints by adding a piecewise linear penalty function of the Euclidean norm of the constraint violation to the usual log barrier objective function. This method has features of both a penalty method and a filter method and has strong global and local convergence properties. Numerical results comparing it with both interior-point penalty and filter methods will be presented. This is joint work with Lifeng Chen.

16:40

Title: Quadratic-objective uncapacitated facility location
Speaker: Oktay Gunluk
Affiliation: Math. Sciences, IBM Research
Abstract: We study a variant of the UFL (Uncapacitated Facility Location) problem. In our variant, the objective function is linear on the facility variables as is usual, but we allow for nonlinear convex dependence of the objective function on the shipment variables. We attack the problem by proceeding as in outer approximation, but we refine the approach by (i) disaggregating the objective function by its inseparable components, (ii) introducing a new variable corresponding to each nonlinear inseparable component, and then (iii) establishing problem-specific cutting planes. This approach seems to be quite general, but we focus on a variant of the UFL for the sake of concreteness.

17:05

Title: Statistical Mixture Models, Bender's Decomposition, and Interior Point Algorithms
Speaker: Jim Burke
Affiliation: University of Washington
Abstract: In this talk we introduce statistical mixture models illustrating their application in cluster analysis and nonparametric population analysis. We then formulate the nonparametric mixture density estimation problem as a maximum likelihood problem on the space of regular Borel measures. This turns out to be a convex programming problem, but in infinite dimensions. After applying a bit of elementary convex analysis, it is shown that the problem can be recast as a finite dimensional, but nonconvex, mathematical program. By separating out what remains of the original convex programming problem we arrive at a Bender's decomposition where the inner problem is convex program with an elegant duality theory. We then show how a log barrier relaxation of the inner problem gives rise to an efficient Newton algorithm for the original problem, and conclude with at least one numerical illustration. Joint work with Yeongcheon Baek (University of Washington).

17:50

Title: UNAMALLA 3.0. A system for structured numerical grid generation
Speaker: Pablo Barrera-Sánchez
Affiliation: Facultad de Ciencias U.N.A.M
Abstract: We present a preliminary version of UNAMALLA 3.0, an efficient and robust system to generate good-quality structured grids, regarding some geometrical properties using new discrete variational functionals. It is a high quality, intuitive, task-oriented Graphical User Interface based on Gtk+Glade, OpenGL and uses Fortran and C languages. Joint work with Guilmer F. González Flores, Longina Castellanos Noda,
Angel Pérez Domínguez, Francisco J. Domínguez-Mota

18:15

Title: Some new results in derivative free optimization
Speaker: Andrew R. Conn
Affiliation: IBM
Abstract: Successful derivative free methods have to balance the geometry of sample points with efficiency. We present a general framework for a trust region derivative free algorithm that, for the models, assumes only that they can be made to satisfy Taylor-like error bounds. Under the assumptions that need to be satisfied by the function and the algorithm a suitable second order convergence proof is given. This has broader implications for, for example, second-order trust-region methods, the connection between geometry and a (scaled) basis matrix condition numbers and is of both theoretical and practical interest. Joint work with Katya Scheinberg and Luis Vicente

18:40

FRIDAY

9:00

Title: Linear convergence of a modified Frank-Wolfe algorithm
Speaker: Mike Todd
Affiliation: Cornell University
Abstract: We show that a modified version of the Frank-Wolfe algorithm incorporating Wolfe's "away’’ steps is linearly convergent under suitable conditions when the feasible region is the unit simplex. No conditions at all are required for the special case where the problem is the dual of the minimum-volume enclosing ellipsoid problem, which is the D-optimal design problem of statistics. Here the method is the Atwood modification of the Fedorov-Wynn algorithm. Joint work with Damla Ahipasaoglu and Peng Sun.

9:40

Title: Derivative Free Optimization and Average Curvature Information
Speaker: Trond Steihaug
Affiliation: University of Bergen, Norway
Abstract: The class of Generating Set Search (GSS) Methods is a large class within derivative free optimization methods. We present a GSS method which uses average curvature to generate the search directions. If the function that is minimized is smooth then the average curvature will be a good approximation to the Hessian matrix.
Some functions are expensive to evaluate accurately, but cheap to evaluate approximately. The approximated function can be regarded as the original function subject to numerical noise and the function will be non-smooth.
We show that partial separability properties can still be exploited in the context of an optimization method although the original function is distorted by noise. We show this by introducing the covariation graph of the variables which may be derived from a data dependency graph. The average curvature can be computed efficiently using information about the covariation graph.
In the context of computing the curvature information matrix, we encounter a subproblem of selecting rows from a matrix, where the number of rows is much greater than the number of columns, to obtain a full rank and well-conditioned matrix with minimum effort. Finding the optimal solution to this problem is an open problem. We present an efficient heuristic solution.
The theoretical framework we use for computing the curvature information matrix can also be used for approximating Hessians in other derivative free optimization methods.
Joint work with Lennart Frmannslund, Department of Informatics, University of Bergen.

10:20

Title: A gradient-based approach for computing Nash equilibria of large sequential games
Speaker: Javier Pena
Affiliation: Carnegie Mellon University
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 a new gradient-based algorithm that computes Nash equilibria of large two-person, zero-sum sequential games within arbitrary accuracy. The algorithm combines modern smoothing techniques for saddle-point problems with the combinatorial tree-structure of the game. This results in a solution approach with an extremely low computational overhead, which makes it particularly suitable for large-scale problems.
Joint work with Sam Hoda, Andrew Gilpin, and Tuomas Sandholm at Carnegie Mellon University.

11:00

Title: Active-set identification via parametric linear programming
Speaker: Richard Waltz
Affiliation: University of Southern California
Abstract: We investigate a new method of estimating active constraints in nonlinear programming by solving a parametric linear program.  This technique can
be viewed as an attempt to implement gradient projection methods for general nonlinear programs. We discuss issues related to this approach and present some
preliminary numerical results.

Title: New constraint qualifications in convex optimization
Speaker: Miguel A. Goberna
Affiliation: University of Alicante ( Spain )
Abstract: We introduce two constraint qualifications for convex optimization problems posed in locally convex topological vector spaces which provide KKT and saddle point optimality conditions, duality theorems and stability theorems. The convex systems satisfying these constraint qualifications are characterized in terms of the Lagrangian duality for arbitrary convex objective functions.
Joint work with Marco A. Lopez (University of Alicante), Nguyen Dinh (International University), and Vaithilingam Jeyakumar (University of New South Wales)