Questions tagged [dynamic-programming]
Dynamic programming is a mathematical optimization/programming approach applicable if an optimal solution can be constructed efficiently from optimal solutions of its subproblems. A classic example is the Towers of Hanoi.
583
questions
0
votes
0
answers
13
views
Special Case - How to generate a formula to calculate where next additional items in a set of items, in a particular row and at a particular index
I've tried to generate a simple formula to do this calculation but I've not successfully arrived at a working formula.
Here, I have a list of items displayed in a grid.
Let's use these symbols
...
4
votes
0
answers
47
views
Calculate probability of flipping coins with probabilities dependent on previous results
Let's say I have a biased coin that has a probability of 0.2 for heads and 0.8 for tails. If you flip it 6 times without getting a heads however, the probability of heads increases by 0.2 per non-...
0
votes
0
answers
18
views
Dynamic programming algorithm to maximize job execution steps on two machines
I have a problem that requires finding a plan to execute a job on two machines, A and B, or moving the job between machines to maximize the number of executed steps. Specifically, in each time ...
- 1
0
votes
0
answers
15
views
How can I prove the contraction property on a joint system of equations?
I'm studying a simple dynamic programming problem whose solution is a system of Bellman equations, and am running into some issues trying to prove the Contraction Mapping Theorem for the system as a ...
- 1
0
votes
0
answers
25
views
Value iteration, Bellman [closed]
can someone please explain how V2 values are calculated in this picture. I have a pretty good understanding of Bellman equation, or at least I think I do. But when I calculate it, my v2 Values turn ...
- 3
0
votes
2
answers
70
views
repeatedly XOR n-bit string - probability of getting all 1s
Start with n-bits of all 0s
Each round, generate a n-bit string, delta, with probability of getting a 1 being p.
Output of the ...
- 111
-1
votes
0
answers
12
views
Random Dynamical System
there are two questions here, but I have no ideas at all about it, can you give a clue or book recommendation?
zoom
1
vote
2
answers
54
views
A Basic Question of Continuous Time Macroeconomic Model (Variation of Constant to Solve an ODE)
I am going through the continuous time macro slides by Ben Moll (link is: https://benjaminmoll.com/wp-content/uploads/2019/07/Lecture2_ECO521.pdf), when deriving New keynesian model in continuous time,...
- 21
2
votes
1
answer
51
views
Optimal Edition from string $X$ to string $Y$
$\newcommand{\restrict}[2]{{#1}\restriction_{#2}}$
$\newcommand{\cardinal}[1]{\abs{#1}}$
$\newcommand{\abs}[1]{\left\lvert #1 \right\rvert}$
$\newcommand{\append}[2]{\operatorname{ap}\left(#1,#2\right)...
- 1,748
0
votes
1
answer
19
views
Is there always an optimal deterministic policy in MDPs with a continuous state space?
It is well known that in MDPs with a discrete state space, there exists a deterministic policy that is optimal, in the sense that it maximizes the total expected discounted reward from any initial ...
- 63
0
votes
0
answers
64
views
Solving a Stochastic Dynamic Programming with Vector State
Consider the following stochastic dynamic program (SDP):
$$
V_t(\textbf{s}_t)= \max_{\textbf{a}_t\in A_t(x_t)} \{(1-\lambda(a_t))V_{t+1}(\textbf{s}_t) + \lambda(a_t)(r_t(a_t)+V_{t+1}(\textbf{s}_t-\...
0
votes
0
answers
27
views
A strategy for photographer using limited camera and films to take photos for all houses
I was asked a question about developing strategy for a photographer. This guy has a camera which can take maximum $n$ photos. And he hangs on the street consisting $p$ houses. He wants to take photos ...
- 39
0
votes
0
answers
34
views
Solving a functional equation with dynamic programming (Preparation for mathematics competition)
This question is based a bit on an "Ansatz" but I hope my intuition is right.
I was practising functional equations for a mathematics competition and I encountered the following equation:
$f(...
- 15
-2
votes
1
answer
70
views
Interviews of students with professors [closed]
A professor interviews n students, and each student enters the interview in turn. The student only needs to answer how many people can pass the interview. The professor can freely decide whether the ...
- 39
0
votes
1
answer
39
views
Adding a linear term to the quadratic cost function in the LQR controller design
I am basically trying to see the effect of adding a linear term to the conventional quadratic cost function used in the design of LQR controller for a finite horizon, free terminal state, discrete ...
1
vote
1
answer
76
views
How can I derive Bellman's principle of optimality in discrete-time?
In the context of discrete-time optimal control theory, Bellman's principle of optimality is useful for efficiently determining the control signal $\{u_k\}_{k=0}^{N-1}$ that minimizes the following ...
- 988
0
votes
1
answer
163
views
closed-form solution to a recursive function
My question is about this problem I made up:
'I have a height of unit length, and m glass balls. Dropping a ball higher than some unknown height, h, always breaks them, and dropping a ball lower never ...
- 3
0
votes
0
answers
27
views
Solving non-linear problems with dynamic programming
I am trying to understand the following dynamic programming problem:
Let's consider the following problem
Problem
We want to solve it using dynamic programming, we give the following:
Steps (n): ...
- 1
0
votes
0
answers
13
views
Minimization of average distance in graph by adding $k$ edges
Let $G=(V,E)$ be a graph. WLOG, length of all edges are one. For each two vertices $v,v'\in V$ there exist at least one path and the shortest path between them has distance $d(v,v')$. The mean length ...
- 747
-2
votes
1
answer
77
views
Prove $T(n)=2F(n+1)-1$ by induction. Please read body for full question. [closed]
Given : $F(n)=F(n-1)+F(n-2)$ with $F(0)=0$ and $F(1)=1$. $T(n)$ is the total number of calls needed to calculate $F(n)$ using top-down approach.
By writing top-down approach program, I have calculated ...
0
votes
0
answers
33
views
What algorithm can be used to solve the shortest path problem with timetable data?
Given public transport timetable data, what algorithms are available to find the quickest journey time between two given points? Typically, Dijkstra's algorithm and variants are used to find the ...
- 169
0
votes
1
answer
78
views
Minimizing Euclidean distance between target and sum of selected vectors
I have multiple category sets of food $A,B,...$, each with nutritional information encoded in a vector $x_{a_1},x_{a_2},..., x_{b_1},x_{b_2},...$. I also have a vector, $y$, which encodes the target ...
0
votes
0
answers
26
views
A continuous time model where Nash equilibrium is build in a dynamic programming setting or as a system of backward looking SDEs?
I am looking for a continuous time model, that builds a game among a continuum of agents who interact strategically and they have mean-variance utility function. In particular mean-variance utility ...
- 75
0
votes
1
answer
31
views
Weight Optimization
I was had a question about optimizing for the longest distance travelled.
Suppose there is a highway which we can use to travel for a specific distance based on a set of fee rules involving 3 types of ...
- 141
1
vote
0
answers
29
views
Dynamic Nash Bargaining Solution
Static Game
Let $i \in \{1, 2\}$ denote a player.
Each player can execute an action $a_i \in A_i$, where $A_i \subseteq \mathbb R$ denotes the set of feasible actions.
Given a pair of actions $a = (...
- 737
0
votes
0
answers
48
views
Why should an optimal strategy to this problem be constant?
You are given a 100-sided die. After you roll once, you can choose to either get paid the dollar amount of that roll OR pay one dollar for one more roll. What is the expected value of the game? (There ...
- 348
1
vote
1
answer
24
views
Question about the method of dynamic optimization.
My question is a bit general, but it is more common in solving dynamic optimization. I think dynamic optimization is more like a way of solving problems. We first need to divide the problem into ...
- 348
0
votes
0
answers
41
views
Minimize weight sum on DAG.
Context
In my recent research, I encounter a task assignment problem. Assuming we have a workflow, which is composed of tasks with dependencies. The workflow is a DAG (Directed acyclic graph). For ...
- 1
1
vote
1
answer
102
views
Bin Packing with mutual exclusive items. Goal: Minimum number of bins
I am asking for help for the following problem.
N items. Each Item has to be put into exactly one bin.
C constraints. Each constraints is a pair of items, meaning item x und item y are not allowed in ...
- 33
1
vote
0
answers
39
views
Why do bellman error gradients become big?
I read these notes on deep q learning (DQN) and it said that Bellman error gradients can become pretty big. While watching the lecture video for that slide, the speaker basically said that we are ...
- 231
3
votes
1
answer
121
views
Writing down Bellman equation in recursive macroeconomics world.
Assume an infinite horizon representative agent economy with the following consumer preferences $u(c_t)$
The production technology of this economy uses capital and land, which is fixed amount in ...
- 6,366
0
votes
0
answers
31
views
optimal control: What are the conditions imposed on nonlinear state evolution for a continuous and discrete optimal control problem
I have been looking at some texts on optimal control and its applications in economics. In particular, I am looking at a really nice book by Sydsaeter and Seirstad Further Mathematics for Economic ...
- 1,873
0
votes
0
answers
127
views
The sum of difference in all pairs in an array
I have an array of 2n distinct non-negative integers, the goal is to find if it's possible to put all integers into pairs such that the sum of the absolute difference of all pairs is equal to a ...
- 1
2
votes
1
answer
181
views
Dynamic dice game, how to reasonably estimate answer by hand without laboriously calculating
Here's a question from my probability textbook:
A casino comes up with a fancy dice game. It allows you to roll a dice as many times as you want unless a $6$ appears. After each roll, if $1$ appears, ...
- 1,317
1
vote
1
answer
67
views
Finding the most probable labeling that sums up to some integer
We know that solving the optimization problem such as
$$\max_{y_1, \dots,y_n} \sum_{i=1}^{n-1} f_{i,i+1}(y_i,y_{i+1})$$
$$y_i \in \mathbb{N}_0$$
is easy and can be done via dynamic programming (...
1
vote
1
answer
16
views
How to assign a known number of different size of outbound packages, to a known (different) number of inbound deliveries?
I am trying to solve a problem that looks like the multiple knapsack problem, the multiple bin packing problem and the subset-sum problem, but isn't exactly one of them.
Imagine a warehouse where 4 ...
- 13
0
votes
0
answers
49
views
Solve Value Function Analytically
Say I have a Bellman equation where the state variable is discrete: $$\begin{aligned}
r V(n)=& \max _{\lambda}\{\pi n- nc(\lambda)+ \lambda n[V(n+1)-V(n)]\\
&-\mu n[V(n)-V(n-1)]\}
\end{aligned}...
- 133
0
votes
1
answer
28
views
Dynamic programming efficient network
Hello I have a dynamic programming related question. How can I compute the shortest path in hops from starting vertex u to ending vertex v, with the constrain that the vertices and edges will have an ...
0
votes
1
answer
140
views
Recurrence relations in dynamic programming
I have the following problem:
Assume a truck collects items from a grid with n*n size starting at location (0, 0)and delivers them to a terminal (n, n). The truck can move right, left or down. There ...
0
votes
1
answer
141
views
Is the Bellman-Ford algorithm pseudo-polynomial?
We know that the problem of finding a shortest path that visits each node at most once is NP-hard. It seems to me that Bellman-Ford does that but its time complexity it $O(mn)$ so polynomial. Isn't ...
0
votes
0
answers
39
views
How do I prove this dynamic programming problem?
Given: $y_i$, $w_i$ - variables at stage $i$, $y_{i} \in \mathbb{R}$, $y_{i} \in \mathbb{R}$; $a\leq w_i \leq b$; $i = 1,\dots,n$
We are also given a function $\phi(\cdot)$ which is continuous. $y_1$ ...
- 96
1
vote
0
answers
42
views
How is the Wilson-Han-Powell SQP algorithm applied?
Say for example we need to minimize $x_2$ subject to $x_1^2+x_2^2-1=0$ starting at $x_1=x_2=1/2$ and using $B=\nabla^2[x_2+\lambda(x_1^2+x_2^2-1)]$ with $\lambda=1$.
Now, the WHP-SQP algorithm goes ...
- 373
1
vote
0
answers
25
views
A CSP on bit vector operations
I've got a CSP which is based on constraining bit vector variables. It is explained below through an example, followed by the full definition. So, what I'm concerned about is if you have some idea if ...
0
votes
1
answer
61
views
Determine the location of a logistics center which is optimally close to its providers
Excuse me if my question is not worded perfectly in mathematical terms. I don't have a strong math background.
So, here's the problem which has been brought up by a real-life situation:
For simplicity,...
1
vote
0
answers
121
views
Max edit distance between binary strings of length n
Given a binary string s of length $n>2$.An edit operation is a single character insert, delete or substitution. The edit distance between two strings is the minimum number of edit operations needed ...
- 11
1
vote
0
answers
50
views
Mathematical Requirements for Dynamic Programming
As far as I understand, for Dynamic Programming to "work" (I think this means for Dynamic Programming to return a Globally Optimal Solution?), am optimization problem must have the two ...
- 2,390
1
vote
0
answers
112
views
Can Gradient Descent be "Combined" with Dynamic Programming?
In most applications of Gradient Descent (e.g. optimizing the Loss Functions of Neural Networks) - regardless of the "type" of Gradient Descent algorithm being used (e.g. Stochastic Gradient ...
- 2,390
3
votes
1
answer
95
views
Can Machine Learning models be considered as "Approximate Dynamic Programming"?
In the context of certain statistical/machine learning models, such as models that are trying to estimate "optimal policies" (e.g. reinforcement learning) - can we consider these models as &...
- 2,390
3
votes
1
answer
119
views
What was so "Groundbreaking" about Bellman's Equations?
In the context of Decision Making and Game Theory, "Bellman's Equations and Bellman's Conditions of Optimality" are said to be some of the most important mathematical principles in this ...
- 2,390
2
votes
0
answers
56
views
Efficiency curves, what is this called?
I am studying a set of functions. This seems like something other people would have studied too, and I'd like to know what other people are calling this and how to read up on it.
These "...
- 394