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
0 answers
31 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$ ...
user avatar
1 vote
0 answers
25 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 ...
user avatar
1 vote
0 answers
18 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 ...
user avatar
0 votes
1 answer
45 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,...
user avatar
1 vote
0 answers
20 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 ...
user avatar
1 vote
0 answers
34 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 ...
user avatar
  • 1,698
1 vote
0 answers
23 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 ...
user avatar
  • 1,698
1 vote
1 answer
54 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 &...
user avatar
  • 1,698
2 votes
1 answer
85 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 ...
user avatar
  • 1,698
2 votes
0 answers
55 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 "...
user avatar
0 votes
0 answers
45 views

Ordered Graph Problem

Let G = (V, E) be a directed graph with nodes v1, v2, . . . , vn. We say that G is an ordered graph if it has the following properties. (i) Each edge g Let G = (V, E) be a directed graph with nodes v1,...
user avatar
2 votes
0 answers
32 views

Structured policies in dynamic programming: solving a toy example

I am trying to solve a dynamic programming toy example. Here is the prompt: imagine you arrive in a new city for $N$ days and every night need to pick a restaurant to get dinner at. The qualities of ...
user avatar
0 votes
0 answers
7 views

Reference request: multi-armed bandit problems with analytical solutions

Is there a book/survey on (multi-armed) bandit problems that yield analytical solutions? I.e. has an exactly optimal closed-form solution (e.g. derived using dynamic programming).
user avatar
0 votes
0 answers
12 views

Reference Request for Bandit Problems where myopic strategies are optimal

I recently found a paper (Banks and Sundaram, 1992) on a class of bandit problems where the myopically-optimal strategy (in each period, choose arm that maximizes current period's expected payoff) is ...
user avatar
0 votes
1 answer
56 views

Are these two relations the same?

Suppose we want to find the shortest path with at most $\ell$ edges in a positive weighted directed graph $G=(V,E)$ with weight $w(u,w)$ on each edge. According to Jeff Erickson's algorithms textbook, ...
user avatar
  • 1
0 votes
0 answers
8 views

Risk measures and Bellman's principle of optimality in the context of risk-sensitive MDPs

I'm learning about finite-horizon risk-sensitive Markov Decision Processes (MDP) in the context of stochastic shortest path problems. In a nutshell, instead of finding a policy that minimizes the ...
user avatar
  • 145
0 votes
0 answers
9 views

Speed adjustment on a given path for cost minimization with fixed departure and arrival time

I have an optimization problem which consists in going from a departure point to an arrival point given a set of predefined intermediate points between the departure and the arrival. The departure and ...
user avatar
  • 1
2 votes
0 answers
46 views

Tractable setup for sequential Bayesian estimation with a binary data (in a case where a beta-bernoulli setup seems inappropriate)

An unknown parameter $\theta$ is randomly drawn at time $t=0$ according to prior p.d.f. $\mu_0(\cdot)$ that has support $[L,R]\subseteq\mathbb{R}$. At each time $t\in\{1,2,...\}$ an agent makes an ...
user avatar
1 vote
0 answers
37 views

What the meaning of "impatience" in Bellman equation?

From wiki: A dynamic decision problem ... Finally, we assume impatience, represented by a discount factor $0 < \beta < 1$ What the meaning of "impatience"? I can't understand even if ...
user avatar
  • 111
0 votes
0 answers
23 views

For optimization problems, is the complementary slackness constraint really necessary?

I am dealing with a bilevel optimization problem, and to solve it I am applying the Karush–Kuhn–Tucker conditions to the inner optimization problem. As a result, I can reformulate my bilevel ...
user avatar
1 vote
1 answer
63 views

Expected Number of steps to reach 0.

Consider following problem, You are given $N$ piles, $i^{th}$ pile has size $S_i$. Until size of all the piles become $0$, repeat the following step. With probability $p$, size of atmost one pile will ...
user avatar
0 votes
0 answers
32 views

Solve the optimality equation for this dynamic programming problem

I am learning about stochastic and dynamic programming. I have been going through the book by Sheldon Ross. It's somewhat dated but has a number of examples. I have been trying to work through the ...
user avatar
0 votes
0 answers
35 views

How to proof a greedy algorithm for return loans to bank

This problem was in my homework, now I'm preparing for exam but still couldn't understand it. We have $n$ loans, each loan has initial amount $R[i]$ and interest $a[i]$, and Monthly income $S.$ each ...
user avatar
  • 1
0 votes
0 answers
64 views

Most Likely Number of Wins Given Array of Probabilities

You are given a team's win probability for each game on their schedule in the form P[1..n] where P[i] is the likelihood they win game i. Find the most likely number of wins. For example, if n = 2 and ...
user avatar
  • 85
0 votes
0 answers
23 views

What is the distribution of a future posterior belief given a sequence of data? What if the latter depends on the former?

Let $Y\sim$ Bernoulli($\mu$). The realization $y\in\{0,1\}$ of $Y$ is not observed by the agent, who instead "learns'' about $Y$ over $T\in\mathbb{N}$ time periods. Specifically, in period $t\in\{...
user avatar
5 votes
0 answers
79 views

Optimal control of posterior belief over a finite horizon

$\large \textbf{Preface:}\ $ Below I describe a dynamic programming problem I am not sure how to formalize. In short: a (Bayesian-updating) agent sequentially runs costly experiments over a finite ...
user avatar
0 votes
0 answers
23 views

Multi-Stage Combinatorial Optimization

I am not sure if I used the corret terminology. I think the problem is a multi-stage combinatorial optimization problem. The problem is like this: There is a dynamic equation $$ S_{k+1} = f(S_k,\pi_k) ...
user avatar
1 vote
0 answers
31 views

Maximize the sum of weights of covered intervals

Suppose we are given n open intervals $(a_1, b_1)$, ..., $(a_n, b_n)$, with interval $i$ being assigned a weight $w_i$ for all $i$. We are given an integer $k<n$, and we are allowed to choose $k$ ...
user avatar
  • 163
1 vote
0 answers
14 views

define max function when arguments and operators are given, and you have to decide only where to put braces

I have the following problem: Given a set of $n$ values, $x_1,...,x_n$, and $n-1$ operators between them (that is, we are given the formula $x_1 o_1 x_2 o_2 ... o_{n-1}x_n$), our objective function is ...
user avatar
0 votes
0 answers
13 views

Optimal policies and if we would always choose them

Suppose the value of a policy $\pi$ is defined as $$V^{\pi}(s) =E[R \mid s, a]$$ where $R$ stands for the return associated with following $\pi$ from the initial state $s$. Let an optimal policy be ...
user avatar
3 votes
1 answer
79 views

Optimal stopping of a Poisson Process with a risky reward

I'm confident that there is a well-known solution to this problem, but I am having trouble finding a reference for it. I am also quite rusty on these kinds of problems, so I am having trouble solving ...
user avatar
0 votes
0 answers
16 views

Find the intersection of elements of powerset one by one

Let S = { trigon, tetragon , pentagon , ... ,... } is a set of polygons How to calculate intersection of subsets of (every element actually) ...
user avatar
  • 1
0 votes
0 answers
37 views

Euler Equations in Dynamic Programming: a misunderstanding

I have a question about the solution to infinite horizon problems. Suppose that we have derived the following Lagrangian for a pretty standard growth model in macroeconomics: $ L=\sum_{t=0}^{\infty} \...
user avatar
1 vote
0 answers
45 views

Optimization Problem: Maximize percentage of dependent sum

I have an optimization problem which I currently solved by brute force but I was wondering if there is a more efficient solution. I wasn't able to reduce the problem to some well known problem in ...
user avatar
  • 11
0 votes
0 answers
50 views

Design an algorithm to find k vertices to cover as many edges as possible.

How to design an $O(k^2 n)$-time algorithm to find $k$ vertices in a tree to cover the maximum number of edges, where $G=(V,E)$ is undirected. And $n=|V|,m=|E|$ as usually denoted. What I tried is to ...
user avatar
0 votes
0 answers
36 views

how many triples of positive integers a b c are there so that a+b+c<=S and a*b*c<=P (programming c++) formula without three nested loops

For example, if S and P are 5 and 2, respectively. The answer would be - 4. 1 1 1 1 1 2 1 2 1 2 1 1
user avatar
0 votes
0 answers
16 views

Secure multiparty computation and dynamic programming solution concept?

Consider the usual problem of secure communication, where each of the $I$ agents have a private signal $s_1,s_2,\dots,I$ and they wish to compute any function $f(s_1,s_1,...,s_I)=(x_1,x_2,...,x_I)$ in ...
user avatar
  • 251
1 vote
1 answer
89 views

Source of a Dynamic Programming Algorithm for Finding the Maximum Independent Set in a Graph of Treewidth k

On the Wikipedia page of Tree decomposition, there is a dynamic programming algorithm for finding the maximum independent set in a graph of treewidth $k$. For a node $X_i$ of the tree decomposition, ...
user avatar
  • 11
-2 votes
1 answer
46 views

This is a dynamic programming question. Details can be found in the body(Including an image)

Write the optimal profit of the problem as a function of $z_{k}{(i)}.$ Solve $z_{1}(i)$ for all i ∈ {0,...,α}. Write a recurrence equation satisfied by $z_{k}(i)$ for all (k,i) ∈ {1,...,n} × {0,...,α}....
user avatar
0 votes
1 answer
53 views

How to model history-dependent dynamic program?

Suppose there is a dynamic program that the state of the problem grows over time (more info is added to the state of the problem over time) and at each time, we need all historical data, full history. ...
user avatar
  • 111
2 votes
1 answer
101 views

CSES "Moving Robots": How can we solve this expected value problem?

I am trying to solve the following problem: Given a 8x8 board where each square has one robot on it, define a move as follows: every robot moves either up, down, left, or right (each with an equal ...
user avatar
1 vote
0 answers
17 views

How can we find the minimum cost of redistributing gold.

problem statement: We are given n gold mines having A[i] amount of gold at ith gold mine ...
user avatar
0 votes
0 answers
34 views

Find the most optimal plan to sell the products (Python)

I'm working on a dynamic programming problem and actually, I'm not quite sure whether it is dynamic programming since moving average $M$ is based on previous $M$. No need to consider the efficiency. ...
user avatar
0 votes
0 answers
56 views

Overlapping line-segments

I came across a question that was a part of a coding contest on CodeForces. The contest is over now and this is the link to the question. You are given $n$ lengths of segments that need to be placed ...
user avatar
0 votes
0 answers
15 views

Dynamic Programming of Product Sales based on moving average

I'm working on a dynamic programming problem and the problem requires selling a product over T time periods and maximizing the total actual sale amount. The total number of products for sale is N and ...
user avatar
1 vote
0 answers
30 views

minimising performance using pontrayagins maximum principle

given that we want to minimize a performance $$\min \int_{t_{0}}^{t_{1}} L\big[x(t),u(t)\big ]\ \mathrm dt$$ subject to $$\dot{x} = f(x,u)$$ $$x(0) = x_{0}$$ when constructing the Hamiltonian would we ...
user avatar
0 votes
0 answers
39 views

Help with envelope theorem macroeconomics

I am really stuck on how to solve a optimisation question, in infinite time: consumer problem: $\sum_{t=0}^{\infty}\beta^t \ln (c_t + \chi c_{t-1})$ s.t.: $c_t + k_{t+1} = k^{\alpha}_t + (1- \delta)...
user avatar
0 votes
0 answers
37 views

Dynamic Programming of Product Sales

I'm working on a dynamic programming problem and the problem requires selling a product over $T$ time periods and maximizing the total actual sale amount. The total number of products is $N$ and I ...
user avatar
0 votes
0 answers
44 views

No Ponzi Game Conditions

I had a question related to Dynamic Programming in discrete time. Assuming a No Ponzi Game condition of: $\lim_{T \to \infty} (\frac{1}{1+r})^T a_T = 0$ for the capital stock, I got that the lifetime ...
user avatar
-2 votes
2 answers
106 views

How many ways are there to form a 5 𝑐𝑚 × 3 𝑐𝑚 rectangle from squares of side lengths 1𝑐𝑚, 2 𝑐𝑚 and 3 𝑐𝑚? [closed]

"How many ways are there to form a 5 𝑐𝑚 × 3 𝑐𝑚 rectangle from squares of side lengths 1𝑐𝑚, 2 𝑐𝑚 and 3 𝑐𝑚 ?" Above is a question from SEAMO(South East Asian Math Olympiad). I tried ...
user avatar

1
2 3 4 5
12