# 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.

561 questions
Filter by
Sorted by
Tagged with
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$ ...
1 vote
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 ...
1 vote
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 ...
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,...
1 vote
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 ...
1 vote
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 ...
1 vote
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 ...
1 vote
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 &...
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 ...
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 "...
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,...
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 ...
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).
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 ...
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, ...
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 ...
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 ...
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 ...
1 vote
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 ...
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 ...
1 vote
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 ...
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 ... 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 ...
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 ...
23 views

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 ...
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 ...