Convex Programming for Disjunctive Convex Optimization
Sebastián Ceria
1998-01-01
Given a finite number of closed convex sets whose algebraic representationis known, we study the problem of optimizing a convex functionover the closure of the convex hull of the union of these sets.We derive an algebraic characterization of the feasible region in ahigher-dimensional space and propose a solution procedure akin tothe interior-point approach for convex programming.Research partly supported by NSF
Wang, Mengdi
2013-01-01
This thesis considers stochastic methods for large-scale linear systems, variational inequalities, and convex optimization problems. I focus on special structures that lend themselves to sampling, such as when the ...
Advances in Convex Optimization
S. Boyd; L. Vandenberghe; M. Grant
2006-01-01
In this talk I will give an overview of general convex optimization, which can be thought of as an extension of linear programming, and some recently developed subfamilies such as second-order cone, semidefinite, and geometric programming. Like linear programming, we have a fairly complete duality theory, and very effective numerical methods for these problem classes; in addition, recently developed software
Sidky, Emil Y.; Jørgensen, Jakob H.; Pan, Xiaochuan
2012-01-01
The primal-dual optimization algorithm developed in Chambolle and Pock (CP), 2011 is applied to various convex optimization problems of interest in computed tomography (CT) image reconstruction. This algorithm allows for rapid prototyping of optimization problems for the purpose of designing iterative image reconstruction algorithms for CT. The primal-dual algorithm is briefly summarized in the article, and its potential for prototyping is demonstrated by explicitly deriving CP algorithm instances for many optimization problems relevant to CT. An example application modeling breast CT with low-intensity X-ray illumination is presented. PMID:22538474
Convex optimization methods for model reduction
Sou, Kin Cheong, 1979-
2008-01-01
Model reduction and convex optimization are prevalent in science and engineering applications. In this thesis, convex optimization solution techniques to three different model reduction problems are studied.Parameterized ...
Subspace identification via convex optimization
Saunderson, James (James Francis)
2011-01-01
In this thesis we consider convex optimization-based approaches to the classical problem of identifying a subspace from noisy measurements of a random process taking values in the subspace. We focus on the case where the ...
Solving quadratically constrained convex optimization problems with an interior-point method
Csaba Mészáros
2011-01-01
The paper describes the design of our interior-point implementation to solve large-scale quadratically constrained convex optimization problems. We outline the details of the implemented algorithm, which is based on the primal-dual interior-point method. Our discussion includes topics related to starting point strategies and to the implementation of the numerical algebra employed, with emphasis on sparsity and stability issues. Computational results
Goodrich, Michael T.
for realizing a planar 3connected triangulation as a convex polyhedron, which may be of independent interest. Key words: Convex polyhedra, approximation, Steinitz's theorem, planar graphs, art gallery theorems]). They are the product of convex hull algorithms, and are key components for problems in robot motion planning
Convex programming for disjunctive convex optimization
Sebastián Ceria; João Soares
1999-01-01
. Given a finite number of closed convex sets whose algebraic representation is known, we study the problem of finding the minimum\\u000a of a convex function on the closure of the convex hull of the union of those sets. We derive an algebraic characterization\\u000a of the feasible region in a higher-dimensional space and propose a solution procedure akin to the
1 Automatic Code Generation for Real-Time Convex Optimization
Press, 2009. This chapter concerns the use of convex optimization in real-time embedded systems problems. In real-time embedded convex optimization the same optimization problem is solved many times generation system for real-time embedded convex optimization. Such a system scans a description
Joint Equalization and Decoding via Convex Optimization
Kim, Byung Hak
2012-07-16
The unifying theme of this dissertation is the development of new solutions for decoding and inference problems based on convex optimization methods. Th first part considers the joint detection and decoding problem for low-density parity-check (LDPC...
Henrion, Didier
A review of the book "Functional analysis and applied optimization in Banach spaces - Applications to non-convex variational problems" by Fabio Botelho, Springer, Cham, Switzerland, 2014. The book extensively in the landmark book [I. Ekeland, R. Temam. Convex analysis and variational problems. Elsevier
Real-Time Convex Optimization in Signal Processing
Jacob Mattingley; Stephen Boyd
2010-01-01
This article shows the potential for convex optimization methods to be much more widely used in signal processing. In particular, automatic code generation makes it easier to create convex optimization solvers that are made much faster by being designed for a specific problem family. The disciplined convex programming framework that has been shown useful in transforming problems to a standard
A General Framework for Convex Relaxation of Polynomial Optimization Problems over Cones
Kojima, Masakazu
-and-project procedure for 0-1 IPs by Balas-Ceria-Cornu´ejols'93. (d) SCRM (Successive Convex Relaxation Method) for QOPs-1 IPs by Balas-Ceria-Cornu´ejols'93. (d) SCRM (Successive Convex Relaxation Method) for QOPs by Kojima-1 IPs by Balas-Ceria-Cornu´ejols'93. (d) SCRM (Successive Convex Relaxation Method) for QOPs by Kojima
Lossless Convexification of a Class of Optimal Control Problems with Non-Convex Control Constraints
Williams, Brian C.
are needed for manned and robotic missions to Mars, the Moon, and asteroids. The optimal control problems of Technology. Government sponsorship acknowledged. E-mail Addresses: behcet@jpl.nasa.gov (B. A¸cikme¸se), lars@jpl.nasa
Convex Optimization: from Real-Time Embedded
Hall, Julian
Convex Optimization: from Real-Time Embedded to Large-Scale Distributed Stephen Boyd Neal Parikh of Edinburgh, June 25 2014 1 #12;Outline Convex Optimization Real-Time Embedded Optimization Large-Scale Distributed Optimization Summary 2 #12;Outline Convex Optimization Real-Time Embedded Optimization Large
Privacy constraints in regularized convex optimization
Chaudhuri, Kamalika
2009-01-01
Privacy concerns are becoming more important as more personal data moves online. It is therefore of interest to develop versions of data-processing algorithms which can be guaranteed to preserve the privacy of individuals' data. A general method for creating a privacy-preserving version of a convex optimization problem is described, along with applications to machine learning, statistics, and resource allocation problems.
An approximation algorithm for convex multiplicative programming problems
Lizhen Shao; Matthias Ehrgott
2011-01-01
Multiplicative programming problems are difficult global optimization problems known to be NP-hard. In this paper we propose a method for approximately solving convex multiplicative programming problems. This work is based on our previous work \\
Taher Niknam
2010-01-01
Economic dispatch (ED) plays an important role in power system operation. ED problem is a non-smooth and non-convex problem when valve-point effects of generation units are taken into account. This paper presents an efficient hybrid evolutionary approach for solving the ED problem considering the valve-point effect. The proposed algorithm combines a fuzzy adaptive particle swarm optimization (FAPSO) algorithm with Nelder–Mead
August 2000 (Convex Optimization ) JP Goux The mega title ...
An interior point cutting plane method for convex feasibility problem with ..... A Fast Algorithm for Edge-Preserving Variational Multichannel Image Restoration ..... Problem Formulations for Simulation-based Design Optimization using Statistical ...
Privacy Preserving Online Convex Optimization
Jain, Prateek; Thakurta, Abhradeep
2011-01-01
In this paper, we consider the problem of preserving privacy for online convex programming (OCP), an important online learning paradigm. We use the notion of differential privacy as our privacy measure. For this problem, we distill two critical attributes a private OCP algorithm should have, namely, linearly decreasing sensitivity and sub-linear regret bound. Assuming these two conditions, we provide a general framework for OCP that preserves privacy while guaranteeing sub-linear regret bound. We then analyze Implicit Gradient Descent (IGD) algorithm for OCP in our framework, and show $\\tilde O(\\sqrt{T})$ regret bound while preserving differential privacy for Lipschitz continuous, strongly convex cost functions. We also analyze the Generalized Infinitesimal Gradient Ascent (GIGA) method, a popular OCP algorithm, in our privacy preserving framework to obtain $\\tilde O(\\sqrt{T})$ regret bound, albeit for a slightly more restricted class of strongly convex functions with Lipschitz continuous gradient. We then co...
Distributionally Robust Convex Optimization
2013-09-22
Finally, there are deep and insightful connections between classical robust optimization, distributionally ...... The right graph reports the performance of the corresponding .... Statistical Inference. Duxbury Thomson Learning, 2nd edition, 2002.
Convex Duality in Constrained Portfolio Optimization
Jaksa Cvitanic; Ioannis Karatzas
1992-01-01
We study the stochastic control problem of maximizing expected utility from terminal wealth and\\/or consumption, when the portfolio is constrained to take values in a given closed, convex subset of $\\\\mathscr{R}^d$. The setting is that of a continuous-time, Ito process model for the underlying asset prices. General existence results are established for optimal portfolio\\/consumption strategies, by suitably embedding the constrained
Design of PI Controllers based on Non-Convex Optimization
K. J. ÅSTRÖM; H. PANAGOPOULOS; T. HÄGGLUND
1998-01-01
This paper presents an efficient numerical method for designing PI controllers. The design is based on optimization of load disturbance rejection with constraints on sensitivity and weighting of set point response. Thus, the formulation of the design problem captures three essential aspects of industrial control problems, leading to a non-convex optimization problem. Efficient ways to solve the problem are presented.
A Survey of Algorithms for Convex Multicommodity Flow Problems
A. Ouorou; P. Mahey; J.-Ph. Vial
2000-01-01
Routing problems appear frequently when dealing with the operation of communication or transportation networks. Among them, the message routing problem plays a determinant role in the optimization of network performance. Much of the motivation for this work comes from this problem which is shown to belong to the class of nonlinear convex multicommodity flow problems. This paper emphasizes the message
Convex optimization techniques in system identification
Vandenberghe, Lieven
]. The 1-norm and nuclear norm techniques can be extended in several interesting ways. The two typesConvex optimization techniques in system identification Lieven Vandenberghe Electrical: In recent years there has been growing interest in convex optimization techniques for system identification
Optimal Stochastic Approximation Algorithms for Strongly Convex ...
2012-06-18
Jul 1, 2010 ... then SA algorithms became widely used in stochastic optimization (see, e.g., ... where X is a closed convex set in Euclidean space E, X(x) is a simple ..... Proof. The definition of u? and the fact V (˜x,·) is a differentiable convex ...
Pulse Construction in OFDM Systems via convex optimization
Strohmer, Thomas
], a family of intersymbol-interference-free polynomial pulses (POLY) was designed, whose Fourier transform1 Pulse Construction in OFDM Systems via convex optimization Jiadong Xu and Thomas Strohmer systems, we set up an optimization problem to find the transmission pulse which maximizes the signal
Portfolio Optimization under Convex Incentive Schemes
Bichuch, Maxim
2011-01-01
We consider the utility maximization problem of terminal wealth from the point of view of a portfolio manager paid by an incentive scheme given as a convex function $g$ of the terminal wealth. The manager's own utility function $U$ is assumed to be smooth and strictly concave, however the resulting utility function $U \\circ g$ fails to be concave. As a consequence, this problem does not fit into the classical portfolio optimization theory. Using duality theory, we prove wealth-independent existence and uniqueness of the optimal wealth in general (incomplete) semimartingale markets as long as the unique optimizer of the dual problem has no atom with respect to the Lebesgue measure. In many cases, this fact is independent of the incentive scheme and depends only on the structure of the set of equivalent local martingale measures. As example we discuss stochastic volatility models and show that existence and uniqueness of an optimizer are guaranteed as long as the market price of risk satisfies a certain (Mallia...
Dusan Jakovetic; João Xavier; José M. F. Moura
2011-01-01
We study distributed optimization in networked sys- tems, where nodes cooperate to find the optimal quantity of common interest, . The objective function of the cor- responding optimization problem is the sum of private (known only by a node), convex, nodes' objectives and each node im- poses a private convex constraint on the allowed values of .W e solve this
Convex Optimization-based Beamforming: From Receive to Transmit and Network Designs
Alex B. Gershman; Nicholas D. Sidiropoulos; Shahram Shahbazpanahi; Mats Bengtsson
In this article, an overview of advanced convex optimization approaches to multi-sensor beamforming is pre- sented, and connections are drawn between different types of optimization-based beamformers that apply to a broad class of receive, transmit, and network beamformer design problems. It is demonstrated that convex optimization provides an indispensable set of tools for beamforming, enabling rigorous formulation and effective solution
First and second order convex approximation strategies in structural optimization
NASA Technical Reports Server (NTRS)
Fleury, C.
1989-01-01
In this paper, various methods based on convex approximation schemes are discussed that have demonstrated strong potential for efficient solution of structural optimization problems. First, the convex linearization method (Conlin) is briefly described, as well as one of its recent generalizations, the method of moving asymptotes (MMA). Both Conlin and MMA can be interpreted as first-order convex approximation methods that attempt to estimate the curvature of the problem functions on the basis of semiempirical rules. Attention is next directed toward methods that use diagonal second derivatives in order to provide a sound basis for building up high-quality explicit approximations of the behavior constraints. In particular, it is shown how second-order information can be effectively used without demanding a prohibitive computational cost. Various first-order and second-order approaches are compared by applying them to simple problems that have a closed form solution.
Convex Analysis and Optimization with Submodular Functions: a Tutorial
Boyer, Edmond
Convex Analysis and Optimization with Submodular Functions: a Tutorial Francis Bach INRIA - Willow . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 10.2 Cut functions . . . . . . . . . . . . . . . . . .
Optimal static-dynamic hedges for exotic options under convex risk measures
Aytaç ?lhan; Mattias Jonsson; Ronnie Sircar
2009-01-01
We study the problem of optimally hedging exotic derivatives positions using a combination of dynamic trading strategies in underlying stocks and static positions in vanilla options when the performance is quantified by a convex risk measure. We establish conditions for the existence of an optimal static position for general convex risk measures, and then analyze in detail the case of
G. E. Stavroulakis; L. N. Polyakova
1996-01-01
The impact of difference convex optimization techniques on structural analysis algorithms for nonsmooth and non-convex problems is investigated in this paper. Algorithms for the numerical solutions are proposed and studied. The relation to more general optimization techniques and to computational mechanics algorithms is also discussed. The theory is illustrated by a composite beam delamination example.
On an Extension of Condition Number Theory to Non-Conic Convex Optimization
Ordóñez, Fernando
On an Extension of Condition Number Theory to Non-Conic Convex Optimization Robert M. Freund, the modern theory of condition numbers for conic convex optimization: z := minx ctx s.t. Ax - b CY x CX extend the modern theory of condition numbers to the problem format (GPd). As a byproduct, we are able
Vladimir Kolmogorov; Akiyoshi Shioura
Motivated by various applications to computer vision, we consider an integer convex optimization problem which is the dual of the convex cost network ?ow problem. In this paper, we flrst propose a new primal algorithm for computing an optimal solution of the problem. Our primal algorithm iteratively updates primal variables by solving associated minimum cut problems. The main contribution in
Three Problems about Dynamic Convex Hulls Timothy M. Chan
Chan, Timothy M.
Introduction 1.1 Problem 1: Dynamic planar convex hulls with line intersection and related queries Dynamic planar convex hull has long been a favorite topic in classical computational geometry. The problem planar convex hull problem would appear to be fully solved, at least for queries of types (a
Uniform convexity and the splitting problem for selections
Maxim V. Balashov; Dušan Repovš
2009-01-01
We continue to investigate cases when the Repovš–Semenov splitting problem for selections has an affirmative solution for continuous set-valued mappings. We consider the situation in infinite-dimensional uniformly convex Banach spaces. We use the notion of Polyak of uniform convexity and modulus of uniform convexity for arbitrary convex sets (not necessary balls). We study general geometric properties of uniformly convex sets.
Uniform convexity and the splitting problem for selections
Balashov, Maxim V; 10.1016/j.jmaa.2009.06.045
2009-01-01
We continue to investigate cases when the Repov\\v{s}-Semenov splitting problem for selections has an affirmative solution for continuous set-valued mappings. We consider the situation in infinite-dimensional uniformly convex Banach spaces. We use the notion of Polyak of uniform convexity and modulus of uniform convexity for arbitrary convex sets (not necessary balls). We study general geometric properties of uniformly convex sets. We also obtain an affirmative solution of the splitting problem for selections of certain set-valued mappings with uniformly convex images.
Intermediate gradient methods ^for smooth convex problems with inexact oracle
Glineur, François
2013/17 Intermediate gradient methods ^for smooth convex problems with inexact oracle Olivier DISCUSSION PAPER 2013/17 Intermediate gradient methods for smooth convex problems with inexact oracle Olivier ., . denotes the dual pairing. 1.1 Exact and Inexact Oracle Consider F1,1 L (Q), the class of convex functions
Supporting Global Numerical Optimization of Rational Functions by Generic Symbolic Convexity Tests
NASA Astrophysics Data System (ADS)
Neun, Winfried; Sturm, Thomas; Vigerske, Stefan
Convexity is an important property in nonlinear optimization since it allows to apply efficient local methods for finding global solutions. We propose to apply symbolic methods to prove or disprove convexity of rational functions over a polyhedral domain. Our algorithms reduce convexity questions to real quantifier elimination problems. Our methods are implemented and publicly available in the open source computer algebra system Reduce. Our long term goal is to integrate Reduce as a "workhorse" for symbolic computations into a numerical solver.
Optimal transportation in for a distance cost with a convex constraint
NASA Astrophysics Data System (ADS)
Chen, Ping; Jiang, Feida; Yang, Xiao-Ping
2015-06-01
We prove existence of an optimal transportation map for the Monge-Kantorovich's problem associated with a cost function c( x, y) with a convex constraint in . The cost function coincides with the Euclidean distance | x - y| if the displacement y - x belongs to a given closed convex set C with at most countable flat parts and it is infinite otherwise.
SEGMENTATION OF IMAGES WITH SEPARATING LAYERS BY FUZZY C-MEANS AND CONVEX OPTIMIZATION
Steidl, Gabriele
SEGMENTATION OF IMAGES WITH SEPARATING LAYERS BY FUZZY C-MEANS AND CONVEX OPTIMIZATION B. SHAFEI-dimensional images containing separated layers. We tackle this problem by combining the fuzzy c-means algorithm of the convex model. We compute the segment prototypes by the fuzzy c-means algorithm (FCM). Then we use
Skogestad, Sigurd
and y (ny ), the optimal solution is uk = -K^xk, where ^xk is a state estimate from a Kalman filter [3 can be found by solving an iterative Riccati equation. For the case with white noise assumption on x0], which in effect gives a dynamic compensator Klqg (from y to u) of same order nx as the plant
sensitivity analysis in convex quadratic optimization: invariant ...
Aug 20, 2004 ... Keywords: Parametric optimization; Sensitivity analysis; Quadratic opti- ... when the problem has multiple optimal (and thus degenerate) solutions, ...... present, and future, Computers and Chemical Engineering, 23, 667–. 682.
Feltenmark, S.; Lindberg, P.O.
1994-12-31
We consider a problem from power production planning; the Spinning Reserve Constrained Economic Dispatch Problem (EDC). It arises as a subproblem in the more general Unit Commitment problem where it typically has to be solved hundreds of times. The EDC-problem is usually modelled as a convex continuous knapsack problem with one extra constraint that ensures sufficient marginal to the upper capacity limit of the system. We present efficient algorithms based on solving ordinary continuous knapsack problems, e.g. by the algorithm of Bitran & Hax. We also extend the Bitran & Hax algorithm to work with both constraints simultaneously, enabling fast reoptimization. Computational results are given.
Ilan Adler; Ron Shamir
1993-01-01
We extend Clarkson's randomized algorithm for linear programming to a general scheme for solving convex optimization problems. The scheme can be used to speed up existing algorithms on problems which have many more constraints than variables. In particular, we give a randomized algorithm for solving convex quadratic and linear programs, which uses that scheme together with a variant of Karmarkar's
Kernel regression for travel time estimation via convex optimization
Kernel regression for travel time estimation via convex optimization Sébastien Blandin , Laurent El Ghaoui and Alexandre Bayen Abstract--We develop an algorithm aimed at estimating travel time on segments of a road network using a convex optimiza- tion framework. Sampled travel time from probe vehicles
accuracy certificates for computational problems with convex structure
2008-11-26
of convex-concave functions and solving convex Nash equilibrium problems. .... Other black-box oriented intelligent algorithms, like the El- ..... solid X of the Euclidean diameter D be bounded, so that ?(x) 2 ? L < ? for all x ? int X. Then for ...
Convex Configurations In Free Boundary Problems
2002-10-30
temperature of the flame and ? is a normalization factor. We have ... In what follows, we will refer to the system (1)–(3) ..... A. Acker, Heat flow inequalities with applications to heat flow optimization problems, SIAM ...... is a C1,1(QT?h) supersolution of P?. Using the comparison ..... Then we can control the growth of |
Perturbation theory for abstract optimization problems
B. Gollan
1981-01-01
A general perturbation theory is given for optimization problems in locally convex, linear spaces. Neither differentiability of the constraints nor regularity of the solutions of the unperturbed problem are assumed. Without reference to a particular multiplier rule, multipliers of the unperturbed problem are defined and used for characterizing solutions of a perturbed problem. In case of differentiable constraints or finite-dimensional
Modeling flow statistics using convex optimization
Hoepffner, Jérôme
= ExxH M = EwwH At steady state, Lyapunov equation: AP + PAH + M = 0 A : Dynamic operator P : State covariance of disturbances #12;The Lyapunov cone P and M are covariance matrices P 0, M 0, AP + PAH 0 The operator A generates a convex cone. Lyapunov theorem: M 0, !P 0/AP + PAH + M = 0 but P 0/AP + PAH
A convex optimization approach to ARMA Tryphon T. Georgiou and Anders Lindquist
Georgiou, Tryphon T.
1 A convex optimization approach to ARMA modeling Tryphon T. Georgiou and Anders Lindquist Abstract systems. Yet many problems concerning mod- eling of linear systems remain open. A case in point is ARMA (autoregressive moving average) modeling of time-series. In ARMA modeling, least-squares tech- niques often lead
Regularization Constants in LS-SVMs: a Fast Estimate via Convex Optimization
Regularization Constants in LS-SVMs: a Fast Estimate via Convex Optimization Kristiaan Pelckmans Support Vector Machines (LS-SVMs) for regression and classification is considered. The formulation of the LS-SVM training and regularization constant tuning problem (w.r.t. the validation performance
Convex Relaxation for Multilabel Problems with Product Label Spaces
Kim, Tae-Kyun
to apply it to large-scale problems like optic flow, stereo with occlusion detection, and segmentation by a regularization term J(g) R. The regularizer J represents our knowledge about which label con- figurationsConvex Relaxation for Multilabel Problems with Product Label Spaces Bastian Goldluecke and Daniel
Convex Relaxation for Multilabel Problems with Product Label Spaces
Cremers, Daniel
, which enables us to apply it to large-scale problems like optic flow, stereo with occlusion detection by a regularization term J(g) R. The regularizer J represents our knowledge about which label con- figurationsConvex Relaxation for Multilabel Problems with Product Label Spaces Bastian Goldluecke and Daniel
Global convergence of the Heavy-ball method for convex optimization
2014-12-20
Department of Automatic Control, School of Electrical Engineering and ACCESS Linnaeus Center, Royal. Institute of ... convex optimization methods are still open [6]. The basic ...... convex optimization,” Technical Report, 2014. [Online].
Mixed H2\\/H? control for discrete-time systems via convex optimization
Isaac Kaminer; Pramod P. Khargonekar; Mario A. Rotea
1992-01-01
A mixed H2\\/H? control problem for discrete-time systems is considered for both state-feedback and output-feedback cases. It is shown that these problems can be effectively solved by reducing them to convex programming problems. In the state-feedback case, nearly optimal controllers can be chosen to be static gains, while in the output-feedback case the controller dimension does not exceed the plant
Optimal convex error estimators for classification
Chao Sima; Edward R. Dougherty
A cross-validation error estimator is obtained by repeatedly leaving out some data points, deriving classifiers on the remaining points, computing errors for these classifiers on the left-out points, and then averaging these errors. The 0.632 bootstrap estimator is obtained by averaging the errors of classifiers designed from points drawn with replacement and then taking a convex combination of this \\
Optimization over the Pareto Outcome set associated with a Convex ...
2014-02-01
Keywords Optimization over the Pareto image set · Multi-objective Stochastic ... which is generally not explicitly given and not convex (even in the linear case). ... Else, a new efficient point is generated and one triangle is reduced by two new ...... approximation algorithm for generating all efficient extreme points in the out-.
Active Learning as Non-Convex Optimization Andrew Guillory
Noble, William Stafford
@ee.washington.edu Abstract We propose a new view of active learning algo- rithms as optimization. We show that many on- line active learning algo- rithm and non-convex losses. Finally, we discuss and show empirically how viewing- tain active learning algorithms achieve better generalization error than passive learning algo- rithms
GLOBAL OPTIMIZATION IN COMPUTER VISION: CONVEXITY, CUTS AND
Lunds Universitet
GLOBAL OPTIMIZATION IN COMPUTER VISION: CONVEXITY, CUTS AND APPROXIMATION ALGORITHMS CARL OLSSON in computer vision. Numerous prob- lems in this field as well as in image analysis and other branches. International Conference on Computer Vision (ICCV), Rio de Janeiro, Brazil, 2007. · C. Olsson, F. Kahl, R
Adaptive Algorithms for Planar Convex Hull Problems
Hee-Kap Ahn; Yoshio Okamoto
2010-01-01
We study problems in computational geometry from the viewpoint of adaptive algorithms. Adaptive algorithms have been extensively studied for the sorting problem, and in this paper we gener- alize the framework to geometric problems. To this end, we think of geometric problems as permutation (or rearranging) problems of arrays, and dene the \\\\presortedness\\
Penalty/Barrier Multiplier Methods for Convex Programming Problems
Zibulevsky, Michael
for Absorption in Science, Ministry of Immigrant Absorp tion, State of Israel #12; 1 Introduction Methods which are asymptotically primal feasible. Full convergence analysis of the PBM method is con tainedPenalty/Barrier Multiplier Methods for Convex Programming Problems Aharon BenTal 1 and Michael
A convex programming framework for optimal and bounded suboptimal well field management
NASA Astrophysics Data System (ADS)
Dorini, G. F.; Thordarson, F. Ã.-.; Bauer-Gottwein, P.; Madsen, H.; Rosbjerg, D.; Madsen, H.
2012-06-01
This paper presents a groundwater management model, considering the interaction between a confined aquifer and an unlooped Water Distribution Network (WDN), conveying the groundwater into the Water Works distribution mains. The pumps are controlled by regulating the characteristic curves. The objective of the management is to minimize the total cost of pump operations over a multistep time horizon, while fulfilling a set of time-varying management constraints. Optimization in groundwater management and pressurized WDNs have been widely investigated in the literature. Problem formulations are often convex, hence global optimality can be attained by a wealth of algorithms. Among these, the Interior Point methods are extensively employed for practical applications, as they are capable of efficiently solving large-scale problems. Despite this, management models explicitly embedding both systems without simplifications are rare, and they usually involve heuristic techniques. The main limitation with heuristics is that neither optimality nor suboptimality bounds can be guarantee. This paper extends the proof of convexity to mixed management models, enabling the use of Interior Point techniques to compute globally optimal management solutions. If convexity is not achieved, it is shown how suboptimal solutions can be computed, and how to bind their deviation from the optimality. Experimental results obtained by testing the methodology in a well field located nearby Copenhagen (DK), show that management solutions can consistently perform within the 99.9% of the true optimum. Furthermore it is shown how not considering the Water Distribution Network in optimization is likely to result in unfeasible management solutions.
A cutting surface algorithm for semi-infinite convex programming ...
2013-06-16
Jun 16, 2013 ... convex optimization problems, and use it to develop an algorithm for ...... is an (N + 1)-dimensional convex set contained in the convex hull of the points ..... built, which requires considerably more planar cuts han surface cuts.
A partially inexact bundle method for convex semi-infinite minmax problems
NASA Astrophysics Data System (ADS)
Fuduli, Antonio; Gaudioso, Manlio; Giallombardo, Giovanni; Miglionico, Giovanna
2015-04-01
We present a bundle method for solving convex semi-infinite minmax problems which allows inexact solution of the inner maximization. The method is of the partially inexact oracle type, and it is aimed at reducing the occurrence of null steps and at improving bundle handling with respect to existing methods. Termination of the algorithm is proved at a point satisfying an approximate optimality criterion, and the results of some numerical experiments are also reported.
A Repository of Convex Quadratic Programming Problems
Istvan Maros; Csaba Meszaros
1997-01-01
The introduction of a standard set of linear programming problems, to be found in NETLIB\\/LP\\/DATA, had an important impact on measuring, comparing and re- porting the performance of LP solvers .Until recently the eciency of new algorith- mic developments has been measured using this important reference set .Presently, we are witnessing an ever growing interest in the area of quadratic
An improved cellular automata based algorithm for the 45-convex hull problem
Graham, Nick
. 1 #12;1 Introduction Given a set of planar points, the two-dimensional convex hull problemAn improved cellular automata based algorithm for the 45-convex hull problem Adam Clarridge and Kai,ksalomaa}@cs.queensu.ca July 2008 Abstract We give a cellular automaton algorithm for solving a version of the convex hull
An improved cellular automata based algorithm for the 45convex hull problem
Graham, Nick
. 1 #12; 1 Introduction Given a set of planar points, the twoÂdimensional convex hull problemAn improved cellular automata based algorithm for the 45Âconvex hull problem Adam Clarridge and Kai,ksalomaa}@cs.queensu.ca July 2008 Abstract We give a cellular automaton algorithm for solving a version of the convex hull
Solving Standard Quadratic Optimization Problems via Linear, Semidefinite and Copositive Programming
Immanuel M. Bomze; Etienne De Klerk
2002-01-01
The problem of minimizing a (non-convex) quadratic function over the simplex (the standard quadratic optimization problem) has an exact convex reformulation as a copositive programming problem. In this paper we show how to approximate the optimal solution by approximating the cone of copositive matrices via systems of linear inequalities, and, more refined, linear matrix inequalities (LMI's). In particular, we show
A convex analysis approach for convex multiplicative programming
Rúbia M. Oliveira; Paulo A. V. Ferreira
2008-01-01
Global optimization problems involving the minimization of a product of convex functions on a convex set are addressed in\\u000a this paper. Elements of convex analysis are used to obtain a suitable representation of the convex multiplicative problem\\u000a in the outcome space, where its global solution is reduced to the solution of a sequence of quasiconcave minimizations on\\u000a polytopes. Computational experiments
Time and VLSI-Optimal Convex Hull Computation on Meshes with Multiple Broadcasting
Venkatavasu Bokka; Himabindu Gurla; Stephan Olariu; James L. Schwing
1995-01-01
Computing the convex hull of a planar set of points is one of the most extensivelyinvestigated topics in computational geometry. Our main contribution is to present thefirst known general-case, time- and VLSI-optimal, algorithm for convex hull computationon meshes with multiple broadcasting. Specifically, we show that for every choiceof a positive integer constant c, the convex hull of a set of
Sparse representations and convex optimization as tools for LOFAR radio interferometric imaging
Girard, Julien N; Starck, Jean Luc; Corbel, Stéphane; Woiselle, Arnaud; Tasse, Cyril; McKean, John P; Bobin, Jérôme
2015-01-01
Compressed sensing theory is slowly making its way to solve more and more astronomical inverse problems. We address here the application of sparse representations, convex optimization and proximal theory to radio interferometric imaging. First, we expose the theory behind interferometric imaging, sparse representations and convex optimization, and second, we illustrate their application with numerical tests with SASIR, an implementation of the FISTA, a Forward-Backward splitting algorithm hosted in a LOFAR imager. Various tests have been conducted in Garsden et al., 2015. The main results are: i) an improved angular resolution (super resolution of a factor ~2) with point sources as compared to CLEAN on the same data, ii) correct photometry measurements on a field of point sources at high dynamic range and iii) the imaging of extended sources with improved fidelity. SASIR provides better reconstructions (five time less residuals) of the extended emissions as compared to CLEAN. With the advent of large radiotel...
Gálvez, Akemi; Iglesias, Andrés
2013-01-01
Fitting spline curves to data points is a very important issue in many applied fields. It is also challenging, because these curves typically depend on many continuous variables in a highly interrelated nonlinear way. In general, it is not possible to compute these parameters analytically, so the problem is formulated as a continuous nonlinear optimization problem, for which traditional optimization techniques usually fail. This paper presents a new bioinspired method to tackle this issue. In this method, optimization is performed through a combination of two techniques. Firstly, we apply the indirect approach to the knots, in which they are not initially the subject of optimization but precomputed with a coarse approximation scheme. Secondly, a powerful bioinspired metaheuristic technique, the firefly algorithm, is applied to optimization of data parameterization; then, the knot vector is refined by using De Boor's method, thus yielding a better approximation to the optimal knot vector. This scheme converts the original nonlinear continuous optimization problem into a convex optimization problem, solved by singular value decomposition. Our method is applied to some illustrative real-world examples from the CAD/CAM field. Our experimental results show that the proposed scheme can solve the original continuous nonlinear optimization problem very efficiently. PMID:24376380
A Double Smoothing Technique for Constrained Convex ...
2011-02-27
Key words. convex optimization, fast gradient methods, complexity theory, smoothing tech- .... method [19] for smooth and strongly convex functions and describe its rate of conver- ...... Boolean variables (this is a well-known NP-hard problem).
DEMOS for OPTIMIZATION Problems
NSDL National Science Digital Library
Roberts, Lila F.
2002-09-16
This demo provides a gallery of visual aids that illustrate fundamental concepts for understanding and developing equations that model optimization problems, commonly referred to as max-min problems. Animations, MATLAB routines and Java applets are included.
An Optimal Algorithm for Intersecting Three-Dimensional Convex Polyhedra
Bernard Chazelle
1992-01-01
This paper describes a linear-time algorithm for computing the intersection of two convex polyhedra in 3-space. Applications of this result to computing intersections, convex hulls, and Voronoi diagrams are also given.
The optimal path-matching problem
Cunningham, W.H.; Geelen, J.F. [Univ. of Waterloo, Ontario (Canada)
1996-12-31
We describe a common generalization of the weighted matching problem and the weighted matroid intersection problem. In this context we present results implying the polynomial-time solvability of the two problems. We also use our results to give the first strongly polynomial separation algorithm for the convex hull of matchable sets of a graph, and the first polynomial-time algorithm to compute the rank of a certain matrix of indeterminates. Our algorithmic results are based on polyhedral characterizations, and on the equivalence of separation and optimization.
BROADBAND SENSOR LOCATION SELECTION USING CONVEX OPTIMIZATION IN VERY LARGE SCALE ARRAYS
Balan, Radu V.
BROADBAND SENSOR LOCATION SELECTION USING CONVEX OPTIMIZATION IN VERY LARGE SCALE ARRAYS Yenming M pattern design, sensor location selection, very large scale arrays, convex op- timization, simulated annealing 1. INTRODUCTION Consider a large scale sensor array having N sensors that monitors a surveillance
A Perspective-Based Convex Relaxation for Switched-Affine Optimal Control
-integer convex program (MICP), based on perspective functions. Relaxing the integer constraints of this MICP-known MICP reduction (via conversion to a mixed logical dynamical system); our numerical study indicates-integer convex program (MICP), lower bounds on the optimal value can be obtained by relaxing the integer
Dynamic Planar Convex Hull with Optimal Query Time and O(log n log log n) Update Time
Riko Jacob
Dynamic Planar Convex Hull with Optimal Query Time and O(log n #1; log log n) Update Time Gerth St fgerth,rjacobg@brics.dk Abstract. The dynamic maintenance of the convex hull of a set of points(log n #1; log log n) time, and various queries about the convex hull in optimal O(log n) worst-case time
The unit distance problem for centrally symmetric convex Bernardo M. brego
Abrego, Bernardo
The unit distance problem for centrally symmetric convex polygons Bernardo M. Ãbrego Department) and H-(x, y) will denote the upper and lower half-planes determined by the oriented line -xy (we include bound. Let P denote a convex centrally symmetric polygon with n vertices, and let pq be a diameter of P
Optimization problems of gnostics
P. Kovanic
Data processing algorithms based on the gnostical theory of uncertain data possess high robustness with respect to both outlying data and changes of their statistical characteristics. However, application of this new powerful technique gives rise to interesting optimization problems resulting from the complicated nature of extremized functions. Effectiveness of the solution of this new problem is demonstrated by examples connected
Onn, Shmuel
CONVEX MATROID OPTIMIZATION SHMUEL ONN SIAM J. DISCRETE MATH. c 2003 Society for Industrial functionals over matroid bases. It is richly expressive and captures certain quadratic assignment, matroid, greedy algorithm, quadratic assignment, polytope, polynomial time, strongly polynomial time AMS
An optimal real-time algorithm for planar convex hulls
Franco P. Preparata
1979-01-01
An algorithm is described for the construction in real-time of the convex hull of a set of n points in the plane. Using an appropriate data structure, the algorithm constructs the convex hull by successive updates, each taking time O(log n), thereby achieving a total processing time O(n log n).
Dynamic Resource Allocation in Cognitive Radio Networks: A Convex Optimization Perspective
Zhang, Rui; Cui, Shuguang
2010-01-01
This article provides an overview of the state-of-art results on communication resource allocation over space, time, and frequency for emerging cognitive radio (CR) wireless networks. Focusing on the interference-power/interference-temperature (IT) constraint approach for CRs to protect primary radio transmissions, many new and challenging problems regarding the design of CR systems are formulated, and some of the corresponding solutions are shown to be obtainable by restructuring some classic results known for traditional (non-CR) wireless networks. It is demonstrated that convex optimization plays an essential role in solving these problems, in a both rigorous and efficient way. Promising research directions on interference management for CR and other related multiuser communication systems are discussed.
libCreme: An optimization library for evaluating convex-roof entanglement measures
Beat Röthlisberger; Jörg Lehmann; Daniel Loss
2011-07-22
We present the software library libCreme which we have previously used to successfully calculate convex-roof entanglement measures of mixed quantum states appearing in realistic physical systems. Evaluating the amount of entanglement in such states is in general a non-trivial task requiring to solve a highly non-linear complex optimization problem. The algorithms provided here are able to achieve to do this for a large and important class of entanglement measures. The library is mostly written in the Matlab programming language, but is fully compatible to the free and open-source Octave platform. Some inefficient subroutines are written in C/C++ for better performance. This manuscript discusses the most important theoretical concepts and workings of the algorithms, focussing on the actual implementation and usage within the library. Detailed examples in the end should make it easy for the user to apply libCreme to specific problems.
Equivalence of Convex Problem Geometry and Computational Complexity in the Separation Oracle Model
Vera Andreo, Jorge R.
Consider the supposedly simple problem of computing a point in a convex set that is conveyed by a separation oracle with no further information (e.g., no domain ball containing or intersecting the set, etc.). The authors' ...
Worst-Case Violation of Sampled Convex Programs for Optimization ...
2008-12-23
Uncertain programs have been developed to deal with optimization problems in- cluding inexact data, i.e., ..... Even in such a situation, we can derive a meaningful upper bound ..... The above inequality is proved by using the Binomial formula. See Theorem 3.1 ...... respectively. Here, K2 denotes a cone with a vertex at ¯u.
Non-convex optimization for the design of sparse FIR filters
Wei, Dennis
This paper presents a method for designing sparse FIR filters by means of a sequence of p-norm minimization problems with p gradually decreasing from 1 toward 0. The lack of convexity for p < 1 is partially overcome by ...
Non-euclidean restricted memory level method for large-scale convex optimization
Aharon Ben-tal; Arkadi Nemirovski
2005-01-01
. We propose a new subgradient-type method for minimizing extremely large-scale nonsmooth convex functions over simple domains. The characteristic features of the method are (a) the possibility to adjust the scheme to the geometry of the feasible set, thus allowing to get (nearly) dimension-independent (and nearly optimal in the large-scale case) rate-of-convergence results for minimization of a convex Lipschitz continuous function
Dan Goreac; Oana-Silvia Serea
2010-01-01
The aim of this paper is to study two classes of discontinuous control problems without any convexity assumption on the dynamics. In the first part we characterize the value function for the Mayer problem and the supremum cost problem using viscosity tools and the notion of ?-viability (near viability). These value functions are given with respect to discontinuous cost functionals.
Optimal structural design via optimality criteria as a nonsmooth mechanics problem
NASA Astrophysics Data System (ADS)
Tzaferopoulos, M. Ap.; Stravroulakis, G. E.
1995-06-01
In the theory of plastic structural design via optimality criteria (due to W. Prager), the optimal design problem is transformed to a nonlinear elastic structural analysis problem with appropriate stress-strain laws, which generally include complete vertical branches. In this context, the concept of structural universe (in the sense of G. Rozvany) permits the treatment of complicated optimal layout problems. Recent progress in the field of nonsmooth mechanics makes the solution of structural analysis problems with this kind of 'complete' law possible. Elements from the two fields are combined in this paper for the solution of optimal design and layout problems for structures. The optimal layout of plane trusses with various specific cost functions is studied here as a representative problem. The use of convex, continuous and piecewise linear specific cost functions for the structural members leads to problems of linear variational inequalities or equivalently piecewise linear, convex but nonsmooth optimization problems, which are solved by means of an iterative algorithm based on sequential linear programming techniques. Numerical examples illustrate the theory and its applicability to practical engineering structures. Following a parametric investigation of an optimal bridge design, certain aspects of the optimal truss layout problem are discussed, which can be extended to other types of structural systems as well.
FILTER-BANK OPTIMIZATION WITH CONVEX OBJECTIVES, AND THE OPTIMALITY OF PRINCIPAL COMPONENT FORMS1
Sony Akkarakaran; P. P. Vaidyanathan
This paper proposes a general framework for the optimization of orthonormal filter banks (FB's) for given input statistics. This includes as special cases, many recent results on filter bank optimization for compression. It also solves problems that have not been considered thus far. FB optimization for coding gain maximization (for compression applications) has been well studied before. The optimum FB
Filterbank optimization with convex objectives and the optimality of principal component forms
Sony Akkarakaran; P. P. Vaidyanathan
2001-01-01
This paper proposes a general framework for the optimization of orthonormal filterbanks (FBs) for given input statistics. This includes as special cases, many previous results on FB optimization for compression. It also solves problems that have not been considered thus far. FB optimization for coding gain maximization (for compression applications) has been well studied before. The optimum FB has been
A Study of Near-Field Direct Antenna Modulation Systems Using Convex Optimization
Hajimiri, Ali
de- sign for a class of communication systems known as near-field direct antenna modulation (NFDAMA Study of Near-Field Direct Antenna Modulation Systems Using Convex Optimization Javad Lavaei systems, referred to as near-field direct antenna modulation (NFDAM) systems. The objective is to propose a s
Non-Euclidean Restricted Memory Level Method for Large-Scale Convex Optimization
Nemirovski, Arkadi
Non-Euclidean Restricted Memory Level Method for Large-Scale Convex Optimization Aharon Ben Lipschitz continuous function over a Euclidean ball, a standard simplex, and a spectahedron (the set. In this paper we propose a new subgradient-type method Non-Euclidean restricted Memory Level (NERML
Minimum-Landing-Error Powered-Descent Guidance for Mars Landing Using Convex Optimization
Williams, Brian C.
Minimum-Landing-Error Powered-Descent Guidance for Mars Landing Using Convex Optimization Lars Rovers [2]. The 2009 Mars Science Laboratory mission aims to achieve a landing ellipse of around 10 km [3 to Mars and to enable sample return missions, the accuracy with which a lander can be delivered
Paris-Sud XI, Université de
A Convex Optimization Approach to Feedback Scheduling Mongi Ben Gaid, Daniel Simon and Olivier-mails: {Mohamed.Bengaid,Daniel.Simon}@inrialpes.fr). O. Sename is with the Control Systems Department, Gipsa. Simon are with the NeCS Project-Team, INRIA Rh^one-Alpes, Montbonnot Saint Martin, France (e
Single-Ballot Risk-Limiting Audits Using Convex Optimization Stephen Checkoway
Zhou, Yuanyuan
Single-Ballot Risk-Limiting Audits Using Convex Optimization Stephen Checkoway UC San Diego Anand. · First, audits must be risk-limiting [22]. If the audit certifies the outcome reported in the initial enough ev- idence that the reported outcome is incorrect when it actually is. An audit is risk
Class and Home Problems: Optimization Problems
ERIC Educational Resources Information Center
Anderson, Brian J.; Hissam, Robin S.; Shaeiwitz, Joseph A.; Turton, Richard
2011-01-01
Optimization problems suitable for all levels of chemical engineering students are available. These problems do not require advanced mathematical techniques, since they can be solved using typical software used by students and practitioners. The method used to solve these problems forces students to understand the trends for the different terms…
Wang, Li; Gao, Yaozong; Shi, Feng; Liao, Shu; Li, Gang [Department of Radiology and BRIC, University of North Carolina at Chapel Hill, North Carolina 27599 (United States)] [Department of Radiology and BRIC, University of North Carolina at Chapel Hill, North Carolina 27599 (United States); Chen, Ken Chung [Department of Oral and Maxillofacial Surgery, Houston Methodist Hospital Research Institute, Houston, Texas 77030 and Department of Stomatology, National Cheng Kung University Medical College and Hospital, Tainan, Taiwan 70403 (China)] [Department of Oral and Maxillofacial Surgery, Houston Methodist Hospital Research Institute, Houston, Texas 77030 and Department of Stomatology, National Cheng Kung University Medical College and Hospital, Tainan, Taiwan 70403 (China); Shen, Steve G. F.; Yan, Jin [Department of Oral and Craniomaxillofacial Surgery and Science, Shanghai Ninth People's Hospital, Shanghai Jiao Tong University College of Medicine, Shanghai, China 200011 (China)] [Department of Oral and Craniomaxillofacial Surgery and Science, Shanghai Ninth People's Hospital, Shanghai Jiao Tong University College of Medicine, Shanghai, China 200011 (China); Lee, Philip K. M.; Chow, Ben [Hong Kong Dental Implant and Maxillofacial Centre, Hong Kong, China 999077 (China)] [Hong Kong Dental Implant and Maxillofacial Centre, Hong Kong, China 999077 (China); Liu, Nancy X. [Department of Oral and Maxillofacial Surgery, Houston Methodist Hospital Research Institute, Houston, Texas 77030 and Department of Oral and Maxillofacial Surgery, Peking University School and Hospital of Stomatology, Beijing, China 100050 (China)] [Department of Oral and Maxillofacial Surgery, Houston Methodist Hospital Research Institute, Houston, Texas 77030 and Department of Oral and Maxillofacial Surgery, Peking University School and Hospital of Stomatology, Beijing, China 100050 (China); Xia, James J. [Department of Oral and Maxillofacial Surgery, Houston Methodist Hospital Research Institute, Houston, Texas 77030 (United States) [Department of Oral and Maxillofacial Surgery, Houston Methodist Hospital Research Institute, Houston, Texas 77030 (United States); Department of Surgery (Oral and Maxillofacial Surgery), Weill Medical College, Cornell University, New York, New York 10065 (United States); Department of Oral and Craniomaxillofacial Surgery and Science, Shanghai Ninth People's Hospital, Shanghai Jiao Tong University College of Medicine, Shanghai, China 200011 (China); Shen, Dinggang, E-mail: dgshen@med.unc.edu [Department of Radiology and BRIC, University of North Carolina at Chapel Hill, North Carolina 27599 and Department of Brain and Cognitive Engineering, Korea University, Seoul, 136701 (Korea, Republic of)] [Department of Radiology and BRIC, University of North Carolina at Chapel Hill, North Carolina 27599 and Department of Brain and Cognitive Engineering, Korea University, Seoul, 136701 (Korea, Republic of)
2014-04-15
Purpose: Cone-beam computed tomography (CBCT) is an increasingly utilized imaging modality for the diagnosis and treatment planning of the patients with craniomaxillofacial (CMF) deformities. Accurate segmentation of CBCT image is an essential step to generate three-dimensional (3D) models for the diagnosis and treatment planning of the patients with CMF deformities. However, due to the poor image quality, including very low signal-to-noise ratio and the widespread image artifacts such as noise, beam hardening, and inhomogeneity, it is challenging to segment the CBCT images. In this paper, the authors present a new automatic segmentation method to address these problems. Methods: To segment CBCT images, the authors propose a new method for fully automated CBCT segmentation by using patch-based sparse representation to (1) segment bony structures from the soft tissues and (2) further separate the mandible from the maxilla. Specifically, a region-specific registration strategy is first proposed to warp all the atlases to the current testing subject and then a sparse-based label propagation strategy is employed to estimate a patient-specific atlas from all aligned atlases. Finally, the patient-specific atlas is integrated into amaximum a posteriori probability-based convex segmentation framework for accurate segmentation. Results: The proposed method has been evaluated on a dataset with 15 CBCT images. The effectiveness of the proposed region-specific registration strategy and patient-specific atlas has been validated by comparing with the traditional registration strategy and population-based atlas. The experimental results show that the proposed method achieves the best segmentation accuracy by comparison with other state-of-the-art segmentation methods. Conclusions: The authors have proposed a new CBCT segmentation method by using patch-based sparse representation and convex optimization, which can achieve considerably accurate segmentation results in CBCT segmentation based on 15 patients.
EE 231 Convex Optimization in Engineering Applications (Winter 2014)
Mohsenian-Rad, Hamed
theory. Gradient, Steepest Descent, and Newton's Methods. Applications in engineering. Textbook: S. Boyd [Chapters 9011]: Gradient Descent Method Steepest Descent Method Newton's Method for Unconstrained Optimization Newton's Method for Equality Constrained Optimization Prerequisites: EE 230: Mathematical Methods
Convex optimization for control analysis application to the steam generator water level
Slim Hbaieb; Pascale Bendotti; Clement-Marc Falinower
2002-01-01
In this paper a convex synthesis methodology is applied to a benchmark problem. The objective is to control the water level in the steam generator of a Pressurized Water Reactor. Both robustness and performance constraints are specified for this benchmark. The proposed approach explicitly takes into account constraints in both time and frequency domains. In this method, specifications are expressed
Structural topology and shape optimization for a frequency response problem
NASA Astrophysics Data System (ADS)
Ma, Z.-D.; Kikuchi, N.; Hagiwara, I.
1993-12-01
A topology and shape optimization technique using the homogenization method was developed for stiffness of a linearly elastic structure by Bendsøe and Kikuchi (1988), Suzuki and Kikuchi (1990, 1991), and others. This method has also been extended to deal with an optimal reinforcement problem for a free vibration structure by Diaz and Kikuchi (1992). In this paper, we consider a frequency response optimization problem for both the optimal layout and the reinforcement of an elastic structure. First, the structural optimization problem is transformed to an Optimal Material Distribution problem (OMD) introducing microscale voids, and then the homogenization method is employed to determine and equivalent “averaged” structural analysis model. A new optimization algorithm, which is derived from a Sequential Approximate Optimization approach (SAO) with the dual method, is presented to solve the present optimization problem. This optimization algorithm is different from the CONLIN (Fleury 1986) and MMA (Svanderg 1987), and it is based on a simpler idea that employs a shifted Lagrangian function to make a convex approximation. The new algorithm is called “Modified Optimality Criteria method (MOC)” because it can be reduced to the traditional OC method by using a zero value for the shift parameter. Two sensitivity analysis methods, the Direct Frequency Response method (DFR) and the Modal Frequency Response method (MFR), are employed to calculate the sensitivities of the object functions. Finally, three examples are given to show the feasibility of the present approach.
Thibaut Labbe; Bruno Dehez
2010-01-01
In order to perform parameter or shape optimizations, an initial topology is required which affects the final solution. This constraint is released in topology optimization methods. They are based on a splitting of the design space into cells, in which they attempt to distribute optimally predefined materials. In topology optimization, a lack of convexity has already been observed by several
Chintala, Rohit
2012-10-19
Numerical methods of designing control systems are currently an active area of research. Convex optimization with linear matrix inequalities (LMIs) is one such method. Control objectives like minimizing the H_2, H_infinity norms, limiting...
Criteria for Unconstrained Global Optimization in Nonconvex Problems
NASA Astrophysics Data System (ADS)
Demidenko, Eugene
2007-09-01
We develop criteria for the existence and uniqueness of global minima of a continuous bounded function on a noncompact set. Special attention is given to the problem of parameter estimation via minimization of the sum of squares in nonlinear regression and maximum likelihood. Definitions of local convexity and unimodality are given using the level set. A fundamental theorem of nonconvex optimization is formulated: If a function approaches the minimal limiting value at the boundary of the optimization domain from below and its Hessian matrix is positive definite at the point where the gradient vanishes then the function has a unique minimum. It is shown that the local convexity level of the sum of squares is equal to the minimal squared radius of the regression curvature.
Christoph Scholl; Stefan Disch; Florian Pigorsch; Stefan Kupferschmid
2009-01-01
We present a method which computes optimized representations for non-convex polyhedra. Our method detects so-called redundant\\u000a linear constraints in these representations by using an incremental SMT (Satisfiability Modulo Theories) solver and then removes\\u000a the redundant constraints based on Craig interpolation. The approach is motivated by applications in the context of model\\u000a checking for Linear Hybrid Automata. Basically, it can be
A feasible active set method for strictly convex quadratic problems ...
2015-05-22
problem appears as a basic building block in many applications, for instance in the context of sequential ... In Section 6 we show the efficiency of the new ...... of the energy computed from the surface position and squared norm of its gradient.
Neurocomputing with time delay analysis for solving convex quadratic programming problems.
Chen, Y H; Fang, S C
2000-01-01
This paper presents a neural-network computational scheme with time-delay consideration for solving convex quadratic programming problems. Based on some known results, a delay margin is explicitly determined for the stability of the neural dynamics, under which the states of the neural network does not oscillate. The configuration of the proposed neural network is provided. Operational characteristics of the neural network are demonstrated via numerical examples. PMID:18249755
BILEVEL OPTIMIZATION PROBLEMS WITH VECTORVALUED ...
2012-05-21
determined for at least one value of the parameter x, problem (1.2) is in general not ... Bilevel programming; multiobjective optimization; linear optimiza- ... over a Pareto set using sequentially improved relaxations of the efficient set is pro-.
Convex optimization methods for graphs and statistical modeling
Chandrasekaran, Venkat
2011-01-01
An outstanding challenge in many problems throughout science and engineering is to succinctly characterize the relationships among a large number of interacting entities. Models based on graphs form one major thrust in ...
Optimization over the Efficient Set of a Bicriteria Convex ...
2011-11-03
Nov 3, 2011 ... a multiple objective programming problem arises in a variety of ap- plications. ... A point x? is said to be an efficient solution for Problem (V P) if there exists no ... case when X is a polyhedron and f1,f2 are linear function on Rn for each i = 1,2. .... A 2-simplex S is said to be a simplex generated by two points.
Newton-Raphson consensus for distributed convex optimization
Schenato, Luca
of Padova April 28th, 2011 schenato@dei.unipd.it (DEI - UniPD) Distrib. Newton-Raphson optimization April 28 where neighbors cooperate to find the optimum f1 f2 f3 f4 f5 f6 f7 schenato@dei.unipd.it (DEI - Uni) 0.2 0.4 0.6 0.8 2 4 6 8 -3-2-1 0 1 2 3 0 1 2 3 4 schenato@dei.unipd.it (DEI - UniPD) Distrib. Newton
The Power of Convex Relaxation: Near-Optimal Matrix Completion
Candes, Emmanuel J.
problem, and comes up in a great number of applications, including the famous Netflix Prize and other [7], and comes up in a great number of applications, including the famous Netflix Prize and other information from many users. Netflix is a commercial company implementing collaborative filtering, and seeks
Accelerated Microstructure Imaging via Convex Optimization (AMICO) from diffusion MRI data.
Daducci, Alessandro; Canales-Rodríguez, Erick J; Zhang, Hui; Dyrby, Tim B; Alexander, Daniel C; Thiran, Jean-Philippe
2015-01-15
Microstructure imaging from diffusion magnetic resonance (MR) data represents an invaluable tool to study non-invasively the morphology of tissues and to provide a biological insight into their microstructural organization. In recent years, a variety of biophysical models have been proposed to associate particular patterns observed in the measured signal with specific microstructural properties of the neuronal tissue, such as axon diameter and fiber density. Despite very appealing results showing that the estimated microstructure indices agree very well with histological examinations, existing techniques require computationally very expensive non-linear procedures to fit the models to the data which, in practice, demand the use of powerful computer clusters for large-scale applications. In this work, we present a general framework for Accelerated Microstructure Imaging via Convex Optimization (AMICO) and show how to re-formulate this class of techniques as convenient linear systems which, then, can be efficiently solved using very fast algorithms. We demonstrate this linearization of the fitting problem for two specific models, i.e. ActiveAx and NODDI, providing a very attractive alternative for parameter estimation in those techniques; however, the AMICO framework is general and flexible enough to work also for the wider space of microstructure imaging methods. Results demonstrate that AMICO represents an effective means to accelerate the fit of existing techniques drastically (up to four orders of magnitude faster) while preserving accuracy and precision in the estimated model parameters (correlation above 0.9). We believe that the availability of such ultrafast algorithms will help to accelerate the spread of microstructure imaging to larger cohorts of patients and to study a wider spectrum of neurological disorders. PMID:25462697
A Weiszfeld-like algorithm for a Weber location problem constrained to a closed and convex set
Torres, Germán A
2012-01-01
The Weber problem consists of finding a point in $\\mathbbm{R}^n$ that minimizes the weighted sum of distances from $m$ points in $\\mathbbm{R}^n$ that are not collinear. An application that motivated this problem is the optimal location of facilities in the 2-dimensional case. A classical method to solve the Weber problem, proposed by Weiszfeld in 1937, is based on a fixed point iteration. In this work a Weber problem constrained to a closed and convex set is considered. A Weiszfeld-like algorithm, well defined even when an iterate is a vertex, is presented. The iteration function $Q$ that defines the proposed algorithm, is based mainly on an orthogonal projection over the feasible set, combined with the iteration function of the modified Weiszfeld algorithm presented by Vardi and Zhang in 2001. It can be proved that $x^*$ is a fixed point of the iteration function $Q$ if and only if $x^*$ is the solution of the constrained Weber problem. Besides that, under certain hypotheses, $x^*$ satisfies the KKT optimali...
Thibaut Labbe; Bruno Dehez
2010-01-01
When applied to the topology optimization of electromagnetic devices, gradient-based algorithms suffer from a lack of convexity. They usually converge to local minimizers and the obtained designs depend on the initial material distributions. This paper focuses on avoiding these local minimizers for the optimization of ferromagnetic moving parts in electromagnetic actuators. The proposed method intends to maximize the average reluctant
Unified Particle Swarm Optimization for Solving Constrained Engineering Optimization Problems
Parsopoulos, Konstantinos
Unified Particle Swarm Optimization for Solving Constrained Engineering Optimization Problems K investigate the performance of the recently proposed Uni- fied Particle Swarm Optimization method and global variant of Particle Swarm Optimization are re- ported and discussed. 1 Introduction Many
Dynamic Planar Convex Hull Operations in Near-Logarithmic Amortized Time
Chan, Timothy M.
Dynamic Planar Convex Hull Operations in Near-Logarithmic Amortized Time #3; Timothy M. Chan y May, the basic problem of optimally maintaining the planar convex hull under insertions and deletions of points point set P and supports basic queries on the convex hull of P , such as membership and tangent- #12
Dynamic Planar Convex Hull with Optimal Query Time and O(log n · log log n ) Update Time
Gerth Stølting Brodal; Riko Jacob
The dynamic maintenance of the convex hull of a set of points in the plane is one of the most important problems in computational\\u000a geometry. We present a data structure supporting point insertions in amortized O(log n · log log log n) time, point deletions in amortized O(log n · log log n) time, and various queries about the convex
Wagner, Marcus
-dimensional spaces) 1. Algebraic properties; the convex hull 2. Special case of convex cones 3. Topological. Polytopes and combinatorial problems of convex analysis 1. Graphs and polytopes 2. Planar graphs, 3 for Optimization Lecture "Convex Analysis" (summer term 2004) Lecture "Convex Analysis" (summer term 2004
Bahlali, Seid
2008-01-01
We consider a stochastic control problem, where the control domain is convex and the system is governed by a nonlinear backward stochastic differential equation. With a L1 terminal data, we derive necessary optimality conditions in the form of stochastic maximum principle.
Online Optimization with Switching Cost Minghong Lin Adam Wierman
Andrew, Lachlan
- timization (SOCO)" problems. SOCO is a variant of the class of "online convex optimization (OCO)" problems optimization that we term Smoothed Online Convex Opti- mization (SOCO). The only change in a smoothed online costs to online convex optimization, SOCO captures a wide variety of important applications. In fact
Approximating Convex Functions Via Non-Convex Oracles Under ...
2014-06-12
Jun 12, 2014 ... when given a black box access to an L-approximation oracle ˜? of ? (the oracle value is always within ..... Now, if zt+1 and gt are convex functions, under some technical conditions ... provide concluding remarks and state open problems in Section 4. ...... Technical report 3918, www.optimization-.
Linear-Convex Control and Duality R.T. Rockafellar
Goebel, Rafal
. For simplicity of presentation, but also with control engineering applications in mind, we specialize the keyLinear-Convex Control and Duality R.T. Rockafellar and Rafal Goebel April 2, 2007 Abstract An optimal control problem with linear dynamics and convex but not necessarily quadratic and possibly
Bibliography Analysis of the Optimal Control Problem
Grigorieva, Ellina V.
Bibliography Analysis of the Optimal Control Problem in the model of HIV treatment Grigorieva E. V. Analytical Methods in Optimal Control of HIV Treatment #12;Bibliography Analysis of control for problem (2 of HIV Treatment #12;Bibliography HIV is a Global Problem HIV is a global problem, however, an eective
NASA Astrophysics Data System (ADS)
Chang, J.; Nakshatrala, K.
2014-12-01
It is well know that the standard finite element methods, in general, do not satisfy element-wise mass/species balance properties. It is, however, desirable to have element-wide mass balance property in subsurface modeling. Several studies over the years have aimed to overcome this drawback of finite element formulations. Currently, a post-processing optimization-based methodology is commonly employed to recover the local mass balance for porous media models. However, such a post-processing technique does not respect the underlying variational structure that the finite element formulation may enjoy. Motivated by this, a consistent methodology to satisfy element-wise local mass balance for porous media models is constructed using convex optimization techniques. The assembled system of global equations is reconstructed into a quadratic programming problem subjected to bounded equality constraints that ensure conservation at the element level. The proposed methodology can be applied to any computational mesh and to any non-locally conservative nodal-based finite element method. Herein, we integrate our proposed methodology into the framework of the classical mixed Galerkin formulation using Taylor-Hood elements and the least-squares finite element formulation. Our numerical studies will include computational cost, numerical convergence, and comparision with popular methods. In particular, it will be shown that the accuracy of the solutions is comparable with that of several popular locally conservative finite element formulations like the lowest order Raviart-Thomas formulation. We believe the proposed optimization-based approach is a viable approach to preserve local mass balance on general computational grids and is amenable for large-scale parallel implementation.
Particle Swarms for Dynamic Optimization Problems
Li, Xiaodong
Particle Swarms for Dynamic Optimization Problems Tim Blackwell1 , J¨urgen Branke2 , and Xiaodong. An optimization algorithm, therefore, has to both find and subsequently track the changing optimum. Examples of particle swarm optimization. Particle swarm optimization (PSO) is a versatile population-based opti
Vickers, Douglas; Lee, Michael D; Dry, Matthew; Hughes, Peter
2003-10-01
The planar Euclidean version of the traveling salesperson problem requires finding the shortest tour through a two-dimensional array of points. MacGregor and Ormerod (1996) have suggested that people solve such problems by using a global-to-local perceptual organizing process based on the convex hull of the array. We review evidence for and against this idea, before considering an alternative, local-to-global perceptual process, based on the rapid automatic identification of nearest neighbors. We compare these approaches in an experiment in which the effects of number of convex hull points and number of potential intersections on solution performance are measured. Performance worsened with more points on the convex hull and with fewer potential intersections. A measure of response uncertainty was unaffected by the number of convex hull points but increased with fewer potential intersections. We discuss a possible interpretation of these results in terms of a hierarchical solution process based on linking nearest neighbor clusters. PMID:14704024
Optimal impulse control problems and linear programming
Dario Bauso
2009-01-01
Optimal impulse control problems are, in general, difficult to solve. A current research goal is to isolate those problems that lead to tractable solutions. In this paper, we identify a special class of optimal impulse control problems which are easy to solve. Easy to solve means that solution algorithms are polynomial in time and therefore suitable to the on-line implementation
Global optimization in inverse problem of scatterometry
Paris-Sud XI, Université de
of a surrogate model. Keywords Inverse problem in scatterometry, Kriging, Global Optimization 1 IntroductionGlobal optimization in inverse problem of scatterometry Lekbir Afraites1,2 Jerome Hazard3 Patrick ellipsometric signature. The reformulation of the given nonlinear identification problem was considered
Automatic Segmentation of Neonatal Images Using Convex Optimization and Coupled Level Sets
Wang, Li; Shi, Feng; Lin, Weili; Gilmore, John H.; Shen, Dinggang
2011-01-01
Accurate segmentation of neonatal brain MR images remains challenging mainly due to their poor spatial resolution, inverted contrast between white matter and gray matter, and high intensity inhomogeneity. Most existing methods for neonatal brain segmentation are atlas-based and voxel-wise. Although active contour/surface models with geometric information constraint have been successfully applied to adult brain segmentation, they are not fully explored in the neonatal image segmentation. In this paper, we propose a novel neonatal image segmentation method by combining local intensity information, atlas spatial prior, and cortical thickness constraint in a single level-set framework. Besides, we also provide a robust and reliable tissue surface initialization for the proposed method by using a convex optimization technique. Thus, tissue segmentation, as well as inner and outer cortical surface reconstruction, can be obtained simultaneously. The proposed method has been tested on a large neonatal dataset, and the validation on 10 neonatal brain images (with manual segmentations) shows very promising results. PMID:21763443
Social Emotional Optimization Algorithm for Nonlinear Constrained Optimization Problems
NASA Astrophysics Data System (ADS)
Xu, Yuechun; Cui, Zhihua; Zeng, Jianchao
Nonlinear programming problem is one important branch in operational research, and has been successfully applied to various real-life problems. In this paper, a new approach called Social emotional optimization algorithm (SEOA) is used to solve this problem which is a new swarm intelligent technique by simulating the human behavior guided by emotion. Simulation results show that the social emotional optimization algorithm proposed in this paper is effective and efficiency for the nonlinear constrained programming problems.
Convex Drawings of Graphs Non-convex Boundary Constraints
Hong,Seokhee
Convex Drawings of Graphs with Non-convex Boundary Constraints Seok-Hee Hong School of Information@amp.i.kyoto-u.ac.jp Abstract: In this paper, we study a new problem of convex drawing of planar graphs with non-convex boundary-shaped polygon admits a drawing in which every inner facial cycle is drawn as a convex polygon. We also prove
NP-hardness of deciding convexity of quartic polynomials and related problems
Ahmadi, Amir Ali
We show that unless P = NP, there exists no polynomial time (or even pseudo-polynomial time) algorithm that can decide whether a multivariate polynomial of degree four (or higher even degree) is globally convex. This solves ...
Solving constrained optimization problems with hybrid particle swarm optimization
Erwie Zahara; Chia-Hsin Hu
2008-01-01
Constrained optimization problems (COPs) are very important in that they frequently appear in the real world. A COP, in which both the function and constraints may be nonlinear, consists of the optimization of a function subject to constraints. Constraint handling is one of the major concerns when solving COPs with particle swarm optimization (PSO) combined with the Nelder-Mead simplex search
Constrained Graph Optimization: Interdiction and Preservation Problems
Schild, Aaron V [Los Alamos National Laboratory
2012-07-30
The maximum flow, shortest path, and maximum matching problems are a set of basic graph problems that are critical in theoretical computer science and applications. Constrained graph optimization, a variation of these basic graph problems involving modification of the underlying graph, is equally important but sometimes significantly harder. In particular, one can explore these optimization problems with additional cost constraints. In the preservation case, the optimizer has a budget to preserve vertices or edges of a graph, preventing them from being deleted. The optimizer wants to find the best set of preserved edges/vertices in which the cost constraints are satisfied and the basic graph problems are optimized. For example, in shortest path preservation, the optimizer wants to find a set of edges/vertices within which the shortest path between two predetermined points is smallest. In interdiction problems, one deletes vertices or edges from the graph with a particular cost in order to impede the basic graph problems as much as possible (for example, delete edges/vertices to maximize the shortest path between two predetermined vertices). Applications of preservation problems include optimal road maintenance, power grid maintenance, and job scheduling, while interdiction problems are related to drug trafficking prevention, network stability assessment, and counterterrorism. Computational hardness results are presented, along with heuristic methods for approximating solutions to the matching interdiction problem. Also, efficient algorithms are presented for special cases of graphs, including on planar graphs. The graphs in many of the listed applications are planar, so these algorithms have important practical implications.
A Mathematical Optimization Problem in Bioinformatics
ERIC Educational Resources Information Center
Heyer, Laurie J.
2008-01-01
This article describes the sequence alignment problem in bioinformatics. Through examples, we formulate sequence alignment as an optimization problem and show how to compute the optimal alignment with dynamic programming. The examples and sample exercises have been used by the author in a specialized course in bioinformatics, but could be adapted…
About solving hybrid optimal control problems
P. Riedinger; J. Daafouz; C. Iung
The main objective of this paper is to discuss nu- merical difculties in solving hybrid optimal control problems and to propose a multiple phase-multiple shooting formula- tion for hybrid optimal control design. Such a formulation allows to solve directly the problem using nonlinear program- ming techniques. In the case of switched systems, it is shown that the switching rule can
Convex Nondifferentiable Optimization: a Survey Focussed on the Analytic Center Cutting Plane Method
J.-L. Goffin; JEAN-PHILIPPE VIAL
1999-01-01
We present a survey of nondifferentiable optimization problems and methods with special focus on the analytic center cutting plane method. We propose a self-contained convergence analysis, that uses the formalism of the theory of self-concordant fucntions, but for the main results, we give direct proofs based on the properties of the logarithmic function. We also provide an in depth analysis
Path following algorithm for the graph matching problem
Mikhail Zaslavskiy; Francis Bach; Jean-Philippe Vert
2008-01-01
Abstract We propose a convex-concave programming,approach for the labeled weighted graph matching problem. The convex-concave programming,formulation is obtained by rewriting the weighted graph matching problem as a least-square problem on the set of permutation matrices and relaxing it to two different optimization problems: a quadratic convex and a quadratic concave optimization problem on the set of doubly stochastic matrices. The
A Path Following Algorithm for the Graph Matching Problem
Mikhail Zaslavskiy; Francis R. Bach; Jean-philippe Vert
2009-01-01
We propose a convex-concave programming approach for the labeled weighted graph matching problem. The convex-concave programming formulation is obtained by rewriting the weighted graph matching problem as a least-square problem on the set of permutation matrices and relaxing it to two different optimization problems: a quadratic convex and a quadratic concave optimization problem on the set of doubly stochastic matrices.
Leizarowitz, Arie [Department of Mathematics, Technion, Haifa 32000 (Israel)], E-mail: la@techunix.technion.ac.il; Rubinstein, Jacob [Mathematics Department, Indiana University, Bloomington, IN 47405 (United States)], E-mail: jrubinst@indiana.edu
2003-12-15
Pattern formation in associative neural networks is related to a quadratic optimization problem. Biological considerations imply that the functional is constrained in the L{sub {infinity}} norm and in the L{sub 1} norm. We consider such optimization problems. We derive the Euler-Lagrange equations, and construct basic properties of the maximizers. We study in some detail the case where the kernel of the quadratic functional is finite-dimensional. In this case the optimization problem can be fully characterized by the geometry of a certain convex and compact finite-dimensional set.
Large Scale Computational Problems in Numerical Optimization
coleman, thomas f. [cornell university] [cornell university
2000-07-01
Our work under this support broadly falls into five categories: automatic differentiation, sparsity, constraints, parallel computation, and applications. Automatic Differentiation (AD): We developed strong practical methods for computing sparse Jacobian and Hessian matrices which arise frequently in large scale optimization problems [10,35]. In addition, we developed a novel view of "structure" in applied problems along with AD techniques that allowed for the efficient application of sparse AD techniques to dense, but structured, problems. Our AD work included development of freely available MATLAB AD software. Sparsity: We developed new effective and practical techniques for exploiting sparsity when solving a variety of optimization problems. These problems include: bound constrained problems, robust regression problems, the null space problem, and sparse orthogonal factorization. Our sparsity work included development of freely available and published software [38,39]. Constraints: Effectively handling constraints in large scale optimization remains a challenge. We developed a number of new approaches to constrained problems with emphasis on trust region methodologies. Parallel Computation: Our work included the development of specifically parallel techniques for the linear algebra tasks underpinning optimization algorithms. Our work contributed to the nonlinear least-squares problem, nonlinear equations, triangular systems, orthogonalization, and linear programming. Applications: Our optimization work is broadly applicable across numerous application domains. Nevertheless we have specifically worked in several application areas including molecular conformation, molecular energy minimization, computational finance, and bone remodeling.
Optimization problems in network connectivity
Panigrahi, Debmalya
2012-01-01
Besides being one of the principal driving forces behind research in algorithmic theory for more than five decades, network optimization has assumed increased significance in recent times with the advent and widespread use ...
NASA Astrophysics Data System (ADS)
Liolios, K.; Georgiev, I.; Liolios, A.
2012-10-01
A numerical approach for a problem arising in Civil and Environmental Engineering is presented. This problem concerns the dynamic soil-pipeline interaction, when unilateral contact conditions due to tensionless and elastoplastic softening/fracturing behaviour of the soil as well as due to gapping caused by earthquake excitations are taken into account. Moreover, soil-capacity degradation due to environmental effects are taken into account. The mathematical formulation of this dynamic elastoplasticity problem leads to a system of partial differential equations with equality domain and inequality boundary conditions. The proposed numerical approach is based on a double discretization, in space and time, and on mathematical programming methods. First, in space the finite element method (FEM) is used for the simulation of the pipeline and the unilateral contact interface, in combination with the boundary element method (BEM) for the soil simulation. Concepts of the non-convex analysis are used. Next, with the aid of Laplace transform, the equality problem conditions are transformed to convolutional ones involving as unknowns the unilateral quantities only. So the number of unknowns is significantly reduced. Then a marching-time approach is applied and a non-convex linear complementarity problem is solved in each time-step.
A Generic Bee Colony Optimization Framework for Combinatorial Optimization Problems
Li-Pei Wong; Malcolm Yoke Hean Low; Chin Soon Chong
2010-01-01
Combinatorial Optimization Problems (COPs) appear in various types of industrial applications. Finding an optimum solution for COPs with large scale of data, constraints and variables is NP-hard. This paper proposed a generic Bee Colony Optimization (BCO) framework for COPs that mimics the foraging process and waggle dance performed by bees. The framework is designed and organized such that it is
Improved Approximation Bound for Quadratic Optimization Problems ...
2007-11-21
Nov 21, 2007 ... In Proceedings of the IEEE International Conference on Acoustics ... Assignment Problems and the Location of Economic. Activities. ... SIAM Journal on Optimization,. 18(1):1–28, 2007. ... American Mathematical Society, 1994.
Analog Processor To Solve Optimization Problems
NASA Technical Reports Server (NTRS)
Duong, Tuan A.; Eberhardt, Silvio P.; Thakoor, Anil P.
1993-01-01
Proposed analog processor solves "traveling-salesman" problem, considered paradigm of global-optimization problems involving routing or allocation of resources. Includes electronic neural network and auxiliary circuitry based partly on concepts described in "Neural-Network Processor Would Allocate Resources" (NPO-17781) and "Neural Network Solves 'Traveling-Salesman' Problem" (NPO-17807). Processor based on highly parallel computing solves problem in significantly less time.
An FPTAS for Minimizing a Class of Low-Rank Quasi-Concave Functions over a Convex Set
Vineet Goyal; R. Ravi
We consider minimizing a class of low rank quasi-concave functions over a convex set and give a fully polynomial time approximation scheme (FPTAS) for the problem. The algorithm is based on a binary search for the optimal objective value which is guided by solving a polynomial number of linear minimization problems over the convex set with appropriate objective functions. Our
Kurien, Susan
Practical iterative image reconstruction in digital breast tomosynthesis by non-convex Tp the limitation that the complex 3D breast structure is projected into a plane. Lesions can be obscured National Laboratory, Los Alamos, NM cMassachusetts General Hospital, Boston, MA ABSTRACT Digital breast
Parameter Identification Problem Using Particle Swarm Optimization
An Liu; Erwie Zahara
2009-01-01
Ordinary differential equations have been a useful tool for describing the behavior of wide variety of dynamic physical systems. In this study, a method for solving parameter identification problem for ordinary second order differential equations using particle swarm optimization approach is presented.Experiments using two case problems are presented and compared with the best known solutions reported in the literature. The
Solving constrained optimization problems with hybrid particle swarm optimization
NASA Astrophysics Data System (ADS)
Zahara, Erwie; Hu, Chia-Hsin
2008-11-01
Constrained optimization problems (COPs) are very important in that they frequently appear in the real world. A COP, in which both the function and constraints may be nonlinear, consists of the optimization of a function subject to constraints. Constraint handling is one of the major concerns when solving COPs with particle swarm optimization (PSO) combined with the Nelder-Mead simplex search method (NM-PSO). This article proposes embedded constraint handling methods, which include the gradient repair method and constraint fitness priority-based ranking method, as a special operator in NM-PSO for dealing with constraints. Experiments using 13 benchmark problems are explained and the NM-PSO results are compared with the best known solutions reported in the literature. Comparison with three different meta-heuristics demonstrates that NM-PSO with the embedded constraint operator is extremely effective and efficient at locating optimal solutions.
Stochastic time-optimal control problems
NASA Technical Reports Server (NTRS)
Zhang, W.; Elliot, D.
1988-01-01
Two types of stochastic time-optimal controls in a one-dimensional setting are considered. Multidimensional problems, in the case of complete state information available and the system modeled by stochastic differential equations, are studied under the formulation of minimizing the expected transient-response time. The necessary condition of optimality is the satisfaction for the value function of a parabolic partial differential equation with boundary conditions. The sufficient condition of optimality is also provided, based on Dynkin's formula. Finally, three examples are given.
Linear stochastic optimal control and estimation problem
NASA Technical Reports Server (NTRS)
Geyser, L. C.; Lehtinen, F. K. B.
1980-01-01
Problem involves design of controls for linear time-invariant system disturbed by white noise. Solution is Kalman filter coupled through set of optimal regulator gains to produce desired control signal. Key to solution is solving matrix Riccati differential equation. LSOCE effectively solves problem for wide range of practical applications. Program is written in FORTRAN IV for batch execution and has been implemented on IBM 360.
Cheung, Ngaam J; Shen, Hong-Bin
2014-11-01
The stable conformation of a molecule is greatly important to uncover the secret of its properties and functions. Generally, the conformation of a molecule will be the most stable when it is of the minimum potential energy. Accordingly, the determination of the conformation can be solved in the optimization framework. It is, however, not an easy task to achieve the only conformation with the lowest energy among all the potential ones because of the high complexity of the energy landscape and the exponential computation increasing with molecular size. In this paper, we develop a hierarchical and heterogeneous particle swarm optimizer (HHPSO) to deal with the problem in the minimization of the potential energy. The proposed method is evaluated over a scalable simplified molecular potential energy function with up to 200 degrees of freedom and a realistic energy function of pseudo-ethane molecule. The experimental results are compared with other six PSO variants and four genetic algorithms. The results show HHPSO is significantly better than the compared PSOs with p-value less than 0.01277 over molecular potential energy function. PMID:25459763
Ant Algorithms Solve Difficult Optimization Problems
Libre de Bruxelles, Université
Ant Algorithms Solve Difficult Optimization Problems Marco Dorigo IRIDIA Universit´e Libre de Bruxelles 50 Avenue F. Roosevelt B-1050 Brussels, Belgium mdorigo@ulb.ac.be Abstract. The ant algorithms research field builds on the idea that the study of the behavior of ant colonies or other social insects
Optimization problems involving collections of dependent objects
David L. Roberts; Charles L. Isbell Jr; Michael L. Littman
2008-01-01
We describe a class of problems motivated by numerous real-world applications where there is a collection of objects that have both a cost and a value, but where some of those objects depend upon other objects to obtain their full value. Applications include nding an optimal order for transferring les under threat of system failure, ordering sequences of actions by
Mathematical Optimization for Engineering Design Problems
NASA Astrophysics Data System (ADS)
Dandurand, Brian C.
Applications in engineering design and the material sciences motivate the development of optimization theory in a manner that additionally draws from other branches of mathematics including the functional, complex, and numerical analyses. The first contribution, motivated by an automotive design application, extends multiobjective optimization theory under the assumption that the problem information is not available in its entirety to a single decision maker as traditionally assumed in the multiobjective optimization literature. Rather, the problem information and the design control are distributed among different decision makers. This requirement appears in the design of an automotive system whose subsystem components themselves correspond to highly involved design subproblems each of whose performance is measured by multiple criteria. This leads to a system/subsystem interaction requiring a coordination whose algorithmic foundation is developed and rigorously examined mathematically. The second contribution develops and analyzes a parameter estimation approach motivated from a time domain modeling problem in the material sciences. In addition to drawing from the theory of least-squares optimization and numerical analysis, the development of a mathematical foundation for comparing a baseline parameter estimation approach with an alternative parameter estimation approach relies on theory from both the functional and complex analyses. The application of the developed theory and algorithms associated with both contributions is also discussed.
NASA Astrophysics Data System (ADS)
Park, Y. C.; Chang, M. H.; Lee, T.-Y.
2007-06-01
A deterministic global optimization method that is applicable to general nonlinear programming problems composed of twice-differentiable objective and constraint functions is proposed. The method hybridizes the branch-and-bound algorithm and a convex cut function (CCF). For a given subregion, the difference of a convex underestimator that does not need an iterative local optimizer to determine the lower bound of the objective function is generated. If the obtained lower bound is located in an infeasible region, then the CCF is generated for constraints to cut this region. The cutting region generated by the CCF forms a hyperellipsoid and serves as the basis of a discarding rule for the selected subregion. However, the convergence rate decreases as the number of cutting regions increases. To accelerate the convergence rate, an inclusion relation between two hyperellipsoids should be applied in order to reduce the number of cutting regions. It is shown that the two-hyperellipsoid inclusion relation is determined by maximizing a quadratic function over a sphere, which is a special case of a trust region subproblem. The proposed method is applied to twelve nonlinear programming test problems and five engineering design problems. Numerical results show that the proposed method converges in a finite calculation time and produces accurate solutions.
Interaction prediction optimization in multidisciplinary design optimization problems.
Meng, Debiao; Zhang, Xiaoling; Huang, Hong-Zhong; Wang, Zhonglai; Xu, Huanwei
2014-01-01
The distributed strategy of Collaborative Optimization (CO) is suitable for large-scale engineering systems. However, it is hard for CO to converge when there is a high level coupled dimension. Furthermore, the discipline objectives cannot be considered in each discipline optimization problem. In this paper, one large-scale systems control strategy, the interaction prediction method (IPM), is introduced to enhance CO. IPM is utilized for controlling subsystems and coordinating the produce process in large-scale systems originally. We combine the strategy of IPM with CO and propose the Interaction Prediction Optimization (IPO) method to solve MDO problems. As a hierarchical strategy, there are a system level and a subsystem level in IPO. The interaction design variables (including shared design variables and linking design variables) are operated at the system level and assigned to the subsystem level as design parameters. Each discipline objective is considered and optimized at the subsystem level simultaneously. The values of design variables are transported between system level and subsystem level. The compatibility constraints are replaced with the enhanced compatibility constraints to reduce the dimension of design variables in compatibility constraints. Two examples are presented to show the potential application of IPO for MDO. PMID:24744685
Fast Multi-swarm Optimization for Dynamic Optimization Problems Department of Computer Science
Yang, Shengxiang
algorithm based on fast parti- cle swarm optimization for dynamic optimization problems. The algorithmFast Multi-swarm Optimization for Dynamic Optimization Problems Changhe Li Department of Computer that the optimization algorithms need to not only find the global optimal solution but also track the trajectory
Optimality results for dividend problems in insurance
Hansjörg Albrecher; Stefan Thonhauser
2009-01-01
This paper is a survey of some classical contributions and recent progress in identifying optimal dividend payment strategies\\u000a in the framework of collective risk theory. In particular, available mathematical tools are discussed and some challenges\\u000a are described that occur under various objective functions and model assumptions. Finally, some open research problems in\\u000a this field are stated.
NASA Astrophysics Data System (ADS)
Crasta, Graziano; Fragalà, Ilaria
2015-05-01
Given an open bounded subset ? of {{R}^n} , which is convex and satisfies an interior sphere condition, we consider the pde {-?_{infty} u = 1} in ?, subject to the homogeneous boundary condition u = 0 on ??. We prove that the unique solution to this Dirichlet problem is power-concave (precisely, 3/4 concave) and it is of class C 1(?). We then investigate the overdetermined Serrin-type problem, formerly considered in uc(Buttazzo) and uc(Kawohl) (Int Math Res Not, pp 237-247, 2011), obtained by adding the extra boundary condition {|nabla u| = a} on ??; by using a suitable P-function we prove that, if ? satisfies the same assumptions as above and in addition contains a ball which touches ?? at two diametral points, then the existence of a solution to this Serrin-type problem implies that necessarily the cut locus and the high ridge of ? coincide. In turn, in dimension n = 2, this entails that ? must be a stadium-like domain, and in particular it must be a ball in case its boundary is of class C 2.
LDRD Final Report: Global Optimization for Engineering Science Problems
HART,WILLIAM E.
1999-12-01
For a wide variety of scientific and engineering problems the desired solution corresponds to an optimal set of objective function parameters, where the objective function measures a solution's quality. The main goal of the LDRD ''Global Optimization for Engineering Science Problems'' was the development of new robust and efficient optimization algorithms that can be used to find globally optimal solutions to complex optimization problems. This SAND report summarizes the technical accomplishments of this LDRD, discusses lessons learned and describes open research issues.
Heterogeneous Sensor Networks with convex constraints
NASA Astrophysics Data System (ADS)
Rogers, U.; Chen, Hao
A wireless sensor network design is always subject to constraints. There are constraints on bandwidth, cost, detection robustness, and even false alarm rates to name but a few. This paper studies the design of Heterogeneous Sensor Networks (HSN) performing distributed binary hypothesis testing subject to convex constraints on the total number and types of sensors available. The relationship between real world engineering constraints and a resultant convex set or solution space will be highlighted. Under these convex sets, a theorem will be presented that defines when a homogenous sensor network will have better performance than a HSN. This theorem depends on stationary statistics, which is not the case for most problems of interest. These challenges are explored in detail for a parallel distributed HSN using the Kullback-Leibler (K-L) information number (K-L Divergence) in conjunction with the Chernoff-Stein Lemma. This method allows sensor counts to be optimized across a finite set of hypothesis or events, enabling a robust hypothesis testing solution similar to problems in traditional multiple hypothesis testing or classification problem. This paper also compares and contrast the detection performance of the standard parallel distributed HSN topology and a modified binary relay tree topology that is similar to clustering methods, where the final fusion is done using a logical OR rule. Finally, the asymptotic performance between these two topologies is studied, including the performance relative to optimal bounds. Ultimately providing a methodology to broadly analyze and optimize HSN design.
Dapeng Wang; Greg F. Naterer; G. Gary Wang
2008-01-01
One major challenge in multidisciplinary design optimization (MDO) is the presence of couplings among state parameters, which\\u000a demands an iterative and often expensive system analysis (SA) process for each function evaluation in optimization. This paper\\u000a offers a new perspective and proposes a corresponding method for solving MDO problems. The proposed method, named the boundary\\u000a search and simplex decomposition method (BSSDM),
Optimal control as a graphical model inference problem
Bert Kappen; Vicenc Gomez; Manfred Opper
2009-01-01
We reformulate a class of non-linear stochastic optimal control problems introduced by (1) as a KL minimization problem. As a result, the optimal control computation reduces to an inference computation and approximate inference methods can be applied to efficiently compute approximate optimal controls. We show that the path integral control problem introduced in (2) can be obtained as a special
SINGULAR PERTURBATION OF OPTIMAL CONTROL PROBLEMS ON MULTI-DOMAINS
Paris-Sud XI, Université de
SINGULAR PERTURBATION OF OPTIMAL CONTROL PROBLEMS ON MULTI-DOMAINS NICOLAS FORCADEL AND ZHIPING RAO Abstract. The goal of this paper is to study a singular perturbation problem in the framework of optimal of singular perturbation problems for Hamilton-Jacobi-Bellman equations motivated by optimal control systems
A global optimization approach for solving the maximum clique problem
P. M. Pardalos; A. T. Phillips
1990-01-01
The problem of finding a maximum clique of an undirected graph is formulated and solved as a linearly constrained indefinite quadratic global optimization problem. Theoretical upper and lower bounds on the size k of the maximum clique are derived from the global optimization formulation, and a relationship between the set of distinct global maxima of the optimization problem and the
A Binary Particle Swarm Optimization Algorithm for Lot Sizing Problem
M. Fatih; Yun-Chia Liang
This paper presents a binary particle swarm optimization algorithm for the lot sizing problem. The problem is to find order quantities which will minimize the total ordering and holding costs of ordering decisions. Test problems are constructed randomly, and solved optimally by Wagner and Whitin Algorithm. Then a binary particle swarm optimization algorithm and a traditional genetic algorithm are coded
An inexact proximal bundle method with applications to convex ...
2013-03-07
where Q is a self-adjoint positive semidefinite linear operator acting on E, and ˆs ? E. Its ... enables one to study major classes of optimization problems (e.g., the standard convex qua- ...... Motivated by this, we give our following choice for ?.
Exact Matrix Completion via Convex Optimization Emmanuel J. Cand`es
Xie, Yao
a sampling of its entries. · The Netflix problem. In the area of recommender systems, users submit ratings items. A special instance of this problem is the now famous Netflix problem [2]. Users (rows of the data would like to complete this matrix so that the vendor (here Netflix) might recommend titles that any
Optimal Planning and Problem-Solving
NASA Technical Reports Server (NTRS)
Clemet, Bradley; Schaffer, Steven; Rabideau, Gregg
2008-01-01
CTAEMS MDP Optimal Planner is a problem-solving software designed to command a single spacecraft/rover, or a team of spacecraft/rovers, to perform the best action possible at all times according to an abstract model of the spacecraft/rover and its environment. It also may be useful in solving logistical problems encountered in commercial applications such as shipping and manufacturing. The planner reasons around uncertainty according to specified probabilities of outcomes using a plan hierarchy to avoid exploring certain kinds of suboptimal actions. Also, planned actions are calculated as the state-action space is expanded, rather than afterward, to reduce by an order of magnitude the processing time and memory used. The software solves planning problems with actions that can execute concurrently, that have uncertain duration and quality, and that have functional dependencies on others that affect quality. These problems are modeled in a hierarchical planning language called C_TAEMS, a derivative of the TAEMS language for specifying domains for the DARPA Coordinators program. In realistic environments, actions often have uncertain outcomes and can have complex relationships with other tasks. The planner approaches problems by considering all possible actions that may be taken from any state reachable from a given, initial state, and from within the constraints of a given task hierarchy that specifies what tasks may be performed by which team member.
Neighboring optimization for constrained control problems in real time
Adam Korytowski; M. Szymkat; A. Turnau
2002-01-01
A neighboring trajectory closed-loop control is proposed for fixed-horizon constrained optimal control problems. The lower level of the algorithm adjusts the switching times based on the linearization of the optimal controller and performs reduced optimization with a change of control structure, whereas the upper level finds the optimal control and recalculates the linearization each time the deviation from the optimal
Bilevel problems over polyhedra with extreme point optimal solutions
Herminia I. Calvete; Carmen Galé; Stephan Dempe; Sebastian Lohse
2012-01-01
Bilevel programming involves two optimization problems where the constraint region of the upper level problem is implicitly\\u000a determined by another optimization problem. In this paper we focus on bilevel problems over polyhedra with upper level constraints\\u000a involving lower level variables. On the one hand, under the uniqueness of the optimal solution of the lower level problem,\\u000a we prove that the
A ``cellular neuronal'' approach to optimization problems
NASA Astrophysics Data System (ADS)
Duane, Gregory S.
2009-09-01
The Hopfield-Tank [J. J. Hopfield and D. W. Tank, Biol. Cybern. 52, 141 (1985)] recurrent neural network architecture for the traveling salesman problem is generalized to a fully interconnected "cellular" neural network of regular oscillators. Tours are defined by synchronization patterns, allowing the simultaneous representation of all cyclic permutations of a given tour. The network converges to local optima some of which correspond to shortest-distance tours, as can be shown analytically in a stationary phase approximation. Simulated annealing is required for global optimization, but the stochastic element might be replaced by chaotic intermittency in a further generalization of the architecture to a network of chaotic oscillators.
Optimization Online Digest -- July 2012
Interior point methods for sufficient LCP in a wide neighborhood of the central path with ... A variable smoothing algorithm for solving convex optimization problems ... Mixed Integer Linear Programming Formulation Techniques ... POST
Exact Matrix Completion via Convex Optimization Emmanuel J. Cand`es
Recht, Ben
would like to be able to recover a low-rank matrix from a sampling of its entries. · The Netflix problem is the now famous Netflix problem [2]. Users (rows of the data matrix) are given the opportunity to rate that the vendor (here Netflix) might recommend titles that any particular user is likely to be willing to order
P. L. Yu
1974-01-01
Although there is no universally accepted solution concept for decision problems with multiple noncommensurable objectives, one would agree that agood solution must not be dominated by the other feasible alternatives. Here, we propose a structure of domination over the objective space and explore the geometry of the set of all nondominated solutions. Two methods for locating the set of all
Optimal Auction Design for Agents with Hard Valuation Problems
Chen, Yiling
Optimal Auction Design for Agents with Hard Valuation Problems David C. Parkes ? Computer human expert. Although auction design cannot simplify the valuation problem itself, we show that good. Keywords: agent-mediated electronic commerce, valuation problem, metade- liberation, auction theory
Masao Fukushima
1992-01-01
Whether or not the general asymmetric variational inequality problem can be formulated as a differentiable optimization problem has been an open question. This paper gives an affirmative answer to this question. We provide a new optimization problem formulation of the variational inequality problem, and show that its objective function is continuously differentiable whenever the mapping involved in the latter problem
Group Search Optimizer for the Mobile Location Management Problem
Wang, Dan; Xiong, Congcong; Huang, Wei
2014-01-01
We propose a diversity-guided group search optimizer-based approach for solving the location management problem in mobile computing. The location management problem, which is to find the optimal network configurations of management under the mobile computing environment, is considered here as an optimization problem. The proposed diversity-guided group search optimizer algorithm is realized with the aid of diversity operator, which helps alleviate the premature convergence problem of group search optimizer algorithm, a successful optimization algorithm inspired by the animal behavior. To address the location management problem, diversity-guided group search optimizer algorithm is exploited to optimize network configurations of management by minimizing the sum of location update cost and location paging cost. Experimental results illustrate the effectiveness of the proposed approach. PMID:25180199
Nguyen V. Thoai
2000-01-01
One of the most important and interesting approaches in multiple criteria optimization is the problem of optimizing some function over the set of efficient solutions. This is a very difficult multiextremal global optimization problem, even for the case that the underlying multiple criteria program is linear and the function to be optimized over the efficient set is linear as well.
Optimal shape design as a material distribution problem
M. P. Bendsøe
1989-01-01
Shape optimization in a general setting requires the determination of the optimal spatial material distribution for given loads and boundary conditions. Every point in space is thus a material point or a void and the optimization problem is a discrete variable one. This paper describes various ways of removing this discrete nature of the problem by the introduction of a
Chaotic Particle Swarm Optimization Algorithm for Traveling Salesman Problem
Zhenglei Yuan; Liliang Yang; Yaohua Wu; Li Liao; Guoqiang Li
2007-01-01
In this paper, a novel algorithm based on particle optimization algorithm (PSO) and chaos optimization algorithm (COA) is presented to solve traveling salesman problem. Some new operators are proposed to overcome the difficulties of implementing PSO into solving the discreet problems. Meanwhile embedded with chaos optimization algorithm (COA) it can enhance particle's global searching ability so as not to converge
Le Thi Hoai An; Pham Dinh Tao; Nguyen Canh Nam; Le Dung Muu
2010-01-01
Both the efficient and weakly efficient sets of an affine fractional vector optimization problem, in general, are neither convex nor given explicitly. Optimization problems over one of these sets are thus nonconvex. We propose two methods for optimizing a real-valued function over the efficient and weakly efficient sets of an affine fractional vector optimization problem. The first method is a
Hedging Uncertainty: Approximation Algorithms for Stochastic Optimization Problems
R. Ravi; Amitabh Sinha
2004-01-01
We study the design of approximation algorithms for stoch- astic combinatorial optimization problems. We formulate the problems in the framework of two-stage stochastic optimization, and provide nearly tight approximations. Our problems range from the simple (shortest path, vertex cover, bin packing) to complex (facility location, set cover), and contain representatives with different approximation ratios. The approximation ratio of the stochastic
Bee Colony Optimization with local search for traveling salesman problem
Li-Pei Wong; M. Y. H. Low; Chin Soon Chong
2008-01-01
Many real world industrial applications involve finding a Hamiltonian path with minimum cost. Some instances that belong to this category are transportation routing problem, scan chain optimization and drilling problem in integrated circuit testing and production. This paper presents a bee colony optimization (BCO) algorithm for traveling salesman problem (TSP). The BCO model is constructed algorithmically based on the collective
Bee Colony Optimization with Local Search for Traveling Salesman Problem
Li-Pei Wong; Malcolm Yoke-Hean Low; Chin Soon Chong
2010-01-01
Abstract- Many real world industrial applications involve finding a Hamiltonian path with minimum cost. Some instances that belong to this category are transportation routing problem, scan chain optimization and drilling problem in integrated circuit testing and production. This paper presents a Bee Colony Optimization (BCO) algorithm for Traveling Salesman Problem (TSP). The BCO model is constructed algorithmically based on the
Spectral Finite-Element Methods for Parametric Constrained Optimization Problems
Mihai Anitescu
2009-01-01
We present a method to approximate the solution mapping of parametric constrained optimization problems. The approximation, which is of the spectral finite element type, is repre- sented as a linear combination of orthogonal polynomials. Its coefficients are determined by solving an appropriate finite-dimensional constrained optimization problem. We show that, under certain conditions, the latter problem is solvable because it is
Genetic Algorithms for Combinatorial Optimization: The Assembly Line Balancing Problem
Ferris, Michael C.
Genetic Algorithms for Combinatorial Optimization: The Assembly Line Balancing Problem Edward J optimization. We consider the application of the genetic algorithm to a particular problem, the Assembly Line Balancing Problem. A general description of genetic algorithms is given, and their specialized use on our
A fuzzy satisficing method for multiobjective linear optimal control problems
Masatoshi Sakawa; Masahiro Inuiguchi; Kosuke Kato; Tomohiro Ikeda
1996-01-01
In this paper, we propose a fuzzy satisficing method for the solution of multiobjective linear continuous optimal control problems. To solve these multiobjective linear continuous optimal control problems, we first discretize the time and replace the system of differential equations by difference equations. By introducing suitable auxiliary variables, approximate linear multiobjective programming problems are formulated. Then by considering the vague
On some multiobjective optimization problems arising in biology
Majid Soleimani-Damaneh
2011-01-01
In this paper, we discuss modelling and solving some multiobjective optimization problems arising in biology. A class of comparison problems for string selection in molecular biology and a relocation problem in conservation biology are modelled as multiobjective optimization programmes. Some discussions about applications, solvability and different variants of the obtained models are given, as well. A crucial part of the
The Convex Hull of Freeform Surfaces
Joon-kyung Seong; Gershon Elber; John K. Johnstone; Myung-soo Kim
2004-01-01
We present an algorithm for computing the convex hull of freeform rational surfaces. The convex hull problem is reformulated as one of finding the zero-sets of polynomial equations; using these zero-sets we characterize developable surface patches and planar patches that belong to the boundary of the convex hull.
Some optimization problems in power system reliability analysis
Jirutitijaroen, Panida
2009-05-15
This dissertation aims to address two optimization problems involving power system reliabilty analysis, namely multi-area power system adequacy planning and transformer maintenance optimization. A new simulation method for power system reliability...
PIBEA: Prospect Indicator Based Evolutionary Algorithm for Multiobjective Optimization Problems
Suzuki, Jun
PIBEA: Prospect Indicator Based Evolutionary Algorithm for Multiobjective Optimization Problems multiobjective optimization algorithm (EMOA) that uses a new quality indicator, called the prospect indicator, for parent selection and environmental selection operators. The prospect indicator measures the potential
Paris-Sud XI, Université de
consider a firm which produces and sells a good which can be stored. The firm acts in continuous time management problem is in the same vein as the one launched in 1958 by K. J. Harrow, S. Karlin and H. Scarf [1 to the selling of x units of goods, the cost of producing y units, and the cost of storing S units of the good
An outcome space approach for generalized convex multiplicative programs
Rúbia M. Oliveira; Paulo A. V. Ferreira
2010-01-01
This paper addresses the problem of minimizing an arbitrary finite sum of products of two convex functions over a convex set.\\u000a Nonconvex problems in this form constitute a class of generalized convex multiplicative problems. Convex analysis results\\u000a allow to reformulate the problem as an indefinite quadratic problem with infinitely many linear constraints. Special properties\\u000a of the quadratic problem combined with
A Simple But Effective Evolutionary Algorithm for Complicated Optimization Problems
Xu, Y.G.
A simple but effective evolutionary algorithm is proposed in this paper for solving complicated optimization problems. The new algorithm presents two hybridization operations incorporated with the conventional genetic ...
LP formulations for mixed-integer polynomial optimization problems ...
2015-03-20
of the constraints has bounded tree-width our construction yields a class of ...... [9] D. Bienstock, Progress on solving power flow problems, Optima, 93 (2013), pp. .... Application of Semidefinite Optimization Techniques to Problems in Electric.
The Optimal Single Copy Measurement for the Hidden Subgroup Problem
Dave Bacon; Thomas Decker
2008-01-22
The optimization of measurements for the state distinction problem has recently been applied to the theory of quantum algorithms with considerable successes, including efficient new quantum algorithms for the non-abelian hidden subgroup problem. Previous work has identified the optimal single copy measurement for the hidden subgroup problem over abelian groups as well as for the non-abelian problem in the setting where the subgroups are restricted to be all conjugate to each other. Here we describe the optimal single copy measurement for the hidden subgroup problem when all of the subgroups of the group are given with equal a priori probability. The optimal measurement is seen to be a hybrid of the two previously discovered single copy optimal measurements for the hidden subgroup problem.
Parametric Programming Applied to Reliability Optimization Problems
Maw-Sheng Chern; Rong-Hong Jan
1985-01-01
In practical reliability optimization models, finding an optimal solution to the model is not the only requirement. One may also be interested in solutions that are close to optimum, or one may want to know what happens if a change is made in the model. This paper presents new reliability optimization models which can be formulated as parametric nonlinear integer
Fast Approximate Convex Decomposition
Ghosh, Mukulika
2012-10-19
Approximate convex decomposition (ACD) is a technique that partitions an input object into "approximately convex" components. Decomposition into approximately convex pieces is both more efficient to compute than exact convex decomposition and can...
Average case analysis of dynamic geometric optimization
Eppstein, David
for constructing geometric structures such as convex hulls and ar- rangements. Such algorithms can also be used structures: convex hulls, arrangements, and the like. However problems of geometric optimization have been ne spanning tree of a planar point set, as points are inserted or deleted, in O(log3 n) expected time per
Optimization Online - Integer Programming Submissions - 2012
A conic representation of the convex hull of disjunctive sets and conic cuts for integer ... Two-stage Models and Algorithms for Optimizing Infrastructure Design and ... Solving mixed integer nonlinear programming problems for mine production ...
Problem Decomposition and MultiObjective Optimization Richard A. Watson
Coello, Carlos A. Coello
@cs.brandeis.edu 1 SubÂProblems and Objectives Divide and conquer techniques in problem solving are familiar and intuitive; first find the solution to subÂproblems and then reÂuse these to find solutions to the whole prob neatly into separable subÂproblems. For example, the optimal properties of a drive system have
Necessarily efficient solutions of multiobjective linear optimal control problems
Ida Masaaki
1997-01-01
We consider multiobjective linear programming problem with interval objective functions. One solution for this problem is called a necessarily efficient solution, that is efficient for every possible perturbation of coefficients within given intervals, which can be regarded as a kind of robust solution for optimal control problems. We improve the simplex based multiobjective problem solving method for generating a set
Approximation of a singularly perturbed elliptic problem of optimal control
Danilin, A R [Urals State Pedagogical University (Russian Federation)
2000-10-31
A problem of optimal control of solutions of an elliptic equation with a small parameter at higher derivatives is considered in a rectangle with two sides parallel to the characteristic of the limit equation. The limit problem is found and asymptotic estimates for solutions of a problem that approximates the original problem are obtained.
A moving horizon solution to the gas pipeline optimization problem
Grossmann, Ignacio E.
A moving horizon solution to the gas pipeline optimization problem EWO MEETING, Fall 2010 Ajit Gopalakrishnan Advisor: L. T. Biegler #12;Background: Gas pipeline optimization 2 Gas pipeline networks optimization Load forecast Weather, load history Controller #12;Pipeline modeling [Baumrucker & Biegler, 09
Two Dimensional Optimal Mechanism Design for a Sequencing Problem
Al Hanbali, Ahmad
an optimal mechanism, that is, a scheduling rule and incentive compatible payments that minimize the totalTwo Dimensional Optimal Mechanism Design for a Sequencing Problem Ruben Hoeksma and Marc Uetz.p.hoeksma, m.uetz}@utwente.nl Abstract. We consider optimal mechanism design for a sequencing prob- lem with n
On Identification of the Optimal Partition of Second Order Cone Optimization Problems
Snyder, Larry
. This paper discusses the identification of the optimal partition of second order cone optimization (SOCO). By giving definitions of two condition numbers which only dependent on the SOCO problem itself, we derive that the optimal partition B, N , R, and T for SOCO problems can be identified along the central path when
Artificial bee colony algorithm for constrained possibilistic portfolio optimization problem
NASA Astrophysics Data System (ADS)
Chen, Wei
2015-07-01
In this paper, we discuss the portfolio optimization problem with real-world constraints under the assumption that the returns of risky assets are fuzzy numbers. A new possibilistic mean-semiabsolute deviation model is proposed, in which transaction costs, cardinality and quantity constraints are considered. Due to such constraints the proposed model becomes a mixed integer nonlinear programming problem and traditional optimization methods fail to find the optimal solution efficiently. Thus, a modified artificial bee colony (MABC) algorithm is developed to solve the corresponding optimization problem. Finally, a numerical example is given to illustrate the effectiveness of the proposed model and the corresponding algorithm.
On Evolutionary Optimization of Large Problems Using Small Populations
Jin, Yaochu
Optimization of Large Problems Using Small Populations 1141 studies is that the population size shouldOn Evolutionary Optimization of Large Problems Using Small Populations Yaochu Jin, Markus Olhofer yaochu.jin@honda-ri.de Abstract. Small populations are very desirable for reducing the re- quired
A Genetic Algorithm for Minimax Optimization Problems Jeffrey W. Herrmann
Herrmann, Jeffrey W.
A Genetic Algorithm for Minimax Optimization Problems Jeffrey W. Herrmann Department of Mechanical-space genetic algorithm as a general technique to solve minimax optimization problems. This algorithm maintains of applications. To illustrate its potential, we use the two-space genetic algorithm to solve a parallel machine
Random Sampling and Greedy Sparsification for Matroid Optimization Problems.
Random Sampling and Greedy Sparsification for Matroid Optimization Problems. David R. Karger the effectiveness of these paradigms for two optimization problems on matroids: finding an optimum matroid basis and packing disjoint matroid bases. Applications of these ideas to the graphic matroid led to fast algorithms
The Role of Intuition in the Solving of Optimization Problems
ERIC Educational Resources Information Center
Malaspina, Uldarico; Font, Vicenc
2010-01-01
This article presents the partial results obtained in the first stage of the research, which sought to answer the following questions: (a) What is the role of intuition in university students' solutions to optimization problems? (b) What is the role of rigor in university students' solutions to optimization problems? (c) How is the combination of…
Sequential Multiresolution Trajectory Optimization Schemes for Problems with Moving Targets
Tsiotras, Panagiotis
. Introduction CONSIDER the problem of finding the optimal control that will steer a vehicle from point A to some, then there is no real advantage to finding the optimal trajectory online with high precision from the starting point control problem for various reference trajectories and storing these reference trajectories onboard
PARALLEL ALGORITHMS FOR A MULTI-LEVEL NETWORK OPTIMIZATION PROBLEM
Cruz, Frederico
-integer programming; G.2.2. [Discrete Mathematics]: Graph Theory-network problems; G.4.[Mathematics of ComputingPARALLEL ALGORITHMS FOR A MULTI-LEVEL NETWORK OPTIMIZATION PROBLEM F.R.B. CRUZa, * and G.R. MATEUSbÂMG, Brazil (Received 15 February 2000; In final form 12 March 2001) Multi-level network optimization (MLNO
Execution of Multidisciplinary Design Optimization Approaches on Common Test Problems
NASA Technical Reports Server (NTRS)
Balling, R. J.; Wilkinson, C. A.
1997-01-01
A class of synthetic problems for testing multidisciplinary design optimization (MDO) approaches is presented. These test problems are easy to reproduce because all functions are given as closed-form mathematical expressions. They are constructed in such a way that the optimal value of all variables and the objective is unity. The test problems involve three disciplines and allow the user to specify the number of design variables, state variables, coupling functions, design constraints, controlling design constraints, and the strength of coupling. Several MDO approaches were executed on two sample synthetic test problems. These approaches included single-level optimization approaches, collaborative optimization approaches, and concurrent subspace optimization approaches. Execution results are presented, and the robustness and efficiency of these approaches an evaluated for these sample problems.
Particle Swarm Optimization and Fitness Sharing to solve Multi-Objective Optimization Problems
Coello, Carlos A. Coello
.e.rowe@cs.bham.ac.uk Abstract- The particle swarm optimization algorithm has been shown to be a competitive heuristic to solve by that specific particle. Particle swarm optimization shares many similarities with genetic algorithms andParticle Swarm Optimization and Fitness Sharing to solve Multi-Objective Optimization Problems
Solving disjunctive optimization problems by generalized semi ...
2015-02-27
Feb 27, 2015 ... linear functions can be approximated by multiple linear underestimators and ...... disjunctive programming, Computers and Chemical Engineering, Vol. 24 ... ity constraints: Stationarity, optimality, and sensitivity, Mathematics.
Optimal solutions to multi-objective robust fault detection problems
Nike Liu; Kemin Zhou
2007-01-01
This paper will give complete, analytic, and optimal solutions to several robust fault detection problems that have been considered in the research community in the last twenty years. It is shown that several well-recognized robust fault detection problems, such as H-\\/Hinfin, H2\\/Hinfin, and Hinfin\\/Hinfin problems, have a very simple optimal solution in an observer form by solving a standard algebraic
Dual Methods for Nonconvex Spectrum Optimization of Multicarrier Systems
Wei Yu; Raymond Lui
2006-01-01
The design and optimization of multicarrier communications systems often involve a maximization of the total throughput subject to system resource constraints. The optimization problem is numerically difficult to solve when the problem does not have a convexity structure. This paper makes progress toward solving optimization problems of this type by showing that under a certain condition called the time-sharing condition,
Optimization Problems in Natural Gas Transportation Systems
Roger Z. Rios-Mercado
2015-03-02
Mar 2, 2015 ... The literature reveals three major groups of gas pipeline systems, ... (line-packing problems), gas quality satisfaction (pooling problems), and ... Category 1: Applications -- OR and Management Sciences (Transportation ).
A Hierarchical Particle Swarm Optimizer for Dynamic Optimization Problems
Stefan Janson; Martin Middendorf
2004-01-01
\\u000a Particle Swarm Optimization (PSO) methods for dynamic function optimization are studied in this paper. We compare dynamic\\u000a variants of standard PSO and Hierarchical PSO (H-PSO) on different dynamic benchmark functions. Moreover, a new type of hierarchical\\u000a PSO, called Partitioned H-PSO (PH-PSO), is proposed. In this algorithm the hierarchy is partitioned into several sub-swarms\\u000a for a limited number of generations after
A Planning Problem Combining Calculus of Variations and Optimal Transport
Carlier, G., E-mail: carlier@ceremade.dauphine.fr; Lachapelle, A., E-mail: lachapelle@ceremade.dauphine.f [Universite Paris IX Dauphine, CEREMADE, UMR CNRS 7534 (France)
2011-02-15
We consider some variants of the classical optimal transport where not only one optimizes over couplings between some variables x and y but also over some control variables governing the evolutions of these variables with time. Such a situation is motivated by an assignment problem of tasks with workers whose characteristics can evolve with time (and be controlled). We distinguish between the coupled and decoupled case. The coupled case is a standard optimal transport with the value of some optimal control problem as cost. The decoupled case is more involved since it is nonlinear in the transport plan.
Optimized Waveform Relaxation Solution of Electromagnetic and Circuit Problems
Gander, Martin J.
a method for the parallel solution of time domain combined ElectroMagetic (EM) and circuit problems. The EM1 Optimized Waveform Relaxation Solution of Electromagnetic and Circuit Problems Martin J. Gander-- New algorithms are needed to solve electromagnetic problems using today's widely available parallel
GLOBAL OPTIMIZATION FOR THE PHASE AND CHEMICAL EQUILIBRIUM PROBLEM
Neumaier, Arnold
GLOBAL OPTIMIZATION FOR THE PHASE AND CHEMICAL EQUILIBRIUM PROBLEM: APPLICATION TO THE NRTL of solutions to the phase and chemical equilibrium problem when the problem is posed as the minimization the equilibrium condition. For many chemical engineering applications this function will be the Gibbs free energy
Optimal solutions for a free boundary problem for crystal growth
Seidman, Thomas I.
Optimal solutions for a free boundary problem for crystal growth Pekka NeittaanmÂ¨ aki Thomas I. Seidman Abstract. We consider a free boundary problem modeling the growth/dissolution of a crystal boundary problem corresponding to a model of growth (dissolution) of a radially symmetric crystal grain
Optimal Auction Design for Agents with Hard Valuation Problems
Chen, Yiling
Optimal Auction Design for Agents with Hard Valuation Problems David C. Parkes ? Computer human expert. Although auction design cannot simplify the valuation problem itself, we show that good hold for the good. Keywords: agentÂmediated electronic commerce, valuation problem, metadeÂ liberation
On optimization techniques for solving nonlinear inverse problems
Eldad Haber; Uri M. Ascher; Doug Oldenburg
2000-01-01
This paper considers optimization techniques for the solution of nonlinear inverse problems where the forward problems, like those encountered in electromagnetics, are modelled by differential equations. Such problems are often solved by utilizing a Gauss-Newton method in which the forward model constraints are implicitly incorporated. Variants of Newton's method which use second-derivative information are rarely employed because their perceived disadvantage
Applications of parallel global optimization to mechanics problems
NASA Astrophysics Data System (ADS)
Schutte, Jaco Francois
Global optimization of complex engineering problems, with a high number of variables and local minima, requires sophisticated algorithms with global search capabilities and high computational efficiency. With the growing availability of parallel processing, it makes sense to address these requirements by increasing the parallelism in optimization strategies. This study proposes three methods of concurrent processing. The first method entails exploiting the structure of population-based global algorithms such as the stochastic Particle Swarm Optimization (PSO) algorithm and the Genetic Algorithm (GA). As a demonstration of how such an algorithm may be adapted for concurrent processing we modify and apply the PSO to several mechanical optimization problems on a parallel processing machine. Desirable PSO algorithm features such as insensitivity to design variable scaling and modest sensitivity to algorithm parameters are demonstrated. A second approach to parallelism and improving algorithm efficiency is by utilizing multiple optimizations. With this method a budget of fitness evaluations is distributed among several independent sub-optimizations in place of a single extended optimization. Under certain conditions this strategy obtains a higher combined probability of converging to the global optimum than a single optimization which utilizes the full budget of fitness evaluations. The third and final method of parallelism addressed in this study is the use of quasiseparable decomposition, which is applied to decompose loosely coupled problems. This yields several sub-problems of lesser dimensionality which may be concurrently optimized with reduced effort.
Afonso, Manya V; Bioucas-Dias, José M; Figueiredo, Mário A T
2011-03-01
We propose a new fast algorithm for solving one of the standard approaches to ill-posed linear inverse problems (IPLIP), where a (possibly nonsmooth) regularizer is minimized under the constraint that the solution explains the observations sufficiently well. Although the regularizer and constraint are usually convex, several particular features of these problems (huge dimensionality, nonsmoothness) preclude the use of off-the-shelf optimization tools and have stimulated a considerable amount of research. In this paper, we propose a new efficient algorithm to handle one class of constrained problems (often known as basis pursuit denoising) tailored to image recovery applications. The proposed algorithm, which belongs to the family of augmented Lagrangian methods, can be used to deal with a variety of imaging IPLIP, including deconvolution and reconstruction from compressive observations (such as MRI), using either total-variation or wavelet-based (or, more generally, frame-based) regularization. The proposed algorithm is an instance of the so-called alternating direction method of multipliers, for which convergence sufficient conditions are known; we show that these conditions are satisfied by the proposed algorithm. Experiments on a set of image restoration and reconstruction benchmark problems show that the proposed algorithm is a strong contender for the state-of-the-art. PMID:20840899
Optimal measurements for the dihedral hidden subgroup problem
Dave Bacon; Andrew M. Childs; Wim van Dam
2005-04-26
We consider the dihedral hidden subgroup problem as the problem of distinguishing hidden subgroup states. We show that the optimal measurement for solving this problem is the so-called pretty good measurement. We then prove that the success probability of this measurement exhibits a sharp threshold as a function of the density nu=k/log N, where k is the number of copies of the hidden subgroup state and 2N is the order of the dihedral group. In particular, for nu1 the optimal measurement identifies the hidden subgroup with a probability of order unity. Thus the dihedral group provides an example of a group G for which Omega(log|G|) hidden subgroup states are necessary to solve the hidden subgroup problem. We also consider the optimal measurement for determining a single bit of the answer, and show that it exhibits the same threshold. Finally, we consider implementing the optimal measurement by a quantum circuit, and thereby establish further connections between the dihedral hidden subgroup problem and average case subset sum problems. In particular, we show that an efficient quantum algorithm for a restricted version of the optimal measurement would imply an efficient quantum algorithm for the subset sum problem, and conversely, that the ability to quantum sample from subset sum solutions allows one to implement the optimal measurement.
Non-concave and behavioural optimal portfolio choice problems
Meireles Rodrigues, Andrea Sofia; Rodrigues, Andrea
2014-11-27
Our aim is to examine the problem of optimal asset allocation for investors exhibiting a behaviour in the face of uncertainty which is not consistent with the usual axioms of Expected Utility Theory. This thesis is divided ...
Direct Multiple Shooting Optimization with Variable Problem Parameters
NASA Technical Reports Server (NTRS)
Whitley, Ryan J.; Ocampo, Cesar A.
2009-01-01
Taking advantage of a novel approach to the design of the orbital transfer optimization problem and advanced non-linear programming algorithms, several optimal transfer trajectories are found for problems with and without known analytic solutions. This method treats the fixed known gravitational constants as optimization variables in order to reduce the need for an advanced initial guess. Complex periodic orbits are targeted with very simple guesses and the ability to find optimal transfers in spite of these bad guesses is successfully demonstrated. Impulsive transfers are considered for orbits in both the 2-body frame as well as the circular restricted three-body problem (CRTBP). The results with this new approach demonstrate the potential for increasing robustness for all types of orbit transfer problems.
Decomposition methods for large scale stochastic and robust optimization problems
Becker, Adrian Bernard Druke
2011-01-01
We propose new decomposition methods for use on broad families of stochastic and robust optimization problems in order to yield tractable approaches for large-scale real world application. We introduce a new type of a ...
Two improved harmony search algorithms for solving engineering optimization problems
NASA Astrophysics Data System (ADS)
Jaberipour, Majid; Khorram, Esmaile
2010-11-01
This paper describes two new harmony search (HS) meta-heuristic algorithms for engineering optimization problems with continuous design variables. The key difference between these algorithms and traditional (HS) method is in the way of adjusting bandwidth (bw). bw is very important factor for the high efficiency of the harmony search algorithms and can be potentially useful in adjusting convergence rate of algorithms to optimal solution. First algorithm, proposed harmony search (PHS), introduces a new definition of bandwidth (bw). Second algorithm, improving proposed harmony search (IPHS) employs to enhance accuracy and convergence rate of PHS algorithm. In IPHS, non-uniform mutation operation is introduced which is combination of Yang bandwidth and PHS bandwidth. Various engineering optimization problems, including mathematical function minimization problems and structural engineering optimization problems, are presented to demonstrate the effectiveness and robustness of these algorithms. In all cases, the solutions obtained using IPHS are in agreement or better than those obtained from other methods.
PLASMA Approximate Dynamic Programming finally cracks the locomotive optimization problem
Powell, Warren B.
PLASMA Approximate Dynamic Programming finally cracks the locomotive optimization problem schedules and new operating policies. PLASMA is currently running at Norfolk Southern for strategic of PLASMA: Each locomotive is modeled individually, making it possible to capture both horsepower
An algorithm for nonlinear optimization problems with binary variables
Walter Murray; Kien-Ming Ng
2010-01-01
One of the challenging optimization problems is determining the minimizer of a nonlinear programming problem that has binary\\u000a variables. A vexing difficulty is the rate the work to solve such problems increases as the number of discrete variables increases.\\u000a Any such problem with bounded discrete variables, especially binary variables, may be transformed to that of finding a global optimum of a
Schott, RenÃ© - Institut de MathÃ©matiques Ã?lie Cartan, UniversitÃ© Henri PoincarÃ©
When a local optimal solution is reached with classi- cal Particle Swarm Optimization (PSO), all premature convergence of PSO, we present in this paper a novel variant of PSO al- gorithm, called MPSOM (PSO) [19, 22, 1]. PSO is quite popular heuristics for solving complex optimization problems
Optimal control problems in public health
Feng Lin
2010-01-01
The health care delivery system in the United States is poorly planned to meet the growing needs of its population. This research establishes the foundations of developing decision-support tools in the emerging field of health care engineering, with special emphasis on public health. It demonstrates the potential of applying engineering methods, especially optimal control theory, to facilitate decision making in
ROBUSTNESS OPTIMIZATION FOR CONSTRAINED NONLINEAR PROGRAMMING PROBLEMS
INDRANEEL DAS
2000-01-01
In realistic situations engineering designs should take into consideration random aberrations from the stipulated design variables arising from manufacturing variability. Moreover, many environmental parameters are often stochastic in nature. Traditional nonlinear optimization attempts to find a deterministic optimum of a cost function and does not take into account the effect of these random variations on the objective. This paper attempts
A unified modeling and solution framework for combinatorial optimization problems
Gary A. Kochenberger; Fred Glover; Bahram Alidaee; Cesar Rego
2004-01-01
Combinatorial optimization problems are often too complex to be solved within reasonable time limits by exact methods, in spite of the theoretical guarantee that such methods will ultimately obtain an optimal solution. Instead, heuristic methods, which do not offer a convergence guarantee, but which have greater flexibility to take advantage of special properties of the search space, are commonly a
Some Finance Problems Solved with Nonsmooth Optimization Techniques
Vinter, Richard
Some Finance Problems Solved with Nonsmooth Optimization Techniques R. B. VINTER 1 AND H. ZHENG 2 analysis and mathematical finance communities to the scope for applications of nonsmooth optimization to finance, by studying in detail two illustrative examples. The first concerns the maximization of a ter
A Decision Support System for Solving Multiple Criteria Optimization Problems
ERIC Educational Resources Information Center
Filatovas, Ernestas; Kurasova, Olga
2011-01-01
In this paper, multiple criteria optimization has been investigated. A new decision support system (DSS) has been developed for interactive solving of multiple criteria optimization problems (MOPs). The weighted-sum (WS) approach is implemented to solve the MOPs. The MOPs are solved by selecting different weight coefficient values for the criteria…
A Distributed Optimization Approach to Constrained OSNR Problem
Pavel, Lacra
signal-to-noise ratio (OSNR) problem via a distributed optimization approach. In multi-channel optical the same optical fiber. Control of optical networks via an optimization-based approach arises systems, the signal over an optical link can be regarded as an interfering noise for others, which leads
Finding Optimal Gains In Linear-Quadratic Control Problems
NASA Technical Reports Server (NTRS)
Milman, Mark H.; Scheid, Robert E., Jr.
1990-01-01
Analytical method based on Volterra factorization leads to new approximations for optimal control gains in finite-time linear-quadratic control problem of system having infinite number of dimensions. Circumvents need to analyze and solve Riccati equations and provides more transparent connection between dynamics of system and optimal gain.
Strategies for Solving High-Fidelity Aerodynamic Shape Optimization Problems
Papalambros, Panos
Strategies for Solving High-Fidelity Aerodynamic Shape Optimization Problems Zhoujie Lyu Aerodynamic shape optimization based on high-fidelity models is a computational intensive endeavor. The techniques are tested using the Common Research Model wing benchmark defined by the Aerodynamic Design
GA-HARDNESS OF DENSE-GAS FLOW OPTIMIZATION PROBLEMS
P. Cinnella; P. m. Congedo
ABSTRACT Astudy about convergence of Genetic Algorithms (GAs) inshape,optimization problems for inviscid flows of real gases is presented. Specifically, working fluids of the Bethe—Zel’dovich—Thompson ,(BZT) type ,are considered, which exhibit non classical dynamic behaviors in the transonic\\/supersonic regime, such as the disintegration of compression shocks. A reference, single- objective optimization problem, namely, wave drag minimization for a non-lifting inviscid transonic
A hybrid immune PSO for constrained optimization problems
Aijia Ouyang
2010-01-01
Precise Algorithms combining evolutionary algorithms and constraint-handling techniques have shown to be effective to solve constrained optimization problems during the past decade. This paper presents a hybrid immune PSO (HIA-PSO) algorithm with a feasibility-based rule which is employed in this paper to handle constraints in solving global nonlinear constrained optimization problems, and Nelder-Mead simplex search method is used to improve
Optimal control problem for impulsive systems with integral boundary conditions
NASA Astrophysics Data System (ADS)
Ashyralyev, Allaberen; Sharifov, Y. A.
2012-08-01
In the present work the optimal control problem is considered, when the state of the system is described by the impulsive differential equations with integral boundary conditions. Applying the Banach contraction principle the existence and uniqueness of solution is proved for the corresponding boundary problem by the fixed admissible control. The first and second variation of the functional is calculated. Various necessary conditions of optimality of the first and second order are obtained by the help of the variation of the controls.
The Vector Model of Artificial Physics Optimization Algorithm for Global Optimization Problems
Liping Xie; Jianchao Zeng; Zhuihua Cui
2009-01-01
To solve complex global optimization problems, Artificial Physics Optimization (APO) algorithm is presented based on Physicomimetics framework, which is a population-based stochastic algorithm inspired by physical force. The solutions (particles) sampled from the feasible region of the problems are treated as physical individuals. Each individual has a mass, position and velocity. The mass of each individual corresponds to a user-defined
Gerth Stølting Brodal; Riko Jacob
2002-01-01
In this paper we determine the computational complex- ity of the dynamic convex hull problem in the planar case. We present a data structure that maintains a finite set ofn points in the plane under insertion and deletion of points in amortizedO(logn) time per operation. The space us- age of the data structure isO(n). The data structure sup- ports extreme
The optimal harvesting problem under risk aversion
2012-04-03
Apr 3, 2012 ... Abstract. We study the exploitation of a one species forest plantation when ... cost of thermal fuel and penalties coming from energy shortages Guigues ... consider the maximum expected sustainable yield problem in which.
Integer Optimization Models of AI Planning Problems
Kautz, Henry
quality solutions for a set of hard benchmark logistics planning problems than had been found by any with the work by Green (Green 1969) on planning as theoremproving in firstorder logic. The basic statement
Chapter 4: Unconstrained Optimization Unconstrained optimization problem minx F(x) or maxx F(x)
Wu, Xiaolin
Chapter 4: Unconstrained Optimization · Unconstrained optimization problem minx F(x) or maxx F(x) · Constrained optimization problem min x F(x) or max x F(x) subject to g(x) = 0 and/or h(x) x) > 0 Example: minimize the outer area of a cylinder subject to a fixed volume. Objective function F(x) = 2r2
Josi?ski, Henryk; Kostrzewa, Daniel; Michalczuk, Agnieszka; Swito?ski, Adam
2014-01-01
This paper introduces an expanded version of the Invasive Weed Optimization algorithm (exIWO) distinguished by the hybrid strategy of the search space exploration proposed by the authors. The algorithm is evaluated by solving three well-known optimization problems: minimization of numerical functions, feature selection, and the Mona Lisa TSP Challenge as one of the instances of the traveling salesman problem. The achieved results are compared with analogous outcomes produced by other optimization methods reported in the literature. PMID:24955420
Vision-based stereo ranging as an optimal control problem
NASA Technical Reports Server (NTRS)
Menon, P. K. A.; Sridhar, B.; Chatterji, G. B.
1992-01-01
The recent interest in the use of machine vision for flight vehicle guidance is motivated by the need to automate the nap-of-the-earth flight regime of helicopters. Vision-based stereo ranging problem is cast as an optimal control problem in this paper. A quadratic performance index consisting of the integral of the error between observed image irradiances and those predicted by a Pade approximation of the correspondence hypothesis is then used to define an optimization problem. The necessary conditions for optimality yield a set of linear two-point boundary-value problems. These two-point boundary-value problems are solved in feedback form using a version of the backward sweep method. Application of the ranging algorithm is illustrated using a laboratory image pair.
An object-oriented toolbox for studying optimization problems
NASA Astrophysics Data System (ADS)
Deng, H. Lydia; Gouveia, Wences; Scales, John
The CWP Object-Oriented Optimization Library (COOOL) is a collection of C++ classes for studying and solving optimization problems. It was developed using the freely available GNU compiler gcc. The library contains the basic building blocks for the efficient design of numerical linear algebra and optimization software; it also comes with a variety of unconstrained optimization algorithms and test objective functions drawn from our own research. The only requirement for using one of the optimization methods is that a simple model of communication be followed. This allows us to use exactly the same code to optimize functions tailored for a variety of hardware, no matter what programming language is used. Further, since we have provided class libraries containing building blocks for general purpose optimization and numerical linear algebra software, the development of new algorithms should be greatly aided. COOOL is now freely available via anonymous ftp at
ON A SMOOTH DUAL GAP FUNCTION FOR A CLASS OF PLAYER CONVEX
Kanzow, Christian
ON A SMOOTH DUAL GAP FUNCTION FOR A CLASS OF PLAYER CONVEX GENERALIZED NASH EQUILIBRIUM PROBLEMS1: Generalized Nash equilibrium, DC optimization, conjugate function, dual gap function, nonconvex duality to the year 2010. There also exist quite a few newer contributions to this area, but the following discussion
SMMH--A Parallel Heuristic for Combinatorial Optimization Problems
Domingues, Guilherme; Morie, Yoshiyuki [Institute of Systems and Information Technologies, Fukuoka (Japan); Research Institute for Information Technology, Kyushu University (Japan); Gu, Feng Long; Nanri, Takeshi [Research Institute for Information Technology, Kyushu University (Japan); Murakami, Kazuaki [Research Institute for Information Technology, Kyushu University (Japan); Department of Informatics, Kyushu University (Japan)
2007-12-26
The process of finding one or more optimal solutions for answering combinatorial optimization problems bases itself on the use of algorithms instances. Those instances usually have to explore a very large search spaces. Heuristics search focusing on the use of High-Order Hopfield neural networks is a largely deployed technique for very large search space. It can be established a very powerful analogy towards the dynamics evolution of a physics spin-glass system while minimizing its own energy and the energy function of the network. This paper presents a new approach for solving combinatorial optimization problems through parallel simulations, based on a High-Order Hopfield neural network using MPI specification.
SMMH - A Parallel Heuristic for Combinatorial Optimization Problems
Domingues, Guilherme; Morie, Yoshiyuki [Institute of Systems and Information Technologies, Fukuoka (Japan); Research Institute for Information Technology, Kyushu University (Japan); Gu, Feng Long; Nanri, Takeshi [Research Institute for Information Technology, Kyushu University (Japan); Murakami, Kazuaki [Research Institute for Information Technology, Kyushu University (Japan); Department of Informatics, Kyushu University (Japan)
2007-12-26
The process of finding one or more optimal solutions for answering combinatorial optimization problems bases itself on the use of algorithms instances. Those instances usually have to explore a very large search spaces. Heuristics search focusing on the use of High-Order Hopfield neural networks is a largely deployed technique for very large search space. It can be established a very powerful analogy towards the dynamics evolution of a physics spin-glass system while minimizing its own energy and the energy function of the network. This paper presents a new approach for solving combinatorial optimization problems through parallel simulations, based on a High-Order Hopfield neural network using MPI specification.
Convexity Rule for Shape Decomposition Based on Discrete Contour Evolution
Longin Jan Latecki; Rolf Lakämper
1999-01-01
We concentrate here on decomposition of 2D objects into mean- ingful parts of visual form ,o rvisual parts. It is a simple observation that convex parts of objects determine visual parts. However, the problem is that many significant visual parts are not convex, since a visual part may have concavities. We solve this problem by identify- ing convex parts at
A probabilistic numerical method for optimal multiple switching problem
for instance the recent massive power system blackouts in Brazil and Paraguay on November 10th and 11th, 2009 in the regressions, and of the truncating time horizon. To make the method viable for problems in high dimension of the optimal generation mix is illustrated on a realistic numerical problem in dimension eight, i.e. with two
A Bee Colony Optimization Algorithm for Traveling Salesman Problem
Li-pei Wong; Malcolm Yoke-hean Low; Chin Soon Chong
2008-01-01
A bee colony optimization (BCO) algorithm for traveling salesman problem (TSP) is presented in this paper. The BCO model is constructed algorithmically based on the collective intelligence shown in bee foraging behaviour. Experimental results comparing the proposed BCO model with some existing approaches on a set of benchmark problems are presented.
Constraint Optimal Selection Techniques (COSTs) for Nonnegative Linear Programming Problems
H. W. Corley; Jay M. Rosenberger; Tai-Kuan Sung
2006-01-01
We describe here two classes of Constraint Optimal Selection Techniques (COSTs) and develop an algorithm of each type for solving nonnegative linear programming problems. In addition, we give geometric interpretations of these new algorithms, provide computational results for some large-scale problems, and present topics for future research.
An Optimal Algo-Tech-Cuit for the Knapsack Problem
Rumen Andonov; Sanjay Rajopadhye
1994-01-01
: We present a formal derivation and proof of correctness of a systolic arrayfor the knapsack problem, a well known, NP-complete problem. The dependency graphof the algorithm is not completely known statically, so the derivation also serves as a casestudy for systolic synthesis for this class of programs. The array is itself important sinceit achieves optimal performance on a model
Approximation on the Web: A Compendium of NP Optimization Problems
Pierluigi Crescenzi; Viggo Kann
1997-01-01
A compendium of NP optimization problems, containing the best approximation results known for each problem, is now available on the web at http:\\/\\/www.nada.kth.se\\/viggo\\/problemlist\\/. In this paper we describe such a compendium, and specify how the compendium is consultable (and modifiable) on the world wide web.
Optimization of the multiple retailer supply chain management problem
Caio Soares; Gerry V. Dozier; Emmett Lodree; Jared Phillips; Katie Nobles; Yong Won Park
2008-01-01
With stock surpluses and shortages representing one of the greatest elements of risk to wholesalers, a solution to the multi- retailer supply chain management problem would result in tremendous economic benefits. In this problem, a single wholesaler with multiple retailer customers must find an optimal balance of quantities ordered from suppliers and acceptable lead time costs, while taking into account
An improved particle swarm optimization algorithm for flowshop scheduling problem
Changsheng Zhang; Jigui Sun; Xingjun Zhu; Qingyun Yang
2008-01-01
The flowshop scheduling problem has been widely studied and many techniques have been applied to it, but few algorithms based on particle swarm optimization (PSO) have been proposed to solve it. In this paper, an improved PSO algorithm (IPSO) based on the “alldifferent” constraint is proposed to solve the flow shop scheduling problem with the objective of minimizing makespan. It
TWO DECOMPOSITION ALGORITHMS FOR NONCONVEX OPTIMIZATION PROBLEMS
Stanford University
of philosophy Angel-Victor de Miguel June 2001 #12; c Copyright 2001 by Angel-Victor de Miguel All Rights into a set of smaller independent problems. One type of connectivity oc- curs when only a few interesting, friendly conversation. Later, at Stanford, Professor Murray became not only my advisor, but also
Decidable optimization problems for database logic programs
Stavros S. Cosmadakis; Haim Gaifman; Paris Kanellakis; Moshe Y. Vardio
1988-01-01
Datalog is the language of logic programs without function symbols. It is used as a database query language. If it is possible to eliminate recursion from a Datalog program &Pgr;, then &Pgr; is said to be bounded. It is known that the problem of deciding whether a given Datalog program is bounded is undecidable, even for binary programs. We show
Nonlinear singularly perturbed optimal control problems with singular arcs
NASA Technical Reports Server (NTRS)
Ardema, M. D.
1977-01-01
A third order, nonlinear, singularly perturbed optimal control problem is considered under assumptions which assure that the full problem is singular and the reduced problem is nonsingular. The separation between the singular arc of the full problem and the optimal control law of the reduced one, both of which are hypersurfaces in state space, is of the same order as the small parameter of the problem. Boundary layer solutions are constructed which are stable and reach the outer solution in a finite time. A uniformly valid composite solution is then formed from the reduced and boundary layer solutions. The value of the approximate solution is that it is relatively easy to obtain and does not involve singular arcs. To illustrate the utility of the results, the technique is used to obtain an approximate solution of a simplified version of the aircraft minimum time-to-climb problem. A numerical example is included.
TSP based Evolutionary optimization approach for the Vehicle Routing Problem
NASA Astrophysics Data System (ADS)
Kouki, Zoulel; Chaar, Besma Fayech; Ksouri, Mekki
2009-03-01
Vehicle Routing and Flexible Job Shop Scheduling Problems (VRP and FJSSP) are two common hard combinatorial optimization problems that show many similarities in their conceptual level [2, 4]. It was proved for both problems that solving techniques like exact methods fail to provide good quality solutions in a reasonable amount of time when dealing with large scale instances [1, 5, 14]. In order to overcome this weakness, we decide in the favour of meta heuristics and we focalize on evolutionary algorithms that have been successfully used in scheduling problems [1, 5, 9]. In this paper we investigate the common properties of the VRP and the FJSSP in order to provide a new controlled evolutionary approach for the CVRP optimization inspired by the FJSSP evolutionary optimization algorithms introduced in [10].
Optimal Adaptive Policies for Sequential Allocation Problems
Apostolos N. Burnetas; Michael N. Katehakis
1996-01-01
Consider the problem of sequential sampling frommstatistical populations to maximize the expected sum of outcomes in the long run. Under suitable assumptions on the unknown parameters[formula], it is shown that there exists a classCRof adaptive policies with the following properties: (i) The expectednhorizon reward[formula]under any policy ?0inCRis equal to[formula], asn??, where[formula]is the largest population mean and[formula]is a constant. (ii) Policies
Salcedo-Sanz, S.; Del Ser, J.; Landa-Torres, I.; Gil-López, S.; Portilla-Figueras, J. A.
2014-01-01
This paper presents a novel bioinspired algorithm to tackle complex optimization problems: the coral reefs optimization (CRO) algorithm. The CRO algorithm artificially simulates a coral reef, where different corals (namely, solutions to the optimization problem considered) grow and reproduce in coral colonies, fighting by choking out other corals for space in the reef. This fight for space, along with the specific characteristics of the corals' reproduction, produces a robust metaheuristic algorithm shown to be powerful for solving hard optimization problems. In this research the CRO algorithm is tested in several continuous and discrete benchmark problems, as well as in practical application scenarios (i.e., optimum mobile network deployment and off-shore wind farm design). The obtained results confirm the excellent performance of the proposed algorithm and open line of research for further application of the algorithm to real-world problems. PMID:25147860
Salcedo-Sanz, S; Del Ser, J; Landa-Torres, I; Gil-López, S; Portilla-Figueras, J A
2014-01-01
This paper presents a novel bioinspired algorithm to tackle complex optimization problems: the coral reefs optimization (CRO) algorithm. The CRO algorithm artificially simulates a coral reef, where different corals (namely, solutions to the optimization problem considered) grow and reproduce in coral colonies, fighting by choking out other corals for space in the reef. This fight for space, along with the specific characteristics of the corals' reproduction, produces a robust metaheuristic algorithm shown to be powerful for solving hard optimization problems. In this research the CRO algorithm is tested in several continuous and discrete benchmark problems, as well as in practical application scenarios (i.e., optimum mobile network deployment and off-shore wind farm design). The obtained results confirm the excellent performance of the proposed algorithm and open line of research for further application of the algorithm to real-world problems. PMID:25147860
Cooperative optimal path planning for herding problems
Lu, Zhenyu
2009-05-15
. As one can see, when w1 = 0 and w2 = 1, the flnal time is removed from the performance index. This corresponds to an efiort optimal case. When w1 = 1 and w2 = 0, the control efiort is not penalized, and any solution with respect to J becomes a time... requirement to change the weight) to penalize the third term. For our example, we choose the initial conditions to be: [xe1(t0);ye1(t0)] = [2:8;4:1], [xe2(t0);ye2(t0)] = [3:5;3:5], [xe3(t0);ye3(t0)] = [3:1;3:7], [xp1(t0);yp1(t0)] = [5;5:6] and [xp2(t0);yp2(t0...
R. Horst; N. V. Thoai
1997-01-01
Natural basic concepts in multiple-objective optimization lead to difficult multiextremal global optimization problems. Examples include detection of efficient points when nonconvexities occur, and optimization of a linear function over the efficient set in the convex (even linear) case. Assuming that a utility function exists allows one to replace in general the multiple-objective program by a single, nonconvex optimization problem, which
Lessons Learned During Solutions of Multidisciplinary Design Optimization Problems
NASA Technical Reports Server (NTRS)
Patnaik, Suna N.; Coroneos, Rula M.; Hopkins, Dale A.; Lavelle, Thomas M.
2000-01-01
Optimization research at NASA Glenn Research Center has addressed the design of structures, aircraft and airbreathing propulsion engines. During solution of the multidisciplinary problems several issues were encountered. This paper lists four issues and discusses the strategies adapted for their resolution: (1) The optimization process can lead to an inefficient local solution. This deficiency was encountered during design of an engine component. The limitation was overcome through an augmentation of animation into optimization. (2) Optimum solutions obtained were infeasible for aircraft and air-breathing propulsion engine problems. Alleviation of this deficiency required a cascading of multiple algorithms. (3) Profile optimization of a beam produced an irregular shape. Engineering intuition restored the regular shape for the beam. (4) The solution obtained for a cylindrical shell by a subproblem strategy converged to a design that can be difficult to manufacture. Resolution of this issue remains a challenge. The issues and resolutions are illustrated through six problems: (1) design of an engine component, (2) synthesis of a subsonic aircraft, (3) operation optimization of a supersonic engine, (4) design of a wave-rotor-topping device, (5) profile optimization of a cantilever beam, and (6) design of a cvlindrical shell. The combined effort of designers and researchers can bring the optimization method from academia to industry.
Optimal Multi-Modes Switching Problem in Infinite Horizon
Asri, Brahim El
2009-01-01
This paper studies the problem of the deterministic version of the Verification Theorem for the optimal m-states switching in infinite horizon under Markovian framework with arbitrary switching cost functions. The problem is formulated as an extended impulse control problem and solved by means of probabilistic tools such as the Snell envelop of processes and reflected backward stochastic differential equations. A viscosity solutions approach is employed to carry out a finne analysis on the associated system of m variational inequalities with inter-connected obstacles. We show that the vector of value functions of the optimal problem is the unique viscosity solution to the system. This problem is in relation with the valuation of firms in a financial market.
Integrated network design and scheduling problems : optimization algorithms and applications.
Nurre, Sarah G.; Carlson, Jeffrey J.
2014-01-01
We consider the class of integrated network design and scheduling problems. These problems focus on selecting and scheduling operations that will change the characteristics of a network, while being speci cally concerned with the performance of the network over time. Motivating applications of INDS problems include infrastructure restoration after extreme events and building humanitarian distribution supply chains. While similar models have been proposed, no one has performed an extensive review of INDS problems from their complexity, network and scheduling characteristics, information, and solution methods. We examine INDS problems under a parallel identical machine scheduling environment where the performance of the network is evaluated by solving classic network optimization problems. We classify that all considered INDS problems as NP-Hard and propose a novel heuristic dispatching rule algorithm that selects and schedules sets of arcs based on their interactions in the network. We present computational analysis based on realistic data sets representing the infrastructures of coastal New Hanover County, North Carolina, lower Manhattan, New York, and a realistic arti cial community CLARC County. These tests demonstrate the importance of a dispatching rule to arrive at near-optimal solutions during real-time decision making activities. We extend INDS problems to incorporate release dates which represent the earliest an operation can be performed and exible release dates through the introduction of specialized machine(s) that can perform work to move the release date earlier in time. An online optimization setting is explored where the release date of a component is not known.
Redundancy optimization problem with warm-standby redundancy
Suprasad V. Amari; G. Dill
2010-01-01
This paper describes and demonstrates a solution methodology that determines optimal design configurations that maximize the reliability of a wide range of non-repairable systems. The problem formulation considers the generic case of warm-standby redundancy and extends state-of-the-art reliability optimization techniques in several dimensions: (1) non-constant component hazard functions, (2) warm standby components including cold and hot standby situations, (3) imperfect
Ant colony optimization for solving university facility layout problem
NASA Astrophysics Data System (ADS)
Mohd Jani, Nurul Hafiza; Mohd Radzi, Nor Haizan; Ngadiman, Mohd Salihin
2013-04-01
Quadratic Assignment Problems (QAP) is classified as the NP hard problem. It has been used to model a lot of problem in several areas such as operational research, combinatorial data analysis and also parallel and distributed computing, optimization problem such as graph portioning and Travel Salesman Problem (TSP). In the literature, researcher use exact algorithm, heuristics algorithm and metaheuristic approaches to solve QAP problem. QAP is largely applied in facility layout problem (FLP). In this paper we used QAP to model university facility layout problem. There are 8 facilities that need to be assigned to 8 locations. Hence we have modeled a QAP problem with n ? 10 and developed an Ant Colony Optimization (ACO) algorithm to solve the university facility layout problem. The objective is to assign n facilities to n locations such that the minimum product of flows and distances is obtained. Flow is the movement from one to another facility, whereas distance is the distance between one locations of a facility to other facilities locations. The objective of the QAP is to obtain minimum total walking (flow) of lecturers from one destination to another (distance).
Numerical Solution of Some Types of Fractional Optimal Control Problems
Sweilam, Nasser Hassan; Al-Ajami, Tamer Mostafa; Hoppe, Ronald H. W.
2013-01-01
We present two different approaches for the numerical solution of fractional optimal control problems (FOCPs) based on a spectral method using Chebyshev polynomials. The fractional derivative is described in the Caputo sense. The first approach follows the paradigm “optimize first, then discretize” and relies on the approximation of the necessary optimality conditions in terms of the associated Hamiltonian. In the second approach, the state equation is discretized first using the Clenshaw and Curtis scheme for the numerical integration of nonsingular functions followed by the Rayleigh-Ritz method to evaluate both the state and control variables. Two illustrative examples are included to demonstrate the validity and applicability of the suggested approaches. PMID:24385874
Application of clustering global optimization to thin film design problems.
Lemarchand, Fabien
2014-03-10
Refinement techniques usually calculate an optimized local solution, which is strongly dependent on the initial formula used for the thin film design. In the present study, a clustering global optimization method is used which can iteratively change this initial formula, thereby progressing further than in the case of local optimization techniques. A wide panel of local solutions is found using this procedure, resulting in a large range of optical thicknesses. The efficiency of this technique is illustrated by two thin film design problems, in particular an infrared antireflection coating, and a solar-selective absorber coating. PMID:24663856
A Discrete Lagrangian Algorithm for Optimal Routing Problems
Kosmas, O. T.; Vlachos, D. S.; Simos, T. E. [University of Peloponnese, 22100 Tripoli (Greece)
2008-11-06
The ideas of discrete Lagrangian methods for conservative systems are exploited for the construction of algorithms applicable in optimal ship routing problems. The algorithm presented here is based on the discretisation of Hamilton's principle of stationary action Lagrangian and specifically on the direct discretization of the Lagrange-Hamilton principle for a conservative system. Since, in contrast to the differential equations, the discrete Euler-Lagrange equations serve as constrains for the optimization of a given cost functional, in the present work we utilize this feature in order to minimize the cost function for optimal ship routing.
Fuel-optimal trajectories for aeroassisted coplanar orbital transfer problem
NASA Technical Reports Server (NTRS)
Naidu, D. S.; Hibey, J. L.; Charalambous, C.
1988-01-01
The optimal-control problem arising in coplanar orbital transfer using aeroassist technology is addressed. The maneuver involves the transfer from high earth orbit to low earth orbit with minimum fuel consumption. Simulations are carried out to obtain a corridor of entry conditions which are suitable for flying the spacecraft through the atmosphere. A highlight of the present work is the application of an efficient multiple shooting method for handling the difficult nonlinear two-point boundary value problem resulting from the optimization procedure.
The Convex Hull of Rational Plane Curves
Gershon Elber; Myung-soo Kim; Hee-seok Heo
2001-01-01
We present an algorithm that computes the convex hull of multiple rational curves in the plane. The problem is reformulated as one of finding the zero-sets of polynomial equations in one or two variables; using these zero-sets we characterize curve segments that belong to the boundary of the convex hull. We also present a preprocessing step that can eliminate many
Urrutia, Jorge
The interest in the rectilinear convex hull of planar point sets arises from the study of ortho-convexity [10XIV Spanish Meeting on Computational Geometry, 27Â30 June 2011 Rectilinear convex hull with minimum the rectilinear convex hull of P has minimum area in optimal (n log n) time and O(n) space. Introduction
On Optimal AMLI Solvers for Incompressible Navier-Stokes Problems
NASA Astrophysics Data System (ADS)
Boyanova, P.; Margenov, S.
2010-11-01
We consider the incompressible Navier-Stokes problem and a projection scheme based on Crouzeix-Raviart finite element approximation of the velocities and piece-wise constant approximation of the pressure. These non-conforming finite elements guarantee that the divergence of the velocity field is zero inside each element, i.e., the approximation is locally conservative. We propose optimal order Algebraic MultiLevel Iteration (AMLI) preconditioners for both, the decoupled scalar parabolic problems at the prediction step as well as to the mixed finite element method (FEM) problem at the projection step. The main contribution of the current paper is the obtained scalability of the AMLI methods for the related composite time-stepping solution method. The algorithm for the Navier-Stokes problem has a total computational complexity of optimal order. We present numerical tests for the efficiency of the AMLI solvers for the case of lid-driven cavity flow for different Reynolds numbers.
An optimal algo-tech-cuit for the knapsack problem
R. Andonov; Sanjay Rajopadhye
1993-01-01
The authors first present a formal derivation and proof of correctness of a systolic array for the knapsack problem, an NP-complete problem whose dependency graph is not completely known statically. With q PEs, each with a fixed size memory, the arraystretch runs in ?(mc\\/q), which gives optimal speedup of the algorithm. However, it has an intricate tag-based control mechanism which
PDE: A Paretofrontier Differential Evolution Approach for Multi-objective Optimization Problems
Coello, Carlos A. Coello
attainment (Wilson and Macleod 1993), and the iso-resource-cost solu- tion method (Zeleny 1998). The concept such as linearity and convexity. The iso-resource-cost solution method (Zeleny 1998) has been recently demonstrated original problem structure) in the solution set (Zeleny 1998). The amount of available resources is decided
Lossless Convexification of Control Constraints for a Class of Nonlinear Optimal Control Problems
Williams, Brian C.
of Technology. behcet@jpl.nasa.gov J. Carson is a Guidance and Control Engineer, JPL, California Institute of Technology. jmcarson@jpl.nasa.gov control problems with nonlinear system dynamics and non- convex control bodies such as moons, comets and asteroids. General nonlinear dynamics prevent the finite
Generating Convex Polynomial Inequalities for Mixed 0–1 Programs
Robert A. Stubbs; Sanjay Mehrotra
2002-01-01
We develop a method for generating valid convex quadratic inequalities for mixed0–1 convex programs. We also show how these inequalities can be generated in the linear case by defining cut generation problems using a projection cone. The basic results for quadratic inequalities are extended to generate convex polynomial inequalities.
Binary optimization for source localization in the inverse problem of ECG.
Potyagaylo, Danila; Cortés, Elisenda Gil; Schulze, Walther H W; Dössel, Olaf
2014-09-01
The goal of ECG-imaging (ECGI) is to reconstruct heart electrical activity from body surface potential maps. The problem is ill-posed, which means that it is extremely sensitive to measurement and modeling errors. The most commonly used method to tackle this obstacle is Tikhonov regularization, which consists in converting the original problem into a well-posed one by adding a penalty term. The method, despite all its practical advantages, has however a serious drawback: The obtained solution is often over-smoothed, which can hinder precise clinical diagnosis and treatment planning. In this paper, we apply a binary optimization approach to the transmembrane voltage (TMV)-based problem. For this, we assume the TMV to take two possible values according to a heart abnormality under consideration. In this work, we investigate the localization of simulated ischemic areas and ectopic foci and one clinical infarction case. This affects only the choice of the binary values, while the core of the algorithms remains the same, making the approximation easily adjustable to the application needs. Two methods, a hybrid metaheuristic approach and the difference of convex functions (DC), algorithm were tested. For this purpose, we performed realistic heart simulations for a complex thorax model and applied the proposed techniques to the obtained ECG signals. Both methods enabled localization of the areas of interest, hence showing their potential for application in ECGI. For the metaheuristic algorithm, it was necessary to subdivide the heart into regions in order to obtain a stable solution unsusceptible to the errors, while the analytical DC scheme can be efficiently applied for higher dimensional problems. With the DC method, we also successfully reconstructed the activation pattern and origin of a simulated extrasystole. In addition, the DC algorithm enables iterative adjustment of binary values ensuring robust performance. PMID:25008005
Johnson's problem with stochastic processing times and optimal service level
Victor Portougal; Dan Trietsch
2006-01-01
Theoretical results about Johnsons problem with stochastic processing times are few. In general, just finding the expected makespan of a given sequence is already difficult, even for discrete processing time distributions. Furthermore, to obtain optimal service level we need to compute the entire distribution of the makespan. Therefore the use of heu- ristics and simulation is justified. We show that
An optimal order for ECG inverse problems with MDL.
Nakamura, H; Aoki, T; Tanaka, H
1995-01-01
A numerical simulation for body surface potential mapping was investigated using Boundary Element Method (B.E.M.). After forward simulation, we investigated the accuracy and stability of ECG inverse solution from the viewpoint of Minimum Description Length Principle (MDL). It became obvious that the solution containing up to 16th expansion components is optimal for ECG inverse problem. PMID:8591314
Intelligent evolutionary algorithms for large parameter optimization problems
Shinn-ying Ho; Li-sun Shu; Jian-hung Chen
2004-01-01
This work proposes two intelligent evolutionary algorithms IEA and IMOEA using a novel intelligent gene collector (IGC) to solve single and multiobjective large parameter optimization problems, respectively. IGC is the main phase in an intelligent recombination operator of IEA and IMOEA. Based on orthogonal experimental design, IGC uses a divide-and-conquer approach, which consists of adaptively dividing two individuals of parents
Using Ant Colony Optimization algorithm for solving project management problems
Hazem Abdallah; Hassan M. Emara; Hassan T. Dorrah; Ahmed Bahgat
2009-01-01
Network analysis provides an effective practical system for planning and controlling large projects in construction and many other fields. Ant Colony System is a recent approach used for solving path minimization problems. This paper presents the use of Ant Colony Optimization (ACO) system for solving and calculating both deterministic and probabilistic CPM\\/PERT networks. The proposed method is investigated for a
Distributed Genetic Algorithms with New Sharing Approach Multiobjective Optimization Problems
Coello, Carlos A. Coello
Distributed Genetic Algorithms with New Sharing Approach Multiobjective Optimization Problems@mail.doshisha.ac.jp sin@mikilab.doshisha.ac.jp 1 Abstract this paper, a new distributed genetic algorithm multiobjective and those in the relationship of tradeoff. genetic algorithm powerful timization methods based mechanics
Ant Colony Optimization for Solving Solid Waste Collection Scheduling Problems
Z. Ismail; S. L. Loh
2009-01-01
Problem statement: Southern Waste Management environment (SWM environment) is a company responsible for the collection and disposal of solid waste for the city of Johor Bahru, a city with over one million populations. The company is implementing an integrated solid waste management system where it involved in the optimization of resources to ensure the effectiveness of its services. Formulating this
Ant Colony Algorithms in Diverse Combinational Optimization Problems -A Survey
K. Thangavel; M. Karnan; P. Jeganathan; R. Sivakumar; G. Geetharamani
Ant Colony Optimization (ACO) metaheuristic is a recent population-based approach inspired by the observation of real ants colony and based upon their collective foraging behavior. In ACO, solutions of the problem are constructed within a stochastic iterative process, by adding solution components to partial solutions. Each individual ant constructs a part of the solution using an artificial pheromone, which reflects
QISA: Incorporating quantum computation into Simulated Annealing for optimization problems
Zhanghui Chen; Ping Luo
2011-01-01
This paper proposes a novel model of QISA (Quantum-Inspired Simulated Annealing) which embeds quan- tum computation into the Simulated Annealing (SA) process for optimization problems. Compared with previous SA studies, QISA adopts Quantum Bits (Qubits) rather than the conventional binary bits as the coding scheme, and update the entries in the Qubits sequence with different probabilities by the proposed methods
Simulation-based optimization for the quay crane scheduling problem
Pasquale Legato; Rina Mary Mazza; Roberto Trunfio
2008-01-01
Maritime terminals of pure transhipment are emerging logistic realities in long-distance containerized trade. Here, complex activities of resource allocation and scheduling should be optimized in a dynamic, non deterministic environment. The assignment of expensive quay cranes to multiple vessel-holds for container discharging and loading operations is a major problem, whose solution affects the operational performance of the whole terminal container.
To the optimization problem in minority game model
Yanishevsky, Vasyl [Drogobych Ivan Franko University, 36 Ivan Franko St., 82100 (Ukraine)
2009-12-14
The article presents the research results of the optimization problem in minority game model to a gaussian approximation using replica symmetry breaking by one step (1RSB). A comparison to replica symmetry approximation (RS) and the results from literary sources received using other methods has been held.
Ant Colony Optimization for VRP and Mail Delivery Problems
Lin Wei Dong; Cai Tian Xiang
2006-01-01
The vehicle routing problem is a central issue in transportation planning and optimization systems. The objective is to determine the most effective routes for a fleet of vehicles in order to service a set of geographically distributed customers while minimizing costs and adhering to capacity restrictions. Due to its inherent complexity, many heuristics have been proposed to solve this combinatorial
Multiagent Optimization System for Solving the Traveling Salesman Problem (TSP)
Xiao-Feng Xie; Jiming Liu
2009-01-01
The multiagent optimization system (MAOS) is a nature-inspired method, which supports cooperative search by the self-organization of a group of compact agents situated in an environment with certain sharing public knowledge. Moreover, each agent in MAOS is an autonomous entity with personal declarative memory and behavioral components. In this paper, MAOS is refined for solving the traveling salesman problem (TSP),
Optimal Surface Deployment Problem in Wireless Sensor Networks
Guo, Xiaohu "Tiger"
set of sensors, a sensor network offers different accuracy in data acquisition when the sensorsOptimal Surface Deployment Problem in Wireless Sensor Networks Miao Jin, Guodong Rong, Hongyi Wu, Liang Shuai, and Xiaohu Guo Abstract--Sensor deployment is a fundamental issue in a wireless sensor
Optimal Surface Deployment Problem in Wireless Sensor Networks
Wu, Hongyi
accuracy in data acquisition when the sensors are deployed in different ways in the Field of Interest (Fo. With a given set of sensors, a sensor network offers different accuracy in data acquisition whenOptimal Surface Deployment Problem in Wireless Sensor Networks Miao Jin1 , Guodong Rong2 , Hongyi
Approximating convex Pareto surfaces in multiobjective radiotherapy planning
Craft, David L.; Halabi, Tarek F.; Shih, Helen A.; Bortfeld, Thomas R. [Department of Radiation Oncology, Massachusetts General Hospital and Harvard Medical School, Boston, Massachusetts 02114 (United States)
2006-09-15
Radiotherapy planning involves inherent tradeoffs: the primary mission, to treat the tumor with a high, uniform dose, is in conflict with normal tissue sparing. We seek to understand these tradeoffs on a case-to-case basis, by computing for each patient a database of Pareto optimal plans. A treatment plan is Pareto optimal if there does not exist another plan which is better in every measurable dimension. The set of all such plans is called the Pareto optimal surface. This article presents an algorithm for computing well distributed points on the (convex) Pareto optimal surface of a multiobjective programming problem. The algorithm is applied to intensity-modulated radiation therapy inverse planning problems, and results of a prostate case and a skull base case are presented, in three and four dimensions, investigating tradeoffs between tumor coverage and critical organ sparing.
Duan, Hai-Bin; Xu, Chun-Fang; Xing, Zhi-Hui
2010-02-01
In this paper, a novel hybrid Artificial Bee Colony (ABC) and Quantum Evolutionary Algorithm (QEA) is proposed for solving continuous optimization problems. ABC is adopted to increase the local search capacity as well as the randomness of the populations. In this way, the improved QEA can jump out of the premature convergence and find the optimal value. To show the performance of our proposed hybrid QEA with ABC, a number of experiments are carried out on a set of well-known Benchmark continuous optimization problems and the related results are compared with two other QEAs: the QEA with classical crossover operation, and the QEA with 2-crossover strategy. The experimental comparison results demonstrate that the proposed hybrid ABC and QEA approach is feasible and effective in solving complex continuous optimization problems. PMID:20180252
Acuña, Daniel E.; Parada, Víctor
2010-01-01
Humans need to solve computationally intractable problems such as visual search, categorization, and simultaneous learning and acting, yet an increasing body of evidence suggests that their solutions to instantiations of these problems are near optimal. Computational complexity advances an explanation to this apparent paradox: (1) only a small portion of instances of such problems are actually hard, and (2) successful heuristics exploit structural properties of the typical instance to selectively improve parts that are likely to be sub-optimal. We hypothesize that these two ideas largely account for the good performance of humans on computationally hard problems. We tested part of this hypothesis by studying the solutions of 28 participants to 28 instances of the Euclidean Traveling Salesman Problem (TSP). Participants were provided feedback on the cost of their solutions and were allowed unlimited solution attempts (trials). We found a significant improvement between the first and last trials and that solutions are significantly different from random tours that follow the convex hull and do not have self-crossings. More importantly, we found that participants modified their current better solutions in such a way that edges belonging to the optimal solution (“good” edges) were significantly more likely to stay than other edges (“bad” edges), a hallmark of structural exploitation. We found, however, that more trials harmed the participants' ability to tell good from bad edges, suggesting that after too many trials the participants “ran out of ideas.” In sum, we provide the first demonstration of significant performance improvement on the TSP under repetition and feedback and evidence that human problem-solving may exploit the structure of hard problems paralleling behavior of state-of-the-art heuristics. PMID:20686597
Acuña, Daniel E; Parada, Víctor
2010-01-01
Humans need to solve computationally intractable problems such as visual search, categorization, and simultaneous learning and acting, yet an increasing body of evidence suggests that their solutions to instantiations of these problems are near optimal. Computational complexity advances an explanation to this apparent paradox: (1) only a small portion of instances of such problems are actually hard, and (2) successful heuristics exploit structural properties of the typical instance to selectively improve parts that are likely to be sub-optimal. We hypothesize that these two ideas largely account for the good performance of humans on computationally hard problems. We tested part of this hypothesis by studying the solutions of 28 participants to 28 instances of the Euclidean Traveling Salesman Problem (TSP). Participants were provided feedback on the cost of their solutions and were allowed unlimited solution attempts (trials). We found a significant improvement between the first and last trials and that solutions are significantly different from random tours that follow the convex hull and do not have self-crossings. More importantly, we found that participants modified their current better solutions in such a way that edges belonging to the optimal solution ("good" edges) were significantly more likely to stay than other edges ("bad" edges), a hallmark of structural exploitation. We found, however, that more trials harmed the participants' ability to tell good from bad edges, suggesting that after too many trials the participants "ran out of ideas." In sum, we provide the first demonstration of significant performance improvement on the TSP under repetition and feedback and evidence that human problem-solving may exploit the structure of hard problems paralleling behavior of state-of-the-art heuristics. PMID:20686597
Optimizing investment fund allocation using vehicle routing problem framework
NASA Astrophysics Data System (ADS)
Mamat, Nur Jumaadzan Zaleha; Jaaman, Saiful Hafizah; Ahmad, Rokiah Rozita
2014-07-01
The objective of investment is to maximize total returns or minimize total risks. To determine the optimum order of investment, vehicle routing problem method is used. The method which is widely used in the field of resource distribution shares almost similar characteristics with the problem of investment fund allocation. In this paper we describe and elucidate the concept of using vehicle routing problem framework in optimizing the allocation of investment fund. To better illustrate these similarities, sectorial data from FTSE Bursa Malaysia is used. Results show that different values of utility for risk-averse investors generate the same investment routes.
Optimization Problems in the Polynomial-Time Hierarchy
Christopher Umans
2006-01-01
\\u000a This talk surveys work on classifying the complexity and approximability of problems residing in the Polynomial-Time Hierarchy,\\u000a above the first level. Along the way, we highlight some prominent natural problems that are believed – but not yet known –\\u000a to be S<\\/font\\u000a>p2\\\\Sigma^p_2-complete. We describe how strong inapproximability results for certain S<\\/font\\u000a>p2\\\\Sigma^p_2 optimization problems can be obtained using dispersers
Advances in dual algorithms and convex approximation methods
NASA Technical Reports Server (NTRS)
Smaoui, H.; Fleury, C.; Schmit, L. A.
1988-01-01
A new algorithm for solving the duals of separable convex optimization problems is presented. The algorithm is based on an active set strategy in conjunction with a variable metric method. This first order algorithm is more reliable than Newton's method used in DUAL-2 because it does not break down when the Hessian matrix becomes singular or nearly singular. A perturbation technique is introduced in order to remove the nondifferentiability of the dual function which arises when linear constraints are present in the approximate problem.
Douglas Vickers; Michael D. Lee; Matthew Dry; Peter Hughes
The planar Euclidean version of the Traveling Salesperson Problem (TSP) requires finding a tour of minimal length through a two-dimensional set of points. Despite the computational intractability of these problems, most em- pirical studies have found that humans are able to find good solutions. For this reason, understanding human performance on TSPs has the potential to offer insights into basic
Christophe Tricaud; Yang Quan Chen
2008-01-01
In this paper, we introduce the general purpose optimal control problem solver RIOTS_95, Matlab toolbox, as a solver for general linear and nonlinear model predictive control (MPC) problems. This optimization toolbox is designed to solve a wide variety of optimal control problems and therefore constitutes a good candidate as a optimization solver in the MPC framework. The illustrative example of
Erwie Zahara; Yi-tung Kao
2009-01-01
Constrained optimization problems are very important in that they frequently appear in the real world. A constrained optimization problem consists of the optimization of a function subject to constraints, in which both the function and constraints may be nonlinear. Constraint handling is one of the major concerns when solving constrained optimization problems by hybrid Nelder–Mead simplex search method and particle
Optimizing the design of complex energy conversion systems by Branch and Cut
Turang Ahadi-Oskui; Stefan Vigerske; Ivo Nowak; George Tsatsaronis
2010-01-01
The paper examines the applicability of mathematical programming methods to the simultaneous optimization of the structure and the operational parameters of a combined-cycle-based cogeneration plant. Thus, the optimization problem is formulated as a highly non-convex mixed-integer nonlinear problem (MINLP) and solved by the MINLP solver LaGO. The algorithm generates a convex relaxation of the MINLP and applies a Branch and
ON MAXIMAL S-FREE CONVEX SETS 1. Introduction. A convex set ...
2010-05-29
?H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute ...... [8] A. Ben-Tal and A. Nemirovski, Lectures on modern convex optimization: ... and engineering applications, Society for Industrial and Applied Mathematics, ...
Solving quadratic programming problems by delayed projection neural network.
Yang, Yongqing; Cao, Jinde
2006-11-01
In this letter, the delayed projection neural network for solving convex quadratic programming problems is proposed. The neural network is proved to be globally exponentially stable and can converge to an optimal solution of the optimization problem. Three examples show the effectiveness of the proposed network. PMID:17131675
CONVEX BACKSCATTERING SUPPORT IN ELECTRIC IMPEDANCE TOMOGRAPHY
Hanke-Bourgeois, Martin
CONVEX BACKSCATTERING SUPPORT IN ELECTRIC IMPEDANCE TOMOGRAPHY MARTIN HANKE, NUUTTI HYV ¨ONEN for the inverse obstacle problem in impedance tomography. Under mild restrictions on the topological prop- erties can be computed numerically; numerical reconstructions are included to illustrate the viability
CONVERGENCE FOR STABILISATION OF DEGENERATELY CONVEX MINIMISATION
Bartels, Soeren
CONVERGENCE FOR STABILISATION OF DEGENERATELY CONVEX MINIMISATION PROBLEMS S. BARTELS, C convergence of straightforward finite element approx- imations cannot be expected but is relevant in many applications. This paper establishes a modified discretization by stabilisation and proves its convergence
A new optimization method, the Algorithm of Changes, for Bin Packing Problem
Sik-Chung Tam; Hou-Kuan Tam; Lap-Mou Tam; Tong Zhang
2010-01-01
The Bin Packing Problem (BPP) is one of the classic NP-hard problems in combinatorial optimization. It is difficult to find the optimal solution even though the size of the problem is small. Many researchers applied the traditional evolutionary algorithm, Genetic Algorithms (GA), Evolution Strategy (ES) etc. to solve the BPP problem in recent research. In this study, a new optimization
AN INTERIOR POINT ALGORITHM FOR SOLVING LINEAR OPTIMIZATION OVER THE EFFICIENT SET PROBLEMS
Wei-Tai Weng; Ue-Pyng Wen
2001-01-01
The efficient set of a multiple objective linear programming problem is usually nonconvex, hence linear optimization over the efficient set problem is classified as a nonlinear optimization problem. This paper presents a modified interior point algorithm for solving linear optimization over the efficient set problems. Using computational experiments, we show that the modified algorithm provides an effective and accurate approach
Duc T. Nguyen
1990-01-01
Practical engineering application can often be formulated in the form of a constrained optimization problem. There are several solution algorithms for solving a constrained optimization problem. One approach is to convert a constrained problem into a series of unconstrained problems. Furthermore, unconstrained solution algorithms can be used as part of the constrained solution algorithms. Structural optimization is an iterative process
Analysis of a turning point problem in flight trajectory optimization
NASA Technical Reports Server (NTRS)
Gracey, C.
1989-01-01
The optimal control policy for the aeroglide portion of the minimum fuel, orbital plane change problem for maneuvering entry vehicles is reduced to the solution of a turning point problem for the bank angle control. For this problem a turning point occurs at the minimum altitude of the flight, when the flight path angle equals zero. The turning point separates the bank angle control into two outer solutions that are valid away from the turning point. In a neighborhood of the turning point, where the bank angle changes rapidly, an inner solution is developed and matched with the two outer solutions. An asymptotic analysis of the turning point problem is given, and an analytic example is provided to illustrate the construction of the bank angle control.
Optimization of spring-loaded crutches via boundary value problem.
Liu, Guangyu; ShaneXie, Sheng-Quan; Zhang, Yanxin
2011-02-01
The objective of the work is to optimize the design of spring-loaded crutches by choosing appropriate spring stiffness based on their dynamic characteristics. It was shown in the literature that ambulation with spring-loaded crutches reduces the initial impulse yielded by ambulation with standard crutches and provides a propulsion mechanism. This research not only provides a genre of the spring-loaded crutches via compliance, but also proposes an approach to optimize the stiffness of the helical spring through studying the dynamics of crutch stance. The method is developed using a boundary value problem and its solution method and is studied numerically. Experiments were carried out on four subjects in a biomechanics laboratory. It suggests that the optimized spring-loaded crutches guarantee the propulsion mechanism at the right time and right position during dynamical ambulation. PMID:20519159
Radio interferometric gain calibration as a complex optimization problem
Smirnov, Oleg
2015-01-01
Recent developments in optimization theory have extended some traditional algorithms for least-squares optimization of real-valued functions (Gauss-Newton, Levenberg-Marquardt, etc.) into the domain of complex functions of a complex variable. This employs a formalism called the Wirtinger derivative, and derives a full-complex Jacobian counterpart to the conventional real Jacobian. We apply these developments to the problem of radio interferometric gain calibration, and show how the general complex Jacobian formalism, when combined with conventional optimization approaches, yields a whole new family of calibration algorithms, including those for the polarized and direction-dependent gain regime. We further extend the Wirtinger calculus to an operator-based matrix calculus for describing the polarized calibration regime. Using approximate matrix inversion results in computationally efficient implementations; we show that some recently proposed calibration algorithms such as StefCal and peeling can be understood...
Optimal least-squares finite element method for elliptic problems
NASA Technical Reports Server (NTRS)
Jiang, Bo-Nan; Povinelli, Louis A.
1991-01-01
An optimal least squares finite element method is proposed for two dimensional and three dimensional elliptic problems and its advantages are discussed over the mixed Galerkin method and the usual least squares finite element method. In the usual least squares finite element method, the second order equation (-Delta x (Delta u) + u = f) is recast as a first order system (-Delta x p + u = f, Delta u - p = 0). The error analysis and numerical experiment show that, in this usual least squares finite element method, the rate of convergence for flux p is one order lower than optimal. In order to get an optimal least squares method, the irrotationality Delta x p = 0 should be included in the first order system.
The Breeder Genetic Algorithm and its application to optimization problems
Muehlenbein, H.
1994-12-31
The Breeder Genetic Algorithm BGA models artificial selection as performed by human breeders. The science of breeding is based on advanced statistical methods. The well known response to selection equation and the concept of heritability have been used to predict the behavior of the BGA. Selection, recombination and mutation have been analyzed within this framework. The theoretical results have been obtained under the assumption of additive gene effects. For general fitness landscapes regression techniques for estimating the heritability are used to analyze and control the BGA. The BGA has been applied to a number of optimization problems, ranging from the optimization of multimodal continuous functions to the breeding of neural networks. In the talk we will describe the first application in some detail and summarize some combinatorial applications e.g. transport optimization, job shop scheduling, autocorrelation.
Fuel-optimal trajectories for aeroassisted coplanar orbital transfer problem
NASA Technical Reports Server (NTRS)
Naidu, Desineni Subbaramaiah; Hibey, Joseph L.; Charalambous, Charalambos D.
1990-01-01
The optimal control problem arising in coplanar orbital transfer employing aeroassist technology is addressed. The maneuver involves the transfer from high to low earth orbit via the atmosphere, with the object of minimizing the total fuel consumption. Simulations are carried out to obtain the fuel-optimal trajectories for flying the spacecraft through the atmosphere. A highlight is the application of an efficient multiple-shooting method for treating the nonlinear two-point boundary value problem resulting from the optimizaion procedure. The strategy for the atmospheric portion of the minimum-fuel transfer is to fly at the maximum lift-to-drag ratio L/D initially in order to recover from the downward plunge, and then to fly at a negative L/D to level off the flight so that the vehicle skips out of the atmosphere with a flight path angle near zero degrees.
An improved particle swarm optimization algorithm for reliability problems.
Wu, Peifeng; Gao, Liqun; Zou, Dexuan; Li, Steven
2011-01-01
An improved particle swarm optimization (IPSO) algorithm is proposed to solve reliability problems in this paper. The IPSO designs two position updating strategies: In the early iterations, each particle flies and searches according to its own best experience with a large probability; in the late iterations, each particle flies and searches according to the fling experience of the most successful particle with a large probability. In addition, the IPSO introduces a mutation operator after position updating, which can not only prevent the IPSO from trapping into the local optimum, but also enhances its space developing ability. Experimental results show that the proposed algorithm has stronger convergence and stability than the other four particle swarm optimization algorithms on solving reliability problems, and that the solutions obtained by the IPSO are better than the previously reported best-known solutions in the recent literature. PMID:20850737
Compensated optimal grids for elliptic boundary-value problems.
Posta, F; Shvartsman, S Y; Muratov, C B
2008-10-01
A method is proposed which allows to efficiently treat elliptic problems on unbounded domains in two and three spatial dimensions in which one is only interested in obtaining accurate solutions at the domain boundary. The method is an extension of the optimal grid approach for elliptic problems, based on optimal rational approximation of the associated Neumann-to-Dirichlet map in Fourier space. It is shown that, using certain types of boundary discretization, one can go from second-order accurate schemes to essentially spectrally accurate schemes in two-dimensional problems, and to fourth-order accurate schemes in three-dimensional problems without any increase in the computational complexity. The main idea of the method is to modify the impedance function being approximated to compensate for the numerical dispersion introduced by a small finite-difference stencil discretizing the differential operator on the boundary. We illustrate how the method can be efficiently applied to nonlinear problems arising in modeling of cell communication. PMID:19802366
Pitam Singh; Shiv Datt Kumar; R. K. Singh
2010-01-01
Many practical optimization problems usually have several conflicting objectives. In those multiobjective optimization, no solution optimizing all the objective functions simultaneously exists in general. Instead, pareto - optimal solutions, which are efficient in terms of all objective functions, are introduced. In general we have many optimal solutions. Therefore we need to decide a final solutions among pareto - optimal solutions
Asynchronous global optimization techniques for medium and large inversion problems
Pereyra, V.; Koshy, M. [Weidlinger Associates, Los Altos, CA (United States); Meza, J.C. [Sandia National Labs., Livermore, CA (United States)
1995-04-01
We discuss global optimization procedures adequate for seismic inversion problems. We explain how to save function evaluations (which may involve large scale ray tracing or other expensive operations) by creating a data base of information on what parts of parameter space have already been inspected. It is also shown how a correct parallel implementation using PVM speeds up the process almost linearly with respect to the number of processors, provided that the function evaluations are expensive enough to offset the communication overhead.
Optimal Control and the Aircraft Radar Evasion Problem
I. I. Hussein; F. H. Zeitz; A. M. Bloch
2007-01-01
This paper considers the problem of optimal path planning for unmanned aerial vehicles in the presence of radar-guided surface-to-air missiles. The goal is to generate trajectories that ensure that the aerial vehicle visit a given set of way points while avoiding a given set of known locations of radar units. In this paper we first discuss the general radar evasion
Particle Swarm Optimization Algorithm for Permutation Flowshop Sequencing Problem
Mehmet Fatih Tasgetiren; Mehmet Sevkli; Yun-chia Liang; Gunes Gencyilmaz
2004-01-01
\\u000a This paper presents a particle swarm optimization algorithm (PSO) to solve the permutation flowshop sequencing problem (PFSP)\\u000a with makespan criterion. Simple but very efficient local search based on the variable neighborhood search (VNS) is embedded\\u000a in the PSO algorithm to solve the benchmark suites in the literature. The results are presented and compared to the best known\\u000a approaches in the
Issues and Strategies in Solving Multidisciplinary Optimization Problems
NASA Technical Reports Server (NTRS)
Patnaik, Surya
2013-01-01
Optimization research at NASA Glenn Research Center has addressed the design of structures, aircraft and airbreathing propulsion engines. The accumulated multidisciplinary design activity is collected under a testbed entitled COMETBOARDS. Several issues were encountered during the solution of the problems. Four issues and the strategies adapted for their resolution are discussed. This is followed by a discussion on analytical methods that is limited to structural design application. An optimization process can lead to an inefficient local solution. This deficiency was encountered during design of an engine component. The limitation was overcome through an augmentation of animation into optimization. Optimum solutions obtained were infeasible for aircraft and airbreathing propulsion engine problems. Alleviation of this deficiency required a cascading of multiple algorithms. Profile optimization of a beam produced an irregular shape. Engineering intuition restored the regular shape for the beam. The solution obtained for a cylindrical shell by a subproblem strategy converged to a design that can be difficult to manufacture. Resolution of this issue remains a challenge. The issues and resolutions are illustrated through a set of problems: Design of an engine component, Synthesis of a subsonic aircraft, Operation optimization of a supersonic engine, Design of a wave-rotor-topping device, Profile optimization of a cantilever beam, and Design of a cylindrical shell. This chapter provides a cursory account of the issues. Cited references provide detailed discussion on the topics. Design of a structure can also be generated by traditional method and the stochastic design concept. Merits and limitations of the three methods (traditional method, optimization method and stochastic concept) are illustrated. In the traditional method, the constraints are manipulated to obtain the design and weight is back calculated. In design optimization, the weight of a structure becomes the merit function with constraints imposed on failure modes and an optimization algorithm is used to generate the solution. Stochastic design concept accounts for uncertainties in loads, material properties, and other parameters and solution is obtained by solving a design optimization problem for a specified reliability. Acceptable solutions can be produced by all the three methods. The variation in the weight calculated by the methods was found to be modest. Some variation was noticed in designs calculated by the methods. The variation may be attributed to structural indeterminacy. It is prudent to develop design by all three methods prior to its fabrication. The traditional design method can be improved when the simplified sensitivities of the behavior constraint is used. Such sensitivity can reduce design calculations and may have a potential to unify the traditional and optimization methods. Weight versus reliability traced out an inverted-S-shaped graph. The center of the graph corresponded to mean valued design. A heavy design with weight approaching infinity could be produced for a near-zero rate of failure. Weight can be reduced to a small value for a most failure-prone design. Probabilistic modeling of load and material properties remained a challenge.
Lloyd S. Shapley
1971-01-01
The core of ann-person game is the set of feasible outcomes that cannot be improved upon by any coalition of players. A convex game is defined as one that is based on a convex set function. In this paper it is shown that the core of a convex game is not empty and that it has an especially regular structure.
Practical Global Optimization for Multiview Geometry
Sameer Agarwal; Manmohan Krishna Chandraker; Fredrik Kahl; David J. Kriegman; Serge Belongie
2006-01-01
This paper presents a practical method for finding the provably globally optimal solution to numerous prob- lems in projective geometry including multiview triangula- tion, camera resectioning and homography estimation. Un- like traditional methods which may get trapped in local min- ima due to the non-convex nature of these problems, this ap- proach provides a theoretical guarantee of global optimality. The
NASA Astrophysics Data System (ADS)
Gao, Qian
For both the conventional radio frequency and the comparably recent optical wireless communication systems, extensive effort from the academia had been made in improving the network spectrum efficiency and/or reducing the error rate. To achieve these goals, many fundamental challenges such as power efficient constellation design, nonlinear distortion mitigation, channel training design, network scheduling and etc. need to be properly addressed. In this dissertation, novel schemes are proposed accordingly to deal with specific problems falling in category of these challenges. Rigorous proofs and analyses are provided for each of our work to make a fair comparison with the corresponding peer works to clearly demonstrate the advantages. The first part of this dissertation considers a multi-carrier optical wireless system employing intensity modulation (IM) and direct detection (DD). A block-wise constellation design is presented, which treats the DC-bias that conventionally used solely for biasing purpose as an information basis. Our scheme, we term it MSM-JDCM, takes advantage of the compactness of sphere packing in a higher dimensional space, and in turn power efficient constellations are obtained by solving an advanced convex optimization problem. Besides the significant power gains, the MSM-JDCM has many other merits such as being capable of mitigating nonlinear distortion by including a peak-to-power ratio (PAPR) constraint, minimizing inter-symbol-interference (ISI) caused by frequency-selective fading with a novel precoder designed and embedded, and further reducing the bit-error-rate (BER) by combining with an optimized labeling scheme. The second part addresses several optimization problems in a multi-color visible light communication system, including power efficient constellation design, joint pre-equalizer and constellation design, and modeling of different structured channels with cross-talks. Our novel constellation design scheme, termed CSK-Advanced, is compared with the conventional decoupled system with the same spectrum efficiency to demonstrate the power efficiency. Crucial lighting requirements are included as optimization constraints. To control non-linear distortion, the optical peak-to-average-power ratio (PAPR) of LEDs can be individually constrained. With a SVD-based pre-equalizer designed and employed, our scheme can achieve lower BER than counterparts applying zero-forcing (ZF) or linear minimum-mean-squared-error (LMMSE) based post-equalizers. Besides, a binary switching algorithm (BSA) is applied to improve BER performance. The third part looks into a problem of two-phase channel estimation in a relayed wireless network. The channel estimates in every phase are obtained by the linear minimum mean squared error (LMMSE) method. Inaccurate estimate of the relay to destination (RtD) channel in phase 1 could affect estimate of the source to relay (StR) channel in phase 2, which is made erroneous. We first derive a close-form expression for the averaged Bayesian mean-square estimation error (ABMSE) for both phase estimates in terms of the length of source and relay training slots, based on which an iterative searching algorithm is then proposed that optimally allocates training slots to the two phases such that estimation errors are balanced. Analysis shows how the ABMSE of the StD channel estimation varies with the lengths of relay training and source training slots, the relay amplification gain, and the channel prior information respectively. The last part deals with a transmission scheduling problem in a uplink multiple-input-multiple-output (MIMO) wireless network. Code division multiple access (CDMA) is assumed as a multiple access scheme and pseudo-random codes are employed for different users. We consider a heavy traffic scenario, in which each user always has packets to transmit in the scheduled time slots. If the relay is scheduled for transmission together with users, then it operates in a full-duplex mode, where the packets previously collected from users are transmitted to the destination
Feed Forward Neural Network and Optimal Control Problem with Control and State Constraints
Kmet', Tibor [Department of Informatics, Constantine the Philosopher University, Tr. A. Hlinku 1, 949 74 Nitra (Slovakia); Kmet'ova, Maria [Department of Mathematics, Constantine the Philosopher University, Tr. A. Hlinku 1, 949 74 Nitra (Slovakia)
2009-09-09
A feed forward neural network based optimal control synthesis is presented for solving optimal control problems with control and state constraints. The paper extends adaptive critic neural network architecture proposed by [5] to the optimal control problems with control and state constraints. The optimal control problem is transcribed into a nonlinear programming problem which is implemented with adaptive critic neural network. The proposed simulation method is illustrated by the optimal control problem of nitrogen transformation cycle model. Results show that adaptive critic based systematic approach holds promise for obtaining the optimal control with control and state constraints.
Multi-objective evolutionary methods for time-changing portfolio optimization problems
Hatzakis, Iason
2007-01-01
This thesis is focused on the discovery of efficient asset allocations with the use of evolutionary algorithms. The portfolio optimization problem is a multi-objective optimization problem for the conflicting criteria of ...
On the robust optimization to the uncertain vaccination strategy problem
Chaerani, D., E-mail: d.chaerani@unpad.ac.id; Anggriani, N., E-mail: d.chaerani@unpad.ac.id; Firdaniza, E-mail: d.chaerani@unpad.ac.id [Department of Mathematics, Faculty of Mathematics and Natural Sciences, University of Padjadjaran Indonesia, Jalan Raya Bandung Sumedang KM 21 Jatinangor Sumedang 45363 (Indonesia)
2014-02-21
In order to prevent an epidemic of infectious diseases, the vaccination coverage needs to be minimized and also the basic reproduction number needs to be maintained below 1. This means that as we get the vaccination coverage as minimum as possible, thus we need to prevent the epidemic to a small number of people who already get infected. In this paper, we discuss the case of vaccination strategy in term of minimizing vaccination coverage, when the basic reproduction number is assumed as an uncertain parameter that lies between 0 and 1. We refer to the linear optimization model for vaccination strategy that propose by Becker and Starrzak (see [2]). Assuming that there is parameter uncertainty involved, we can see Tanner et al (see [9]) who propose the optimal solution of the problem using stochastic programming. In this paper we discuss an alternative way of optimizing the uncertain vaccination strategy using Robust Optimization (see [3]). In this approach we assume that the parameter uncertainty lies within an ellipsoidal uncertainty set such that we can claim that the obtained result will be achieved in a polynomial time algorithm (as it is guaranteed by the RO methodology). The robust counterpart model is presented.
Resource Efficient Gadgets for Compiling Adiabatic Quantum Optimization Problems
Ryan Babbush; Bryan O'Gorman; Alán Aspuru-Guzik
2013-07-30
We develop a resource efficient method by which the ground-state of an arbitrary k-local, optimization Hamiltonian can be encoded as the ground-state of a (k-1)-local optimization Hamiltonian. This result is important because adiabatic quantum algorithms are often most easily formulated using many-body interactions but experimentally available interactions are generally 2-body. In this context, the efficiency of a reduction gadget is measured by the number of ancilla qubits required as well as the amount of control precision needed to implement the resulting Hamiltonian. First, we optimize methods of applying these gadgets to obtain 2-local Hamiltonians using the least possible number of ancilla qubits. Next, we show a novel reduction gadget which minimizes control precision and a heuristic which uses this gadget to compile 3-local problems with a significant reduction in control precision. Finally, we present numerics which indicate a substantial decrease in the resources required to implement randomly generated, 3-body optimization Hamiltonians when compared to other methods in the literature.
Resource efficient gadgets for compiling adiabatic quantum optimization problems
NASA Astrophysics Data System (ADS)
Babbush, Ryan; O'Gorman, Bryan; Aspuru-Guzik, Alán
2013-11-01
We develop a resource efficient method by which the ground-state of an arbitrary k-local, optimization Hamiltonian can be encoded as the ground-state of a (k-1)-local optimization Hamiltonian. This result is important because adiabatic quantum algorithms are often most easily formulated using many-body interactions but experimentally available interactions are generally 2-body. In this context, the efficiency of a reduction gadget is measured by the number of ancilla qubits required as well as the amount of control precision needed to implement the resulting Hamiltonian. First, we optimize methods of applying these gadgets to obtain 2-local Hamiltonians using the least possible number of ancilla qubits. Next, we show a novel reduction gadget which minimizes control precision and a heuristic which uses this gadget to compile 3-local problems with a significant reduction in control precision. Finally, we present numerics which indicate a substantial decrease in the resources required to implement randomly generated, 3-body optimization Hamiltonians when compared to other methods in the literature.
On the problem of optimal thrust programming for a lunar soft landing
J. Meditch; V. G. Boltyanskii; R. V. Gamkrelidze; E. F. Llischenko
1964-01-01
The problem of minimal fuel thrust programming for the terminal phase of a lunar soft landing mission is shown to be equivalent to the minimal time problem for the mission. The existence of an optimal (minimal fuel) thrust program for the problem is then assured by appealing to existence theorems for time optimal controls, and the optimal thrust program is
Forrelation: A Problem that Optimally Separates Quantum from Classical Computing
Scott Aaronson; Andris Ambainis
2014-11-21
We achieve essentially the largest possible separation between quantum and classical query complexities. We do so using a property-testing problem called Forrelation, where one needs to decide whether one Boolean function is highly correlated with the Fourier transform of a second function. This problem can be solved using 1 quantum query, yet we show that any randomized algorithm needs ~sqrt(N)/log(N) queries (improving an ~N^{1/4} lower bound of Aaronson). Conversely, we show that this 1 versus ~sqrt(N) separation is optimal: indeed, any t-query quantum algorithm whatsoever can be simulated by an O(N^{1-1/2t})-query randomized algorithm. Thus, resolving an open question of Buhrman et al. from 2002, there is no partial Boolean function whose quantum query complexity is constant and whose randomized query complexity is linear. We conjecture that a natural generalization of Forrelation achieves the optimal t versus ~N^{1-1/2t} separation for all t. As a bonus, we show that this generalization is BQP-complete. This yields what's arguably the simplest BQP-complete problem yet known, and gives a second sense in which Forrelation "captures the maximum power of quantum computation."
Project impact analysis as an optimal control problem
Anandalingam, G.
1981-01-01
This paper analyzes the effects of a major investment project on a multi-sector less developed economy. Single investment projects with external effects reaching across the entire economy are frequently encountered in developing countries. This study concentrates on the Mahaweli Ganga Development Project in Sri Lanka, a multi-dam irrigation and hydroelectric power project. The Mahaweli Project calls for an annual investment level, in 1970 prices, of Rs 2200 million (US $150 million) over a period of six years, which is 50 percent of the annual expenditure of the government. The project would thus require a large fraction of total investment over a medium term planning period and would materially alter the existing supply and demand for major goods and services. The project is sufficiently large that its effect is economy-wide. The model we use is a dynamic input-output optimizing model having the mathematical structure of an Optimal Control problem.
Mathematical theory of a relaxed design problem in structural optimization
NASA Technical Reports Server (NTRS)
Kikuchi, Noboru; Suzuki, Katsuyuki
1990-01-01
Various attempts have been made to construct a rigorous mathematical theory of optimization for size, shape, and topology (i.e. layout) of an elastic structure. If these are represented by a finite number of parametric functions, as Armand described, it is possible to construct an existence theory of the optimum design using compactness argument in a finite dimensional design space or a closed admissible set of a finite dimensional design space. However, if the admissible design set is a subset of non-reflexive Banach space such as L(sup infinity)(Omega), construction of the existence theory of the optimum design becomes suddenly difficult and requires to extend (i.e. generalize) the design problem to much more wider class of design that is compatible to mechanics of structures in the sense of variational principle. Starting from the study by Cheng and Olhoff, Lurie, Cherkaev, and Fedorov introduced a new concept of convergence of design variables in a generalized sense and construct the 'G-Closure' theory of an extended (relaxed) optimum design problem. A similar attempt, but independent in large extent, can also be found in Kohn and Strang in which the shape and topology optimization problem is relaxed to allow to use of perforated composites rather than restricting it to usual solid structures. An identical idea is also stated in Murat and Tartar using the notion of the homogenization theory. That is, introducing possibility of micro-scale perforation together with the theory of homogenization, the optimum design problem is relaxed to construct its mathematical theory. It is also noted that this type of relaxed design problem is perfectly matched to the variational principle in structural mechanics.
Fast algorithms for L? problems in multiview geometry
Sameer Agarwal; Noah Snavely; Steven M. Seitz
2008-01-01
Many problems in multi-view geometry, when posed as minimization of the maximum reprojection error across observations, can be solved optimally in polynomial time. We show that these problems are instances of a convex-concave generalized fractional program. We survey the major solution methods for solving problems of this form and present them in a unified framework centered around a single parametric
Near-optimal perfectly matched layers for indefinite Helmholtz problems
Vladimir Druskin; Stefan Güttel; Leonid Knizhnerman
2015-07-22
A new construction of an absorbing boundary condition for indefinite Helmholtz problems on unbounded domains is presented. This construction is based on a near-best uniform rational interpolant of the inverse square root function on the union of a negative and positive real interval, designed with the help of a classical result by Zolotarev. Using Krein's interpretation of a Stieltjes continued fraction, this interpolant can be converted into a three-term finite difference discretization of a perfectly matched layer (PML) which converges exponentially fast in the number of grid points. The convergence rate is asymptotically optimal for both propagative and evanescent wave modes. Several numerical experiments and illustrations are included.
Lattice point sets for deterministic learning and approximate optimization problems.
Cervellera, Cristiano
2010-04-01
In this brief, the use of lattice point sets (LPSs) is investigated in the context of general learning problems (including function estimation and dynamic optimization), in the case where the classic empirical risk minimization (ERM) principle is considered and there is freedom to choose the sampling points of the input space. Here it is proved that convergence of the ERM principle is guaranteed when LPSs are employed as training sets for the learning procedure, yielding up to a superlinear convergence rate under some regularity hypotheses on the involved functions. Preliminary simulation results are also provided. PMID:20172819
Algorithms for bilevel optimization
NASA Technical Reports Server (NTRS)
Alexandrov, Natalia; Dennis, J. E., Jr.
1994-01-01
General multilevel nonlinear optimization problems arise in design of complex systems and can be used as a means of regularization for multi-criteria optimization problems. Here, for clarity in displaying our ideas, we restrict ourselves to general bi-level optimization problems, and we present two solution approaches. Both approaches use a trust-region globalization strategy, and they can be easily extended to handle the general multilevel problem. We make no convexity assumptions, but we do assume that the problem has a nondegenerate feasible set. We consider necessary optimality conditions for the bi-level problem formulations and discuss results that can be extended to obtain multilevel optimization formulations with constraints at each level.
Solving the Attribute Reduction Problem with Ant Colony Optimization
NASA Astrophysics Data System (ADS)
Yu, Hong; Wang, Guoyin; Lan, Fakuan
Attribute reduction is an important process in rough set theory. More minimal attribute reductions are expected to help clients make decisions in some cases, though the minimal attribute reduction problem (MARP) is proved to be an NP-hard problem. In this paper, we propose a new heuristic approach for solving the MARP based on the ant colony optimization (ACO) metaheuristic. We first model the MARP as finding an assignment which minimizes the cost in a graph. Afterward, we introduce a preprocessing step that removes the redundant data in a discernibility matrix through the absorption operator and the cutting operator, the goal of which is to favor a smaller exploration of the search space at a lower cost. We then develop a new algorithm R-ACO for solving the MARP. Finally, the simulation results show that our approach can find more minimal attribute reductions more efficiently in most cases.
Random Convex Hulls and Extreme Value Statistics
Satya N. Majumdar; Alain Comtet; Julien Randon-Furling
2010-01-01
In this paper we study the statistical properties of convex hulls of N random points in a plane chosen according to a given distribution. The points may be chosen independently or they may be\\u000a correlated. After a non-exhaustive survey of the somewhat sporadic literature and diverse methods used in the random convex\\u000a hull problem, we present a unifying approach, based
Paris-Sud XI, Université de
have been directed mainly towards solving the vehicle routing problem (VRP). It's an optimization variant of VRP which is the PDPTW (Pickup and Delivery Problem with Time Windows) with capacity Problem (VRP) represents a multi- goal combinatorial optimization problem which has been the subject
Radio interferometric gain calibration as a complex optimization problem
NASA Astrophysics Data System (ADS)
Smirnov, O. M.; Tasse, C.
2015-05-01
Recent developments in optimization theory have extended some traditional algorithms for least-squares optimization of real-valued functions (Gauss-Newton, Levenberg-Marquardt, etc.) into the domain of complex functions of a complex variable. This employs a formalism called the Wirtinger derivative, and derives a full-complex Jacobian counterpart to the conventional real Jacobian. We apply these developments to the problem of radio interferometric gain calibration, and show how the general complex Jacobian formalism, when combined with conventional optimization approaches, yields a whole new family of calibration algorithms, including those for the polarized and direction-dependent gain regime. We further extend the Wirtinger calculus to an operator-based matrix calculus for describing the polarized calibration regime. Using approximate matrix inversion results in computationally efficient implementations; we show that some recently proposed calibration algorithms such as STEFCAL and peeling can be understood as special cases of this, and place them in the context of the general formalism. Finally, we present an implementation and some applied results of COHJONES, another specialized direction-dependent calibration algorithm derived from the formalism.
SIMULTANEOUS OPTIMIZATION OF TALLIES; IN DIFFICULT SHIELDING PROBLEMS
Peplow, Douglas E. [ORNL] [ORNL; Evans, Thomas M [ORNL] [ORNL; Wagner, John C [ORNL] [ORNL
2009-01-01
Monte Carlo is quite useful for calculating specific quantities in complex transport problems. Many variance reduction strategies have been developed that accelerate Monte Carlo calculations for specific tallies. However, when trying to calculate multiple tallies or a mesh tally, users have had to accept different levels of relative uncertainty among the tallies or run separate calculations optimized for each individual tally. To address this limitation, an extension of the CADIS (Consistent Adjoint Driven Importance Sampling) method, which is used for difficult source/detector problems, has been developed to optimize several tallies or the cells of a mesh tally simultaneously. The basis for this method is the development of an importance function that represents the importance of particles to the objective of uniform Monte Carlo particle density in the desired tally regions. This method utilizes the results of a forward discrete ordinates solution, which may be based on a quick, coarse-mesh calculation, to develop a forward-weighted source for the adjoint calculation. The importance map and the biased source computed from the adjoint flux are then used in the forward Monte Carlo calculation to obtain approximately uniform relative uncertainties for the desired tallies. This extension is called forward-weighted CADIS, or FW-CADIS.
Very Large-Scale Neighborhood Search for Solving Multiobjective Combinatorial Optimization Problems
Thibaut Lust; Jacques Teghem; Daniel Tuyttens
2011-01-01
\\u000a Very large-scale neighborhood search (VLSNS) is a technique intensively used in single-objective optimization. However, there\\u000a is almost no study of VLSNS for multiobjective optimization. We show in this paper that this technique is very efficient for\\u000a the resolution of multiobjective combinatorial optimization problems. Two problems are considered: the multiobjective multidimensional\\u000a knapsack problem and the multiobjective set covering problem. VLSNS are
M. H. Afshar
2007-01-01
This paper exploits the unique feature of the Ant Colony Optimization Algorithm (ACOA), namely incremental solution building mechanism, to develop partially constraint ACO algorithms for the solution of optimization problems with explicit constraints. The method is based on the provision of a tabu list for each ant at each decision point of the problem so that some constraints of the
Convex Clustering with Exemplar-Based Models
Lashkari, Danial; Golland, Polina
2015-01-01
Clustering is often formulated as the maximum likelihood estimation of a mixture model that explains the data. The EM algorithm widely used to solve the resulting optimization problem is inherently a gradient-descent method and is sensitive to initialization. The resulting solution is a local optimum in the neighborhood of the initial guess. This sensitivity to initialization presents a significant challenge in clustering large data sets into many clusters. In this paper, we present a different approach to approximate mixture fitting for clustering. We introduce an exemplar-based likelihood function that approximates the exact likelihood. This formulation leads to a convex minimization problem and an efficient algorithm with guaranteed convergence to the globally optimal solution. The resulting clustering can be thought of as a probabilistic mapping of the data points to the set of exemplars that minimizes the average distance and the information-theoretic cost of mapping. We present experimental results illustrating the performance of our algorithm and its comparison with the conventional approach to mixture model clustering.
One-Dimensional Infinite Horizon Nonconcave Optimal Control Problems Arising in Economic Dynamics
Zaslavski, Alexander J., E-mail: ajzasl@tx.technion.ac.il [Technion-Israel Institute of Technology, Department of Mathematics (Israel)
2011-12-15
We study the existence of optimal solutions for a class of infinite horizon nonconvex autonomous discrete-time optimal control problems. This class contains optimal control problems without discounting arising in economic dynamics which describe a model with a nonconcave utility function.
Otoni Nóbrega Neto; Ronaldo R. B. Aquino; Milde M. S. Lira
\\u000a This chapter deals with the study of artificial neural networks (ANNs) and Heuristic Rules (HR) to solve optimization problems.\\u000a The study of ANN as optimization tools for solving large scale problems was due to the fact that this technique has great\\u000a potential for hardware VLSI implementation, in which it may be more efficient than traditional optimization techniques. However,\\u000a the implementation
Weakly convex sets and modulus of nonconvexity
Balashov, Maxim V; 10.1016/j.jmaa.2010.04.039
2010-01-01
We consider a definition of a weakly convex set which is a generalization of the notion of a weakly convex set in the sense of Vial and a proximally smooth set in the sense of Clarke, from the case of the Hilbert space to a class of Banach spaces with the modulus of convexity of the second order. Using the new definition of the weakly convex set with the given modulus of nonconvexity we prove a new retraction theorem and we obtain new results about continuity of the intersection of two continuous set-valued mappings (one of which has nonconvex images) and new affirmative solutions of the splitting problem for selections. We also investigate relationship between the new definition and the definition of a proximally smooth set and a smooth set.
Dynamic Planar Convex Hull Gerth Stlting Brodal ;y Riko Jacob
Riko Jacob
Dynamic Planar Convex Hull Gerth StÃ¸lting Brodal #3;;y Riko Jacob #3; BRICS z , Department the computational complexÂ ity of the dynamic convex hull problem in the planar case. We present a data structure for the neighborÂ ing points on the convex hull in O(log n) time. The extreme point queries can be used to decide
A new Primal-Dual Interior-Point Algorithm for Second-Order Cone Optimization
Roos, Kees
complexity. AMS Subject Classification: 90C22, 90C31 1 Introduction Second-order conic optimization (SOCO feasible, without mentioning y. It is well-known that SOCO problems include linear and convex quadratic programs as special cases. On the other hand, SOCO problems are special cases of semidefinite optimization
Human opinion dynamics: an inspiration to solve complex optimization problems.
Kaur, Rishemjit; Kumar, Ritesh; Bhondekar, Amol P; Kapur, Pawan
2013-01-01
Human interactions give rise to the formation of different kinds of opinions in a society. The study of formations and dynamics of opinions has been one of the most important areas in social physics. The opinion dynamics and associated social structure leads to decision making or so called opinion consensus. Opinion formation is a process of collective intelligence evolving from the integrative tendencies of social influence with the disintegrative effects of individualisation, and therefore could be exploited for developing search strategies. Here, we demonstrate that human opinion dynamics can be utilised to solve complex mathematical optimization problems. The results have been compared with a standard algorithm inspired from bird flocking behaviour and the comparison proves the efficacy of the proposed approach in general. Our investigation may open new avenues towards understanding the collective decision making. PMID:24141795
Human opinion dynamics: An inspiration to solve complex optimization problems
NASA Astrophysics Data System (ADS)
Kaur, Rishemjit; Kumar, Ritesh; Bhondekar, Amol P.; Kapur, Pawan
2013-10-01
Human interactions give rise to the formation of different kinds of opinions in a society. The study of formations and dynamics of opinions has been one of the most important areas in social physics. The opinion dynamics and associated social structure leads to decision making or so called opinion consensus. Opinion formation is a process of collective intelligence evolving from the integrative tendencies of social influence with the disintegrative effects of individualisation, and therefore could be exploited for developing search strategies. Here, we demonstrate that human opinion dynamics can be utilised to solve complex mathematical optimization problems. The results have been compared with a standard algorithm inspired from bird flocking behaviour and the comparison proves the efficacy of the proposed approach in general. Our investigation may open new avenues towards understanding the collective decision making.
Hybrid Ant Colony Optimization Using Memetic Algorithm for Traveling Salesman Problem
Haibin Duan; Xiufen Yu
2007-01-01
Ant colony optimization was originally presented under the inspiration during collective behavior study results on real ant system, and it has strong robustness and easy to combine with other methods in optimization. Although ant colony optimization for the heuristic solution of hard combinational optimization problems enjoy a rapidly growing popularity, but little research is conducted on the optimum configuration strategy
Wei Kang; Qi Gong; I. Michael Ross
We consider the optimal control of feedback linearizable dynamic systems subject to mixed state and control constraints. The optimal controller is allowed to be discontinu- ous including bang-bang control. Although the nonlinear system is assumed to be feedback linearizable, in general, the optimal control does not linearize the dynamics. The continuous optimal control problem is discretized using pseudospectral (PS) meth-
Exact and Approximate Sizes of Convex Datacubes
NASA Astrophysics Data System (ADS)
Nedjar, Sébastien
In various approaches, data cubes are pre-computed in order to efficiently answer Olap queries. The notion of data cube has been explored in various ways: iceberg cubes, range cubes, differential cubes or emerging cubes. Previously, we have introduced the concept of convex cube which generalizes all the quoted variants of cubes. More precisely, the convex cube captures all the tuples satisfying a monotone and/or antimonotone constraint combination. This paper is dedicated to a study of the convex cube size. Actually, knowing the size of such a cube even before computing it has various advantages. First of all, free space can be saved for its storage and the data warehouse administration can be improved. However the main interest of this size knowledge is to choose at best the constraints to apply in order to get a workable result. For an aided calibrating of constraints, we propose a sound characterization, based on inclusion-exclusion principle, of the exact size of convex cube as long as an upper bound which can be very quickly yielded. Moreover we adapt the nearly optimal algorithm HyperLogLog in order to provide a very good approximation of the exact size of convex cubes. Our analytical results are confirmed by experiments: the approximated size of convex cubes is really close to their exact size and can be computed quasi immediately.
A scatter learning particle swarm optimization algorithm for multimodal problems.
Ren, Zhigang; Zhang, Aimin; Wen, Changyun; Feng, Zuren
2014-07-01
Particle swarm optimization (PSO) has been proved to be an effective tool for function optimization. Its performance depends heavily on the characteristics of the employed exemplars. This necessitates considering both the fitness and the distribution of exemplars in designing PSO algorithms. Following this idea, we propose a novel PSO variant, called scatter learning PSO algorithm (SLPSOA) for multimodal problems. SLPSOA contains some new algorithmic features while following the basic framework of PSO. It constructs an exemplar pool (EP) that is composed of a certain number of relatively high-quality solutions scattered in the solution space, and requires particles to select their exemplars from EP using the roulette wheel rule. By this means, more promising solution regions can be found. In addition, SLPSOA employs Solis and Wets' algorithm as a local searcher to enhance its fine search ability in the newfound solution regions. To verify the efficiency of the proposed algorithm, we test it on a set of 16 benchmark functions and compare it with six existing typical PSO algorithms. Computational results demonstrate that SLPSOA can prevent premature convergence and produce competitive solutions. PMID:24108491
Hauck, Cory D [ORNL; Alldredge, Graham [University of Maryland; Tits, Andre [University of Maryland
2012-01-01
We present a numerical algorithm to implement entropy-based (M{sub N}) moment models in the context of a simple, linear kinetic equation for particles moving through a material slab. The closure for these models - as is the case for all entropy-based models - is derived through the solution of constrained, convex optimization problem. The algorithm has two components. The first component is a discretization of the moment equations which preserves the set of realizable moments, thereby ensuring that the optimization problem has a solution (in exact arithmetic). The discretization is a second-order kinetic scheme which uses MUSCL-type limiting in space and a strong-stability-preserving, Runge-Kutta time integrator. The second component of the algorithm is a Newton-based solver for the dual optimization problem, which uses an adaptive quadrature to evaluate integrals in the dual objective and its derivatives. The accuracy of the numerical solution to the dual problem plays a key role in the time step restriction for the kinetic scheme. We study in detail the difficulties in the dual problem that arise near the boundary of realizable moments, where quadrature formulas are less reliable and the Hessian of the dual objection function is highly ill-conditioned. Extensive numerical experiments are performed to illustrate these difficulties. In cases where the dual problem becomes 'too difficult' to solve numerically, we propose a regularization technique to artificially move moments away from the realizable boundary in a way that still preserves local particle concentrations. We present results of numerical simulations for two challenging test problems in order to quantify the characteristics of the optimization solver and to investigate when and how frequently the regularization is needed.
Methods of centers and methods of feasible directions for the solution of optimal control problems.
NASA Technical Reports Server (NTRS)
Polak, E.; Mukai, H.; Pironneau, O.
1971-01-01
Demonstration of the applicability of methods of centers and of methods of feasible directions to optimal control problems. Presented experimental results show that extensions of Frank-Wolfe (1956), Zoutendijk (1960), and Pironneau-Polak (1971) algorithms for nonlinear programming problems can be quite efficient in solving optimal control problems.
S. Kannan; S. Mary Raja Slochanal; P. Subbaraj; Narayana Prasad Padhy
2004-01-01
This paper presents the application of particle swarm optimization (PSO) technique and its variants to least-cost generation expansion planning (GEP) problem. The GEP problem is a highly constrained, combinatorial optimization problem that can be solved by complete enumeration. PSO is one of the swarm intelligence (SI) techniques, which use the group intelligence behavior along with individual intelligence to solve the
Juergen Schmidhuber
2003-01-01
An old dream of computer scientists is to build an optimally efficient universal problem solver. We show how to solve arbitrary computational problems in an optimal fashion inspired by Kurt Godel's celebrated self-referential formulas (1931). Our Godel machine's initial software includes an axiomatic description of: the Godel machine's hardware, the problem-specific utility function (such as the expected future reward of
A multilevel hybrid optimization of magnetohydrodynamic problems in double-diffusive fluid flow
M. J. Colaço; G. S. Dulikravich
2006-01-01
In this paper, we propose a multilevel approach based on our previously developed hybrid optimizer to solve double-diffusive fluid-flow problems in the presence of magnetic body forces. The problem consists in a square cavity subjected to a thermosolutal flow where the patterns of the isoconcentration lines are prescribed. Thus, the optimization problem is formulated in terms of the magnetic boundary
A Generic Global Optimization Algorithm for the Chemical and Phase Equilibrium Problem
Neumaier, Arnold
A Generic Global Optimization Algorithm for the Chemical and Phase Equilibrium Problem Ken Mc Optimization Algorithm for the Chemical and Phase Equilibrium Problem * KEN MCKINNON AND MARCEL MONGEAU ken the problem of finding the number, K, of phases present at equilibrium and their composition, in a chemical
K. R. Fowler; J. P. Reese; C. E. Kees; J. E. Dennis; C. T. Kelley; C. T. Miller; C. Audet; A. J. Booker; G. Couture; R. W. Darwin; M. W. Farthing; D. E. Finkel; J. M. Gablonsky; G. Gray; T. G. Kolda
2008-01-01
Management decisions involving groundwater supply and remediation often rely on optimization techniques to determine an effective strategy. We introduce several derivative-free sampling methods for solving constrained optimization problems that have not yet been considered in this field, and we include a genetic algorithm for completeness. Two well-documented community problems are used for illustration purposes: a groundwater supply problem and a
LSNNO, a FORTRAN subroutine for solving large-scale nonlinear network optimization problems
Philippe L. Toint; Daniel Tuyttens
1992-01-01
The implementation and testing of LSNNO, a new FORTRAN subroutine for solving large-scale nonlinear network optimization problems is described. The implemented algorithm applies the concepts of partial separability and partitioned quasi-Newton updating to high-dimensional nonlinear network optimization problems. Some numerical results on both academic and practical problems are reported.
SAT-decoding in evolutionary algorithms for discrete constrained optimization problems
Martin Lukasiewycz; Michael Glaß; Christian Haubelt; Jürgen Teich
2007-01-01
For complex optimization problems, several population-based heuristics like Multi-Objective Evolutionary Algorithms have been developed. These algorithms are aiming to deliver sufficiently good solutions in an acceptable time. However, for discrete problems that are restricted by several constraints it is mostly a hard problem to even find a single feasible solution. In these cases, the optimization heuristics typically perform poorly as
A NUMERICAL SHAPE OPTIMIZATION FRAMEWORK FOR GENERIC PROBLEMS SOLVED ON UNSTRUCTURED
Ollivier-Gooch, Carl
such as aerodynamics or heat transfer. Numerical shape optimization tools are becoming an important link in the design equations describing the physics of the optimization problems are solved on unstructured triangular meshes
Arasomwan, Martins Akugbe; Adewumi, Aderemi Oluyinka
2014-01-01
A new local search technique is proposed and used to improve the performance of particle swarm optimization algorithms by addressing the problem of premature convergence. In the proposed local search technique, a potential particle position in the solution search space is collectively constructed by a number of randomly selected particles in the swarm. The number of times the selection is made varies with the dimension of the optimization problem and each selected particle donates the value in the location of its randomly selected dimension from its personal best. After constructing the potential particle position, some local search is done around its neighbourhood in comparison with the current swarm global best position. It is then used to replace the global best particle position if it is found to be better; otherwise no replacement is made. Using some well-studied benchmark problems with low and high dimensions, numerical simulations were used to validate the performance of the improved algorithms. Comparisons were made with four different PSO variants, two of the variants implement different local search technique while the other two do not. Results show that the improved algorithms could obtain better quality solution while demonstrating better convergence velocity and precision, stability, robustness, and global-local search ability than the competing variants. PMID:24723827
Arasomwan, Martins Akugbe; Adewumi, Aderemi Oluyinka
2014-01-01
A new local search technique is proposed and used to improve the performance of particle swarm optimization algorithms by addressing the problem of premature convergence. In the proposed local search technique, a potential particle position in the solution search space is collectively constructed by a number of randomly selected particles in the swarm. The number of times the selection is made varies with the dimension of the optimization problem and each selected particle donates the value in the location of its randomly selected dimension from its personal best. After constructing the potential particle position, some local search is done around its neighbourhood in comparison with the current swarm global best position. It is then used to replace the global best particle position if it is found to be better; otherwise no replacement is made. Using some well-studied benchmark problems with low and high dimensions, numerical simulations were used to validate the performance of the improved algorithms. Comparisons were made with four different PSO variants, two of the variants implement different local search technique while the other two do not. Results show that the improved algorithms could obtain better quality solution while demonstrating better convergence velocity and precision, stability, robustness, and global-local search ability than the competing variants. PMID:24723827
ERIC Educational Resources Information Center
Hodge, Jonathan K.; Marshall, Emily; Patterson, Geoff
2010-01-01
Convexity-based measures of shape compactness provide an effective way to identify irregularities in congressional district boundaries. A low convexity coefficient may suggest that a district has been gerrymandered, or it may simply reflect irregularities in the corresponding state boundary. Furthermore, the distribution of population within a…
Tropical Convex Hull Computations
Michael Joswig
2008-01-01
This is a survey on tropical polytopes from the combinatorial point of view and with a focus on algorithms. Tropical convexity is interesting because it relates a number of combinatorial concepts including ordinary convexity, monomial ideals, subdivisions of products of simplices, matroid theory, finite metric spaces, and the tropical Grassmannians. The relationship between these topics is explained via one running
Interior Point Methods for Optimal Experimental Designs Zhaosong Lu
Lu, Zhaosong
problem with a large class of smooth convex optimality criteria, including A-, D- and pth mean criterion words: Optimal experimental design, A-criterion, c-criterion, D-criterion, pth mean criterion, interior) D-criterion (X) := log det(KT X K); (iv) pth mean criterion (X) := tr((KT X K)-p ). for some p
NASA Astrophysics Data System (ADS)
Zhang, Yunong; Wang, Jun
2002-06-01
A recurrent neural network called the dual neural network is proposed in this Letter for solving the strictly convex quadratic programming problems. Compared to other recurrent neural networks, the proposed dual network with fewer neurons can solve quadratic programming problems subject to equality, inequality, and bound constraints. The dual neural network is shown to be globally exponentially convergent to optimal solutions of quadratic programming problems. In addition, compared to neural networks containing high-order nonlinear terms, the dynamic equation of the proposed dual neural network is piecewise linear, and the network architecture is thus much simpler. The global convergence behavior of the dual neural network is demonstrated by an illustrative numerical example.
Convexity recognition of the union of polyhedra
Alberto Bemporad; Komei Fukuda; Fabio Danilo Torrisi
2001-01-01
In this paper we consider the following basic problem in polyhedral computation: Given two polyhedra in Rd, P and Q, decide whether their union is convex, and, if so, compute it. We consider the three natural specializations of the problem: (1) when the polyhedra are given by halfspaces (H-polyhedra), (2) when they are given by vertices and extreme rays (V-polyhedra),
Luo Yousong, E-mail: yluo@rmit.edu.a [RMIT University, School of Mathematical and Geospatial Sciences (Australia)
2010-06-15
In this paper we derive a necessary optimality condition for a local optimal solution of some control problems. These optimal control problems are governed by a semi-linear Vettsel boundary value problem of a linear elliptic equation. The control is applied to the state equation via the boundary and a functional of the control together with the solution of the state equation under such a control will be minimized. A constraint on the solution of the state equation is also considered.
Luo, Yousong
2009-01-01
In this paper we derive a necessary optimality condition for a local optimal solution of some control problems. These optimal control problems are governed by a semi-linear Vettsel boundary value problem of a linear elliptic equation. The control is applied to the state equation via the boundary and a functional of the control together with the solution of the state equation under such a control will be minimized. A constrain on the solution of the state equation is also considered.
Asymptotics of the solution to a singularly perturbed linear-quadratic optimal control problem
NASA Astrophysics Data System (ADS)
Kalinin, A. I.; Lavrinovich, L. I.
2015-02-01
The optimization of a transient process in a linear singularly perturbed system is considered. The goal is to find an admissible control that minimizes an integral quadratic cost functional. Asymptotic approximations to optimal open-loop and feedback controls are constructed for this problem. The basic advantage of the algorithms proposed is that the original optimal control problem splits into two unperturbed problems of lower dimension.
A Particle Swarm Optimization Algorithm with Path Relinking for the Location Routing Problem
Yannis Marinakis; Magdalene Marinaki
2008-01-01
This paper introduces a new hybrid algorithmic nature inspired approach based on particle swarm optimization, for solving\\u000a successfully one of the most popular logistics management problems, the location routing problem (LRP). The proposed algorithm\\u000a for the solution of the location routing problem, the hybrid particle swarm optimization (HybPSO-LRP), combines a particle\\u000a swarm optimization (PSO) algorithm, the multiple phase neighborhood search
Effectiveness-Equity Models for Facility Location Problems on Tree ...
2013-01-19
an efficient set of solutions to these problems, analyze the complexity of the ... as an equity measure, Ogryzcak [31] who uses a multi objective goal program- .... optimization problems is to either generate the entire set of efficient solutions to the ..... linear, convex, with changing slope at each characterizing point on the edge.
Advancement and analysis of Gauss pseudospectral transcription for optimal control problems
Huntington, Geoffrey Todd, 1979-
2007-01-01
As optimal control problems become increasingly complex, innovative numerical methods are needed to solve them. Direct transcription methods, and in particular, methods involving orthogonal collocation have become quite ...
Finite element approximation of an optimal control problem for the von Karman equations
NASA Technical Reports Server (NTRS)
Hou, L. Steven; Turner, James C.
1994-01-01
This paper is concerned with optimal control problems for the von Karman equations with distributed controls. We first show that optimal solutions exist. We then show that Lagrange multipliers may be used to enforce the constraints and derive an optimality system from which optimal states and controls may be deduced. Finally we define finite element approximations of solutions for the optimality system and derive error estimates for the approximations.
A Memetic Cooperative Optimization Schema and Its Application to the Tool Switching Problem
Jhon Edgar Amaya; Carlos Cotta; Antonio José Fernández Leiva
2010-01-01
\\u000a This paper describes a generic (meta-)cooperative optimization schema in which several agents endowed with an optimization\\u000a technique (whose nature is not initially restricted) cooperate to solve an optimization problem. These agents can use a wide\\u000a set of optimization techniques, including local search, population-based methods, and hybrids thereof, hence featuring multilevel\\u000a hybridization. This optimization approach is here deployed on the Tool
Problem Set 6 SOLUTION -Do Not Distribute
Chen, Yiling
with the convex hull will produce an integer solution that is optimal for the IP. Since we can quickly solve LPsProblem Set 6 SOLUTION - Do Not Distribute More IP: Branching and Bounding, Formulating, Tightening in your submission. · Readings: Jensen and Bard, sections 8.18.3. Goals · Practice solving integer
ON THE RECONSTRUCTION OF CONVEX SETS FROM RANDOM NORMAL MEASUREMENTS
Paris-Sud XI, UniversitÃ© de
ON THE RECONSTRUCTION OF CONVEX SETS FROM RANDOM NORMAL MEASUREMENTS HIBA ABDALLAH AND QUENTIN M random locations uniformly distributed along the boundary of our convex set. Given a desired Hausdorff-understood topic in compu- tational geometry. The input of this problem is a finite set of points P measured on (or
Approximating extreme points of infinite dimensional convex sets
Smith, Robert L.
Approximating extreme points of infinite dimensional convex sets William P. Cross H. Edwin Romeijn a continu- ous concave function over a compact convex set in IRn is attained at an extreme point and characterizing infinite dimensional extreme points thus becomes an important problem. Consider now an infinite
Aircraft Routing -A Global Optimization Problem Michael C Bartholomew-Biggs
Neumaier, Arnold
Aircraft Routing - A Global Optimization Problem Michael C Bartholomew-Biggs matqmb@herts.ac.uk University of Hertfordshire, England This paper deals with the problem of calculating aircraft flight paths
Robust control of quantum gates via sequential convex programming
NASA Astrophysics Data System (ADS)
Kosut, Robert L.; Grace, Matthew D.; Brif, Constantin
2013-11-01
Resource trade-offs can often be established by solving an appropriate robust optimization problem for a variety of scenarios involving constraints on optimization variables and uncertainties. Using an approach based on sequential convex programming, we demonstrate that quantum gate transformations can be made substantially robust against uncertainties while simultaneously using limited resources of control amplitude and bandwidth. Achieving such a high degree of robustness requires a quantitative model that specifies the range and character of the uncertainties. Using a model of a controlled one-qubit system for illustrative simulations, we identify robust control fields for a universal gate set and explore the trade-off between the worst-case gate fidelity and the field fluence. Our results demonstrate that, even for this simple model, there exists a rich variety of control design possibilities. In addition, we study the effect of noise represented by a stochastic uncertainty model.
NASA Astrophysics Data System (ADS)
Lewis, Adrian S.; Overton, Michael L.
Optimization problems involving eigenvalues arise in many different mathematical disciplines. This article is divided into two parts. Part I gives a historical account of the development of the field. We discuss various applications that have been especially influential, from structural analysis to combinatorial optimization, and we survey algorithmic developments, including the recent advance of interior-point methods for a specific problem class: semidefinite programming. In Part II we primarily address optimization of convex functions of eigenvalues of symmetric matrices subject to linear constraints. We derive a fairly complete mathematical theory, some of it classical and some of it new. Using the elegant language of conjugate duality theory, we highlight the parallels between the analysis of invariant matrix norms and weakly invariant convex matrix functions. We then restrict our attention further to linear and semidefinite programming, emphasizing the parallel duality theory and comparing primal-dual interior-point methods for the two problem classes. The final section presents some apparently new variational results about eigenvalues of nonsymmetric matrices, unifying known characterizations of the spectral abscissa (related to Lyapunov theory) and the spectral radius (as an infimum of matrix norms).
Optimal experimental design applied to DC resistivity problems
Coles, Darrell Ardon, 1971-
2008-01-01
The systematic design of experiments to optimally query physical systems through manipulation of the data acquisition strategy is termed optimal experimental design (OED). This dissertation introduces the state-of-the-art ...
A Note on the Optimal Single Copy Measurement for the Hidden Subgroup Problem
Bacon, Dave
2007-01-01
The optimization of measurements for the state distinction problem has recently been applied to the theory of quantum algorithms with considerable successes, including efficient new quantum algorithms for the non-abelian hidden subgroup problem. Previous work has identified the optimal single copy measurement for the hidden subgroup problem over abelian groups as well as for the non-abelian problem in the setting where the subgroups are restricted to be all conjugate to each other. Here we describe the optimal single copy measurement for the hidden subgroup problem when all of the subgroups of the group are given with equal a priori probability. The optimal measurement is seen to be a hybrid of the two previously discovered single copy optimal measurements for the hidden subgroup problem.
Computationally Efficient Optimal Solutions to the Lot-Sizing Problem in Multistage Assembly Systems
Panayotis Afentakis; Bezalel Gavish; Uday Karmarkar
1984-01-01
The scheduling of lot sizes in multistage production environments is a fundamental problem in many Material Requirements Planning Systems. Many heuristics have been suggested for this problem with varying degrees of success. Research to date on obtaining optimal solutions has been limited to small problems. This paper presents a new formulation of the lot-sizing problem in multistage assembly systems which
A Cascade Optimization Strategy for Solution of Difficult Multidisciplinary Design Problems
NASA Technical Reports Server (NTRS)
Patnaik, Surya N.; Coroneos, Rula M.; Hopkins, Dale A.; Berke, Laszlo
1996-01-01
A research project to comparatively evaluate 10 nonlinear optimization algorithms was recently completed. A conclusion was that no single optimizer could successfully solve all 40 problems in the test bed, even though most optimizers successfully solved at least one-third of the problems. We realized that improved search directions and step lengths, available in the 10 optimizers compared, were not likely to alleviate the convergence difficulties. For the solution of those difficult problems we have devised an alternative approach called cascade optimization strategy. The cascade strategy uses several optimizers, one followed by another in a specified sequence, to solve a problem. A pseudorandom scheme perturbs design variables between the optimizers. The cascade strategy has been tested successfully in the design of supersonic and subsonic aircraft configurations and air-breathing engines for high-speed civil transport applications. These problems could not be successfully solved by an individual optimizer. The cascade optimization strategy, however, generated feasible optimum solutions for both aircraft and engine problems. This paper presents the cascade strategy and solutions to a number of these problems.
NASA Astrophysics Data System (ADS)
Bera, Sasadhar; Mukherjee, Indrajit
2010-10-01
Ensuring quality of a product is rarely based on observations of a single quality characteristic. Generally, it is based on observations of family of properties, so-called `multiple responses'. These multiple responses are often interacting and are measured in variety of units. Due to presence of interaction(s), overall optimal conditions for all the responses rarely result from isolated optimal condition of individual response. Conventional optimization techniques, such as design of experiment, linear and nonlinear programmings are generally recommended for single response optimization problems. Applying any of these techniques for multiple response optimization problem may lead to unnecessary simplification of the real problem with several restrictive model assumptions. In addition, engineering judgements or subjective ways of decision making may play an important role to apply some of these conventional techniques. In this context, a synergistic approach of desirability functions and metaheuristic technique is a viable alternative to handle multiple response optimization problems. Metaheuristics, such as simulated annealing (SA) and particle swarm optimization (PSO), have shown immense success to solve various discrete and continuous single response optimization problems. Instigated by those successful applications, this chapter assesses the potential of a Nelder-Mead simplex-based SA (SIMSA) and PSO to resolve varied multiple response optimization problems. The computational results clearly indicate the superiority of PSO over SIMSA for the selected problems.
Random Convex Hulls and Extreme Value Statistics
Satya N. Majumdar; Alain Comtet; Julien Randon-Furling
2009-12-03
In this paper we study the statistical properties of convex hulls of $N$ random points in a plane chosen according to a given distribution. The points may be chosen independently or they may be correlated. After a non-exhaustive survey of the somewhat sporadic literature and diverse methods used in the random convex hull problem, we present a unifying approach, based on the notion of support function of a closed curve and the associated Cauchy's formulae, that allows us to compute exactly the mean perimeter and the mean area enclosed by the convex polygon both in case of independent as well as correlated points. Our method demonstrates a beautiful link between the random convex hull problem and the subject of extreme value statistics. As an example of correlated points, we study here in detail the case when the points represent the vertices of $n$ independent random walks. In the continuum time limit this reduces to $n$ independent planar Brownian trajectories for which we compute exactly, for all $n$, the mean perimeter and the mean area of their global convex hull. Our results have relevant applications in ecology in estimating the home range of a herd of animals. Some of these results were announced recently in a short communication [Phys. Rev. Lett. {\\bf 103}, 140602 (2009)].
Random Convex Hulls and Extreme Value Statistics
NASA Astrophysics Data System (ADS)
Majumdar, Satya N.; Comtet, Alain; Randon-Furling, Julien
2009-12-01
In this paper we study the statistical properties of convex hulls of N random points in a plane chosen according to a given distribution. The points may be chosen independently or they may be correlated. After a non-exhaustive survey of the somewhat sporadic literature and diverse methods used in the random convex hull problem, we present a unifying approach, based on the notion of support function of a closed curve and the associated Cauchy’s formulae, that allows us to compute exactly the mean perimeter and the mean area enclosed by the convex polygon both in case of independent as well as correlated points. Our method demonstrates a beautiful link between the random convex hull problem and the subject of extreme value statistics. As an example of correlated points, we study here in detail the case when the points represent the vertices of n independent random walks. In the continuum time limit this reduces to n independent planar Brownian trajectories for which we compute exactly, for all n, the mean perimeter and the mean area of their global convex hull. Our results have relevant applications in ecology in estimating the home range of a herd of animals. Some of these results were announced recently in a short communication [Phys. Rev. Lett. 103:140602, 2009].
Capacity Optimizing Power Allocation in Interference Channels
Shiyang Deng; Tobias Weber; Andreas Ahrens
2009-01-01
The interference channel is an essential model in both wireline and wireless communication systems. This article addresses transmit power allocation in interference channels with total transmit power constraint. The optimum power allocation maximizing the sum rate in two user interference channels can be derived analytically. However, the non-convexity of the optimization problem makes it prohibitively complex to obtain the optimum
Optimal ecosystem management with structural dynamics
Rui Pedro Mota; Tiago Domingos
2004-01-01
We address the problem of optimal management of a self organizing ecosystem along ecological succession. A dynamic carrying capacity is interpreted as depicting the dynamics of habitat creation and occupation along ecological succession. The ecosystem may have three growth modes: pure compensation (concave ecosystem regeneration function), depensation (convex-concave regeneration function) and critical depensation (additionally having negative growth rates for low
Introduction to Stochastic Optimization Part 4: Multi-stage decision problems
Pflug, Georg
Introduction to Stochastic Optimization Part 4: Multi-stage decision problems Georg Ch. Pflug April 23, 2009 Georg Ch. Pflug Introduction to Stochastic Optimization Part 4: Multi-stage decision #12;TheT-1. Georg Ch. Pflug Introduction to Stochastic Optimization Part 4: Multi-stage decision #12;Example
Chandrasekaran, Venkat
The structural properties of graphs are usually characterized in terms of invariants, which are functions of graphs that do not depend on the labeling of the nodes. In this paper we study convex graph invariants, which are ...
A Honey-bee Mating Optimization Algorithm for Educational Timetabling Problems
Qu, Rong
1 A Honey-bee Mating Optimization Algorithm for Educational Timetabling Problems Nasser R. Sabar1 of the Honey-bee Mating Optimization Algorithm for solv- ing educational timetabling problems. The honey-bee algorithm is a nature inspired algorithm which sim- ulates the process of real honey-bees mating
Existence of a solution for complete least squares optimal shape problems
Dana M. Bedivan
1997-01-01
We show the existence of a solution for the complete least squares formulation associated with an elliptic optimal shape problem which appears in semiconductor device theory. The traditional approach for optimal shape problems is to minimize a cost functional subject to a number of governing equations. In the complete least squares formulation, which is considered in this paper, the cost
Tröltzsch, Fredi
On Some Optimal Control Problems for Electric Circuits Kristof Altmann, Simon Stingelin, and Fredi to be expected in such processes, we study here simplified models for electrical circuits based on ordinary's equations. We shall study different types of electrical circuits and associated optimal control problems
Optimal control as a regularization method for ill-posed problems
Soatto, Stefano
Optimal control as a regularization method for ill-posed problems Stefan Kindermann, Carmeliza,navasca}@math.ucla.edu Abstract. We describe two regularization techniques based on optimal control for solving two types of ill- ization. Keywords: Riccati equation, ill-posed problems, regularization 1. Introduction In this work we
Second Order Sufficient Optimality Conditions for a Control Problem with Continuous and Bang-Bang
Maurer, Helmut
Second Order Sufficient Optimality Conditions for a Control Problem with Continuous and Bang-Bang@math.uni-muenster.de Abstract Second order sufficient optimality conditions for bang-bang con- trol problems in a very general: a continuous unconstrained control appear- ing nonlinearly and a bang-bang control appearing linearly
Solving Continuous-Time Optimal-Control Problems with a Spreadsheet.
ERIC Educational Resources Information Center
Naevdal, Eric
2003-01-01
Explains how optimal control problems can be solved with a spreadsheet, such as Microsoft Excel. Suggests the method can be used by students, teachers, and researchers as a tool to find numerical solutions for optimal control problems. Provides several examples that range from simple to advanced. (JEH)
Optimal Control Study of Interception Problems Prof. Hugh H.T. Liu
Liu, Hugh H.T.
vehicle is flying in a pre-defined trajectory. The problem state- ment is to find the optimal solutionOptimal Control Study of Interception Problems Prof. Hugh H.T. Liu 30-Jul-2007 The "Flight Systems and Control" research laboratory at the UTIAS is in- terested in cooperative control and formation flight
Exact slow–fast decomposition of the nonlinear singularly perturbed optimal control problem
E. Fridman
2000-01-01
We study the infinite horizon nonlinear quadratic optimal control problem for a singularly perturbed system, which is nonlinear in both, the slow and the fast variables. It is known that the optimal controller for such problem can be designed by finding a special invariant manifold of the corresponding Hamiltonian system. We obtain exact slow–fast decomposition of the Hamiltonian system and
Exact slow{fast decomposition of the nonlinear singularly perturbed optimal control problem
E. Fridman
2000-01-01
We study the innite horizon nonlinear quadratic optimal control problem for a singularly perturbed system, which is nonlinear in both, the slow and the fast variables. It is known that the optimal controller for such problem can be designed by nding a special invariant manifold of the corresponding Hamiltonian system. We obtain exact slow{fast decomposition of the Hamiltonian system and
Cláudio M. N. A. Pereira; Celso M. F. Lapa
2003-01-01
This work extends the research related to genetic algorithms (GA) in core design optimization problems, which basic investigations were presented in previous work. Here we explore the use of the Island Genetic Algorithm (IGA), a coarse-grained parallel GA model, comparing its performance to that obtained by the application of a traditional non-parallel GA. The optimization problem consists on adjusting several
David Echeverría Ciaurri; O. J. Isebor; Louis J. Durlofsky
2010-01-01
Oil production optimization involves the determination of optimum well controls (e.g., well pressures, injection rates) to maximize an objective function such as cumulative oil production or net present value. In practice, this problem additionally requires the satisfaction of physical and economic constraints. Thus, the overall problem represents a challenging nonlinearly constrained optimization. The cost function and constraints involve calls to
Particle swarm optimization algorithm for single machine total weighted tardiness problem
M. Fatih Tasgetiren; M. Sevkli; Yun-Chia Liang; Gunes Gencyilmaz
2004-01-01
In This work we present a particle swarm optimization algorithm to solve the single machine total weighted tardiness problem. A heuristic rule, the smallest position value (SPV) rule, is developed to enable the continuous particle swarm optimization algorithm to be applied to all classes of sequencing problems, which are NP-hard in the literature. A simple but very efficient local search
Using quantum-behaved particle swarm optimization algorithm to solve non-linear programming problems
Jun Sun; Jing Liu; Wenbo Xu
2007-01-01
In this paper, we focus on solving non-linear programming (NLP) problems using quantum-behaved particle swarm optimization (QPSO). After a brief introduction to the original particle swarm optimization (PSO), we describe the origin and development of QPSO, and the penalty function method for constrained NLP problems. The performance of QPSO is tested on some unconstrained and constrained benchmark functions and compared
Alakananda Bhattacharya; Amit Konar; Swagatam Das; Crina Grosan; Ajith Abraham
2008-01-01
Hardware\\/software partitioning is a crucial problem in embedded system design. In this paper, we provide an alternative approach to solve this problem using Particle Swarm Optimization (PSO) algorithm. Performance analysis of the proposed scheme with Integer Linear Programming, Genetic Algorithm and Ant Colony Optimization technique has been compared using standard benchmark datasets, and the computer simulations reveal that the proposed
Gary Chartrand; John Frederick Fink; Ping Zhang
2002-01-01
For vertices u and v in an oriented graph D, the closed interval I[u,v] consists of u and v together with all vertices lying in a u?v geodesic or v?u geodesic in D. For S?V(D), I[S] is the union of all closed intervals I[u,v] with u,v?S. A set S is convex if I[S]=S. The convexity number con(D) is the maximum
Heinkenschloss, Matthias (Rice University, Houston, TX); Bartlett, Roscoe Ainsworth; Van Bloeman Waanders, Paul; Ridzal, Denis (Rice University, Houston, TX)
2005-04-01
We present an optimization-level domain decomposition (DD) preconditioner for the solution of advection dominated elliptic linear-quadratic optimal control problems. The DD preconditioner is based on a decomposition of the optimality conditions for the elliptic linear-quadratic optimal control problem into smaller subdomain optimality conditions with Dirichlet boundary conditions for the states and the adjoints on the subdomain interfaces. These subdomain optimality conditions are coupled through Robin transmission conditions for the states and the adjoints. The parameters in the Robin transmission condition depend on the advection. This decomposition leads to a Schur complement system in which the unknowns are the state and adjoint variables on the subdomain interfaces. The Schur complement operator is the sum of subdomain Schur complement operators, the application of which is shown to correspond to the solution of subdomain optimal control problems, which are essentially smaller copies of the original optimal control problem. We show that, under suitable conditions, the application of the inverse of the subdomain Schur complement operators requires the solution of a subdomain elliptic linear-quadratic optimal control problem with Robin boundary conditions for the state. Numerical tests for problems with distributed and with boundary control show that the dependence of the preconditioners on mesh size and subdomain size is comparable to its counterpart applied to a single advection dominated equation. These tests also show that the preconditioners are insensitive to the size of the control regularization parameter.
Modeling and optimization of the capacity allocation problem with constraints
Abdellah Idrissi; Chu Min Li
2006-01-01
The Constraint Satisfaction Problem (CSP) is proven more and more promising to model and to solve a great number of real problems. A lot of approaches using constraint reasoning have proposed to solve search problems. In this paper, we propose a modeling of Capacity Allocation Problem of an airport (CAP) and of its fixes (FCAP) in form of a Constraint
Combinatorial Optimization Solutions for the Maximum Quartet Consistency Problem
Antonio Morgado; Joao Marques-Silva
2008-01-01
Given a set of taxa S and a complete set of quartet topologies Q over S, the problem of determining a phylogeny that satisfies the maximum number of topologies is called the Maximum Quartet Consis- tency (MQC) problem. The MQC problem is an NP-problem. MQC has been solved both heuristically and exactly. Exact solutions for MQC include Constraint Programming, Answer
1990-01-01
Practical engineering application can often be formulated in the form of a constrained optimization problem. There are several solution algorithms for solving a constrained optimization problem. One approach is to convert a constrained problem into a series of unconstrained problems. Furthermore, unconstrained solution algorithms can be used as part of the constrained solution algorithms. Structural optimization is an iterative process
Generalized vector calculus on convex domain
NASA Astrophysics Data System (ADS)
Agrawal, Om P.; Xu, Yufeng
2015-06-01
In this paper, we apply recently proposed generalized integral and differential operators to develop generalized vector calculus and generalized variational calculus for problems defined over a convex domain. In particular, we present some generalization of Green's and Gauss divergence theorems involving some new operators, and apply these theorems to generalized variational calculus. For fractional power kernels, the formulation leads to fractional vector calculus and fractional variational calculus for problems defined over a convex domain. In special cases, when certain parameters take integer values, we obtain formulations for integer order problems. Two examples are presented to demonstrate applications of the generalized variational calculus which utilize the generalized vector calculus developed in the paper. The first example leads to a generalized partial differential equation and the second example leads to a generalized eigenvalue problem, both in two dimensional convex domains. We solve the generalized partial differential equation by using polynomial approximation. A special case of the second example is a generalized isoperimetric problem. We find an approximate solution to this problem. Many physical problems containing integer order integrals and derivatives are defined over arbitrary domains. We speculate that future problems containing fractional and generalized integrals and derivatives in fractional mechanics will be defined over arbitrary domains, and therefore, a general variational calculus incorporating a general vector calculus will be needed for these problems. This research is our first attempt in that direction.
On Convex Relaxations for Quadratically Constrained Quadratic ...
2010-07-28
Jul 28, 2010 ... relaxation of the convex hull of the quadratic form that imposes ... of QCQP problems, corresponding to planar circle-packing (or ..... the algorithm of [18], but still required up to 104 CPU seconds on a 2.7 GHz Linux-based.
Methodological Problems in Evolutionary Biology. XI. Optimal Foraging Theory Revisited
Wim J. van der Steen
1998-01-01
Optimality theory, particularly optimal foraging theory (OFT), has spurned controversy over decades. I argue that the controversy results from conceptual pitfalls. The focus in this article is on pitfalls underlying the concept of constraint. Constraints in OFT models are a means to distinguish between possible and impossible behaviours. I argue that the seemingly innocuous notion of (im)possibility is tricky. It
Optimal experimental design and some related control problems
Luc Pronzato
2008-01-01
This paper traces the strong relations between experimental design and control, such as the use of optimal inputs to obtain precise parameter estimation in dynamical systems and the introduction of suitably designed perturbations in adaptive control. The mathematical background of optimal experimental design is briefly presented, and the role of experimental design in the asymptotic properties of estimators is emphasized.
A fast Ant Colony Optimization for traveling salesman problem
Shih-Pang Tseng; Chun-Wei Tsai; Ming-Chao Chiang; Chu-Sing Yang
2010-01-01
In this paper, we present an efficient method for speeding up Ant Colony Optimization (ACO), called Pattern Reduction Enhanced Ant Colony Optimization (PREACO). The proposed algorithm is motivated by the observation that many of the computations of ACO on its convergence process are essentially redundant and thus can be eliminated to reduce its computation time. To evaluate the performance of
Solving Multiobjective Optimization Problems Using an Artificial Immune System
Carlos A. Coello Coello; Nareli Cruz Cortés
2005-01-01
In this paper, we propose an algorithm to solve multiobjective optimization prob- lems (either constrained or unconstrained) using the clonal selection principle. Our approach is compared with respect to three other algorithms that are representative of the state-of-the- art in evolutionary multiobjective optimization. For our comparative study, three metrics are adopted and graphical comparisons with respect to the true Pareto
1 INTRODUCTION We consider the optimization problem of distrib-
Paris-Sud XI, Université de
, unexpected failures or stop- pages of the generation units, to variability in the main power supply a multi-objective optimization (MOO) search engine based on NSGA-II (Deb et al., 2002). Pareto optimal- ously minimize the expected global cost (ECg) and expected energy not supplied (EENS). 2 DISTRIBUTED
Ya. O. Grudo; A. I. Kalinin
2008-01-01
The time-optimal control problem for a nonlinear singularly perturbed system with multidimensional controls bounded in the\\u000a Euclidean norm is considered. An algorithm for constructing asymptotic approximations to its solution is proposed. The main\\u000a advantage of the algorithm is that the original optimal control problem decomposes into two unperturbed problems of lower\\u000a dimensions.
Müller, Stefan; Regensburger, Georg; Steuer, Ralf
2014-04-21
The survival and proliferation of cells and organisms require a highly coordinated allocation of cellular resources to ensure the efficient synthesis of cellular components. In particular, the total enzymatic capacity for cellular metabolism is limited by finite resources that are shared between all enzymes, such as cytosolic space, energy expenditure for amino-acid synthesis, or micro-nutrients. While extensive work has been done to study constrained optimization problems based only on stoichiometric information, mathematical results that characterize the optimal flux in kinetic metabolic networks are still scarce. Here, we study constrained enzyme allocation problems with general kinetics, using the theory of oriented matroids. We give a rigorous proof for the fact that optimal solutions of the non-linear optimization problem are elementary flux modes. This finding has significant consequences for our understanding of optimality in metabolic networks as well as for the identification of metabolic switches and the computation of optimal flux distributions in kinetic metabolic networks. PMID:24295962
Discrete bat algorithm for optimal problem of permutation flow shop scheduling.
Luo, Qifang; Zhou, Yongquan; Xie, Jian; Ma, Mingzhi; Li, Liangliang
2014-01-01
A discrete bat algorithm (DBA) is proposed for optimal permutation flow shop scheduling problem (PFSP). Firstly, the discrete bat algorithm is constructed based on the idea of basic bat algorithm, which divide whole scheduling problem into many subscheduling problems and then NEH heuristic be introduced to solve subscheduling problem. Secondly, some subsequences are operated with certain probability in the pulse emission and loudness phases. An intensive virtual population neighborhood search is integrated into the discrete bat algorithm to further improve the performance. Finally, the experimental results show the suitability and efficiency of the present discrete bat algorithm for optimal permutation flow shop scheduling problem. PMID:25243220
Discrete Bat Algorithm for Optimal Problem of Permutation Flow Shop Scheduling
Luo, Qifang; Zhou, Yongquan; Xie, Jian; Ma, Mingzhi; Li, Liangliang
2014-01-01
A discrete bat algorithm (DBA) is proposed for optimal permutation flow shop scheduling problem (PFSP). Firstly, the discrete bat algorithm is constructed based on the idea of basic bat algorithm, which divide whole scheduling problem into many subscheduling problems and then NEH heuristic be introduced to solve subscheduling problem. Secondly, some subsequences are operated with certain probability in the pulse emission and loudness phases. An intensive virtual population neighborhood search is integrated into the discrete bat algorithm to further improve the performance. Finally, the experimental results show the suitability and efficiency of the present discrete bat algorithm for optimal permutation flow shop scheduling problem. PMID:25243220
The Open Problems Project edited by Erik D. Demaine Joseph S. B. Mitchell
O'Rourke, Joseph
(Problem 4) . Vertical Decompositions in R d (Problem 19) convex hulls: . Dynamic Planar Convex Hull (Problem 12) . Dynamic Planar Nearest Neighbors (Problem 63) . Inplace Convex Hull of a Simple Polygonal Partition Size (Problem 14) . Dynamic Planar Convex Hull (Problem 12) . Dynamic Planar Nearest Neighbors
The Open Problems Project edited by Erik D. Demaine Joseph S. B. Mitchell
O'Rourke, Joseph
Decompositions in Rd (Problem 19) convex hulls: Â· Dynamic Planar Convex Hull (Problem 12) Â· Dynamic Planar Planar Convex Hull (Problem 12) Â· Dynamic Planar Nearest Neighbors (Problem 63) Â· Point Location in 3D Nearest Neighbors (Problem 63) Â· Inplace Convex Hull of a Simple Polygonal Chain (Problem 36) Â· Output
A Collection of Challenging Optimization Problems in Science, Engineering and Economics
Mehta, Dhagash
2015-01-01
Function optimization and finding simultaneous solutions of a system of nonlinear equations (SNE) are two closely related and important optimization problems. However, unlike in the case of function optimization in which one is required to find the global minimum and sometimes local minima, a database of challenging SNEs where one is required to find stationary points (extrama and saddle points) is not readily available. In this article, we initiate building such a database of important SNE (which also includes related function optimization problems), arising from Science, Engineering and Economics. After providing a short review of the most commonly used mathematical and computational approaches to find solutions of such systems, we provide a preliminary list of challenging problems by writing the Mathematical formulation down, briefly explaning the origin and importance of the problem and giving a short account on the currently known results, for each of the problems. We anticipate that this database will n...
Parallel Multi-Swarm Optimization Framework for Search Problems in Water Distribution Systems
Parallel Multi-Swarm Optimization Framework for Search Problems in Water Distribution Systems Sarat concurrent particle swarms is developed and applied to water distribution problems. Details of the enabling characterization problems for two water distribution networks with 1,834 and 12,457 nodes respectively. 1
New evolutionary genetic algorithms for NP-complete combinatorial optimization problems
Fam Quang Bac; V. L. Perov
1993-01-01
Evolutionary genetic algorithms have been proposed to solve NP-complete combinatorial optimization problems. A new crossover operator based on group theory has been created. Computational processes motivated by proposed evolutionary genetic algorithms were described as stochastic processes, using population dynamics and interactive markovian chains. The proposed algorithms were used in solving flowshop problems and an asymmetric traveling salesman problem. The experimental
A descriptor system approach to nonlinear singularly perturbed optimal control problem
Emilia Fridman
2001-01-01
This paper considers the infinite horizon nonlinear quadratic optimal control problem for a singularly perturbed system which is nonlinear in both, the slow and the fast variables. The relationship between this problem and the analogous one for a descriptor system is investigated. Parameter-independent controllers are constructed that solve the problem for the descriptor system and lead the full-order system to
A Global Optimization Method for the Molecular Replacement Problem in X-ray Crystallography
Zhang, Yin
A Global Optimization Method for the Molecular Replacement Problem in X-ray Crystallography #3-ray crystallography, from which the molecular replacement (MR) problem often arises as a critical step. The MR problem will produce calculated intensities closest to those observed from an X-ray crystallography experiment
Shengxiang Yang; Xin Yao
2005-01-01
Evolutionary algorithms have been widely used for stationary optimization problems. However, the environments of real world problems are often dynamic. This seriously challenges traditional evolutionary algorithms. In this paper, the application of population-based incremental learning (PBIL) algorithms, a class of evolutionary algorithms, for dynamic problems is investigated. Inspired by the complementarity mechanism in nature a Dual PBIL is proposed, which
A discrete particle swarm optimization algorithm for the generalized traveling salesman problem
Mehmet Fatih Tasgetiren; Ponnuthurai N. Suganthan; Quan-qe Pan
2007-01-01
Dividing the set of nodes into clusters in the well-known traveling salesman problem results in the generalized traveling salesman problem which seeking a tour with minimum cost passing through only a single node from each cluster. In this paper, a discrete particle swarm optimization is presented to solve the problem on a set of benchmark instances. The discrete particle swarm
How to Solve a Semi-infinite Optimization Problem
2012-03-27
Mar 27, 2012 ... Institute of Operations Research, Karlsruhe Institute of Technology (KIT), Germany ...... [12] F.H. Clarke, Optimization and Nonsmooth Analysis, Wiley, New .... [54] W. Krabs, On time-minimal heating or cooling of a ball, in: Inter-.
Mittal, Shashi, Ph. D. Massachusetts Institute of Technology
2011-01-01
This thesis presents efficient algorithms that give optimal or near-optimal solutions for problems with non-linear objective functions that arise in discrete, continuous and robust optimization. First, we present a general ...
Bukhsh, Waqquas Ahmed
2014-07-01
Optimization plays a central role in the control and operation of electricity power networks. In this thesis we focus on two very important optimization problems in power systems. The first is the optimal power flow ...
A Numerical Method to solve Optimal Transport Problems with Coulomb Cost
Jean-David Benamou; Guillaume Carlier; Luca Nenna
2015-05-07
In this paper, we present a numerical method, based on iterative Bregman projections, to solve the optimal transport problem with Coulomb cost. This is related to the strong interaction limit of Density Functional Theory. The first idea is to introduce an entropic regularization of the Kantorovich formulation of the Optimal Transport problem. The regularized problem then corresponds to the projection of a vector on the intersection of the constraints with respect to the Kullback-Leibler distance. Iterative Bregman projections on each marginal constraint are explicit which enables us to approximate the optimal transport plan. We validate the numerical method against analytical test cases.
Ball and Spindle Convexity with respect to a Convex Body
Lángi, Zsolt; Talata, István
2011-01-01
Let $C\\subset {\\mathbb R}^n$ be a convex body. We introduce two notions of convexity associated to C. A set $K$ is $C$-\\emph{ball convex} if it is the intersection of translates of $C$, or it is either $\\emptyset$, or ${\\mathbb R}^n$. The $C$-ball convex hull of two points is called a $C$-spindle. $K$ is $C$-\\emph{spindle convex} if it contains the $C$-spindle of any pair of its points. We investigate how some fundamental properties of conventional convex sets can be adapted to $C$-spindle convex and $C$-ball convex sets. We study separation properties and Carath\\'eodory numbers of these two convexity structures. We investigate the basic properties of arc-distance, a quantity defined by a centrally symmetric planar disc $C$, which is the length of an arc of a translate of $C$, measured in the $C$-norm, that connects two points. Then we characterize those $n$-dimensional convex bodies $C$ for which every $C$-ball convex set is the $C$-ball convex hull of finitely many points. Finally, we obtain a stability res...
Continuous Blooming of Convex Polyhedra
Demaine, Erik D.
We construct the first two continuous bloomings of all convex polyhedra. First, the source unfolding can be continuously bloomed. Second, any unfolding of a convex polyhedron can be refined (further cut, by a linear number ...
Newton's method for large bound-constrained optimization problems.
Lin, C.-J.; More, J. J.; Mathematics and Computer Science
1999-01-01
We analyze a trust region version of Newton's method for bound-constrained problems. Our approach relies on the geometry of the feasible set, not on the particular representation in terms of constraints. The convergence theory holds for linearly constrained problems and yields global and superlinear convergence without assuming either strict complementarity or linear independence of the active constraints. We also show that the convergence theory leads to an efficient implementation for large bound-constrained problems.
F. Holik; C. Massri; N. Ciancaglini
2010-08-24
In this work we study the convex set of quantum states from a quantum logical point of view. We consider an algebraic structure based on the convex subsets of this set. The relationship of this algebraic structure with the lattice of propositions of quantum logic is shown. This new structure is suitable for the study of compound systems and shows new differences between quantum and classical mechanics. This differences are linked to the nontrivial correlations which appear when quantum systems interact. They are reflected in the new propositional structure, and do not have a classical analogue. This approach is also suitable for an algebraic characterization of entanglement.
Convexity Recognition of the Union of Polyhedra
Alberto Bemporad; Fabio D. Torrisi; Komei Fukuda
2000-01-01
In this paper we consider the following basic problem in polyhedral computation:Given two polyhedra in Rd, P and Q, decide whether their union is convex, and, if so,compute it. We consider the three natural specializations of the problem: (1) when thepolyhedra are given by halfspaces (H-polyhedra) (2) when they are given by verticesand extreme rays (V-polyhedra) (3) when both H-
Solving the optimal attention allocation problem in manual control
NASA Technical Reports Server (NTRS)
Kleinman, D. L.
1976-01-01
Within the context of the optimal control model of human response, analytic expressions for the gradients of closed-loop performance metrics with respect to human operator attention allocation are derived. These derivatives serve as the basis for a gradient algorithm that determines the optimal attention that a human should allocate among several display indicators in a steady-state manual control task. Application of the human modeling techniques are made to study the hover control task for a CH-46 VTOL flight tested by NASA.
Optimal Control Problems for Affine Connection Control Systems: Characterization of Extremals
NASA Astrophysics Data System (ADS)
Barbero-Liñán, M.; Muñoz-Lecanda, M. C.
2008-06-01
Pontryagin's Maximum Principle [8] is considered as an outstanding achievement of optimal control theory. This Principle does not give sufficient conditions to compute an optimal trajectory; it only provides necessary conditions. Thus only candidates to be optimal trajectories, called extremals, are found. The Maximum Principle gives rise to different kinds of them and, particularly, the so-called abnormal extremals have been studied because they can be optimal, as Liu and Sussmann, and Montgomery proved in subRiemannian geometry [5, 7]. We build up a presymplectic algorithm, similar to those defined in [2, 3, 4, 6], to determine where the different kinds of extremals of an optimal control problem can be. After describing such an algorithm, we apply it to the study of extremals, specially the abnormal ones, in optimal control problems for affine connection control systems [1]. These systems model the motion of different types of mechanical systems such as rigid bodies, nonholonomic systems and robotic arms [1].
Shortfall as a risk measure: properties, optimization and applications
Dimitris Bertsimas; Geoffrey J. Lauprete; Alexander Samarov
2004-01-01
Motivated from second-order stochastic dominance, we introduce a risk measure that we call shortfall. We examine shortfall's properties and discuss its relation to such commonly used risk measures as standard deviation, VaR, lower partial moments, and coherent risk measures. We show that the mean-shortfall optimization problem, unlike mean-VaR, can be solved efficiently as a convex optimization problem, while the sample
A New Method for Mapping Optimization Problems onto Neural Networks
Peterson, Carsten
is a reduction of solution space by one dimension by using graded neurons, thereby avoiding the destructive is presented. We consider the graph partition and the travelling salesman problems. The key new ingredient] formulated the Travelling Salesman Problem (TSP) on a highly interconnected neural network and made
GLOBAL OPTIMIZATION FOR ONE-DIMENSIONAL STRUCTURE AND MOTION PROBLEMS
Lunds Universitet
is that of simultaneous localization and mapping (SLAM), also called structure and motion [8]. This is the problem-dimensional retina vision. In such problems, the scene is modeled as a 2D plane, and the camera sensor produces 1D local optima and linear algorithms for algebraic cost functions. In contrast, we present an approach
Oliveira, Ivan B. (Ivan Borges), 1975-
2002-01-01
Optimal control problems often arise in engineering applications when a known desired behavior is to be imposed on a dynamical system. Typically, there is a performance and controller use trade-off that can be quantified ...
Paris-Sud XI, Université de
Adaptation Evolution Strategy (CMA-ES) [10] in the optimization of computationally ex- pensive problems, resulting in the local meta-model CMA-ES (lmm-CMA) [14]. The lmm- CMA outperforms the standard CMA
Application of Particle Swarm Optimization Algorithm in the Heating System Planning Problem
Ma, Rong-Jiang; Yu, Nan-Yang; Hu, Jun-Yi
2013-01-01
Based on the life cycle cost (LCC) approach, this paper presents an integral mathematical model and particle swarm optimization (PSO) algorithm for the heating system planning (HSP) problem. The proposed mathematical model minimizes the cost of heating system as the objective for a given life cycle time. For the particularity of HSP problem, the general particle swarm optimization algorithm was improved. An actual case study was calculated to check its feasibility in practical use. The results show that the improved particle swarm optimization (IPSO) algorithm can more preferably solve the HSP problem than PSO algorithm. Moreover, the results also present the potential to provide useful information when making decisions in the practical planning process. Therefore, it is believed that if this approach is applied correctly and in combination with other elements, it can become a powerful and effective optimization tool for HSP problem. PMID:23935429
Multi-agent Optimization Design for Multi-resource Job Shop Scheduling Problems
Fan Xue; Wei Fan
2007-01-01
As a practical generalization of the job shop scheduling problem, multi-resource job shop scheduling problem (MRJSSP) is discussed\\u000a in this paper. In this problem, operations may be processed by a type of resources and jobs have individual deadlines. How\\u000a to design and optimize this problem with DSAFO, a novel multi-agent algorithm, is introduced in detail by a case study, including
Solving Three-objective Optimization Problems Using Evolutionary Dynamic Weighted
Jin, Yaochu
() generates uniformly distributed random weights between 0 and , t is the generation number. This way, the weight space is divided uniformly into a certain number of cells and #12;an individual is generated-optimal surface. It is shown that such analyses are very helpful for recovering the true Pareto front. 1
Some Marginalist Intuition Concerning the Optimal Commodity Tax Problem
ERIC Educational Resources Information Center
Brett, Craig
2006-01-01
The author offers a simple intuition that can be exploited to derive and to help interpret some canonical results in the theory of optimal commodity taxation. He develops and explores the principle that the marginal social welfare loss per last unit of tax revenue generated be equalized across tax instruments. A simple two-consumer,…
UNIFIED PARTICLE SWARM OPTIMIZATION FOR TACKLING OPERATIONS RESEARCH PROBLEMS
Parsopoulos, Konstantinos
of the variables are real, will be considered in future works. Particle Swarm Optimization (PSO) has proved as a unified PSO scheme that com- bines the exploration and exploitation properties of differ- ent PSO variants of UPSO against the standard PSO variants [7, 8]. We investigate the performance of UPSO on minimax
Random Convex Hulls and Extreme Value Statistics
Majumdar, Satya N; Randon-Furling, Julien
2009-01-01
In this paper we study the statistical properties of convex hulls of $N$ random points in a plane chosen according to a given distribution. The points may be chosen independently or they may be correlated. After a non-exhaustive survey of the somewhat sporadic literature and diverse methods used in the random convex hull problem, we present a unifying approach, based on the notion of support function of a closed curve and the associated Cauchy's formulae, that allows us to compute exactly the mean perimeter and the mean area enclosed by the convex polygon both in case of independent as well as correlated points. Our method demonstrates a beautiful link between the random convex hull problem and the subject of extreme value statistics. As an example of correlated points, we study here in detail the case when the points represent the vertices of $n$ independent random walks. In the continuum time limit this reduces to $n$ independent planar Brownian trajectories for which we compute exactly, for all $n$, the me...
An Optimal Algorithm for the Distinct Elements Problem Daniel M. Kane
An Optimal Algorithm for the Distinct Elements Problem Daniel M. Kane Harvard University One Management]: Miscellaneous General Terms: Algorithms, Theory Keywords: distinct elements, streaming, query, CA 95120 dpwoodru@us.ibm.com ABSTRACT We give the first optimal algorithm for estimating the num- ber
An Optimal Algorithm for the Distinct Elements Problem Daniel M. Kane #
An Optimal Algorithm for the Distinct Elements Problem Daniel M. Kane # Harvard University One Management]: Miscellaneous General Terms: Algorithms, Theory Keywords: distinct elements, streaming, query, CA 95120 dpwoodru@us.ibm.com ABSTRACT We give the first optimal algorithm for estimating the num ber
The Multi-robot Coverage Problem for Optimal Coordinated Search with an Unknown Number of Robots
Minnesota, University of
The Multi-robot Coverage Problem for Optimal Coordinated Search with an Unknown Number of Robots of Minnesota Minneapolis, MN 55455 Email: {hjmin|npapas}@cs.umn.edu Abstract-- This work presents a novel multi-robot coverage scheme for an unknown number of robots; it focuses on optimizing the number of robots and each
On the optimal and suboptimal nonlinear filtering problem for discrete-time systems
M. L. ANDRADE NETTO; L. Gimeno; M. J. MENDES
1978-01-01
This paper examines optimal and suboptimal algorithms for the state filtering problem in discrete-time nonlinear systems. The optimal equations of sequential filtering are analyzed and conditions are obtained which ensure a multimodal character for the a posteriori densities. This analysis is utilized in the discussion of the performance of suboptimal linearized filters, and suggestions are made for their improvement in
Paris-Sud XI, Université de
The Trust Region Sequential Quadratic Programming method applied to two-aircraft acoustic optimal University of Orléans. CNRS-MAPMO (France) Abstract: This paper aims to reduce noise levels of two-aircraft on approach. Keywords: TRSQP algorithm, optimal control problem, aircraft noise levels, AMPL programming
Convergence Proof for a Monte Carlo Method for Combinatorial Optimization Problems
Fidanova, Stefka
(COPs). The Ant Colony Optimization (ACO) is a MC method, created to solve eÆ- ciently COPs. The Ant Colony Optimization (ACO) algorithms are being applied successfully to diverse heavily problems. To show. The sampling is realized con- currently by a collection of di#11;erently instantiated replicas of the same ant
A new decision making approach for optimization of multiple response problem
M. Bashiri; M. Ramezani
2009-01-01
This paper present a new method for multiple response optimization (MRO). Multiresponse problems comprise three stages: data gathering, model building and optimization. The most work in MRO don't consider the results of modeling stage while these outcomes can help in achieving the solution. In this paper, we incorporate the obtained results from stage of model building, i. e. the least
Collocation and inversion for a reentry optimal control problem Tobias NECKEL 1
vector fields and functions are smooth functions. It is desired to find a trajectory of (1) [t0, tfCollocation and inversion for a reentry optimal control problem Tobias NECKEL 1 Christophe TALBOT 2 trajectory optimization as an enabling technology for versatile real-time trajectory gen- eration
Ant colony optimization combined with taboo search for the job shop scheduling problem
Kuo-ling Huang; Ching-jong Liao
2008-01-01
In this paper, we present a hybrid algorithm combining ant colony optimization algorithm with the taboo search algorithm for the classical job shop scheduling problem. Instead of using the conventional construction approach to construct feasible schedules, the proposed ant colony optimization algorithm employs a novel decomposition method inspired by the shifting bottleneck procedure, and a mechanism of occasional reoptimizations of
M. Fatih Tasgetiren; Yun-chia Liang; Mehmet Sevkli; Gunes Gencyilmaz
Abstract: In this paper, a particle swarm optimization algorithm (PSO) is presented to solve the permutaion flowshop sequencing problem (PFSP) with the objectives of minimizing makespan and maximum lateness of jobs, respectively. Simple but very efficient local search based on variable neighborhood search (VNS) is embedded in the particle swarm optimization algorithm to solve the well known benchmark suites in
Ying Wang; Jianzhong Zhou; Hui Qin; Youlin Lu
2010-01-01
Dynamic economic dispatch (DED) problem is one of the optimization issues in power system operation. In this paper, an improved chaotic particle swarm optimization (ICPSO) algorithm is proposed to solve DED with value-point effects. In proposed ICPSO, chaotic mutation is embedded to overcome the drawback of premature in PSO. What’s more, enhanced heuristic strategies are proposed to handling the various
GA-Hardness of Aerodynamic Optimization Problems: Analysis and Proposed Cures
P. Cinnella; P. M. Congedo
A study about convergence of Genetic Algorithms (GAs) applied to aerodynamic optimization problems for transonic flows of dilute and dense gases is presented. Specific attention is devoted to working fluids of the Bethe—Zel'dovich—Thompson (BZT) type, which exhibit non classical dynamic behaviors in the transonic\\/supersonic regime, such as the disintegration of compression shocks. A reference, single-objective optimization problem, namely, wave drag
NASA Technical Reports Server (NTRS)
Price, D. B.; Gracey, C.
1983-01-01
This short paper will demonstrate that the separation of altitude and flight path angle dynamics using singular perturbation techniques for a transport fuel optimization problem results in an unacceptable oscillation in altitude. A technique for damping this oscillation by adding a penalty term to the cost function for the optimization problem will be discussed. This technique will be compared with a different approach that linearizes the altitude and flight path angle boundary layers.
Solution techniques for some allocation problems
A. Federgruen; P. Zipkin
1983-01-01
This paper presents methods for solving allocation problems that can be stated as convex knapsack problems with generalized\\u000a upper bounds. Such bounds may express upper limits on the total amount allocated to each of several subsets of activities.\\u000a In addition our model arises as a subproblem in more complex mathematical programs. We therefore emphasize efficient procedures\\u000a to recover optimality when
The optimization research of the multi-response problems based on the SUR.
Su, Haitao; Yao, Hong Mei; Zeng, Hui
2015-03-01
In the optimization design of products and processes in the biological medicine, we need to consider multiple characteristics of quality simultaneously, namely multi-response problems, multi-response optimization design can improve the quality of the products effectively, and realize enormous economic benefits and so multi-response optimization design is showing a more and more important role in continuous quality improvement activities. But usually there is no specific set of input variables to make all the response variables be optimal, and the traditional multi-response surface method cannot solve the correlation problem between multi-responses and regression model problem effectively. Because we can make a better fitting model and solve the problem of the correlation between the response variables at the same time with SUR method, this thesis uses the SUR method to model the relationship between each response and control variables, and makes predictions; confirms the satisfaction function of each response and the overall satisfaction function; combines with practical problems of a company in biological medicine field named SX to conduct empirical research, this thesis confirms the optimal factor level combination with the overall satisfaction function in the end, thus solves the multi-response optimization problems. PMID:25796165