Sample records for convex optimization problem

  1. Convex Programming for Disjunctive Convex Optimization

    Microsoft Academic Search

    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

  2. Stochastic methods for large-scale linear problems, variational inequalities, and convex optimization

    E-print Network

    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 ...

  3. Advances in Convex Optimization

    Microsoft Academic Search

    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

  4. Convex optimization problem prototyping for image reconstruction in computed tomography with the Chambolle-Pock algorithm

    PubMed Central

    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

  5. Convex optimization methods for model reduction

    E-print Network

    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 ...

  6. Subspace identification via convex optimization

    E-print Network

    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 ...

  7. Solving quadratically constrained convex optimization problems with an interior-point method

    Microsoft Academic Search

    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

  8. On the Complexity of Optimization Problems for 3Dimensional Convex Polyhedra and Decision Trees \\Lambda

    E-print Network

    Goodrich, Michael T.

    for realizing a planar 3­connected 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

  9. Convex programming for disjunctive convex optimization

    Microsoft Academic Search

    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

  10. 1 Automatic Code Generation for Real-Time Convex Optimization

    E-print Network

    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

  11. Joint Equalization and Decoding via Convex Optimization 

    E-print Network

    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...

  12. A review of the book "Functional analysis and applied optimization in Banach spaces -Applications to non-convex variational problems" by Fabio Botelho,

    E-print Network

    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

  13. Real-Time Convex Optimization in Signal Processing

    Microsoft Academic Search

    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

  14. A General Framework for Convex Relaxation of Polynomial Optimization Problems over Cones

    E-print Network

    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

  15. Lossless Convexification of a Class of Optimal Control Problems with Non-Convex Control Constraints

    E-print Network

    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

  16. Convex Optimization: from Real-Time Embedded

    E-print Network

    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

  17. Privacy constraints in regularized convex optimization

    E-print Network

    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.

  18. An approximation algorithm for convex multiplicative programming problems

    Microsoft Academic Search

    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 \\

  19. A new fuzzy adaptive hybrid particle swarm optimization algorithm for non-linear, non-smooth and non-convex economic dispatch problem

    Microsoft Academic Search

    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

  20. August 2000 (Convex Optimization ) JP Goux The mega title ...

    E-print Network

    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 ...

  1. Privacy Preserving Online Convex Optimization

    E-print Network

    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...

  2. Distributionally Robust Convex Optimization

    E-print Network

    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.

  3. Convex Duality in Constrained Portfolio Optimization

    Microsoft Academic Search

    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

  4. Design of PI Controllers based on Non-Convex Optimization

    Microsoft Academic Search

    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.

  5. A Survey of Algorithms for Convex Multicommodity Flow Problems

    Microsoft Academic Search

    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

  6. Convex optimization techniques in system identification

    E-print Network

    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

  7. Optimal Stochastic Approximation Algorithms for Strongly Convex ...

    E-print Network

    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 ...

  8. Pulse Construction in OFDM Systems via convex optimization

    E-print Network

    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

  9. Portfolio Optimization under Convex Incentive Schemes

    E-print Network

    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...

  10. Cooperative Convex Optimization in Networked Systems: Augmented Lagrangian Algorithms With Directed Gossip Communication

    Microsoft Academic Search

    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

  11. Convex Optimization-based Beamforming: From Receive to Transmit and Network Designs

    Microsoft Academic Search

    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

  12. 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.

  13. Convex Analysis and Optimization with Submodular Functions: a Tutorial

    E-print Network

    Boyer, Edmond

    Convex Analysis and Optimization with Submodular Functions: a Tutorial Francis Bach INRIA - Willow . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 10.2 Cut functions . . . . . . . . . . . . . . . . . .

  14. Optimal static-dynamic hedges for exotic options under convex risk measures

    Microsoft Academic Search

    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

  15. Nonsmooth and nonconvex structural analysis algorithms based on difference convex optimization techniques

    Microsoft Academic Search

    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.

  16. On an Extension of Condition Number Theory to Non-Conic Convex Optimization

    E-print Network

    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

  17. New Algorithms for the Dual of the Convex Cost Network Flow Problem with Application to Computer Vision

    Microsoft Academic Search

    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

  18. Three Problems about Dynamic Convex Hulls Timothy M. Chan

    E-print Network

    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

  19. Uniform convexity and the splitting problem for selections

    Microsoft Academic Search

    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.

  20. Uniform convexity and the splitting problem for selections

    E-print Network

    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.

  1. Intermediate gradient methods ^for smooth convex problems with inexact oracle

    E-print Network

    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

  2. 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.

  3. 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.

  4. SEGMENTATION OF IMAGES WITH SEPARATING LAYERS BY FUZZY C-MEANS AND CONVEX OPTIMIZATION

    E-print Network

    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

  5. Convex initialization of the H2-optimal static output feedback problem Henrik Manum, Sigurd Skogestad, and Johannes Jaschke

    E-print Network

    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

  6. sensitivity analysis in convex quadratic optimization: invariant ...

    E-print Network

    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.

  7. A continuous convex knapsack problem with one convex complicating constraint: The Economic dispatch problem

    SciTech Connect

    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.

  8. A randomized scheme for speeding up algorithms for linear and convex programming problems with high constraints-to-variables ratio

    Microsoft Academic Search

    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

  9. Kernel regression for travel time estimation via convex optimization

    E-print Network

    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

  10. accuracy certificates for computational problems with convex structure

    E-print Network

    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 ...

  11. Convex Configurations In Free Boundary Problems

    E-print Network

    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 |

  12. Perturbation theory for abstract optimization problems

    Microsoft Academic Search

    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

  13. Modeling flow statistics using convex optimization

    E-print Network

    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

  14. A convex optimization approach to ARMA Tryphon T. Georgiou and Anders Lindquist

    E-print Network

    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

  15. Regularization Constants in LS-SVMs: a Fast Estimate via Convex Optimization

    E-print Network

    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

  16. Convex Relaxation for Multilabel Problems with Product Label Spaces

    E-print Network

    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

  17. Convex Relaxation for Multilabel Problems with Product Label Spaces

    E-print Network

    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

  18. Global convergence of the Heavy-ball method for convex optimization

    E-print Network

    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].

  19. Mixed H2\\/H? control for discrete-time systems via convex optimization

    Microsoft Academic Search

    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

  20. Optimal convex error estimators for classification

    Microsoft Academic Search

    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 \\

  1. Optimization over the Pareto Outcome set associated with a Convex ...

    E-print Network

    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-.

  2. Active Learning as Non-Convex Optimization Andrew Guillory

    E-print Network

    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

  3. GLOBAL OPTIMIZATION IN COMPUTER VISION: CONVEXITY, CUTS AND

    E-print Network

    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

  4. Adaptive Algorithms for Planar Convex Hull Problems

    Microsoft Academic Search

    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\\

  5. Penalty/Barrier Multiplier Methods for Convex Programming Problems

    E-print Network

    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 Ben­Tal 1 and Michael

  6. 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.

  7. A cutting surface algorithm for semi-infinite convex programming ...

    E-print Network

    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.

  8. 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.

  9. A Repository of Convex Quadratic Programming Problems

    Microsoft Academic Search

    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

  10. An improved cellular automata based algorithm for the 45-convex hull problem

    E-print Network

    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

  11. An improved cellular automata based algorithm for the 45convex hull problem

    E-print Network

    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

  12. Solving Standard Quadratic Optimization Problems via Linear, Semidefinite and Copositive Programming

    Microsoft Academic Search

    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

  13. A convex analysis approach for convex multiplicative programming

    Microsoft Academic Search

    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

  14. Time and VLSI-Optimal Convex Hull Computation on Meshes with Multiple Broadcasting

    Microsoft Academic Search

    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

  15. Sparse representations and convex optimization as tools for LOFAR radio interferometric imaging

    E-print Network

    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...

  16. From nonlinear optimization to convex optimization through firefly algorithm and indirect approach with applications to CAD/CAM.

    PubMed

    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

  17. A Double Smoothing Technique for Constrained Convex ...

    E-print Network

    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).

  18. 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.

  19. An Optimal Algorithm for Intersecting Three-Dimensional Convex Polyhedra

    Microsoft Academic Search

    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.

  20. The optimal path-matching problem

    SciTech Connect

    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.

  1. BROADBAND SENSOR LOCATION SELECTION USING CONVEX OPTIMIZATION IN VERY LARGE SCALE ARRAYS

    E-print Network

    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

  2. A Perspective-Based Convex Relaxation for Switched-Affine Optimal Control

    E-print Network

    -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

  3. Dynamic Planar Convex Hull with Optimal Query Time and O(log n log log n) Update Time

    E-print Network

    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

  4. The unit distance problem for centrally symmetric convex Bernardo M. brego

    E-print Network

    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

  5. Optimization problems of gnostics

    Microsoft Academic Search

    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

  6. CONVEX MATROID OPTIMIZATION SIAM J. DISCRETE MATH. c 2003 Society for Industrial and Applied Mathematics

    E-print Network

    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

  7. An optimal real-time algorithm for planar convex hulls

    Microsoft Academic Search

    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).

  8. Dynamic Resource Allocation in Cognitive Radio Networks: A Convex Optimization Perspective

    E-print Network

    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.

  9. libCreme: An optimization library for evaluating convex-roof entanglement measures

    E-print Network

    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.

  10. Equivalence of Convex Problem Geometry and Computational Complexity in the Separation Oracle Model

    E-print Network

    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' ...

  11. Worst-Case Violation of Sampled Convex Programs for Optimization ...

    E-print Network

    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.

  12. Non-convex optimization for the design of sparse FIR filters

    E-print Network

    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 ...

  13. Non-euclidean restricted memory level method for large-scale convex optimization

    Microsoft Academic Search

    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

  14. Discontinuous control problems for non-convex dynamics and near viability for singularly perturbed control systems

    Microsoft Academic Search

    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.

  15. 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.

  16. FILTER-BANK OPTIMIZATION WITH CONVEX OBJECTIVES, AND THE OPTIMALITY OF PRINCIPAL COMPONENT FORMS1

    Microsoft Academic Search

    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

  17. Filterbank optimization with convex objectives and the optimality of principal component forms

    Microsoft Academic Search

    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

  18. A Study of Near-Field Direct Antenna Modulation Systems Using Convex Optimization

    E-print Network

    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

  19. Non-Euclidean Restricted Memory Level Method for Large-Scale Convex Optimization

    E-print Network

    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

  20. Minimum-Landing-Error Powered-Descent Guidance for Mars Landing Using Convex Optimization

    E-print Network

    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

  1. A Convex Optimization Approach to Feedback Scheduling Mongi Ben Gaid, Daniel Simon and Olivier Sename

    E-print Network

    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

  2. Single-Ballot Risk-Limiting Audits Using Convex Optimization Stephen Checkoway

    E-print Network

    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

  3. 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…

  4. Automated bone segmentation from dental CBCT images using patch-based sparse representation and convex optimization

    SciTech Connect

    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.

  5. EE 231 Convex Optimization in Engineering Applications (Winter 2014)

    E-print Network

    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

  6. Convex optimization for control analysis application to the steam generator water level

    Microsoft Academic Search

    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

  7. 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.

  8. Convexity-Oriented Mapping Method for the Topology Optimization of Electromagnetic Devices Composed of Iron and Coils

    Microsoft Academic Search

    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

  9. Experimental Validation of a Numerical Controller Using Convex Optimization with Linear Matrix Inequalities on a Quarter-Car Suspension System 

    E-print Network

    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...

  10. 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.

  11. Computing Optimized Representations for Non-convex Polyhedra by Detection and Removal of Redundant Linear Constraints

    Microsoft Academic Search

    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

  12. A feasible active set method for strictly convex quadratic problems ...

    E-print Network

    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.

  13. Neurocomputing with time delay analysis for solving convex quadratic programming problems.

    PubMed

    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

  14. BILEVEL OPTIMIZATION PROBLEMS WITH VECTORVALUED ...

    E-print Network

    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-.

  15. Convex optimization methods for graphs and statistical modeling

    E-print Network

    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 ...

  16. Optimization over the Efficient Set of a Bicriteria Convex ...

    E-print Network

    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.

  17. Newton-Raphson consensus for distributed convex optimization

    E-print Network

    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

  18. The Power of Convex Relaxation: Near-Optimal Matrix Completion

    E-print Network

    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

  19. Accelerated Microstructure Imaging via Convex Optimization (AMICO) from diffusion MRI data.

    PubMed

    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

  20. A Weiszfeld-like algorithm for a Weber location problem constrained to a closed and convex set

    E-print Network

    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...

  1. Convexity-Oriented Method for the Topology Optimization of Ferromagnetic Moving Parts in Electromagnetic Actuators Using Magnetic Energy

    Microsoft Academic Search

    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

  2. Unified Particle Swarm Optimization for Solving Constrained Engineering Optimization Problems

    E-print Network

    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

  3. Dynamic Planar Convex Hull Operations in Near-Logarithmic Amortized Time

    E-print Network

    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

  4. Dynamic Planar Convex Hull with Optimal Query Time and O(log n · log log n ) Update Time

    Microsoft Academic Search

    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

  5. Dr. Marcus Wagner Brandenburg University of Technology, Cottbus; Department of Mathematics, Chair for Optimization

    E-print Network

    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

  6. Stochastic maximum principle for optimal control problem of backward systems with terminal condition in L1

    E-print Network

    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.

  7. Online Optimization with Switching Cost Minghong Lin Adam Wierman

    E-print Network

    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

  8. Approximating Convex Functions Via Non-Convex Oracles Under ...

    E-print Network

    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-.

  9. Linear-Convex Control and Duality R.T. Rockafellar

    E-print Network

    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

  10. Bibliography Analysis of the Optimal Control Problem

    E-print Network

    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

  11. A methodology to ensure local mass conservation for porous media models under finite element formulations based on convex optimization

    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.

  12. Particle Swarms for Dynamic Optimization Problems

    E-print Network

    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

  13. The roles of the convex hull and the number of potential intersections in performance on visually presented traveling salesperson problems.

    PubMed

    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

  14. Optimal impulse control problems and linear programming

    Microsoft Academic Search

    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

  15. Global optimization in inverse problem of scatterometry

    E-print Network

    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

  16. Automatic Segmentation of Neonatal Images Using Convex Optimization and Coupled Level Sets

    PubMed Central

    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

  17. 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.

  18. Convex Drawings of Graphs Non-convex Boundary Constraints

    E-print Network

    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

  19. NP-hardness of deciding convexity of quartic polynomials and related problems

    E-print Network

    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 ...

  20. Solving constrained optimization problems with hybrid particle swarm optimization

    Microsoft Academic Search

    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

  1. Constrained Graph Optimization: Interdiction and Preservation Problems

    SciTech Connect

    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.

  2. 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…

  3. About solving hybrid optimal control problems

    Microsoft Academic Search

    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

  4. Convex Nondifferentiable Optimization: a Survey Focussed on the Analytic Center Cutting Plane Method

    Microsoft Academic Search

    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

  5. Path following algorithm for the graph matching problem

    Microsoft Academic Search

    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

  6. A Path Following Algorithm for the Graph Matching Problem

    Microsoft Academic Search

    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.

  7. An L{sub {infinity}}/L{sub 1}-Constrained Quadratic Optimization Problem with Applications to Neural Networks

    SciTech Connect

    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.

  8. Large Scale Computational Problems in Numerical Optimization

    SciTech Connect

    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.

  9. Optimization problems in network connectivity

    E-print Network

    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 ...

  10. A numerical approach to the non-convex dynamic problem of pipeline-soil interaction under environmental effects

    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.

  11. A Generic Bee Colony Optimization Framework for Combinatorial Optimization Problems

    Microsoft Academic Search

    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

  12. Improved Approximation Bound for Quadratic Optimization Problems ...

    E-print Network

    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.

  13. 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.

  14. An FPTAS for Minimizing a Class of Low-Rank Quasi-Concave Functions over a Convex Set

    Microsoft Academic Search

    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

  15. Practical iterative image reconstruction in digital breast tomosynthesis by non-convex TpV optimization

    E-print Network

    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

  16. Parameter Identification Problem Using Particle Swarm Optimization

    Microsoft Academic Search

    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

  17. 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.

  18. 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.

  19. 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.

  20. Hierarchical particle swarm optimizer for minimizing the non-convex potential energy of molecular structure.

    PubMed

    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

  1. Ant Algorithms Solve Difficult Optimization Problems

    E-print Network

    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

  2. Optimization problems involving collections of dependent objects

    Microsoft Academic Search

    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

  3. 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.

  4. A new deterministic global optimization method for general twice-differentiable constrained nonlinear programming problems

    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.

  5. Interaction prediction optimization in multidisciplinary design optimization problems.

    PubMed

    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

  6. Fast Multi-swarm Optimization for Dynamic Optimization Problems Department of Computer Science

    E-print Network

    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

  7. Optimality results for dividend problems in insurance

    Microsoft Academic Search

    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.

  8. On the Dirichlet and Serrin Problems for the Inhomogeneous Infinity Laplacian in Convex Domains: Regularity and Geometric Results

    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.

  9. LDRD Final Report: Global Optimization for Engineering Science Problems

    SciTech Connect

    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.

  10. 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.

  11. Boundary search and simplex decomposition method for MDO problems with a convex or star-like state parameter region

    Microsoft Academic Search

    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),

  12. Optimal control as a graphical model inference problem

    Microsoft Academic Search

    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

  13. SINGULAR PERTURBATION OF OPTIMAL CONTROL PROBLEMS ON MULTI-DOMAINS

    E-print Network

    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

  14. A global optimization approach for solving the maximum clique problem

    Microsoft Academic Search

    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

  15. A Binary Particle Swarm Optimization Algorithm for Lot Sizing Problem

    Microsoft Academic Search

    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

  16. An inexact proximal bundle method with applications to convex ...

    E-print Network

    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 ?.

  17. Exact Matrix Completion via Convex Optimization Emmanuel J. Cand`es

    E-print Network

    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

  18. 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.

  19. Neighboring optimization for constrained control problems in real time

    Microsoft Academic Search

    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

  20. Bilevel problems over polyhedra with extreme point optimal solutions

    Microsoft Academic Search

    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

  1. 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.

  2. Optimization Online Digest -- July 2012

    E-print Network

    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

  3. Exact Matrix Completion via Convex Optimization Emmanuel J. Cand`es

    E-print Network

    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

  4. Cone convexity, cone extreme points, and nondominated solutions in decision problems with multiobjectives

    Microsoft Academic Search

    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

  5. Optimal Auction Design for Agents with Hard Valuation Problems

    E-print Network

    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

  6. Equivalent differentiable optimization problems and descent methods for asymmetric variational inequality problems

    Microsoft Academic Search

    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

  7. Group Search Optimizer for the Mobile Location Management Problem

    PubMed Central

    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

  8. A class of optimization problems over the efficient set of a multiple criteria nonlinear programming problem

    Microsoft Academic Search

    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.

  9. Optimal shape design as a material distribution problem

    Microsoft Academic Search

    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

  10. Chaotic Particle Swarm Optimization Algorithm for Traveling Salesman Problem

    Microsoft Academic Search

    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

  11. Methods for optimizing over the efficient and weakly efficient sets of an affine fractional vector optimization program

    Microsoft Academic Search

    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

  12. Hedging Uncertainty: Approximation Algorithms for Stochastic Optimization Problems

    Microsoft Academic Search

    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

  13. Bee Colony Optimization with local search for traveling salesman problem

    Microsoft Academic Search

    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

  14. Bee Colony Optimization with Local Search for Traveling Salesman Problem

    Microsoft Academic Search

    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

  15. Spectral Finite-Element Methods for Parametric Constrained Optimization Problems

    Microsoft Academic Search

    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

  16. Genetic Algorithms for Combinatorial Optimization: The Assembly Line Balancing Problem

    E-print Network

    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

  17. A fuzzy satisficing method for multiobjective linear optimal control problems

    Microsoft Academic Search

    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

  18. On some multiobjective optimization problems arising in biology

    Microsoft Academic Search

    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

  19. The Convex Hull of Freeform Surfaces

    Microsoft Academic Search

    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.

  20. Some optimization problems in power system reliability analysis 

    E-print Network

    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...

  1. PIBEA: Prospect Indicator Based Evolutionary Algorithm for Multiobjective Optimization Problems

    E-print Network

    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

  2. Production Planning and Inventories Optimization : A Backward Approach in the Convex Storage Cost Case

    E-print Network

    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

  3. An outcome space approach for generalized convex multiplicative programs

    Microsoft Academic Search

    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

  4. A Simple But Effective Evolutionary Algorithm for Complicated Optimization Problems

    E-print Network

    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 ...

  5. LP formulations for mixed-integer polynomial optimization problems ...

    E-print Network

    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.

  6. The Optimal Single Copy Measurement for the Hidden Subgroup Problem

    E-print Network

    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.

  7. Parametric Programming Applied to Reliability Optimization Problems

    Microsoft Academic Search

    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

  8. Fast Approximate Convex Decomposition 

    E-print Network

    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...

  9. Average case analysis of dynamic geometric optimization

    E-print Network

    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

  10. Optimization Online - Integer Programming Submissions - 2012

    E-print Network

    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 ...

  11. Problem Decomposition and MultiObjective Optimization Richard A. Watson

    E-print Network

    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

  12. Necessarily efficient solutions of multiobjective linear optimal control problems

    Microsoft Academic Search

    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

  13. Approximation of a singularly perturbed elliptic problem of optimal control

    SciTech Connect

    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.

  14. A moving horizon solution to the gas pipeline optimization problem

    E-print Network

    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

  15. Two Dimensional Optimal Mechanism Design for a Sequencing Problem

    E-print Network

    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

  16. On Identification of the Optimal Partition of Second Order Cone Optimization Problems

    E-print Network

    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

  17. 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.

  18. On Evolutionary Optimization of Large Problems Using Small Populations

    E-print Network

    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

  19. A Genetic Algorithm for Minimax Optimization Problems Jeffrey W. Herrmann

    E-print Network

    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

  20. Random Sampling and Greedy Sparsification for Matroid Optimization Problems.

    E-print Network

    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

  1. 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…

  2. Sequential Multiresolution Trajectory Optimization Schemes for Problems with Moving Targets

    E-print Network

    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

  3. PARALLEL ALGORITHMS FOR A MULTI-LEVEL NETWORK OPTIMIZATION PROBLEM

    E-print Network

    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

  4. 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.

  5. Particle Swarm Optimization and Fitness Sharing to solve Multi-Objective Optimization Problems

    E-print Network

    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

  6. Solving disjunctive optimization problems by generalized semi ...

    E-print Network

    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.

  7. Optimal solutions to multi-objective robust fault detection problems

    Microsoft Academic Search

    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

  8. Dual Methods for Nonconvex Spectrum Optimization of Multicarrier Systems

    Microsoft Academic Search

    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,

  9. Optimization Problems in Natural Gas Transportation Systems

    E-print Network

    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 ).

  10. A Hierarchical Particle Swarm Optimizer for Dynamic Optimization Problems

    Microsoft Academic Search

    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

  11. A Planning Problem Combining Calculus of Variations and Optimal Transport

    SciTech Connect

    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.

  12. Optimized Waveform Relaxation Solution of Electromagnetic and Circuit Problems

    E-print Network

    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

  13. GLOBAL OPTIMIZATION FOR THE PHASE AND CHEMICAL EQUILIBRIUM PROBLEM

    E-print Network

    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

  14. Optimal solutions for a free boundary problem for crystal growth

    E-print Network

    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

  15. Optimal Auction Design for Agents with Hard Valuation Problems

    E-print Network

    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

  16. On optimization techniques for solving nonlinear inverse problems

    Microsoft Academic Search

    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

  17. 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.

  18. An augmented Lagrangian approach to the constrained optimization formulation of imaging inverse problems.

    PubMed

    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

  19. Optimal measurements for the dihedral hidden subgroup problem

    E-print Network

    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.

  20. Non-concave and behavioural optimal portfolio choice problems 

    E-print Network

    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 ...

  1. 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.

  2. Decomposition methods for large scale stochastic and robust optimization problems

    E-print Network

    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 ...

  3. 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.

  4. PLASMA Approximate Dynamic Programming finally cracks the locomotive optimization problem

    E-print Network

    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

  5. An algorithm for nonlinear optimization problems with binary variables

    Microsoft Academic Search

    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

  6. Metropolis Particle Swarm Optimization Algorithm with Mutation Operator For Global Optimization Problems

    E-print Network

    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

  7. Optimal control problems in public health

    Microsoft Academic Search

    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

  8. ROBUSTNESS OPTIMIZATION FOR CONSTRAINED NONLINEAR PROGRAMMING PROBLEMS

    Microsoft Academic Search

    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

  9. A unified modeling and solution framework for combinatorial optimization problems

    Microsoft Academic Search

    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

  10. Some Finance Problems Solved with Nonsmooth Optimization Techniques

    E-print Network

    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

  11. 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…

  12. A Distributed Optimization Approach to Constrained OSNR Problem

    E-print Network

    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

  13. 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.

  14. Strategies for Solving High-Fidelity Aerodynamic Shape Optimization Problems

    E-print Network

    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

  15. GA-HARDNESS OF DENSE-GAS FLOW OPTIMIZATION PROBLEMS

    Microsoft Academic Search

    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

  16. A hybrid immune PSO for constrained optimization problems

    Microsoft Academic Search

    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

  17. 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.

  18. The Vector Model of Artificial Physics Optimization Algorithm for Global Optimization Problems

    Microsoft Academic Search

    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

  19. Dynamic Planar Convex Hull

    Microsoft Academic Search

    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

  20. The optimal harvesting problem under risk aversion

    E-print Network

    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.

  1. Integer Optimization Models of AI Planning Problems

    E-print Network

    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 theorem­proving in first­order logic. The basic statement

  2. Chapter 4: Unconstrained Optimization Unconstrained optimization problem minx F(x) or maxx F(x)

    E-print Network

    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

  3. The expanded invasive weed optimization metaheuristic for solving continuous and discrete optimization problems.

    PubMed

    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

  4. 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.

  5. 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

  6. ON A SMOOTH DUAL GAP FUNCTION FOR A CLASS OF PLAYER CONVEX

    E-print Network

    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

  7. SMMH--A Parallel Heuristic for Combinatorial Optimization Problems

    SciTech Connect

    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.

  8. SMMH - A Parallel Heuristic for Combinatorial Optimization Problems

    SciTech Connect

    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.

  9. Convexity Rule for Shape Decomposition Based on Discrete Contour Evolution

    Microsoft Academic Search

    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

  10. A probabilistic numerical method for optimal multiple switching problem

    E-print Network

    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

  11. A Bee Colony Optimization Algorithm for Traveling Salesman Problem

    Microsoft Academic Search

    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.

  12. Constraint Optimal Selection Techniques (COSTs) for Nonnegative Linear Programming Problems

    Microsoft Academic Search

    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.

  13. An Optimal Algo-Tech-Cuit for the Knapsack Problem

    Microsoft Academic Search

    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

  14. Approximation on the Web: A Compendium of NP Optimization Problems

    Microsoft Academic Search

    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.

  15. Optimization of the multiple retailer supply chain management problem

    Microsoft Academic Search

    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

  16. An improved particle swarm optimization algorithm for flowshop scheduling problem

    Microsoft Academic Search

    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

  17. TWO DECOMPOSITION ALGORITHMS FOR NONCONVEX OPTIMIZATION PROBLEMS

    E-print Network

    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

  18. Decidable optimization problems for database logic programs

    Microsoft Academic Search

    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

  19. 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.

  20. 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].

  1. Optimal Adaptive Policies for Sequential Allocation Problems

    Microsoft Academic Search

    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

  2. The Coral Reefs Optimization Algorithm: A Novel Metaheuristic for Efficiently Solving Optimization Problems

    PubMed Central

    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

  3. The coral reefs optimization algorithm: a novel metaheuristic for efficiently solving optimization problems.

    PubMed

    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

  4. Cooperative optimal path planning for herding problems

    E-print Network

    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...

  5. Utility Function Programs and Optimization over the Efficient Set in Multiple-Objective Decision Making

    Microsoft Academic Search

    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

  6. 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.

  7. Optimal Multi-Modes Switching Problem in Infinite Horizon

    E-print Network

    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.

  8. Integrated network design and scheduling problems : optimization algorithms and applications.

    SciTech Connect

    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.

  9. Redundancy optimization problem with warm-standby redundancy

    Microsoft Academic Search

    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

  10. 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).

  11. Numerical Solution of Some Types of Fractional Optimal Control Problems

    PubMed Central

    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

  12. Application of clustering global optimization to thin film design problems.

    PubMed

    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

  13. A Discrete Lagrangian Algorithm for Optimal Routing Problems

    SciTech Connect

    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.

  14. 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.

  15. The Convex Hull of Rational Plane Curves

    Microsoft Academic Search

    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

  16. XIV Spanish Meeting on Computational Geometry, 2730 June 2011 Rectilinear convex hull with minimum area

    E-print Network

    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

  17. 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.

  18. An optimal algo-tech-cuit for the knapsack problem

    Microsoft Academic Search

    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

  19. PDE: A Paretofrontier Differential Evolution Approach for Multi-objective Optimization Problems

    E-print Network

    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

  20. Lossless Convexification of Control Constraints for a Class of Nonlinear Optimal Control Problems

    E-print Network

    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

  1. Generating Convex Polynomial Inequalities for Mixed 0–1 Programs

    Microsoft Academic Search

    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.

  2. Binary optimization for source localization in the inverse problem of ECG.

    PubMed

    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

  3. Johnson's problem with stochastic processing times and optimal service level

    Microsoft Academic Search

    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

  4. An optimal order for ECG inverse problems with MDL.

    PubMed

    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

  5. Intelligent evolutionary algorithms for large parameter optimization problems

    Microsoft Academic Search

    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

  6. Using Ant Colony Optimization algorithm for solving project management problems

    Microsoft Academic Search

    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

  7. Distributed Genetic Algorithms with New Sharing Approach Multiobjective Optimization Problems

    E-print Network

    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 trade­off. genetic algorithm powerful timization methods based mechanics

  8. Ant Colony Optimization for Solving Solid Waste Collection Scheduling Problems

    Microsoft Academic Search

    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

  9. Ant Colony Algorithms in Diverse Combinational Optimization Problems -A Survey

    Microsoft Academic Search

    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

  10. QISA: Incorporating quantum computation into Simulated Annealing for optimization problems

    Microsoft Academic Search

    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

  11. Simulation-based optimization for the quay crane scheduling problem

    Microsoft Academic Search

    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.

  12. To the optimization problem in minority game model

    SciTech Connect

    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.

  13. Ant Colony Optimization for VRP and Mail Delivery Problems

    Microsoft Academic Search

    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

  14. Multiagent Optimization System for Solving the Traveling Salesman Problem (TSP)

    Microsoft Academic Search

    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),

  15. Optimal Surface Deployment Problem in Wireless Sensor Networks

    E-print Network

    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

  16. Optimal Surface Deployment Problem in Wireless Sensor Networks

    E-print Network

    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

  17. Approximating convex Pareto surfaces in multiobjective radiotherapy planning

    SciTech Connect

    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.

  18. A hybrid artificial bee colony optimization and quantum evolutionary algorithm for continuous optimization problems.

    PubMed

    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

  19. People Efficiently Explore the Solution Space of the Computationally Intractable Traveling Salesman Problem to Find Near-Optimal Tours

    PubMed Central

    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

  20. People efficiently explore the solution space of the computationally intractable traveling salesman problem to find near-optimal tours.

    PubMed

    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

  1. 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.

  2. Optimization Problems in the Polynomial-Time Hierarchy

    Microsoft Academic Search

    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

  3. 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.

  4. The roles of the convex hull and number of intersections upon performance on visually presented traveling salesperson problems

    Microsoft Academic Search

    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

  5. Linear and nonlinear model predictive control using a general purpose optimal control problem solver RIOTS 95

    Microsoft Academic Search

    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

  6. Hybrid Nelder-Mead simplex search and particle swarm optimization for constrained engineering design problems

    Microsoft Academic Search

    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

  7. Optimizing the design of complex energy conversion systems by Branch and Cut

    Microsoft Academic Search

    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

  8. ON MAXIMAL S-FREE CONVEX SETS 1. Introduction. A convex set ...

    E-print Network

    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, ...

  9. Solving quadratic programming problems by delayed projection neural network.

    PubMed

    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

  10. CONVEX BACKSCATTERING SUPPORT IN ELECTRIC IMPEDANCE TOMOGRAPHY

    E-print Network

    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

  11. CONVERGENCE FOR STABILISATION OF DEGENERATELY CONVEX MINIMISATION

    E-print Network

    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

  12. A new optimization method, the Algorithm of Changes, for Bin Packing Problem

    Microsoft Academic Search

    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

  13. AN INTERIOR POINT ALGORITHM FOR SOLVING LINEAR OPTIMIZATION OVER THE EFFICIENT SET PROBLEMS

    Microsoft Academic Search

    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

  14. Parallel-vector computation for structural analysis and nonlinear unconstrained optimization problems

    Microsoft Academic Search

    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

  15. 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.

  16. Optimization of spring-loaded crutches via boundary value problem.

    PubMed

    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

  17. Radio interferometric gain calibration as a complex optimization problem

    E-print Network

    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...

  18. 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.

  19. The Breeder Genetic Algorithm and its application to optimization problems

    SciTech Connect

    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.

  20. 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.

  1. An improved particle swarm optimization algorithm for reliability problems.

    PubMed

    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

  2. Compensated optimal grids for elliptic boundary-value problems.

    PubMed

    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

  3. Fuzzy efficient and pareto — Optimal solution for multiobjective linear plus linear fractional programming problem

    Microsoft Academic Search

    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

  4. Asynchronous global optimization techniques for medium and large inversion problems

    SciTech Connect

    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.

  5. Optimal Control and the Aircraft Radar Evasion Problem

    Microsoft Academic Search

    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

  6. Particle Swarm Optimization Algorithm for Permutation Flowshop Sequencing Problem

    Microsoft Academic Search

    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

  7. 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.

  8. Cores of convex games

    Microsoft Academic Search

    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.

  9. Practical Global Optimization for Multiview Geometry

    Microsoft Academic Search

    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

  10. On Several Fundamental Problems of Optimization, Estimation, and Scheduling in Wireless Communications

    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

  11. Feed Forward Neural Network and Optimal Control Problem with Control and State Constraints

    SciTech Connect

    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.

  12. Multi-objective evolutionary methods for time-changing portfolio optimization problems

    E-print Network

    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 ...

  13. On the robust optimization to the uncertain vaccination strategy problem

    SciTech Connect

    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.

  14. Resource Efficient Gadgets for Compiling Adiabatic Quantum Optimization Problems

    E-print Network

    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.

  15. 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.

  16. On the problem of optimal thrust programming for a lunar soft landing

    Microsoft Academic Search

    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

  17. Forrelation: A Problem that Optimally Separates Quantum from Classical Computing

    E-print Network

    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."

  18. Project impact analysis as an optimal control problem

    SciTech Connect

    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.

  19. 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.

  20. Fast algorithms for L? problems in multiview geometry

    Microsoft Academic Search

    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

  1. Near-optimal perfectly matched layers for indefinite Helmholtz problems

    E-print Network

    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.

  2. Lattice point sets for deterministic learning and approximate optimization problems.

    PubMed

    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

  3. 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.

  4. 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.

  5. Random Convex Hulls and Extreme Value Statistics

    Microsoft Academic Search

    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

  6. Genetic Algorithm for Mulicriteria Optimization of a Multi-Pickup and Delivery Problem with Time Windows

    E-print Network

    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

  7. 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.

  8. SIMULTANEOUS OPTIMIZATION OF TALLIES; IN DIFFICULT SHIELDING PROBLEMS

    SciTech Connect

    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.

  9. Very Large-Scale Neighborhood Search for Solving Multiobjective Combinatorial Optimization Problems

    Microsoft Academic Search

    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

  10. Partially constrained ant colony optimization algorithm for the solution of constrained optimization problems: Application to storm water network design

    Microsoft Academic Search

    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

  11. Convex Clustering with Exemplar-Based Models

    PubMed Central

    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.

  12. One-Dimensional Infinite Horizon Nonconcave Optimal Control Problems Arising in Economic Dynamics

    SciTech Connect

    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.

  13. New Hybrid Intelligent Systems to Solve Linear and Quadratic Optimization Problems and Increase Guaranteed Optimal Convergence Speed of Recurrent ANN

    Microsoft Academic Search

    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

  14. Weakly convex sets and modulus of nonconvexity

    E-print Network

    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.

  15. Dynamic Planar Convex Hull Gerth Stlting Brodal ;y Riko Jacob

    E-print Network

    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

  16. A new Primal-Dual Interior-Point Algorithm for Second-Order Cone Optimization

    E-print Network

    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

  17. Human opinion dynamics: an inspiration to solve complex optimization problems.

    PubMed

    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

  18. 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.

  19. Hybrid Ant Colony Optimization Using Memetic Algorithm for Traveling Salesman Problem

    Microsoft Academic Search

    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

  20. Convergence of Pseudospectral Methods for a Class of Discontinuous-Control Nonlinear Optimal Control Problems

    Microsoft Academic Search

    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-

  1. 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.

  2. A scatter learning particle swarm optimization algorithm for multimodal problems.

    PubMed

    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

  3. High-order entropy-based closures for linear transport in slab geometry II: A computational study of the optimization problem

    SciTech Connect

    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.

  4. 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.

  5. Application of particle swarm optimization technique and its variants to generation expansion planning problem

    Microsoft Academic Search

    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

  6. Goedel Machines: Self-Referential Universal Problem Solvers Making Provably Optimal Self-Improvements

    Microsoft Academic Search

    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

  7. A multilevel hybrid optimization of magnetohydrodynamic problems in double-diffusive fluid flow

    Microsoft Academic Search

    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

  8. A Generic Global Optimization Algorithm for the Chemical and Phase Equilibrium Problem

    E-print Network

    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

  9. Comparison of derivative-free optimization methods for groundwater supply and hydraulic capture community problems

    Microsoft Academic Search

    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

  10. LSNNO, a FORTRAN subroutine for solving large-scale nonlinear network optimization problems

    Microsoft Academic Search

    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.

  11. SAT-decoding in evolutionary algorithms for discrete constrained optimization problems

    Microsoft Academic Search

    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

  12. A NUMERICAL SHAPE OPTIMIZATION FRAMEWORK FOR GENERIC PROBLEMS SOLVED ON UNSTRUCTURED

    E-print Network

    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

  13. Improved Particle Swarm Optimization with a Collective Local Unimodal Search for Continuous Optimization Problems

    PubMed Central

    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

  14. Improved particle swarm optimization with a collective local unimodal search for continuous optimization problems.

    PubMed

    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

  15. Gerrymandering and Convexity

    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…

  16. Tropical Convex Hull Computations

    Microsoft Academic Search

    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

  17. Interior Point Methods for Optimal Experimental Designs Zhaosong Lu

    E-print Network

    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

  18. A dual neural network for convex quadratic programming subject to linear equality and inequality constraints

    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.

  19. Convexity recognition of the union of polyhedra

    Microsoft Academic Search

    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),

  20. Necessary Optimality Conditions for Some Control Problems of Elliptic Equations with Venttsel Boundary Conditions

    SciTech Connect

    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.

  1. Necessary Optimality Conditions for Some Control Problems of Elliptic Equations with Venttsel Boundary Conditions

    E-print Network

    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.

  2. 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.

  3. A Particle Swarm Optimization Algorithm with Path Relinking for the Location Routing Problem

    Microsoft Academic Search

    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

  4. Effectiveness-Equity Models for Facility Location Problems on Tree ...

    E-print Network

    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.

  5. Advancement and analysis of Gauss pseudospectral transcription for optimal control problems

    E-print Network

    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 ...

  6. 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.

  7. A Memetic Cooperative Optimization Schema and Its Application to the Tool Switching Problem

    Microsoft Academic Search

    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

  8. Problem Set 6 SOLUTION -Do Not Distribute

    E-print Network

    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.1­8.3. Goals · Practice solving integer

  9. ON THE RECONSTRUCTION OF CONVEX SETS FROM RANDOM NORMAL MEASUREMENTS

    E-print Network

    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

  10. Approximating extreme points of infinite dimensional convex sets

    E-print Network

    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

  11. Aircraft Routing -A Global Optimization Problem Michael C Bartholomew-Biggs

    E-print Network

    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

  12. 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.

  13. Eigenvalue optimization

    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).

  14. Optimal experimental design applied to DC resistivity problems

    E-print Network

    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 ...

  15. A Note on the Optimal Single Copy Measurement for the Hidden Subgroup Problem

    E-print Network

    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.

  16. Computationally Efficient Optimal Solutions to the Lot-Sizing Problem in Multistage Assembly Systems

    Microsoft Academic Search

    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

  17. 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.

  18. A Synergistic Approach of Desirability Functions and Metaheuristic Strategy to Solve Multiple Response Optimization 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.

  19. Random Convex Hulls and Extreme Value Statistics

    E-print Network

    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)].

  20. 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].

  1. Capacity Optimizing Power Allocation in Interference Channels

    Microsoft Academic Search

    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

  2. Optimal ecosystem management with structural dynamics

    Microsoft Academic Search

    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

  3. Introduction to Stochastic Optimization Part 4: Multi-stage decision problems

    E-print Network

    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

  4. Convex Graph Invariants

    E-print Network

    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 ...

  5. A Honey-bee Mating Optimization Algorithm for Educational Timetabling Problems

    E-print Network

    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

  6. Existence of a solution for complete least squares optimal shape problems

    Microsoft Academic Search

    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

  7. On Some Optimal Control Problems for Electric Circuits Kristof Altmann, Simon Stingelin, and Fredi Troltzsch

    E-print Network

    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

  8. Optimal control as a regularization method for ill-posed problems

    E-print Network

    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

  9. Second Order Sufficient Optimality Conditions for a Control Problem with Continuous and Bang-Bang

    E-print Network

    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

  10. 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)

  11. Optimal Control Study of Interception Problems Prof. Hugh H.T. Liu

    E-print Network

    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

  12. Exact slow–fast decomposition of the nonlinear singularly perturbed optimal control problem

    Microsoft Academic Search

    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

  13. Exact slow{fast decomposition of the nonlinear singularly perturbed optimal control problem

    Microsoft Academic Search

    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

  14. Coarse-grained parallel genetic algorithm applied to a nuclear reactor core design optimization problem

    Microsoft Academic Search

    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

  15. Application of derivative-free methodologies to generally constrained oil production optimization problems

    Microsoft Academic Search

    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

  16. Particle swarm optimization algorithm for single machine total weighted tardiness problem

    Microsoft Academic Search

    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

  17. Using quantum-behaved particle swarm optimization algorithm to solve non-linear programming problems

    Microsoft Academic Search

    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

  18. Hardware Software Partitioning Problem in Embedded System Design Using Particle Swarm Optimization Algorithm

    Microsoft Academic Search

    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

  19. Convexity in oriented graphs

    Microsoft Academic Search

    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

  20. Domain decomposition methods for advection dominated linear-quadratic elliptic optimal control problems.

    SciTech Connect

    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.

  1. Modeling and optimization of the capacity allocation problem with constraints

    Microsoft Academic Search

    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

  2. Combinatorial Optimization Solutions for the Maximum Quartet Consistency Problem

    Microsoft Academic Search

    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

  3. Parallel-vector computation for structural analysis and nonlinear unconstrained optimization problems. Final Report, period ending 15 Jun. 1990

    Microsoft Academic Search

    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

  4. 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.

  5. On Convex Relaxations for Quadratically Constrained Quadratic ...

    E-print Network

    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.

  6. Methodological Problems in Evolutionary Biology. XI. Optimal Foraging Theory Revisited

    Microsoft Academic Search

    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

  7. Optimal experimental design and some related control problems

    Microsoft Academic Search

    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.

  8. A fast Ant Colony Optimization for traveling salesman problem

    Microsoft Academic Search

    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

  9. Solving Multiobjective Optimization Problems Using an Artificial Immune System

    Microsoft Academic Search

    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

  10. 1 INTRODUCTION We consider the optimization problem of distrib-

    E-print Network

    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

  11. Asymptotic method for solving the time-optimal control problem for a nonlinear singularly perturbed system

    Microsoft Academic Search

    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.

  12. Enzyme allocation problems in kinetic metabolic networks: optimal solutions are elementary flux modes.

    PubMed

    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

  13. Discrete bat algorithm for optimal problem of permutation flow shop scheduling.

    PubMed

    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

  14. Discrete Bat Algorithm for Optimal Problem of Permutation Flow Shop Scheduling

    PubMed Central

    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

  15. The Open Problems Project edited by Erik D. Demaine Joseph S. B. Mitchell

    E-print Network

    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

  16. The Open Problems Project edited by Erik D. Demaine Joseph S. B. Mitchell

    E-print Network

    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

  17. A Collection of Challenging Optimization Problems in Science, Engineering and Economics

    E-print Network

    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...

  18. Parallel Multi-Swarm Optimization Framework for Search Problems in Water Distribution Systems

    E-print Network

    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

  19. New evolutionary genetic algorithms for NP-complete combinatorial optimization problems

    Microsoft Academic Search

    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

  20. A descriptor system approach to nonlinear singularly perturbed optimal control problem

    Microsoft Academic Search

    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

  1. A Global Optimization Method for the Molecular Replacement Problem in X-ray Crystallography

    E-print Network

    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

  2. Experimental study on population-based incremental learning algorithms for dynamic optimization problems

    Microsoft Academic Search

    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

  3. A discrete particle swarm optimization algorithm for the generalized traveling salesman problem

    Microsoft Academic Search

    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

  4. How to Solve a Semi-infinite Optimization Problem

    E-print Network

    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-.

  5. Algorithms for discrete, non-linear and robust optimization problems with applications in scheduling and service operations

    E-print Network

    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 ...

  6. Islanding model for preventing wide-area blackouts and the issue of local solutions of the optimal power flow problem

    E-print Network

    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 ...

  7. A Numerical Method to solve Optimal Transport Problems with Coulomb Cost

    E-print Network

    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.

  8. Ball and Spindle Convexity with respect to a Convex Body

    E-print Network

    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...

  9. Continuous Blooming of Convex Polyhedra

    E-print Network

    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 ...

  10. Newton's method for large bound-constrained optimization problems.

    SciTech Connect

    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.

  11. Convex Quantum Logic

    E-print Network

    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.

  12. Convexity Recognition of the Union of Polyhedra

    Microsoft Academic Search

    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-

  13. 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.

  14. 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].

  15. Shortfall as a risk measure: properties, optimization and applications

    Microsoft Academic Search

    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

  16. A New Method for Mapping Optimization Problems onto Neural Networks

    E-print Network

    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

  17. GLOBAL OPTIMIZATION FOR ONE-DIMENSIONAL STRUCTURE AND MOTION PROBLEMS

    E-print Network

    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

  18. A "HUM" conjugate gradient algorithm for constrained nonlinear optimal control : terminal and regular problems

    E-print Network

    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 ...

  19. Evolutionary and Deterministic Methods for Design, Optimization and Control with Applications to Industrial and Societal Problems

    E-print Network

    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

  20. Application of Particle Swarm Optimization Algorithm in the Heating System Planning Problem

    PubMed Central

    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

  1. Multi-agent Optimization Design for Multi-resource Job Shop Scheduling Problems

    Microsoft Academic Search

    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

  2. Solving Three-objective Optimization Problems Using Evolutionary Dynamic Weighted

    E-print Network

    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

  3. 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,…

  4. UNIFIED PARTICLE SWARM OPTIMIZATION FOR TACKLING OPERATIONS RESEARCH PROBLEMS

    E-print Network

    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

  5. Random Convex Hulls and Extreme Value Statistics

    E-print Network

    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...

  6. An Optimal Algorithm for the Distinct Elements Problem Daniel M. Kane

    E-print Network

    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

  7. An Optimal Algorithm for the Distinct Elements Problem Daniel M. Kane #

    E-print Network

    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

  8. The Multi-robot Coverage Problem for Optimal Coordinated Search with an Unknown Number of Robots

    E-print Network

    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

  9. On the optimal and suboptimal nonlinear filtering problem for discrete-time systems

    Microsoft Academic Search

    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

  10. The Trust Region Sequential Quadratic Programming method applied to two-aircraft acoustic optimal control problem

    E-print Network

    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

  11. Convergence Proof for a Monte Carlo Method for Combinatorial Optimization Problems

    E-print Network

    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

  12. A new decision making approach for optimization of multiple response problem

    Microsoft Academic Search

    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

  13. Collocation and inversion for a reentry optimal control problem Tobias NECKEL 1

    E-print Network

    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

  14. Ant colony optimization combined with taboo search for the job shop scheduling problem

    Microsoft Academic Search

    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

  15. Particle Swarm Optimization Algorithm for Makespan and Maximum Lateness Minimization in Permutation Flowshop Sequencing Problem

    Microsoft Academic Search

    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

  16. Improved chaotic particle swarm optimization algorithm for dynamic economic dispatch problem with valve-point effects

    Microsoft Academic Search

    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

  17. GA-Hardness of Aerodynamic Optimization Problems: Analysis and Proposed Cures

    Microsoft Academic Search

    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

  18. A study of altitude and flight path angle dynamics for a singularly perturbed fuel optimization problem

    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.

  19. Solution techniques for some allocation problems

    Microsoft Academic Search

    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

  20. The optimization research of the multi-response problems based on the SUR.

    PubMed

    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