1st Annual McMaster Optimization Conference:
Theory and Applications
(MOPTA 01)
Abstracts of Invited Talks
Click on the speaker name to see the abstract. To go back to the main conference page, click here.
Title: Pseudonormality and a Lagrange Multiplier Theory for Constrained Optimization
We consider optimization problems with equality, inequality, and abstract set constraints, and we explore various characteristics of the constraint set that imply the existence of Lagrange multipliers. We prove a generalized version of the Fritz-John theorem, and we introduce new and general conditions that extend and unify the major constraint qualifications. Among these conditions, two new properties, pseudonormality and quasinormality, emerge as central within the taxonomy of interesting constraint characteristics. In the case where there is no abstract set constraint, these properties provide the connecting link between the classical constraint qualifications and two distinct pathways to the existence of Lagrange multipliers: one involving the notion of quasiregularity and Farkas' Lemma, and the other involving the use of exact penalty functions. The second approach is also effective in the general case where there is an abstract set constraint.Back to top
Title: Constrained Optimization Using Surrogates
Many engineering design problems are governed by coupled systems of partial differential equations, table lookups, and who knows what. It is common in these problems for the governing simulations to return no value for a high proportion of feasible points. This talk is an introduction to the filtered direct search method incorporated into the current Boeing Design Explorer release. This talk slights the algorithmic and theoretical details in favor of supporting numerical results. Technical reports giving the omitted details are available from www.caam.rice.edu.Back to top
Title: Recent Developments in Nonlinear Generalized Disjunctive Programming
Generalized Disjunctive Programming (GDP) has been introduced recently as an alternative model to mixed-integer nonlinear programs for representing discrete/continuous optimization problems. The basic idea of GDP consists of representing discrete decisions in the continuous space with disjunctions, and constraints in the discrete space with logic propositions. In this paper, we summarize the major developments in this area. These include convex nonlinear relaxation of the nonlinear GDP problem that relies on the use of the convex hull of each of the disjunctions involving nonlinear inequalities. The proposed nonlinear relaxation is used to reformulate the GDP problem as a tight MINLP problem, and for deriving a branch and bound method. The extension for the solution of nonconvex GDP problems involving bilinear, linear fractional and concave separable functions is also described. Basic theoretical properties are reviewed, as well as relations to other logic-based optimization approaches. Finally, numerical results are presented for several test problems and in a variety of applications.Back to top
Title: Optimization in the automotive industry
How is optimization currently used in the automotive industry? What are the outstanding challenges? These are the questions that will be addressed in this talk. My goal is to provide the audience with a big-picture perspective and, hopefully, with some ideas they can take back to the office. Accordingly, the talk will not dwell on the details of any one application, though references will occasionally be given so that interested individuals can dig deeper. Today, most successful applications of optimization in the automotive industry are at the detailed-design level. Examples include structural optimization of metal gauges and beam cross sections, topology optimization of cast parts, piston shape optimization, cutting stock problems, engine calibration, optimization of shock-absorber rates, assembly-line resequencing, and line balancing. Several of these examples will be reviewed. Persons unfamiliar with topology optimization will find this methodology especially fascinating, since it finds good topologies without explicitly defining parameters, objective functions, etc. Despite these successes, however, it is fair to say that optimization is used less often, and has had a smaller impact, than most researchers in the field of optimization might have expected. The reason is the presence of numerous barriers that need to be overcome. What are the barriers? In engineering, a major barrier has been the poor interface between computer-aided design (CAD) and computer aided engineering (CAE). For example, much CAD work is still non-parametric and not geometrically clean, making it difficult to export data for CAE analysis and to iterate the process with new design parameters suggested by an optimization algorithm. Crashworthiness presents a challenge because crash is a notoriously non-repeatable phenomenon. To obtain a robust design, one must take into account the likely variation in angle of impact, driver position, material stiffness, etc. Yet data on the natural variation of these factors may be poor, and assessing how this variation will impact performance may require more computer runs than can easily be afforded. Managers may be reluctant to trust the results of optimization runs unless the math models are sufficiently accurate; hence, issues of model validation and calibration have come to the forefront. While the value of multidisciplinary optimization is well recognized, different disciplines (structures, durability, crashworthiness, etc.) often develop models at different points in the design process (because they require different levels of detail). As a result, care must be taken to insure that each discipline is working with the same version of the design. In operations research, applications of optimization have sometimes met resistance due to excessive data requirements. While these barriers are substantial, much progress has been made. As I review this progress, I will point out implications for University curricula, for research, and for successfully implementing optimization within industry.Back to top
Title: Interior-Point Methods for Semidefinite and Second-Order-Cone Programming
We discuss primal-dual interior-point methods for semidefinite programming and related problems, and the SDPT3 code of Toh, Tutuncu, and Todd. We provide some computational results for semidefinite programming problems from SDPLIB and some SQL (semidefinite-quadratic-linear) programming problems from a recent DIMACS challenge.Back to top
Title: Interior-point methods for signal processing and control
We will give a survey of recent progress in interior-point methods for certain classes of semidefinite programming problems (SDPs) that are common in signal processing and control. During the 90s there has been intensive reseach in the control community on identifying control problems that can be cast as SDPs. At the same time there has been rapid progress in the area of primal-dual interior-point methods for solving SDPs, and several general-purpose solvers are now available. It was also recognized early on that SDPs arising in systems and control are usually highly structured, and that exploiting this structure using conjugate gradients can lead to dramatic improvements in efficiency. Unfortunately, attempts to exploit structure using direct linear algebra methods (similar to sparse linear programming solvers) have had limited success. This talk will survey recent work on fast methods for solving some important classes of SDP problems, related to the Kalman-Yakubovich-Popov lemma. We will show that the implementation of interior-point methods for those problems greatly benefits from convex duality and from direct linear algebra techniques for structured matrices. We will discuss applications in filter design, system identification, and control.Back to top
Title: The Primal-Dual Method for Approximation Algorithms
The primal-dual method is a well-known tool used in the design of algorithms for problems in combinatorial optimization. Typically it is used for problems whose solution can be characterized by linear programs (for example, shortest paths, network flows, bipartite matchings). However, in the last decade a wealth of results has shown that a modified version of the method is also useful for designing approximation algorithms for a wide variety of NP-hard optimization problems. An approximation algorithm is one that runs in polynomial time and produces a solution whose value is within some factor of the optimal solution. The primal-dual method has been shown to give good approximation algorithms for the set cover problem, the vertex cover problem, network design problems, feedback vertex set problems, the uncapacitated facility location problem, the k-median problem, and others. Additionally, experimental results show that the method results in practical heuristics, whose solution values are typically quite close to the value of the optimal. In this talk, I will review the primal-dual method for approximation algorithms and some interesting results that have been derived from it.Back to top