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.

Filter by
Sorted by
Tagged with
0
votes
0answers
14 views

Existence of solutions to stochastic dynamic programs

What can be said about existence of solutions to a finite-horizon finite state-space stochastic dynamic program? Any references/resources would be appreciated.
1
vote
1answer
22 views

For the value iteration function, if the immediate cost is a linear function in state, then is this value iteration function convex?

For the state value function $V(s)$, if the immediate cost is a linear function in the state, for example $r(s,a) = s + a^2$, where $s$ and $a$ are state and action, which are finite. Is this value ...
0
votes
0answers
26 views

Minimum sum of distances between array element and k array elements.

We need to find the minimum sum of the distances between an element in the array and the k-elements of the array, not including that element. For example: arr = {5, 7, 4, 9} k = 2 min_sum(5) = |5-4| + ...
0
votes
1answer
16 views

L1 constraint on first-differences of sequential binary optimization

I'm working on a sequential decision making problem and am looking at a constraint that I'm not sure how to deal with. We want to maximize the sum of a finite known sequence of bounded functions $F_{t}...
0
votes
0answers
23 views

Solve Dynamic Programming Equations with constraints numerically; Should terminal conditions also obey the constraints?

I'm trying to solve the DPE in the picture below. I checked the terminal condition of $\omega(T,q)$ with the second constraint and found that always $e^{-\kappa*\xi}\omega(t,q-1)>\omega(t,q)$. The ...
1
vote
0answers
17 views

Differentiating value function

I have the following dynamic programming problem: $$ \max_{C_t,H_t} \ V_{t}^{w}= \left\{ \left[ (C_t^w)^\upsilon(1-H_t)^{1-\upsilon} \right]^\rho + \beta \left[ \omega V_{t+1}^w + (1-\omega)V_{t+1}^r ...
2
votes
2answers
63 views

Minimal steps to reach a natural number by a signed arithmetic progression

$F:=\big\{f\,\big|\,\text{function }f: \mathbf N\rightarrow \{1,2\}\big\}$. \begin{align} &\min_{f\in F,\,k\in\mathbf N} k, \\ &\sum_{i=1}^k (-1)^{f(i)}i = n \in\mathbf N. \end{align} Is ...
0
votes
1answer
22 views

Can a signed arithmetic progression reach all integers?

$F:=\big\{f\,\big|\,\text{function }f: \mathbf N\rightarrow \{1,2\}\big\}$. $S:=\big\{\sum_{i=1}^k (-1)^{f(i)}i\,\big|k\in\mathbf N, f\in F\big\}$. Is $S=\mathbf Z$? I had thought of using dynamic ...
1
vote
1answer
57 views

Mathematical formulation of an optimization problem

I have the following optimization problem at hand. There are N integer numbers, $a_{i},a_{i+1},\dots,a_{n}$ where $a_{i} > 0$. We need to partition these numbers ...
0
votes
0answers
18 views

Dynamic programming for a cost function of $\exp$ type

Suppose I have a finite horizon dynamic programming problem, i.e. I want to minimize the following expression $$E[\sum_{t=0}^Tg(X_t, U_t) + G(X_T)|X_0 = x_0] $$ The standard trick is to solve this via ...
1
vote
1answer
37 views

Max of algebraic equations

I am going through Dynamic Programming and Optimal Control text by Dimitri Bertsekas, on p. 18 - he derives these equations ... $$\begin{equation}\begin{aligned} \text{open-loop probability of win} &...
1
vote
1answer
33 views

What is the equation to determine an element's index in a jagged array given it's index from the equivalent flattened array?

If one has a jagged array of N dimensions and an index of an element in the flattened representation of that array, is there an equation that would retrieve the ...
0
votes
0answers
17 views

Can every dynamic programming model be written as a linear (or non) model? If no, when is this possible?

I know that some dynamic programming problems can be written as linear programming ones, an example is the knapsack problem in which I must choose subset $X$ of a set $S=\{ s_1,...s_n \}$ to maximize ...
3
votes
2answers
81 views

Continuous (Smooth) Fractal Zoom

This is my first ever post, I made an account to ask this question. Could have put it on a code forum but thought this challenge would be better suited to a mathematician with a programming foundation....
0
votes
1answer
19 views

Bellmann Equation loss function optimal Q-Value

I am currently working on reinfocement learning and there is this Bellman Equation which I need, so I can minimize the loss-Function calculated by my neural Network. When we calculate the loss, we ...
3
votes
3answers
102 views

Counting The Number Of K-Bounded Good Lists Of Length N

Problem Statement: A k-bounded list of length n is a sequence [x1, x2, . . . , xn] where each xj is an integer between 0 and k, inclusive. A good list is one that does not contain three consecutive ...
1
vote
0answers
24 views

Convergence of value iteration of dynamic programming

$\newcommand{\R}{\mathbb{R}}\newcommand{\T}{\mathbb{T}}$Let $\ell:\R^n\times\R^m\to[0, \infty)$ be a continuous stage cost function and $f:\R^n\times\R^m\to\R^n$ be a continuous function associated ...
0
votes
2answers
33 views

longest increasing subsequence with at most k deletion

Given a number array of length n and a number k, what is the longest non-decreasing contiguous subarray if we allow at most k deletions in our original array? example: n, k = 5, 2 array = 5 2 1 3 4 ...
1
vote
1answer
56 views

Optimal Stock Selection Algorithm (Python)

Given a total amount of available capital, the values of stocks at the current date and the values of the same stocks at a later date, I need to find a way to calculate the optimal return if I can buy ...
0
votes
0answers
45 views

Exercise in Dynamic Programming

I have the following dynamic programming problem that i have to solve in order to find the euler equation and later the corresponding values.I have tried using the guess and verify method but i wasn't ...
2
votes
1answer
56 views

one optimization problem in matrix multiplication and related recurrence

We want to calculate $A_1 \times A_2 \times \cdots \times A_n$, where $A_i$ has dimensions $d_{i-1} \times d_i$. In the classical matrix chain multiplication problem, we wish to minimize the total ...
2
votes
0answers
99 views

Pools of problems

Using a pool of problems, 16 tests will be formed. Every test should have the same number of problems. Any problem should be included in at most 8 tests. For every 4 tests, there should be at least 1 ...
4
votes
1answer
80 views

Brick wall with maximum height 3

Given n same-sized rectangular bricks. We want to build a wall with these constraints: All bricks should be horizontal. We can put a brick on two other bricks, such that the middle of the top brick ...
0
votes
0answers
21 views

Optimal Binary Search Tree

Construct an optimal binary search tree for 4 keys with $p_1 = 0.1$, $p_2 = 0.4$, $p_3 = 0.2$, $p_4 = 0.3$ using dynamic programming. Show the tables as well. What really confuses me is how keys are ...
1
vote
1answer
78 views

Matrix Multiply and Finding Scalar Multiplication is need with a fast method? [closed]

I want to find the optimal scalar multiply for following matrix: Answer is $405$. it means this is not homework ! I see a nice link Here wrote "For the example below, there are four sides: A, B, ...
1
vote
0answers
68 views

Dynamic Programming question - n floors and m boxes

Q: Given a building with $n$ floors, each floor $i$ has $c_i$ boxes in it. You need to find a way to store all the boxes in at most $m$ floors. Moving boxes from one floor to another is allowed only ...
1
vote
1answer
87 views

Dynamic Programming Problem (?) [closed]

Bob walks across the desert from A to B which is L miles away. There are n oases along the way. The i-th (i = 1, 2, · · · , n) oasis is $l_i$ miles away from A (0 < $l_1$ < $l_2$ < · · · < ...
0
votes
0answers
20 views

proving Dynamic Programming principle lemma

I tried to prove this lemma, but I am stuck somewhere. let u(x,t) be value function defined by: $u(x,t)=\inf_{\alpha}[\int_{t}^{T}L(y(s),\alpha(s))+g(T)]$ prove that for $0< h< T-t$ we have the ...
2
votes
0answers
78 views

Algorithm to find all linearly separable bipartitions

Given a set $S$ of $N$ points in $d$-dimensional euclidean space. I know that the number of different ways to separate these points in exactly two disjoint subsets by an hyperplane is limited by $2\...
0
votes
0answers
7 views

Confusion over the supremum in the definition of a value function.

As an economics student I'm struggling and not particularly confident with the following definition concerning dynamic programming. If anyone could shed some light on the problem I would really ...
1
vote
0answers
32 views

Number of strings of fixed size having fixed number of lexicographically greater substrings

Problem description Given a string $\it{s}$, length $\it{l}$ and an integer $\it{b}$, calculate the number of strings of size $\it{l}$ which has exactly $\it{b}$ substrings which are lexicographically ...
0
votes
0answers
28 views

2 dimensional non-linear recurrence $f(n,k) = \frac{f(n-1,k) + f(n-1,k-1)}{2} - \frac{\left(f(n-1,k) - f(n-1,k-1)\right)^2}{320}$

$f(n,k) = \frac{f(n-1,k) + f(n-1,k-1)}{2} - \frac{\left(f(n-1,k) - f(n-1,k-1)\right)^2}{320}$, with boundary conditions $f(n,k) = 0$ $\;$ if $\;$ $n \leq k$, $f(n,k) = 20n$ $\;$ if $\;$ $k = 0$. While ...
0
votes
0answers
30 views

Multiple Knapsack slots with total capacity

If there are a number of slots (s) and for each slot, we can only select a single item (items have price) from all the items of that corresponding slot. We want to ...
1
vote
0answers
23 views

How to optimize subset sum problem through bitmask with the option to generate indices?

I was solving the subset-sum problem. There are many ways to solve the problem but I prefer the bitmask approach which is explained here. Now If I want to get the index of the elements that form my ...
1
vote
0answers
24 views

Find the optimal solution with the maximum principle $\max_{\{u_t\}{T\\ t=0}} \ \ \sum_{t = 0}^{T}-\frac{1}{2}(x_t^2+u_t^2)$

I want to use the maximum principle to find the optimal solution as a function of states $x_0,...,x_T$ and state the optimal controls u_t^* and costates p_{t+1} as functions of states. We only had the ...
1
vote
0answers
15 views

Solving dynamic program with open interval $\max_{\{u_t\}{T-1\\ t=0}} \ \ \sum_{t = 0}^{T-1}-(x_t^2-(x_t+u_t)^2)^2-x_T^4$

I want to solve this dynamic program but I am quite unsure about the approach, as there is an open interval for the control space. I would appreciate any suggestions. $$\max_{\{u_t\}^{T-1}_{t=0}} \ \ \...
1
vote
0answers
49 views

How do you convert Linear Programming Problem into Game Theory Problem?

Given an objective function and constraints we can solve an LPP using Simplex, Graphical methods but can we convert it into a game theory problem? thus solving the LPP using game theory methods.
1
vote
1answer
68 views

Maximize expected sum of uniformly chosen numbers

Each day for the next ten days, you are presented with a number chosen uniformly at random on the interval [0,1] (each day the number chosen is independent of previous days). You are allowed to ...
0
votes
1answer
60 views

Solve the maximization problem involving summation

I am currently working on the following problem: Let $T \geq 1$ be some finite integer. Solve the following maximization problem: $$ \max \sum_{t=1}^T \frac{1}{2^t} \sqrt{x_t} \quad \text{ s.t. } \...
0
votes
1answer
44 views

Hard to count subsets

Suppose $\mathcal{B}=\{0,1\}^N$ is the set of binary sequences of length $N$. I am looking for examples of subsets $\mathcal{A}\subset \mathcal{B}$ which are easy to describe, in the sense that all ...
0
votes
1answer
33 views

Why does optimal control always have optimal substructure?

I've seen a lot of phrases relating to solving optimal control problems, like "Bellman equation, " "Hamilton-Jacobi-Bellman equation," and so forth. My (amateur) understanding of ...
2
votes
2answers
53 views

Number of ways to permute $\{1A, 2A, \ldots, NA, 1B, 2B, \ldots, NB\}$ such that the corresponding $iB$ occurs after $iA$?

I am solving a combinatorics problem using dynamic programming. The question asks for Number of ways to permute $\{1A, 2A, \ldots, NA, 1B, 2B, \ldots, NB\}$ such that the corresponding $iB$ occurs ...
2
votes
1answer
113 views

Help on a proof about some property of a solution to a given algorithmic problem.

Below is a problem I am trying to solve: There are $n$ people to be allocated on $k$ gondolas. The first $q_1$ persons will go with the first gondola. The first $q_2$ persons from the remaining crowd ...
1
vote
0answers
77 views

Moving Robots - (Expectation)

Problem Each square of an $8\times8$ chessboard has a robot. Each robot independently moves $k$ steps, and there can be many robots on the same square. On each turn, a robot moves one step left, right,...
1
vote
2answers
71 views

0/1 - Knapsack and similar problem on 2D Matrix [closed]

Problem: Given a 2d matrix of item weights, their respective costs in another 2d matrix, and max capacity W. Find the optimal selection such that profit is maximum(i.e sum of costs is maximum) and ...
0
votes
0answers
13 views

confused about Bellman equation on student mrp problem

I don't understand how the state values for class1 -> -13, class2 ->-1.5, .. I mean it depends on the next state. How do we calculate the next state. I don't understand from the formula to ...
0
votes
0answers
67 views

Books recommendation for dynamic programming

Good time of the day! I have some math background and I would like to learn dynamic programming. I know about Bellman's "Dynamic programming", but this book is more then 60 years old. Is ...
0
votes
0answers
30 views

(Dynamic) Optimization Problem

My problem is the following. Let $t\in[0,1]$, let $u(t)\in[0,1]$ be the control funciton, and $a\in[\underline{a},\overline{a}]$ is a parameter. I know that the solution to the problem $$ \int_0^1 L(u,...
0
votes
0answers
46 views

How to solve the following non linear second order PDE (Dynamic Programming)

I'm trying to solve the following Dynamic Programming equation in continuous time ($dt \rightarrow 0$) $$ v(x,t) = \max\Big\{|x|\,,\,v(x,t)+dt\Big(v_t(x,t)+\frac{1}{2(t+1)}v_{xx}(x,t)\Big) \Big\} - \...
1
vote
0answers
54 views

First Order Condition with 1 decision variable and 2D state space

TL;DR: I'm trying to find the first-order condition (FOC) for an optimization problem with two state variables and one control variable. I don't want the value function $V$ to appear in the FOC but ...

1
2 3 4 5
10