71 results
Search Results
2. High-Dimensional Gaussian Sampling: A Review and a Unifying Approach Based on a Stochastic Proximal Point Algorithm.
- Author
-
Vono, Maxime, Dobigeon, Nicolas, and Chainais, Pierre
- Subjects
MARKOV chain Monte Carlo ,NUMERICAL solutions for linear algebra ,MATHEMATICAL optimization ,ALGORITHMS - Abstract
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]
- Published
- 2022
- Full Text
- View/download PDF
3. What Tropical Geometry Tells Us about the Complexity of Linear Programming.
- Author
-
Allamigeon, Xavier, Benchimol, Pascal, Gaubert, Stéphane, and Joswig, Michael
- Subjects
GEOMETRY ,MATHEMATICAL optimization ,LINEAR programming ,GAME theory ,INTERIOR-point methods ,ALGORITHMS - Abstract
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 Ω(2
r ). 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]- Published
- 2021
- Full Text
- View/download PDF
4. Phase Retrieval via Matrix Completion.
- Author
-
Candes, Emmanuel J., Eldar, Yonina C., Strohmer, Thomas, and Voroninski, Vladislav
- Subjects
CRYSTALLOGRAPHY ,IMAGING systems ,MATHEMATICAL optimization ,CONVEX functions ,SIGNAL-to-noise ratio - Abstract
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]
- Published
- 2015
- Full Text
- View/download PDF
5. Semidual Regularized Optimal Transport.
- Author
-
Cuturi, Marco and Peyré, Gabriel
- Subjects
TRANSPORT theory ,MATHEMATICAL optimization ,PROBABILITY theory - Abstract
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]
- Published
- 2018
- Full Text
- View/download PDF
6. The Singular Value Decomposition: Anatomy of Optimizing an Algorithm for Extreme Scale.
- Author
-
Gates, Mark, Haidar, Azzam, Kurzak, Jakub, Luszczek, Piotr, Tomov, Stanimire, Ichitaro Yamazaki, and Dongarra, Jack
- Subjects
SINGULAR value decomposition ,MATHEMATICAL optimization ,ALGORITHMS - Abstract
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]
- Published
- 2018
- Full Text
- View/download PDF
7. Optimization Methods for Large-Scale Machine Learning.
- Author
-
Bottou, Léon, Curtis, Frank E., and Nocedal, Jorge
- Subjects
MATHEMATICAL optimization ,ARTIFICIAL neural networks ,DEEP learning - Abstract
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]
- Published
- 2018
- Full Text
- View/download PDF
8. The Trace Ratio Optimization Problem.
- Author
-
Ngo, T. T., Bellalij, M., and Saad, Y.
- Subjects
MATRICES (Mathematics) ,MATHEMATICAL optimization ,NUMERICAL analysis ,PROBLEM solving ,MATHEMATICS problems & exercises - Abstract
This paper considers the problem of optimizing the ratio Tr[V
T 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]- Published
- 2012
- Full Text
- View/download PDF
9. Local Warming.
- Author
-
Vanderbei, Robert J.
- Subjects
METEOROLOGICAL stations ,LINEAR programming ,MATHEMATICAL optimization ,REGRESSION analysis ,SOLAR cycle - Abstract
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]
- Published
- 2012
- Full Text
- View/download PDF
10. A Discrete Invitation to Quantum Filtering and Feedback Control.
- Author
-
Bouten, Luc, Van Handel, Ramon, and James, Matthew R.
- Subjects
QUANTUM theory ,DYNAMIC programming ,STOCHASTIC processes ,LYAPUNOV functions ,PROBABILITY theory ,MATHEMATICAL optimization - Abstract
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]
- Published
- 2009
- Full Text
- View/download PDF
11. Constrained Nonlinear Programming for Volatility Estimation with GARCH Models.
- Author
-
Altay-Salih, Aslihan, Pinar, Mustafa C., and Leyffer, Sven
- Subjects
NONLINEAR programming ,MATHEMATICAL optimization ,LINEAR programming ,AUTOREGRESSION (Statistics) ,STOCHASTIC processes ,ECONOMETRICS ,ESTIMATION theory ,MATHEMATICAL models - Abstract
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]
- Published
- 2003
- Full Text
- View/download PDF
12. SIGEST.
- Subjects
PARTICLE swarm optimization ,MATHEMATICAL optimization - Abstract
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.
- Published
- 2014
- Full Text
- View/download PDF
13. SIGEST.
- Subjects
MATHEMATICAL optimization ,RATIO analysis - Abstract
An introduction to the article "The Trace Ratio Optimization Problem," by T. T. Ngo, M. Bellalij, and Y. Saad, is presented.
- Published
- 2012
- Full Text
- View/download PDF
14. SIGEST.
- Subjects
MATHEMATICAL optimization ,MATHEMATICAL analysis - Abstract
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.
- Published
- 2013
- Full Text
- View/download PDF
15. Theory and Applications of Robust Optimization.
- Author
-
Bertsimas, Dimitris, Brown, David B., and Caramanis, Constantine
- Subjects
ROBUST optimization ,MATHEMATICAL research ,MATHEMATICAL optimization ,MATHEMATICAL models ,FINANCE ,STATISTICS - Abstract
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]
- Published
- 2011
- Full Text
- View/download PDF
16. Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization.
- Author
-
Recht, Benjamin, Fazel, Maryam, and Parrilo, Pablo A.
- Subjects
MATRICES (Mathematics) ,EQUATIONS ,MAXIMA & minima ,MATHEMATICAL optimization ,MATHEMATICS - Abstract
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]
- Published
- 2010
- Full Text
- View/download PDF
17. Nonsmooth Coordination and Geometric Optimization via Distributed Dynamical Systems.
- Author
-
Cortés, Jorge and Bullo, Francesco
- Subjects
GEOMETRY ,MATHEMATICS ,EUCLID'S elements ,MATHEMATICAL optimization ,MAXIMA & minima ,OPERATIONS research - Abstract
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]
- Published
- 2009
- Full Text
- View/download PDF
18. Minimizing Effective Resistance of a Graph.
- Author
-
Ghosh, Arpita, Boyd, Stephen, and Saberi, Amin
- Subjects
LAPLACIAN operator ,EIGENVALUES ,MARKOV processes ,MATHEMATICAL optimization ,GRAPHIC methods ,MATHEMATICAL analysis - Abstract
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]
- Published
- 2008
- Full Text
- View/download PDF
19. The Fastest Mixing Markov Process on a Graph and a Connection to a Maximum Variance Unfolding Problem.
- Author
-
Jun Sun, Boyd, Stephen, Lin Xiao, and Diaconis, Persi
- Subjects
MARKOV processes ,STOCHASTIC processes ,UNIFORM distribution (Probability theory) ,AUTOCORRELATION (Statistics) ,GRAPH theory ,MATHEMATICAL optimization - Abstract
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]- Published
- 2006
- Full Text
- View/download PDF
20. Optimization in High Dimensions via Accelerated, Parallel, and Proximal Coordinate Descent.
- Author
-
Fercoq, Olivier and Richtárik, Peter
- Subjects
MATHEMATICAL optimization ,LIPSCHITZ spaces ,BIG data - Abstract
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ωLR
2 /(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]- Published
- 2016
- Full Text
- View/download PDF
21. SIGEST.
- Subjects
GEOMETRY ,MATHEMATICAL optimization - Abstract
An introduction to the journal is presented in which the editor discusses an article on geometric optimization by Jorge Cortéz et al.
- Published
- 2009
- Full Text
- View/download PDF
22. Problems and Techniques.
- Author
-
Ipsen, Ilse and Editor, Section
- Subjects
MATHEMATICAL optimization ,ASYMPTOTIC expansions ,INTEGRALS ,DIFFERENCE equations ,MATHEMATICAL functions - Abstract
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.
- Published
- 2006
- Full Text
- View/download PDF
23. SURVEY and REVIEW.
- Author
-
Sanz-Serna, J. M.
- Subjects
SCATTERING (Mathematics) ,MATHEMATICAL optimization ,ALGORITHMS - Abstract
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."
- Published
- 2018
- Full Text
- View/download PDF
24. Generalized Chebyshev Bounds via Semidefinite Programming.
- Author
-
Vandenberghe, Lieven, Boyd, Stephen, and Comanor, Katherine
- Subjects
CHEBYSHEV systems ,MATHEMATICAL programming ,MATHEMATICAL optimization ,CONVEX domains ,DUALITY theory (Mathematics) ,MATHEMATICAL analysis - Abstract
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]
- Published
- 2007
- Full Text
- View/download PDF
25. Splines Are Universal Solutions of Linear Inverse Problems with Generalized TV Regularization.
- Author
-
Unser, Michael, Fageot, Julien, and Ward, John Paul
- Subjects
MATHEMATICAL optimization ,SPLINES - Abstract
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]
- Published
- 2017
- Full Text
- View/download PDF
26. JuMP: A Modeling Language for Mathematical Optimization.
- Author
-
Dunning, Iain, Huchette, Joey, and Lubin, Miles
- Subjects
MATHEMATICAL optimization ,JULIA (Computer program language) ,VISUALIZATION - Abstract
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]
- Published
- 2017
- Full Text
- View/download PDF
27. Optimal Ball Placement in Rugby Conversions.
- Author
-
Freitas, Pedro
- Subjects
MATHEMATICAL optimization ,RUGBY football ,RUGBY football players ,MATHEMATICS ,BALLS (Sporting goods) - Abstract
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]
- Published
- 2014
- Full Text
- View/download PDF
28. RESEARCH SPOTLIGHTS.
- Author
-
Wright, Stephen J.
- Subjects
CONSTRAINED optimization ,MATHEMATICAL optimization ,RENEWABLE energy sources - Abstract
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.
- Published
- 2014
- Full Text
- View/download PDF
29. Chance-Constrained Optimal Power Flow: Risk-Aware Network Control under Uncertainty.
- Author
-
Bienstock, Daniel, Chertkov, Michael, and Harnett, Sean
- Subjects
MATHEMATICAL optimization ,MATHEMATICAL analysis ,UNCERTAINTY (Information theory) ,WIND power plants ,ELECTRIC power - Abstract
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]
- Published
- 2014
- Full Text
- View/download PDF
30. Packing Ellipsoids with Overlap.
- Author
-
Uhler, Caroline and Wright, Stephen J.
- Subjects
ELLIPSOIDS ,MATHEMATICAL optimization ,ALGORITHMS ,STOCHASTIC convergence ,HUMAN cell nuclei ,HUMAN chromosomes - Abstract
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]
- Published
- 2013
- Full Text
- View/download PDF
31. Global Convergence of Radial Basis Function Trust-Region Algorithms for Derivative-Free Optimization.
- Author
-
Wild, Stefan M. and Shoemaker, Christine
- Subjects
MATHEMATICAL optimization ,MATHEMATICAL analysis ,RADIAL basis functions ,APPROXIMATION theory ,FUNCTIONAL analysis - Abstract
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]
- Published
- 2013
- Full Text
- View/download PDF
32. Conditional Gradient Algorithms for Rank-One Matrix Approximations with a Sparsity Constraint.
- Author
-
Luss, Ronny and Teboulle, Marc
- Subjects
APPROXIMATION theory ,MATHEMATICAL optimization ,ALGORITHMS ,GENETIC algorithms ,COMPUTATIONAL complexity - Abstract
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]
- Published
- 2013
- Full Text
- View/download PDF
33. Topological Optimization of Rod-Stirring Devices.
- Author
-
Finn, Matthew D. and Thiffeault, Jean-Luc
- Subjects
BARS (Engineering) ,ENTROPY ,TOPOLOGY ,LOGARITHMS ,MATHEMATICAL optimization - Abstract
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]
- Published
- 2011
- Full Text
- View/download PDF
34. Megapixel Topology Optimization on a Graphics Processing Unit.
- Author
-
Wadbro, Eddie and Berggren, Martin
- Subjects
GRAPHICS processing units ,TOPOLOGY ,PIXELS ,MATHEMATICAL optimization ,DISTRIBUTION (Probability theory) ,NONLINEAR programming ,POISSON'S equation - Abstract
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]
- Published
- 2009
- Full Text
- View/download PDF
35. Multigrid Methods for PDE Optimization.
- Author
-
Borzì, Alfio and Schulz, Volker
- Subjects
PARTIAL differential equations ,MULTIGRID methods (Numerical analysis) ,MATHEMATICAL optimization ,NUMERICAL analysis ,EQUATIONS ,MATHEMATICS - Abstract
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]
- Published
- 2009
- Full Text
- View/download PDF
36. SURVEY and REVIEW.
- Author
-
LeVeque, Randy
- Subjects
MATHEMATICS ,MATHEMATICAL optimization ,MATHEMATICAL functions ,MAXIMA & minima ,MATHEMATICAL analysis - Abstract
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.
- Published
- 2003
- Full Text
- View/download PDF
37. Potpourri of Conjectures and Open Questions in Nonlinear Analysis and Optimization.
- Author
-
Hiriart-Urruty, Jean-Baptiste
- Subjects
NONLINEAR statistical models ,MATHEMATICAL optimization ,MATRICES (Mathematics) ,CONVEX functions ,LEGENDRE'S functions ,MATHEMATICAL models - Abstract
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]
- Published
- 2007
- Full Text
- View/download PDF
38. A Hybrid Approach for Efficient Robust Design of Dynamic Systems.
- Author
-
Mönnigmann, Martin, Marquardt, Wolfgang, Bischof, Christian H., Beelitz, Thomas, Lang, Bruno, and Willems, Paul
- Subjects
DYNAMICS ,PARAMETER estimation ,MATHEMATICAL optimization ,ANALYTICAL mechanics ,ROBUST optimization ,NONLINEAR systems - Abstract
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]
- Published
- 2007
- Full Text
- View/download PDF
39. Dominance of Cyclic Solutions and Challenges in the Scheduling of Robotic Cells.
- Author
-
Dawande, Milind W., Geismar, H. Neil, and Sethi, Suresh P.
- Subjects
COMBINATORIAL optimization ,ROBOTICS ,DISCRETE-time systems ,COMBINATORICS ,MATHEMATICAL optimization - Abstract
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]
- Published
- 2006
- Full Text
- View/download PDF
40. SNOPT: An SQP Algorithm for Large-Scale Constrained Optimization.
- Author
-
Gill, Philip E., Murray, Walter, and Saunders, Michael A.
- Subjects
QUADRATIC programming ,NONLINEAR programming ,MATHEMATICAL optimization ,ALGORITHMS ,LAGRANGIAN functions - Abstract
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]
- Published
- 2005
- Full Text
- View/download PDF
41. Optimization by Direct Search: New Perspectives on Some Classical and Modern Methods.
- Author
-
Kolda, Tamara G., Lewis, Robert Michael, and Torczon, Virginia
- Subjects
MATHEMATICAL optimization ,MATHEMATICAL analysis ,DISTRIBUTED computing ,MATHEMATICAL programming ,CONSTRAINT satisfaction ,MAXIMA & minima - Abstract
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]
- Published
- 2003
- Full Text
- View/download PDF
42. Interior Methods for Nonlinear Optimization.
- Author
-
Forsgren, Anders, Gill, Philip E., and Wright, Margaret H.
- Subjects
MATHEMATICAL optimization ,NONLINEAR programming ,MATHEMATICAL analysis - Abstract
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.
- Published
- 2002
- Full Text
- View/download PDF
43. Managing Risk in a Four-Digit Number Game.
- Author
-
Chung-Piaw teo and Siew Meng Leong
- Subjects
MATHEMATICAL optimization ,GAMBLING systems ,CONTROL theory (Engineering) - Abstract
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.
- Published
- 2002
- Full Text
- View/download PDF
44. Regularity versus Degeneracy in Dynamics, Games, and Optimization: A Unified Approach to Different Aspects.
- Author
-
Bomze, Immanuel M.
- Subjects
MATHEMATICAL optimization ,NONLINEAR theories ,GAME theory - Abstract
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.
- Published
- 2002
- Full Text
- View/download PDF
45. Computationally tractable counterparts of distributionally robust constraints on risk measures
- Author
-
Bertrand Melenberg, Dick den Hertog, Krzysztof Postek, Center Ph. D. Students, Research Group: Operations Research, and Econometrics and Operations Research
- Subjects
Mathematical optimization ,050208 finance ,021103 operations research ,Optimization problem ,Computer science ,Applied Mathematics ,Risk measure ,05 social sciences ,0211 other engineering and technologies ,Robust optimization ,robust optimization ,support functions ,02 engineering and technology ,robust counterpart ,Theoretical Computer Science ,Constraint (information theory) ,Set (abstract data type) ,risk measure ,Computational Mathematics ,0502 economics and business ,Range (statistics) ,nonlinear inequality ,Probability distribution ,Random variable - Abstract
In optimization problems appearing in fields such as economics, finance, or engineering, it is often important that a risk measure of a decision-dependent random variable stays below a prescribed level. At the same time, the underlying probability distribution determining the risk measure's value is typically known only up to a certain degree and the constraint should hold for a reasonably wide class of probability distributions. In addition, the constraint should be computationally tractable. In this paper we review and generalize results on the derivation of tractable counterparts of such constraints for discrete probability distributions. Using established techniques in robust optimization, we show that the derivation of a tractable robust counterpart can be split into two parts, one corresponding to the risk measure and the other to the uncertainty set. This holds for a wide range of risk measures and uncertainty sets for probability distributions defined using statistical goodness-of-fit tests or probability metrics. In this way, we provide a unified framework for reformulating this class of constraints, extending the number of solvable risk measure-uncertainty set combinations considerably, also including risk measures that are nonlinear in the probabilities. To provide a clear overview for the user, we provide the computational tractability status for each of the uncertainty set-risk measure pairs, some of which have been solved in the literature. Examples, including portfolio optimization and antenna array design, illustrate the proposed approach in a theoretical and numerical setting.
- Published
- 2016
46. Optimization case studies in the NEOS Guide.
- Author
-
Czyzyk, Joseph and Wisniewski, Timothy
- Subjects
MATHEMATICAL optimization ,WEBSITES - Abstract
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.
- Published
- 1999
- Full Text
- View/download PDF
47. Optimization problems with perturbations: A guided tour.
- Author
-
Bonnans, J. Frederic and Shapiro, Alexander
- Subjects
MATHEMATICAL optimization ,PERTURBATION theory - Abstract
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.
- Published
- 1998
- Full Text
- View/download PDF
48. Lagrange Multiplier Approach to Variational Problems and Applications.
- Author
-
ROSEN, I. GARY
- Subjects
MATHEMATICAL optimization ,NONFICTION - Abstract
The article reviews the book "Lagrange Multiplier Approach to Variational Problems and Applications," by Kazufumi Ito and Karl Kunisch.
- Published
- 2011
49. Book Reviews.
- Author
-
Nazareth, J. Larry and O'Malley Jr., Robert E.
- Subjects
NONFICTION ,MATHEMATICAL optimization - Abstract
Reviews the book `Iterative Methods for Optimization,' by C.T. Kelley.
- Published
- 2000
50. Introduction to Global Optimization Exploiting Space-Filling Curves.
- Author
-
BUTENKO, SERGIY
- Subjects
MATHEMATICAL optimization ,NONFICTION - Published
- 2015
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.