Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top

2015 | Book

A Conic Representation of the Convex Hull of Disjunctive Sets and Conic Cuts for Integer Second Order Cone Optimization Read chapter Read first chapter

Numerical Analysis and Optimization

NAO-III, Muscat, Oman, January 2014

Editors: Mehiddin Al-Baali, Lucio Grandinetti, Anton Purnama

Publisher: Springer International Publishing

Book Series : Springer Proceedings in Mathematics & Statistics

Part of: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Login to get access
insite
SEARCH

About this book

Presenting the latest findings in the field of numerical analysis and optimization, this volume balances pure research with practical applications of the subject. Accompanied by detailed tables, figures, and examinations of useful software tools, this volume will equip the reader to perform detailed and layered analysis of complex datasets.

Many real-world complex problems can be formulated as optimization tasks. Such problems can be characterized as large scale, unconstrained, constrained, non-convex, non-differentiable, and discontinuous, and therefore require adequate computational methods, algorithms, and software tools. These same tools are often employed by researchers working in current IT hot topics such as big data, optimization and other complex numerical algorithms on the cloud, devising special techniques for supercomputing systems.

The list of topics covered include, but are not limited to: numerical analysis, numerical optimization, numerical linear algebra, numerical differential equations, optimal control, approximation theory, applied mathematics, algorithms and software developments, derivative free optimization methods and programming models. The volume also examines challenging applications to various types of computational optimization methods which usually occur in statistics, econometrics, finance, physics, medicine, biology, engineering and industrial sciences.

Table of Contents

Frontmatter
A Conic Representation of the Convex Hull of Disjunctive Sets and Conic Cuts for Integer Second Order Cone Optimization
Abstract
We study the convex hull of the intersection of a convex set E and a disjunctive set. This intersection is at the core of solution techniques for Mixed Integer Convex Optimization. We prove that if there exists a cone K (resp., a cylinder C) that has the same intersection with the boundary of the disjunction as E, then the convex hull is the intersection of E with K (resp., C).The existence of such a cone (resp., a cylinder) is difficult to prove for general conic optimization. We prove existence and unicity of a second order cone (resp., a cylinder), when E is the intersection of an affine space and a second order cone (resp., a cylinder). We also provide a method for finding that cone, and hence the convex hull, for the continuous relaxation of the feasible set of a Mixed Integer Second Order Cone Optimization (MISOCO) problem, assumed to be the intersection of an ellipsoid with a general linear disjunction. This cone provides a new conic cut for MISOCO that can be used in branch-and-cut algorithms for MISOCO problems.
Pietro Belotti, Julio C. Góez, Imre Pólik, Ted K. Ralphs, Tamás Terlaky
Runge–Kutta Methods for Ordinary Differential Equations
Abstract
Since their first discovery by Runge (Math Ann 46:167–178, 1895), Heun (Z Math Phys 45:23–38, 1900) and Kutta (Z Math Phys 46:435–453, 1901), Runge–Kutta methods have been one of the most important procedures for the numerical solution of ordinary differential equation systems. This survey paper ranges over many aspects of Runge–Kutta methods, including order conditions, order barriers, the efficient implementation of implicit methods, effective order methods and strong stability-preserving methods. Finally, applications to the analysis and implementation of G-symplectic methods will be discussed.
J. C. Butcher
A Positive Barzilai–Borwein-Like Stepsize and an Extension for Symmetric Linear Systems
Abstract
The Barzilai and Borwein (BB) gradient method has achieved a lot of attention since it performs much more better than the classical steepest descent method. In this paper, we analyze a positive BB-like gradient stepsize and discuss its possible uses. Specifically, we present an analysis of the positive stepsize for two-dimensional strictly convex quadratic functions and prove the R-superlinear convergence under some assumption. Meanwhile, we extend BB-like methods for solving symmetric linear systems and find that a variant of the positive stepsize is very useful in the context. Some useful discussions on the positive stepsize are also given.
Yu-Hong Dai, Mehiddin Al-Baali, Xiaoqi Yang
Necessary Optimality Conditions for the Control of Partial Integro-Differential Equations
Abstract
In this paper we derive necessary optimality conditions for optimization problems with partial integro-differential equations. We use the concept of mild solutions coming from semi-group theory for evolution equations. The application considered is a model for a cell adhesion process which leads to a two-dimensional system of nonlinear partial integro-differential equations. The objective function is of tracking type with the coefficients in the integral operators as unknown control or design variables. We derive necessary optimality conditions in the form of an adjoint system of partial integro-differential equations.
Leonhard Frerick, Ekkehard W. Sachs, Lukas A. Zimmer
The AMPL Modeling Language: An Aid to Formulating and Solving Optimization Problems
Abstract
Optimization problems arise in many contexts. Sometimes finding a good formulation takes considerable effort. A modeling language, such as AMPL, facilitates experimenting with formulations and simplifies using suitable solvers to solve the resulting optimization problems. AMPL lets one use notation close to familiar mathematical notation to state variables, objectives, and constraints and the sets and parameters that may be involved. AMPL does some problem transformations and makes relevant problem information available to solvers. The AMPL command language permits computing and displaying information about problem details and solutions returned by solvers. It also lets one modify problem formulations and solve sequences of problems. AMPL addresses both continuous and discrete optimization problems and offers some constraint-programming facilities for the latter. More generally, AMPL permits stating and solving problems with complementarity constraints. For continuous problems, AMPL makes first and second derivatives available via automatic differentiation. The freely available AMPL/solver interface library (ASL) facilitates interfacing with solvers. This paper gives an overview of AMPL and its interaction with solvers and discusses some problem transformations and implementation techniques. It also looks forward to possible enhancements to AMPL.
David M. Gay
An Interior-Point ℓ 1 $$\boldsymbol{\ell_{1}}$$ -Penalty Method for Nonlinear Optimization
Abstract
We describe a mixed interior/exterior-point method for nonlinear programming that handles constraints by way of an ℓ 1-penalty function. The penalty problem is reformulated as a smooth inequality-constrained problem that always possesses bounded multipliers, and that may be solved using interior-point techniques as finding a strictly feasible point is trivial. If finite multipliers exist for the original problem, exactness of the penalty function eliminates the need to drive the penalty parameter to infinity. If the penalty parameter needs to increase without bound and if feasibility is ultimately attained, a certificate of degeneracy is delivered. Global and fast local convergence of the proposed scheme are established and practical aspects of the method are discussed.
Nick I. M. Gould, Dominique Orban, Philippe L. Toint
An ℓ 1-Penalty Scheme for the Optimal Control of Elliptic Variational Inequalities
Abstract
Anℓ 1-penalty scheme in function space for the optimal control of elliptic variational inequalities is proposed. In anL 2-tracking context, an iterative algorithm is proven to generate a sequence which converges to some weakly C-stationary point and, under certain conditions, even to a strongly stationary point of the original problem. In the case of point tracking control, where the objective contains pointwise function evaluations of the state variable, a modified model problem with constraints on the dual variable associated with the variational inequality constraint is introduced and an auxiliary problem that penalizes not only the complementarity, but also the state constraint, is analyzed. Passing to the limit with the penalty parameter in the stationarity system of the auxiliary problem yields some weak form of a C-stationarity system for the original problem if the additional dual constraints are not active. Finally, numerical results obtained by the new algorithms are documented.
M. Hintermüller, C. Löbhard, M. H. Tber
Reduced Space Dynamics-Based Geo-Statistical Prior Sampling for Uncertainty Quantification of End Goal Decisions
Abstract
The inversion of large-scale ill-posed problems introduces multiple challenges. These include, identifying appropriate noise model, prescription of suitable prior information, design of an informative experiment, uncertainty quantification, incorporation of heterogeneous sources of data, and definition of an appropriate optimization scheme. In the context of flow in porous media, subsurface parameters are inferred through the inversion of oil production data (a process called history matching). In this study, the inherent uncertainty of the problem is mitigated by devising efficient and comprehensive approaches for prior sampling. Despite meticulous efforts to minimize the variability of the solution space, the distribution of the posterior may remain intractable. In particular, geo-statisticians may often propose large sets of prior samples that regardless of their apparent geological distinction are almost entirely flow equivalent. As an antidote, a reduced space hierarchical clustering of flow relevant indicators is proposed for aggregation of these samples. The effectiveness of the method is demonstrated both with synthetic and field scale data. In addition, numerical linear algebra techniques that exploit the special structure of the underlying problems are elucidated.
Lior Horesh, Andrew R. Conn, Eduardo A. Jimenez, Gijs M. van Essen
Solving Multiscale Linear Programs Using the Simplex Method in Quadruple Precision
Abstract
Systems biologists are developing increasingly large models of metabolism and integrated models of metabolism and macromolecular expression. These Metabolic Expression (ME) models lead to sequences of multiscale linear programs for which small solution values of order 10−6 to 10−10 are meaningful. Standard LP solvers do not give sufficiently accurate solutions, and exact simplex solvers are extremely slow. We investigate whether double-precision and quadruple-precision simplex solvers can together achieve reliability at acceptable cost.A double-precision LP solver often provides a reasonably good starting point for a Quad simplex solver. On a range of multiscale examples we find that 34-digit Quad floating-point achieves exceptionally small primal and dual infeasibilities (of order 10−30) when no more than 10−15 is requested. On a significant ME model we also observe robustness in almost all (even small) solution values following relative perturbations of order 10−6 to non-integer data values.Double and Quad Fortran 77 implementations of the linear and nonlinear optimization solver MINOS are available upon request.
Ding Ma, Michael A. Saunders
Real and Integer Extended Rank Reduction Formulas and Matrix Decompositions: A Review
Abstract
We have recently developed an extended rank reducing process for rank reduction of a matrix leading to various matrix decompositions containing the Abaffy-Broyden-Spedicato (ABS) and Wedderburn processes. Notably, the extended process contains both the Wedderburn biconjugation process and the scaled extended ABS class of algorithms. The process provides a general finite iterative approach for constructing factorizations of a matrix and its transpose under a common framework of a general decomposition having various useful structures such as triangular, orthogonal, diagonal, banded and Hessenberg and many others. One main new result is the derivation of an extended rank reducing process for an integer matrix leading to the so-called Smith normal form. For this process, to solve the arising quadratic Diophantine equations, we have proposed two algorithms. Here, we report some numerical results on randomly generated test problems showing a better performance of one algorithm, based on a recent ABS algorithm, in controlling the size of the solution. We also report results obtained by our algorithm on the Smith normal form having a more balanced distribution of the intermediate values as compared to the ones obtained by Maple.
Nezam Mahdavi-Amiri, Effat Golpar-Raboky
Distributed Block Coordinate Descent for Minimizing Partially Separable Functions
Abstract
A distributed randomized block coordinate descent method for minimizing a convex function of a huge number of variables is proposed. The complexity of the method is analyzed under the assumption that the smooth part of the objective function is partially block separable. The number of iterations required is bounded by a function of the error and the degree of separability, which extends the results in Richtárik and Takác (Parallel Coordinate Descent Methods for Big Data Optimization, Mathematical Programming, DOI:10.1007/s10107-015-0901-6) to a distributed environment. Several approaches to the distribution and synchronization of the computation across a cluster of multi-core computer are described and promising computational results are provided.
Jakub Mareček, Peter Richtárik, Martin Takáč
Models for Optimization of Power Systems
Abstract
This chapter provides an overview of possible approaches that can be outlined to model and analyze the decision problems encountered in different stages of power production and delivery. The introduced models can be used for the control of two of the most important activities in power system management: production and transmission. In both cases, we describe how a single producer or an entire system can draw benefits from using optimization techniques for fine-tuning the expansion decisions to be taken. The theoretical basis for the analysis is drawn from different branches of operational research and optimization, ranging from mixed integer linear programming to stochastic programming and bilevel programming.
Paolo Pisciella, Marida Bertocchi, Maria Teresa Vespucci
On Chubanov’s Method for Solving a Homogeneous Inequality System
Abstract
We deal with a recently proposed method of Chubanov for solving linear homogeneous systems with positive variables. Our first aim is to show that the performance of this method can be improved by a slight modification of Chubanov’s so-called Basic Procedure. In theory this results in at least the same decrease of the merit function used by Chubanov, but both in theory and in practice the decrease may be much faster. Theoretical evidence for the speed-up follows from a lemma, whereas some numerical experiments provide convincing computational evidence. We also present a complete, somewhat simplified analysis of Chubanov’s Main Algorithm, thereby including also some numerical experiments.
Kees Roos
Backmatter
Metadata
Title
Numerical Analysis and Optimization
Editors
Mehiddin Al-Baali
Lucio Grandinetti
Anton Purnama
Copyright Year
2015
Electronic ISBN
978-3-319-17689-5
Print ISBN
978-3-319-17688-8
DOI
https://doi.org/10.1007/978-3-319-17689-5

Premium Partner

    Image Credits