Your email was sent successfully. Check your inbox.

An error occurred while sending the email. Please try again.

Proceed reservation?

Export
Filter
  • linear programming  (7)
  • duality  (5)
  • 1
    Electronic Resource
    Electronic Resource
    Springer
    ISSN: 1432-5217
    Keywords: linear programming ; projective algorithms ; computation of descent directions ; polynomial complexity
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Description / Table of Contents: Zusammenfassung Zur Lösung linearer Optimierungsaufgaben beschreiben und bewerten wir Abstiegsrichtungen bei projektiven Methoden in der Formulierung von de Ghellinck and Vial (1986). Es zeigt sich, daß bei Wahl von Suchrichtungen aus dem projizierten Simplex um 1 im transformierten Raum stets polynomiale Laufzeitabschätzungen gelten. Insbesondere die Projektion der 1 stimmt mit der von de Ghellinck and Vial (1986) gewählten Suchrichtung überein, die bekanntlich bei zulässiger Startlösung äquivalent zu Karmarkar's Suchrichtung ist. Nahe bei dieser Suchrichtung bleibt die Komplexität der Methode unverändert [0(nL) Iterationen], während im allgemeinen die Schranke 0(n2 ·L) gilt, wobeiL die Größe des Linearen Optimierungsproblemes beschreibt. Die Untersuchungen zielen nicht darauf ab, Schranken für den ungünstigsten Fall zu verbessern, sondern sollen die freie Wahl von Suchrichtungen aus einer großen Klasse „polynomialer“ Richtungen zulassen. Wir zeigen, wie man unterschiedliche Suchrichtungen innerhalb einer Iteration aus der Projektion der 1 mit relativ kleinem zusätzlichen Aufwand berechnen kann. In projektiven Methoden wird die Lineare Optimierungsaufgabe als einparametrisches Zulässigkeitsproblem reformuliert, wobei als Parameter die jeweils bekannte obere Schranke des Optimalwertes dient. Daher ist es sehr wichtig, diese Schranke bei jeder Gelegenheit zu verbessern. Durch Verallgemeinerung von Schranken aus de Ghellinck and Vial (1986) leiten wir einige Unzulässigkeitstests her. Insbesondere liefert jede berechnete Suchrichtung eine obere Schranke, die möglicherweise die bekannte obere Schranke verbessert. Alle Schranken können durch Lösung einer Reihe einfacher linearer und quadratischer Gleichungen berechnet werden.
    Notes: Abstract For solving linear programming problems, we describe and evaluate descent directions for projective methods in the setting of the method of de Ghellinck and Vial (1986). It is shown that choosing search directions from the projected simplex centered at 1 in transformed space guarantees a polynomial time bound. In particular, the projection of 1 coincides with the direction chosen by de Ghellinck and Vial (1986) which is well known to be equivalent to Karmarkar's search direction when the initial solution is feasible. Close to that search direction the complexity of the method is unchanged [0(nL) iterations] while in general the bound is 0(n2 ·L), whereL is the size of the linear programming problem. The investigations were not made in order to improve worst case bounds, but rather to enable a free choice of search directions from a quite large class of “polynomial” directions. We show how different directions can be computed in one iteration using the projection of 1 with relatively small extra computational effort. In projective methods linear programming is reformulated as one-parametric feasibility problem where the parameter is the currently known upper bound on the optimal value. It is therefore very important to improve that bound whenever possible. Generalizing bounds from de Ghellinck and Vial (1986) we prove some infeasibility criteria. In particular, any computed search direction yields some upper bound which eventually improves that currently used. All bounds can be computed by solving sets of simple linear and quadratic equations.
    Type of Medium: Electronic Resource
    Signatur Availability
    BibTip Others were also interested in ...
  • 2
    Electronic Resource
    Electronic Resource
    Springer
    ISSN: 1432-5217
    Keywords: Generalized convexity ; duality ; root term ; optimal solution
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Notes: Abstract We extend the duality theorems for a class of nondifferentiable problems with Mond-Weir type duals.
    Type of Medium: Electronic Resource
    Signatur Availability
    BibTip Others were also interested in ...
  • 3
    ISSN: 1432-5217
    Keywords: Multi-chain Markov Decision Processes ; average cost criterion ; state-action frequencies ; deviation measure ; linear programming ; lagrange formulation
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Notes: Abstract Linear Programming is known to be an important and useful tool for solving Markov Decision Processes (MDP). Its derivation relies on the Dynamic Programming approach, which also serves to solve MDP. However, for Markov Decision Processes with several constraints the only available methods are based on Linear Programs. The aim of this paper is to investigate some aspects of such Linear Programs, related to multi-chain MDPs. We first present a stochastic interpretation of the decision variables that appear in the Linear Programs available in the literature. We then show for the multi-constrained Markov Decision Process that the Linear Program suggested in [9] can be obtained from an equivalent unconstrained Lagrange formulation of the control problem. This shows the connection between the Linear Program approach and the Lagrange approach, that was previously used only for the case of a single constraint [3, 14, 15].
    Type of Medium: Electronic Resource
    Signatur Availability
    BibTip Others were also interested in ...
  • 4
    Electronic Resource
    Electronic Resource
    Springer
    ISSN: 1432-5217
    Keywords: Quasi-inverse ; epi-inverse ; hypo-inverse ; nondecreasing functions ; quasiconvex functions ; convex functions ; duality ; rearrangement ; modulus of continuity
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Description / Table of Contents: Zusammenfassung In dieser Arbeit wird systematisch die Umkehrung monoton nichtfallender Funktionenf: ℝ → ℝ ∪ {−∞, +∞} studiert. Die Ergebnisse bilden die Grundlage für eine neue Dualitätstheorie quasikonvexer Probleme [6]. Da jedoch die Fragestellung bei einer ganzen Anzahl weiterer Situationen auftritt, verdient sie eine gesonderte Behandlung. Anwendungen in der Topologie, Wahrscheinlichkeitstheorie, monotonen Umordnungen und in der konvexen Analysis werden aufgezeigt und skizziert.
    Notes: Abstract This work is devoted to a systematic study of the inversion of nondecreasing one variable extended real-valued functions. Its results are preparatory for a new duality theory for quasiconvex problem [6]. However the question arises in a variety of situations and as such deserves a separate treatment. Applications to topology, probability theory, monotone rearrangements, convex analysis are either pointed out or sketched.
    Type of Medium: Electronic Resource
    Signatur Availability
    BibTip Others were also interested in ...
  • 5
    ISSN: 1432-5217
    Keywords: linear programming ; programming in conditions of uncertainty ; sensitivity ; interval and finite arithmetic ; systems of equations
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Notes: Abstract This note gives a synopsis of new methods for solving linear systems and linear programming problems with uncertain data. All input data can vary between given lower and upper bounds. The methods calculate very sharp and guaranteed error bounds for the solution set of those problems and permit a rigorous sensitivity analysis. For problems with exact input data in general the calculated bounds differ only in the last bit in the mantissa, i.e. they are of maximum accuracy.
    Type of Medium: Electronic Resource
    Signatur Availability
    BibTip Others were also interested in ...
  • 6
    Electronic Resource
    Electronic Resource
    Springer
    ISSN: 1432-5217
    Keywords: vectorial control-approximation problem ; vectorial location problem ; duality ; efficiency
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Description / Table of Contents: Zusammenfassung In der Arbeit werden für eine Klasse von vektoriellen Steuer-Approximationsproblemen in reellen reflexiven Banachräumen vektorielle Dualprobleme konstruiert und Dualitätseigenschaften hergeleitet. Als Spezialfall ergeben sich entsprechende Aussagen für vektorielle Standortprobleme.
    Notes: Abstract The author formulates vectorial dual problems for a certain class of vectorial control-approximation problems in real reflexive Banach spaces. A number of propositions concerning duality are derived. Corresponding propositions are mentioned for the special case of the vectorial location problems.
    Type of Medium: Electronic Resource
    Signatur Availability
    BibTip Others were also interested in ...
  • 7
    ISSN: 1432-5217
    Keywords: Markov decision processes ; countable state space ; Linear programming ; duality
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Notes: Abstract We present an Linear Programming formulation of MDPs with countable state and action spaces and no unichain assumption. This is an extension of the Hordijk and Kallenberg (1979) formulation in finite state and action spaces. We provide sufficient conditions for both existence of optimal solutions to the primal LP program and absence of duality gap. Then, existence of a (possibly randomized) average optimal policy is also guaranteed. Existence of a stationary average optimal deterministic policy is also investigated.
    Type of Medium: Electronic Resource
    Signatur Availability
    BibTip Others were also interested in ...
  • 8
    ISSN: 1432-5217
    Keywords: Markov decision processes ; partially observable ; linear programming
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Notes: Abstract In this paper we use an approach which uses a superharmonic property of a sequence of functions generated by an algorithm to show that these functions converge in a non-increasing manner to the optimal value function for our problem, and bounds are given for the loss of optimality if the computational process is terminated at any iteration. The basic procedure is to add an additional linear term at each iteration, selected by solving a particular optimisation problem, for which primal and dual linear programming formulations are given.
    Type of Medium: Electronic Resource
    Signatur Availability
    BibTip Others were also interested in ...
  • 9
    ISSN: 1432-5217
    Keywords: Ellipsoid method ; linear programming ; simplex ; volume
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Notes: Abstract Yamnitsky and Levin proposed a variant of Khachiyan's ellopsoid method for testing feasibility of systems of linear inequalities that also runs in polynomial time but uses simplices instead of ellipsoids. Starting with then-simplexS and the half-space {x¦a Tx ≤ β}, the algorithm finds a simplexS YL of small volume that enclosesS ∩ {x¦a Tx ≤ β}. We interpretS YL as a simplex obtainable by point-sliding and show that the smallest such simplex can be determined by minimizing a simple strictly convex function. We furthermore discuss some numerical results. The results suggest that the number of iterations used by our method may be considerably less than that of the standard ellipsoid method.
    Type of Medium: Electronic Resource
    Signatur Availability
    BibTip Others were also interested in ...
  • 10
    Electronic Resource
    Electronic Resource
    Springer
    ISSN: 1432-5217
    Keywords: Optimization theory ; mathematical programming ; duality ; half spaces ; minimum norm duality ; separating hyperplanes
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Notes: Abstract This note shows that half spaces play a very special role in the development of duality. In addition to the minimum norm duality, the duality in linear programming, and Wolfe's and Johri's formulations in nonlinear programming can all be derived via half spaces by following an identical five step procedure.
    Type of Medium: Electronic Resource
    Signatur Availability
    BibTip Others were also interested in ...
Close ⊗
This website uses cookies and the analysis tool Matomo. More information can be found here...