Search

An introduction to the article "Topological Optimization of Rod-Stirring Devices," by Matthew Finna nd Jean-Lug Thiffeault, published in this issue is presented.

Efficient sampling from a high-dimensional Gaussian distribution is an old but high-stakes issue. Vanilla Cholesky samplers imply a computational cost and memory requirements that can rapidly become prohibitive in high dimensions. To tackle these issues, multiple methods have been proposed from different communities ranging from iterative numerical linear algebra to Markov chain Monte Carlo (MCMC) approaches. Surprisingly, no complete review and comparison of these methods has been conducted. This paper aims to review all these approaches by pointing out their differences, close relations, benefits, and limitations. In addition to reviewing the state of the art, this paper proposes a unifying Gaussian simulation framework by deriving a stochastic counterpart of the celebrated proximal point algorithm in optimization. This framework offers a novel and unifying revisiting of most of the existing MCMC approaches while also extending them. Guidelines to choosing the appropriate Gaussian simulation method for a given sampling problem in high dimensions are proposed and illustrated with numerical examples. [ABSTRACT FROM AUTHOR]

Tropical geometry has been recently used to obtain new complexity results in convex optimization and game theory. In this paper, we present an application of this approach to a famous class of algorithms for linear programming, i.e., log-barrier interior point methods. We show that these methods are not strongly polynomial by constructing a family of linear programs with 3r + 1 inequalities in dimension 2r for which the number of iterations performed is in Ω(2r). The total curvature of the central path of these linear programs is also exponential in r, disproving a continuous analogue of the Hirsch conjecture proposed by Deza, Terlaky, and Zinchenko. These results are obtained by analyzing the tropical central path, which is the piecewise linear limit of the central paths of parameterized families of classical linear programs viewed through "logarithmic glasses." This allows us to provide combinatorial lower bounds for the number of iterations and the total curvature in a general setting. [ABSTRACT FROM AUTHOR]

This paper develops a novel framework for phase retrieval, a problem which arises in X-ray crystallography, diffraction imaging, astronomical imaging, and many other applications. Our approach, called PhaseLift, combines multiple structured illuminations together with ideas from convex programming to recover the phase from intensity measurements, typically from the modulus of the diffracted wave. We demonstrate empirically that a complex-valued object can be recovered from the knowledge of the magnitude of just a few diffracted patterns by solving a simple convex optimization problem inspired by the recent literature on matrix completion. More importantly, we also demonstrate that our noise-aware algorithms are stable in the sense that the reconstruction degrades gracefully as the signal-to-noise ratio decreases. Finally, we introduce some theory showing that one can design very simple structured illumination patterns such that three diffracted figures uniquely determine the phase of the object we wish to recover. [ABSTRACT FROM AUTHOR]

Variational problems that involve Wasserstein distances and more generally optimal transport (OT) theory are playing an increasingly important role in data sciences. Such problems can be used to form an exemplar measure out of various probability measures, as in the Wasserstein barycenter problem, or to carry out parametric inference and density fitting, where the loss is measured in terms of an optimal transport cost to the measure of observations. Despite being conceptually simple, such problems are computationally challenging because they involve minimizing over quantities (Wasserstein distances) that are themselves hard to compute. Entropic regularization has recently emerged as an efficient tool to approximate the solution of such variational Wasserstein problems. In this paper, we give a thorough duality tour of these regularization techniques. In particular, we show how important concepts from classical OT such as c-transforms and semidiscrete approaches translate into similar ideas in a regularized setting. These dual formulations lead to smooth variational problems, which can be solved using smooth, differentiable, and convex optimization problems that are simpler to implement and numerically more stable than their unregularized counterparts. We illustrate the versatility of this approach by applying it to the computation of Wasserstein barycenters and gradient flows of spatial regularization functionals. [ABSTRACT FROM AUTHOR]

The computation of the singular value decomposition, or SVD, has a long history with many improvements over the years, both in its implementations and algorithmically. Here, we survey the evolution of SVD algorithms for dense matrices, discussing the motivation and performance impacts of changes. There are two main branches of dense SVD methods: bidiagonalization and Jacobi. Bidiagonalization methods started with the implementation by Golub and Reinsch in Algol60, which was subsequently ported to Fortran in the EISPACK library, and was later more efficiently implemented in the LINPACK library, targeting contemporary vector machines. To address cache-based memory hierarchies, the SVD algorithm was reformulated to use Level 3 BLAS in the LAPACK library. To address new architectures, ScaLAPACK was introduced to take advantage of distributed computing, and MAGMA was developed for accelerators such as GPUs. Algorithmically, the divide and conquer and MRRR algorithms were developed to reduce the number of operations. Still, these methods remained memory bound, so two-stage algorithms were developed to reduce memory operations and increase the computational intensity, with efficient implementations in PLASMA, DPLASMA, and MAGMA. Jacobi methods started with the two-sided method of Kogbetliantz and the one-sided method of Hestenes. They have likewise had many developments, including parallel and block versions and preconditioning to improve convergence. In this paper, we investigate the impact of these changes by testing various historical and current implementations on a common, modern multicore machine and a distributed computing platform. We show that algorithmic and implementation improvements have increased the speed of the SVD by several orders of magnitude, while using up to 40 times less energy. [ABSTRACT FROM AUTHOR]

This paper provides a review and commentary on the past, present, and future of numerical optimization algorithms in the context of machine learning applications. Through case studies on text classification and the training of deep neural networks, we discuss how optimization problems arise in machine learning and what makes them challenging. A major theme of our study is that large-scale machine learning represents a distinctive setting in which the stochastic gradient (SG) method has traditionally played a central role while conventional gradient-based nonlinear optimization techniques typically falter. Based on this viewpoint, we present a comprehensive theory of a straightforward, yet versatile SG algorithm, discuss its practical behavior, and highlight opportunities for designing algorithms with improved performance. This leads to a discussion about the next generation of optimization methods for large-scale machine learning, including an investigation of two main streams of research on techniques that diminish noise in the stochastic directions and methods that make use of second-order derivative approximations. [ABSTRACT FROM AUTHOR]

This paper considers the problem of optimizing the ratio Tr[VT AV]/Tr[VT BV] over all unitary matrices V with p columns, where A, B are two positive definite matrices. This problem is common in supervised learning techniques. However, because its numerical solution is typically expensive it is often replaced by the simpler optimization problem which consists of optimizing Tr[VT AV] under the constraint that VT BV = I, the identity matrix. The goal of this paper is to examine this trace ratio optimization problem in detail, to consider different algorithms for solving it, and to illustrate the use of these algorithms for dimensionality reduction. [ABSTRACT FROM AUTHOR]

Using 55 years of daily average temperatures from a local weather station, I made a least-absolute-deviations (LAD) regression model that accounts for three effects: seasonal variations, the 11-year solar cycle, and a linear trend. The model was formulated as a linear programming problem and solved using widely available optimization software. The solution indicates that temperatures have gone up by about 2°F over the 55 years covered by the data. It also correctly identifies the known phase of the solar cycle; i.e., the date of the last solar minimum. It turns out that the maximum slope of the solar cycle sinusoid in the regression model is about the same size as the slope produced by the linear trend. The fact that the solar cycle was correctly extracted by the model is a strong indicator that effects of this size, in particular the slope of the linear trend, can be accurately determined from the 55 years of data analyzed. The main purpose for doing this analysis is to demonstrate that it is easy to find and analyze archived temperature data for oneself. In particular, this problem makes a good class project for upper-level undergraduate courses in optimization or in statistics. It is worth noting that a similar least-squares model failed to characterize the solar cycle correctly, and hence even though it too indicates that temperatures have been rising locally, one can be less confident in this result. The paper ends with a section presenting similar results from a few thousand sites distributed worldwide, some results from a modification of the model that includes both temperature and humidity, as well as a number of suggestions for future work and/or ideas for enhancements that could be used as classroom projects. [ABSTRACT FROM AUTHOR]

The engineering and control of devices at the quantum mechanical level--such as those consisting of small numbers of atoms and photons--is a delicate business. The fundamental uncertainty that is inherently present at this scale manifests itself in the unavoidable presence of noise, making this a novel field of application for stochastic estimation and control theory. In this expository paper we demonstrate estimation and feedback control of quantum mechanical systems in what is essentially a noncommutative version of the binomial model that is popular in mathematical finance. The model is extremely rich and allows a full development of the theory while remaining completely within the setting of finite-dimensional Hilbert spaces (thus avoiding the technical complications of the continuous theory). We introduce discretized models of an atom in interaction with the electromagnetic field, obtain filtering equations for photon counting and homodyne detection, and solve a stochastic control problem using dynamic programming and Lyapunov function methods. [ABSTRACT FROM AUTHOR]

This paper proposes a constrained nonlinear programming view of generalized autoregressive conditional heteroskedasticity (GARCH) volatility estimation models in financial econometrics. These models are usually presented to the reader as unconstrained optimization models with recursive terms in the literature, whereas they actually fall into the domain of nonconvex nonlinear programming. Our results demonstrate that constrained nonlinear programming is a worthwhile exercise for GARCH models, especially for the bivariate and trivariate cases, as they offer a significant improvement in the quality of the solution of the optimization problem over the diagonal VECH and the BEKK representations of the multivariate GARCH model. [ABSTRACT FROM AUTHOR]

An introduction to the paper "The Smallest Possible Iteration Radius for Synchronization of Self-Propelled Particles" by Ge Chen, Zhixin Liu and Lei Guo, which appeared in the "SIAM Journal on Control and Optimization" is presented.

An introduction to the article "The Trace Ratio Optimization Problem," by T. T. Ngo, M. Bellalij, and Y. Saad, is presented.

An introduction to the article "Global Convergence of Radial Basis Function Trust-Region Algorithms for Derivative-Free Optimization," by Stefan M. Wild and Christine Shoemaker, is presented.

In this paper we survey the primary research, both theoretical and applied, in the area of robust optimization (RO). Our focus is on the computational attractiveness of RO approaches, as well as the modeling power and broad applicability of the methodology. In addition to surveying prominent theoretical results of RO, we also present some recent results linking RO to adaptable models for multistage decision-making problems. Finally, we highlight applications of RO across a wide spectrum of domains, including finance, statistics, learning, and various areas of engineering. [ABSTRACT FROM AUTHOR]

The affine rank minimization problem consists of finding a matrix of minimum rank that satisfies a given system of linear equality constraints. Such problems have appeared in the literature of a diverse set of fields including system identification and control, Euclidean embedding, and collaborative filtering. Although specific instances can often be solved with specialized algorithms, the general affine rank minimization problem is NP-hard because it contains vector cardinality minimization as a special case. In this paper, we show that if a certain restricted isometry property holds for the linear transformation defining the constraints, the minimum-rank solution can be recovered by solving a convex optimization problem, namely, the minimization of the nuclear norm over the given affine space. We present several random ensembles of equations where the restricted isometry property holds with overwhelming probability, provided the codimension of the subspace is sufficiently large. The techniques used in our analysis have strong parallels in the compressed sensing framework. We discuss how affine rank minimization generalizes this preexisting concept and outline a dictionary relating concepts from cardinality minimization to those of rank minimization. We also discuss several algorithmic approaches to minimizing the nuclear norm and illustrate our results with numerical examples. [ABSTRACT FROM AUTHOR]

Emerging applications for networked and cooperative robots motivate the study of motion coordination for groups of agents. For example, it is envisioned that groups of agents will perform a variety of useful tasks including surveillance, exploration, and environmental monitoring. This paper deals with basic interactions among mobile agents such as "move away from the closest other agent" or "move toward the furthest vertex of your own Voronoi polygon." These simple interactions amount to distributed dynamical systems because their implementation requires only minimal information about neighboring agents. We characterize the close relationship between these distributed dynamical systems and the disk-covering and sphere-packing cost functions from geometric optimization. Our main results are as follows: (i) we characterize the smoothness properties of these geometric cost functions, (ii) we show that the interaction laws are variations of the nonsmooth gradient of the cost functions, and (iii) we establish various asymptotic convergence properties of the laws. The technical approach relies on concepts from computational geometry, nonsmooth analysis, and nonsmooth stability theory. [ABSTRACT FROM AUTHOR]

The effective resistance between two nodes of a weighted graph is the electrical resistance seen between the nodes of a resistor network with branch conductances given by the edge weights. The effective resistance comes up in many applications and fields in addition to electrical network analysis, including, for example, Markov chains and continuous-time averaging networks. In this paper we study the problem of allocating edge weights on a given graph in order to minimize the total effective resistance, i.e., the sum of the resistances between all pairs of nodes. We show that this is a convex optimization problem and can be solved efficiently either numerically or, in some cases, analytically. We show that optimal allocation of the edge weights can reduce the total effective resistance of the graph (compared to uniform weights) by a factor that grows unboundedly with the size of the graph. We show that among all graphs with n nodes, the path has the largest value of optimal total effective resistance and the complete graph has the least. [ABSTRACT FROM AUTHOR]

We consider a Markov process on a connected graph, with edges labeled with transition rates between the adjacent vertices. The distribution of the Markov process converges to the uniform distribution at a rate determined by the second smallest eigenvalue λ2 of the Laplacian of the weighted graph. In this paper we consider the problem of assigning transition rates to the edges so as to maximize λ2 subject to a linear constraint on the rates. This is the problem of finding the fastest mixing Markov process (FMMP) on the graph. We show that the FMMP problem is a convex optimization problem, which can in turn be expressed as a semidefinite program, and therefore effectively solved numerically. We formulate a dual of the FMMP problem and show that it has a natural geometric interpretation as a maximum variance unfolding (MVU) problem, i.e., the problem of choosing a set of points to be as far apart as possible, measured by their variance, while respecting local distance constraints. This MVU problem is closely related to a problem recently proposed by Weinberger and Saul as a method for ‘unfolding’ high-dimensional data that lies on a low-dimensional manifold. The duality between the FMMP and MVU problems sheds light on both problems, and allows us to characterize and, in some cases, find optimal solutions. [ABSTRACT FROM AUTHOR]

We propose a new randomized coordinate descent method for minimizing the sum of convex functions, each of which depends on a small number of coordinates only. Our method (APPROX) is simultaneously Accelerated, Parallel, and PROXimal; this is the first time such a method has been proposed. In the special case when the number of processors is equal to the number of coordinates, the method converges at the rate 2ωLR2/(k + 1)2, where k is the iteration counter, ω is a data-weighted average degree of separability of the loss function, L is the average of Lipschitz constants associated with the coordinates and individual functions in the sum, and R is the distance of the initial point from the minimizer. We show that the method can be implemented without the need to perform full-dimensional vector operations, which is the major bottleneck of accelerated coordinate descent, rendering it impractical. The fact that the method depends on the average degree of separability, and not on the maximum degree, can be attributed to the use of new safe large stepsizes, leading to improved expected separable overapproximation (ESO). These are of independent interest and can be utilized in all existing parallel randomized coordinate descent algorithms based on the concept of ESO. In special cases, our method recovers several classical and recent algorithms such as simple and accelerated proximal gradient descent, as well as serial, parallel, and distributed versions of randomized block coordinate descent. Due to this flexibility, APPROX had been used successfully by the authors in a graduate class setting as a modern introduction to deterministic and randomized proximal gradient methods. Our bounds match or improve upon the best known bounds for each of the methods APPROX specializes to. Our method has applications in a number of areas, including machine learning, submodular optimization, and linear and semidefinite programming. [ABSTRACT FROM AUTHOR]

An introduction to the journal is presented in which the editor discusses an article on geometric optimization by Jorge Cortéz et al.

The article presents an abstract on optimization, linear equations and asymptotic expansion of integrals in Laplace form. An approach of making individual system components more reliable is called reliability allocation. To justify the effectiveness of a particular approach for solving systems of linear equations.

An introduction is presented in which the editor discusses articles in the issue including the Survey and Review article "Looking Back on Inverse Scattering Theory" by David Colton and Rainer Kress, and "The Singular Value Decomposition: Anatomy of Optimizing an Algorithm for Extreme Scale."

A sharp lower bound on the probability of a set defined by quadratic inequalities, given the first two moments of the distribution, can be efficiently computed using convex optimization. This result generalizes Chebyshev's inequality for scalar random variables. Two semidefinite programming formulations are presented, with a constructive proof based on convex optimization duality and elementary linear algebra. [ABSTRACT FROM AUTHOR]

Splines come in a variety of flavors that can be characterized in terms of some differential operator L. The simplest piecewise-constant model corresponds to the derivative operator. Likewise, one can extend the traditional notion of total variation by considering more general operators than the derivative. This results in the definitions of a generalized total variation seminorm and its corresponding native space, which is further identified as the direct sum of two Banach spaces. We then prove that the minimization of the generalized total variation (gTV), subject to some arbitrary (convex) consistency constraints on the linear measurements of the signal, admits nonuniform L-spline solutions with fewer knots than the number of measurements. This shows that nonuniform splines are universal solutions of continuous-domain linear inverse problems with LASSO, L1, or total-variationlike regularization constraints. Remarkably, the type of spline is fully determined by the choice of L and does not depend on the actual nature of the measurements. [ABSTRACT FROM AUTHOR]

JuMP is an open-source modeling language that allows users to express a wide range of optimization problems (linear, mixed-integer, quadratic, conic-quadratic, semidefinite, and nonlinear) in a high-level, algebraic syntax. JuMP takes advantage of advanced features of the Julia programming language to offer unique functionality while achieving performance on par with commercial modeling tools for standard tasks. In this work we will provide benchmarks, present the novel aspects of the implementation, and discuss how JuMP can be extended to new problem classes and composed with state-of-the-art tools for visualization and interactivity. [ABSTRACT FROM AUTHOR]

In the game of rugby, attempting to score a conversion following a try gives rise to a situation which may be modeled mathematically as an optimization problem, namely, that of choosing the best spot from which to kick the ball. Due to its appeal and simplicity, this problem has been widely used as an example of an application of mathematics to sports. Starting from the model suggested by Hughes over 30 years ago, on which all other models used until now have been based, we analyze the situations in which these models are not applicable. From this we will see how the quantity to be optimized should be changed in order to overcome these problems and also to obtain results which are compatible with the data quoted in the literature for professional players, for the whole range of possible scenarios. To obtain more realistic results, we then incorporate the initial speed and elevation angle of the ball into the model. [ABSTRACT FROM AUTHOR]

An introduction is presented in which the section editor discusses a chance-constrained optimization framework that takes into consideration the uncertainty in output of renewable generation sources.

When uncontrollable resources fluctuate, optimal power flow (OPF), routinely used by the electric power industry to redispatch hourly controllable generation (coal, gas, and hydro plants) over control areas of transmission networks, can result in grid instability and, potentially, cascading outages. This risk arises because OPF dispatch is computed without awareness of major uncertainty, in particular fluctuations in renewable output. As a result, grid operation under OPF with renewable variability can lead to frequent conditions where power line flow ratings are significantly exceeded. Such a condition, which is borne by our simulations of real grids, is considered undesirable in power engineering practice. Possibly, it can lead to a risky outcome that compromises grid stability--line tripping. Smart grid goals include a commitment to large penetration of highly fluctuating renewables, thus calling to reconsider current practices, in particular the use of standard OPF. Our chance-constrained (CC) OPF corrects the problem and mitigates dangerous renewable fluctuations with minimal changes in the current operational procedure. Assuming availability of a reliable wind forecast parameterizing the distribution function of the uncertain generation, our CC-OPF satisfies all the constraints with high probability while simultaneously minimizing the cost of economic redispatch. CC-OPF allows efficient implementation, e.g., solving a typical instance over the 2746-bus Polish network in 20 seconds on a standard laptop. [ABSTRACT FROM AUTHOR]

The problem of packing ellipsoids of different sizes and shapes into an ellipsoidal container so as to minimize a measure of overlap between ellipsoids is considered. A bilevel optimization formulation is given, together with an algorithm for the general case and a simpler algorithm for the special case in which all ellipsoids are in fact spheres. Convergence results are proved and computational experience is described and illustrated. The motivating application--chromosome organization in the human cell nucleus--is discussed briefly, and some illustrative results are presented. [ABSTRACT FROM AUTHOR]

We analyze globally convergent, derivative-free trust-region algorithms relying on radial basis function interpolation models. Our results extend the recent work of Conn, Scheinberg, and Vicente [SIAM J. Optim., 20 (2009), pp. 387-415] to fully linear models that have a nonlinear term. We characterize the types of radial basis functions that fit in our analysis and thus show global convergence to first-order critical points for the ORBIT algorithm of Wild, Regis, and Shoemaker [SIAM J. Sci. Comput., 30 (2008), pp. 3197-3219]. Using ORBIT, we present numerical results for different types of radial basis functions on a series of test problems. We also demonstrate the use of ORBIT in finding local minima on a computationally expensive environmental engineering problem involving remediation of contaminated groundwater. [ABSTRACT FROM AUTHOR]

The sparsity constrained rank-one matrix approximation problem is a difficult mathematical optimization problem which arises in a wide array of useful applications in engineering, machine learning, and statistics, and the design of algorithms for this problem has attracted intensive research activities. We introduce an algorithmic framework, called ConGradU, that unifies a variety of seemingly different algorithms that have been derived from disparate approaches, and that allows for deriving new schemes. Building on the old and well-known conditional gradient algorithm, ConGradU is a simplified version with unit step size that yields a generic algorithm which either is given by an analytic formula or requires a very low computational complexity. Mathematical properties are systematically developed and numerical experiments are given. [ABSTRACT FROM AUTHOR]

There are many industrial situations where rods are used to stir a fluid, or where rods repeatedly knead a material such as bread dough or taffy. The goal in these applications is to stretch either material lines (in a fluid) or the material itself (for dough or taffy) as rapidly ms possible. The growth rate of material lines is conveniently given by the topological entropy of the rod motion. We discuss the problem of optimizing such rod devices from a topological viewpoint. We express rod motions in terms of generators of the braid group and assign a cost based on the minimum number of generators needed to write the braid. We show that for one cost function--the topological entropy per generator the optimal growth rate is the logarithm of the golden ratio. For a more realistic cost function, involving the topological entropy per operation where rods are allowed to move together, the optimal growth rate is the logarithm of the silver ratio, 1 + √2. We show how to construct devices that realize this optimal growth, which we call silver mixers. [ABSTRACT FROM AUTHOR]

We show how the computational power and programmability of modern graphics processing units (GPUs) can be used to efficiently solve large-scale pixel-based material distribution problems using a gradient-based optimality criterion method. To illustrate the principle, a so-called topology optimization problem that results in a constrained nonlinear programming problem with over 4 million decision variables is solved on a commodity GPU. [ABSTRACT FROM AUTHOR]

Research on multigrid methods for optimization problems is reviewed. Optimization problems considered include shape design, parameter optimization, anti optimal control problems governed by partial differential equations of elliptic, parabolic, and hyperbolic type. [ABSTRACT FROM AUTHOR]

Provides an overview of direct search methods that can be used to solve multidimensional optimization problem in mathematics. Effectiveness of the method in quantifying function values; Challenge of solving constrained optimization problems with direct methods.

We present a collection of fourteen conjectures and open problems in the fields of nonlinear analysis and optimization. These problems can be classified into three groups: problems of pure mathematical interest, problems motivated by scientific computing and applications, and problems whose solutions are known but for which we would like to know better proofs. For each problem we provide a succinct presentation, a list of appropriate references, and a view of the state of the art of the subject. [ABSTRACT FROM AUTHOR]

We propose a novel approach for the parametrically robust design of dynamic systems. The approach can be applied to system models with parameters that are uncertain in the sense that values for these parameters are not known precisely, but only within certain bounds. The novel approach is guaranteed to find an optimal steady state that is stable for each parameter combination within these bounds. Our approach combines the use of a standard solver for constrained optimization problems with the rigorous solution of nonlinear systems. The constraints for the optimization problems are based on the concept of parameter space normal vectors that measure the distance of a tentative optimum to the nearest known critical point, i.e., a point where stability may be lost. Such normal vectors are derived using methods from nonlinear dynamics. After the optimization, the rigorous solver is used to provide a guarantee that no critical points exist in the vicinity of the optimum, or to detect such points. In the latter case, the optimization is resumed, taking the newly found critical points into account. This optimize-and-verify procedure is repeated until the rigorous nonlinear solver can guarantee that the vicinity of the optimum is free from critical points and therefore the optimum is parametrically robust. In contrast to existing design methodologies, our approach can be automated and does not rely on the experience of the designing engineer. A simple model of a fermenter is used to illustrate the concepts and the order of activities arising in a typical design process. [ABSTRACT FROM AUTHOR]

We consider the problem of scheduling operations in bufferless robotic cells that produce identical parts. Maximizing the long-term average throughput of parts is an important problem in both theory and practice. We define an appropriate state space required to analyze this problem and show that cyclic schedules which repeat a fixed sequence of robot moves indefinitely are the only ones that need to be considered. For the different classes of robotic cells studied in the literature, we discuss the current state of knowledge with respect to cyclic schedules. Finally, we discuss the importance of two fundamental open problems concerning optimal cyclic schedules, special cases for which these problems have been solved, and attempts to solve the general case. [ABSTRACT FROM AUTHOR]

Sequential quadratic programming (SQP) methods have proved highly effective for solving constrained optimization problems with smooth nonlinear functions in the objective and constraints. Here we consider problems with general inequality constraints (linear and nonlinear). We assume that first derivatives are available and that the constraint gradients are sparse. Second derivatives are assumed to be unavailable or too expensive to calculate. We discuss an SQP algorithm that uses a smooth augmented Lagrangian merit function and makes explicit provision for infeasibility in the original problem and the QP subproblems. The Hessian of the Lagrangian is approximated using a limited-memory quasi-Newton method. SNOPT is a particular implementation that uses a reduced-Hessian semidefinite QP solver (SQOPT) for the QP subproblems. It is designed for problems with many thousands of constraints and variables but is best suited for problems with a moderate number of degrees of freedom (say, up to 2000). Numerical results are given for most of the CUTEr and COPS test collections (about 1020 examples of all sizes up to 40000 constraints and variables, and up to 20000 degrees of freedom). [ABSTRACT FROM AUTHOR]

Direct search methods are best known as unconstrained optimization techniques that do not explicitly use derivatives. Direct search methods were formally proposed and widely applied in the 1960s but fell out of favor with the mathematical optimization community by the early 1970s because they lacked coherent mathematical analysis. Nonetheless, users remained loyal to these methods, most of which were easy to program, some of which were reliable. In the past fifteen years, these methods have seen a revival due, in part, to the appearance of mathematical analysis, as well as to interest in parallel and distributed computing. This review begins by briefly summarizing the history of direct search methods and considering the special properties of problems for which they are well suited. Our focus then turns to a broad class of methods for which we provide a unifying framework that lends itself to a variety of convergence results. The underlying principles allow generalization to handle bound constraints and linear constraints. We also discuss extensions to problems with nonlinear constraints. [ABSTRACT FROM AUTHOR]

Examines the interior methods for nonlinearly constrained optimization. Details of inequality-constrained optimization; Discussion of classical barrier methods; Examination of the Newton's method and barrier functions.

Proposes a nonlinear optimization model for the design of a control mechanism to manage bets in the four-digit number game. Discussion of control mechanism; Analysis of existing control mechanism for the game; Empirical results.

Focuses on the correlation between optimality conditions for quadratic optimization problems, qualitative properties in nonlinear selection replicator dynamics and the concepts of evolutionary game theory. Properties of selection replicator dynamics; Elements of the game theory; Conditions for general optimization problems.

Describes several of the case studies on NEOS Guide, a Web site that contains informational and educational material about optimization. Use of interactivity to build intuition that allows users define their own problems and examine the corresponding solutions; Problem of the United States Army after the end of World War II; Portfolio optimization problem.

Presents an overview of progress made in the theory of optimization problems with perturbations. Description of nonlinear programming problems; Results of stability and sensitivity analysis of optimization problems; Identification of real-valued functions.