共查询到20条相似文献,搜索用时 0 毫秒
1.
2.
J. Lewin 《Journal of Optimization Theory and Applications》1976,18(3):429-432
The solution given by Isaacs to the bang-bang-bang problem is shown to be a solution in aweak sense only. A solution in a stronger sense is demonstrated involving the notions of extended closed-loop strategies and of extended value-function. The bang-bang-bang singular surface is interpreted in a new way.The author is grateful to Professor J. V. Breakwell for his criticism and valuable remarks. 相似文献
3.
We take another look at the problem of intersecting rectangles with parallel sides. For this we derive a one-pass, time optimal algorithm which is easy to program, generalizes tod dimensions well, and illustrates a basic duality in its data structures and approach.The work of the first author was supported by the DAAD (Deutscher Akademischer Austauschdienst) and carried out while visiting McMaster University as a postdoctoral fellow. The work of the second author was supported by a Natural Sciences and Engineering Research Council of Canada Grant No. A-7700. 相似文献
4.
5.
Mihály Bessenyei 《Indagationes Mathematicae》2018,29(3):873-877
The aim of this note is to characterize in terms of inequalities those pairs of real functions (acting on a convex subset of a vector space) that possess an affine separator. The main result is originally due to Behrends and Nikodem. Their method is based on the Hahn–Banach Theorem and a variant of the Helly Theorem. In our approach, a direct and independent proof is presented via the Radon and the Helly Theorems. 相似文献
6.
7.
Ronald L. Smith 《Linear algebra and its applications》2008,429(7):1442-1452
In [R. Grone, C.R. Johnson, E. Sa, H. Wolkowicz, Positive definite completions of partial Hermitian matrices, Linear Algebra Appl. 58 (1984) 109-124] the positive definite (semi-) completion problem in which the underlying graph is chordal was solved. For the positive definite case, the process was constructive and the completion was obtained by completing the partial matrix an entry at a time. For the positive semidefinite case, they obtained completions of a particular sequence of partial positive definite matrices with the same underlying graph and noted that there is a convergent subsequence of these completions that converges to the desired completion. Here, in the chordal case, we provide a constructive solution, based entirely on matrix/graph theoretic methods, to the positive (semi-)definite completion problem. Our solution associates a specific tree (called the “clique tree” [C.R. Johnson, M. Lundquist, Matrices with chordal inverse zero-patterns, Linear and Multilinear Algebra 36 (1993) 1-17]) with the (chordal) graph of the given partial positive (semi-)definite matrix. This tree structure allows us to complete the matrix a “block at a time” as opposed to an “entry at a time” (as in Grone et al. (1984) for the positive definite case). In Grone et al. (1984), using complex analytic techniques, the completion for the positive definite case was shown to be the unique determinant maximizing completion and was shown to be the unique completion that has zeros in its inverse in the positions corresponding to the unspecified entries of the partial matrix. Here, we show the same using only matrix/graph theoretic tools. 相似文献
8.
J. Lewin 《Journal of Optimization Theory and Applications》1986,49(3):411-430
A pursuerP, whose speed is bounded by 1, wants to get closer to an evaderE, whose speed is bounded by >1.P wants to reduce his distancePE fromE below the capture radius . Both players are confined to a circular arena. This problem is equivalent to a problem discussed by Flynn, who characterized and gave numerical bounds to the least upper boundd* on the values ofPE thatE can maintain. He used direct methods and did not use Isaacs' theory.We solve our problem relying on the theory of singular surfaces in differential games. We construct and investigate barriers of the game of kind, and we replace Flynn's bounds ond* by analytical (exact) values for various speeds .The support of the TW Department of THT, Enschede, Holland, is gratefully acknowledged. 相似文献
9.
The generalized linear complementarity problem revisited 总被引:5,自引:0,他引:5
Given a vertical block matrixA, we consider in this paper the generalized linear complementarity problem VLCP(q, A) introduced by Cottle and Dantzig. We formulate this problem as a linear complementarity problem with a square matrixM, a formulation which is different from a similar formulation given earlier by Lemke. Our formulation helps in extending many
well-known results in linear complementarity to the generalized linear complementarity problem. We also show that the class
of vertical block matrices which Cottle and Dantzig's algorithm can process is the same as the class of equivalent square
matrices which Lemke's algorithm can process. We also present some degree-theoretic results on a vertical block matrix. 相似文献
10.
Marco Chiarandini Luca Di Gaspero Stefano Gualandi Andrea Schaerf 《Journal of Heuristics》2012,18(1):119-148
The Balanced Academic Curriculum Problem (BACP) consists in assigning courses to teaching terms satisfying prerequisites and
balancing the credit course load within each term. The BACP is part of the CSPLib with three benchmark instances, but its
formulation is simpler than the problem solved in practice by universities. In this article, we introduce a generalized version
of the problem that takes different curricula and professor preferences into account, and we provide a set of real-life problem
instances arisen at University of Udine. Since the existing formulation based on a min–max objective function does not balance
effectively the credit load for the new instances, we also propose alternative objective functions. Whereas all the CSPLib
instances are efficiently solved with Integer Linear Programming (ILP) state-of-the-art solvers, our new set of real-life
instances turns out to be much more challenging and still intractable for ILP solvers. Therefore, we have designed, implemented,
and analyzed heuristics based on local search. We have collected computational results on all the new instances with the proposed
approaches and assessed the quality of solutions with respect to the lower bounds found by ILP on a relaxed and decomposed
problem. Results show that a selected heuristic finds solutions of quality at 9%–60% distance from the lower bound. We make
all data publicly available, in order to stimulate further research on this problem. 相似文献
11.
12.
Weronika Barwicz 《Journal of Mathematical Analysis and Applications》2010,366(2):663-672
We present a new computation of the Birkhoff normal form for the Hamiltonian of the restricted three body problem near the Lagrangian libration points. This leads to a new proof of the Lyapunov stability of these points. 相似文献
13.
The central warehouse location problem revisited 总被引:1,自引:0,他引:1
Drezner Zvi; Scott Carlton; Song Jing-Sheng 《IMA Journal of Management Mathematics》2003,14(4):321-336
This paper is concerned with the optimal location of a centralwarehouse, given a fixed number and the locations of the localwarehouses. We investigate whether the solution determined bythe traditional model that minimizes total transportation costdiffers from the one determined by a model that also takes intoaccount the inventory and service costs. We build simple modelsto address this question. Numerical results show that ignoringinventory costs in modelling location models may lead to inferiorlocation solutions. 相似文献
14.
The two-dimensional cutting stock problem revisited 总被引:1,自引:0,他引:1
In the strip packing problem (a standard version of the two-dimensional cutting stock problem), the goal is to pack a given set of rectangles into a vertical strip of unit width so as to minimize the total height of the strip needed. The k-stage Guillotine packings form a particularly simple and attractive family of feasible solutions for strip packing. We present a complete analysis of the quality of k-stage Guillotine strip packings versus globally optimal packings: k=2 stages cannot guarantee any bounded asymptotic performance ratio. k=3 stages lead to asymptotic performance ratios arbitrarily close to 1.69103; this bound is tight. Finally, k=4 stages yield asymptotic performance ratios arbitrarily close to 1.Steve Seiden died in a tragic accident on June 11, 2002. This paper resulted from a number of email discussions between the authors in spring 2002. 相似文献
15.
《Stochastic Processes and their Applications》2005,115(9):1437-1450
A change in the arrival rate of a Poisson process sometimes necessitates immediate action. If the change time is unobservable, then the design of online change detection procedures becomes important and is known as the Poisson disorder problem. Formulated and partially solved by Davis [Banach Center Publ., 1 (1976) 65–72], the standard Poisson problem addresses the tradeoff between false alarms and detection delay costs in the most useful way for applications. In this paper we solve the standard problem completely and describe efficient numerical methods to calculate the policy parameters. 相似文献
16.
The min-edge clique partition problem asks to find a partition of the vertices of a graph into a set of cliques with the fewest edges between cliques. This is a known NP-complete problem and has been studied extensively in the scope of fixed-parameter tractability (FPT) where it is commonly known as the Cluster Deletion problem. Many of the recently-developed FPT algorithms rely on being able to solve Cluster Deletion in polynomial time on restricted graph structures. 相似文献
17.
Multi-Armed bandit problem revisited 总被引:1,自引:0,他引:1
In this paper, we revisit aspects of the multi-armed bandit problem in the earlier work (Ref. 1). An alternative proof of the optimality of the Gittins index rule is derived under the discounted reward criterion. The proof does not involve an explicit use of the interchange argument. The ideas of the proof are extended to derive the asymptotic optimality of the index rule under the average reward criterion. Problems involving superprocesses and arm-acquiring bandits are also reexamined. The properties of an optimal policy for an arm-acquiring bandit are discussed.This research was supported by NSF Grant IRI-91-20074. 相似文献
18.
V. K. Srinivasan 《International Journal of Mathematical Education in Science & Technology》2013,44(6):934-937
There are many nice problems in the theory of geometric series. The famous problem where atiny bird flies repeatedly between two trains approaching each other on the same track from opposite ends is analysed in this paper. While the common sense solution is very quick and clever, there are very nice things that students in a calculus course can learn by taking the infinite series route. 相似文献
19.
We consider branch and bound methods for enclosing all unconstrained global minimizers of a nonconvex nonlinear twice-continuously differentiable objective function. In particular, we consider bounds obtained with interval arithmetic, with the midpoint test, but no acceleration procedures. Unless the lower bound is exact, the algorithm without acceleration procedures in general gives an undesirable cluster of boxes around each minimizer. In a previous paper, we analyzed this problem for univariate objective functions. In this paper, we generalize that analysis to multi-dimensional objective functions. As in the univariate case, the results show that the problem is highly related to the behavior of the objective function near the global minimizers and to the order of the corresponding interval extension.This work was partially funded by National Science Foundation grant # CCR-9203730. 相似文献
20.
Deterministic branch-and-bound algorithms for continuous global optimization often visit a large number of boxes in the neighborhood of a global minimizer, resulting in the so-called cluster problem (Du and Kearfott in J Glob Optim 5(3):253–265, 1994). This article extends previous analyses of the cluster problem in unconstrained global optimization (Du and Kearfott 1994; Wechsung et al. in J Glob Optim 58(3):429–438, 2014) to the constrained setting based on a recently-developed notion of convergence order for convex relaxation-based lower bounding schemes. It is shown that clustering can occur both on nearly-optimal and nearly-feasible regions in the vicinity of a global minimizer. In contrast to the case of unconstrained optimization, where at least second-order convergent schemes of relaxations are required to mitigate the cluster problem when the minimizer sits at a point of differentiability of the objective function, it is shown that first-order convergent lower bounding schemes for constrained problems may mitigate the cluster problem under certain conditions. Additionally, conditions under which second-order convergent lower bounding schemes are sufficient to mitigate the cluster problem around a global minimizer are developed. Conditions on the convergence order prefactor that are sufficient to altogether eliminate the cluster problem are also provided. This analysis reduces to previous analyses of the cluster problem for unconstrained optimization under suitable assumptions. 相似文献