# Questions tagged [optimization]

Optimization is the process of choosing the "best" value among possible values. They are often formulated as questions on the minimization/maximization of functions, with or without constraints.

22,852 questions
Filter by
Sorted by
Tagged with
72k views

### Please explain the intuition behind the dual problem in optimization.

I've studied convex optimization pretty carefully, but don't feel that I have yet "grokked" the dual problem. Here are some questions I would like to understand more deeply/clearly/simply: ...
• 52.6k
20k views

### What is the maximum volume that can be contained by a sheet of paper?

I was writing some exercises about the AM-GM inequality and I got carried away by the following (pretty nontrivial, I believe) question: Q: By properly folding a common $210mm\times 297mm$ sheet of ...
• 356k
10k views

### Optimizing response times of an ambulance corp: short-term versus average

Background: I work for an Ambulance service. We are one of the largest ambulance services in the world. We have a dispatch system that will always send the closest ambulance to any emergency call. ...
• 1,483
120k views

### The median minimizes the sum of absolute deviations (the ${\ell}_{1}$ norm)

Suppose we have a set $S$ of real numbers. Show that $$\sum_{s\in S}|s-x|$$ is minimal if $x$ is equal to the median. This is a sample exam question of one of the exams that I need to take and ...
• 2,187
6k views

### Making Friends around a Circular Table

I have $n$ people seated around a circular table, initially in arbitrary order. At each step, I choose two people and switch their seats. What is the minimum number of steps required such that every ...
• 3,304
2k views

### What is the largest volume of a polyhedron whose skeleton has total length 1? Is it the regular triangular prism?

Say that the perimeter of a polyhedron is the sum of its edge lengths. What is the maximum volume of a polyhedron with a unit perimeter? A reasonable first guess would be the regular tetrahedron of ...
• 17.7k
8k views

### What's the largest possible volume of a taco, and how do I make one that big?

Let $f$ be a continuous, even function over some interval $I=[-a,a]$ such that the total arc length of $f$ over $I$ is at least $2$, $f(0)=0$, and $f$ is increasing on $(0,a)$. [You might imagine ...
• 55.2k
13k views

### The "pepperoni pizza problem"

This problem arose in a different context at work, but I have translated it to pizza. Suppose you have a circular pizza of radius $R$. Upon this disc, $n$ pepperoni will be distributed completely ...
• 505
3k views

### Escaping infinitely many pursuers

The fugitive is at the origin. They move at a speed of 1. There's a guard at every integer coordinate except the origin. A guard's speed is 1/100. The fugitive and the guards move simultaneously and ...
• 1,919
12k views

### Why is the Traveling Salesperson Problem "Difficult"?

The Traveling Salesperson Problem is originally a mathematics/computer science optimization problem in which the goal is to determine a path to take between a group of cities such that you return to ...
• 3,110
13k views

### Why do engineers use derivatives in discontinuous functions? Is it correct?

I am a Software Engineering student and this year I learned about how CPUs work, it turns out that electronic engineers and I also see it a lot in my field, we do use derivatives with discontinuous ...
47k views

### What is the difference between projected gradient descent and ordinary gradient descent?

I just read about projected gradient descent but I did not see the intuition to use Projected one instead of normal gradient descent. Would you tell me the reason and preferable situations of ...
• 1,127
2k views

### The most effective windshield-wiper setup. (Packing a square with sectors)

I was on the bus on the way to uni this morning and it was raining quite heavily. I was sitting right up near the front where I could see the window wipers doing their thing. It made me think "what is ...
• 8,270
17k views

### Geometric intuition of conjugate function

I am looking for a geometric and intuitive explanation of the conjugate function and how it maps to the below analytical formula. $$f^*(y)= \sup_{x \in \operatorname{dom} f } (y^Tx-f(x))$$
• 1,668
3k views

### AM-GM-HM Triplets

I want to understand what values can be simultaneously attained as the arithmetic (AM), geometric (GM), and harmonic (HM) means of finite sequences of positive real numbers. Precisely, for what points ...
• 26.5k
4k views

### Finding the largest equilateral triangle inside a given triangle

My wife came up with the following problem while we were making some decorations for our baby: given a triangle, what is the largest equilateral triangle that can be inscribed in it? (In other words: ...
• 41.7k
26k views

### How do Lagrange multipliers work to find the lowest value of a function subject to a constraint?

I have been using Lagrange multipliers in constrained optimization problems, but I don't see how they actually work to simultaneously satisfy the constraint and find the lowest possible value of an ...
4k views

### What is the optimal path between $2$ fixed points around an invisible obstructing wall?

Every day you walk from point A to point B, which are $3$ miles apart. There is a $50$% chance each walk that there is an invisible wall somewhere strictly between the two points (never at A or B). ...
• 1,702
4k views

### Choosing office hours to maximise number of students who can attend at least one time slot

I have the following (real world!) problem which is most easily described using an example. I ask my six students when the best time to hold office hours would be. I give them four options, and say ...
• 2,340
41k views

In order to find the local minima of a scalar function $p(x), x\in \mathbb{R}^3$, I know we can use the gradient descent method: $$x_{k+1}=x_k-\alpha_k \nabla_xp(x)$$ where $\alpha_k$ is the step size ...
• 5,258
3k views

### Where to build a bridge to cross a river in the shape of an annulus

There is a river in the shape of an annulus. Outside the annulus there is town "A" and inside there is town "B". One must build a bridge towards the center of the annulus such that the path from A to ...
• 587
102k views

### Show that there's a unique minimum spanning tree if all edges have different costs

Show that there's a unique minimum spanning tree (MST) in case the edges' weights are pairwise different $(w(e)\neq w(f) \text{ for } e\neq f)$. I thought that the proof can be done for example by ...
• 607
10k views

### What is the best rest position for two elevators in a 10-story building?

Situation My apartment block has ten stories. The first ground level is 1, the highest story is 10. There are two equivalent elevators, spanning all stories. Current configuration: One elevator ...
42k views

### How to know whether Lagrange multipliers gives maximum or minimum?

My book tells me that of the solutions to the Lagrange system, the smallest is the minimum of the function given the constraint and the largest is the maximum given that one actually exists. But what ...
• 18.7k
7k views

### The Stupid Computer Problem : can every polynomial be written with only one $x$?

When I was a child, I wanted to be a mathematician so I asked my parents to buy me a computer to make super complex calculations. Of course, they were not crazy enough to buy an expensive super ...
• 1,758
3k views

### Cutting $n$ circular cakes of different radii but equal heights into $p>n$ equal shares

You probably know the following problem: We have two circular cakes of the same height but unknown and potentially different radii, and we want to cut them into two equal shares. Each cut can only ...
• 7,780
64k views

• 471
1k views

• 25.9k