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.

learn more… | top users | synonyms (5)

192
votes
16answers
7k 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. ...
76
votes
4answers
6k 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 ...
65
votes
1answer
3k 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 ...
44
votes
4answers
1k 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 ...
43
votes
3answers
1k 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 ...
37
votes
3answers
6k 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 ...
32
votes
5answers
1k views

Can this ant find its way back to the nest?

So the puzzle is like this: An ant is out from its nest searching for food. It travels in a straight line from its nest. After this ant gets 40 ft away from the nest, suddenly a rain starts to ...
32
votes
2answers
542 views

A System of Matrix Equations (2 Riccati, 1 Lyapunov)

Setup: Consider the following system of real matrices, \begin{align} {\bf P} &={\bf F}({\bf I}_{n}-{\bf K} {\bf H}^\top){\bf P}{\bf F}^\top+{\bf Q}, \;\;\;\;\;\;\;\;\text{where}\;\;\;\;{\bf ...
29
votes
4answers
1k views

Run away from lions in a cage

I came across an interesting problem: There is a round cage and you are in it. Also two lions are in this cage too. The start position is that the distance between you and both lions is the ...
25
votes
1answer
595 views

Can Three Equilateral Triangles with Sidelength $s$ Cover A Unit Square?

A previous question on the site asked for a short proof of the fact that three equilateral triangles with unit side length cannot be arranged to cover a square with unit side lengths. Given the truth ...
24
votes
4answers
13k 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 ...
22
votes
5answers
840 views

Math Wizardry - Formula for selecting the best spell

Imagine we have a wizard that knows a few spells. Each spell has 3 attributes: Damage, cooldown time, and a cast time. Cooldown time: the amount of time (t) it takes before being able to cast that ...
18
votes
2answers
706 views

Largest circle between $y=x^n$ and $y=\sqrt[n]{x}$

Something I have been wondering about for a while. Let us look at the area between $x^n$ and $\sqrt[n]{x}$ when $x\in [0,1]$. Where $n$ is a positive integer. Below is an image. With a given n, how ...
17
votes
4answers
6k views

What does “curly (curved) less than” sign $\succcurlyeq$ mean?

I am reading "Convex Optimization" by Stephen Boyd. He is using a curved greater than and curved less than equal to signs. $f(x^*) \succcurlyeq \alpha$ or $f(x*) \preccurlyeq \alpha$ Can someone ...
17
votes
2answers
2k views

Derivation of the method of Lagrange multipliers?

I've always used the method of Lagrange multipliers with blind confidence that it will give the correct results when optimizing problems with constraints. But I would like to know if anyone can ...
17
votes
3answers
383 views

What is the largest circle that fits in $\sin(x)?$

Imagine dropping a circle into the trough of $\sin(x)$. Would it reach the bottom or get wedged between two points on the curve? Depends on the size of the circle. So, what is the radius of the ...
17
votes
5answers
361 views

If $A+B+C+D+E = 540^\circ$ what is $\min (\cos A+\cos B+\cos C+\cos D+\cos E)$?

Let each of $A, B, C, D, E$ be an angle that is less than $180^\circ$ and is greater than $0^\circ$. Note that each angle can be neither $0^\circ$ nor $180^\circ$. If $A+B+C+D+E = 540^\circ,$ what is ...
17
votes
4answers
642 views

How fat is a triangle?

The slimness factor of a geometric shape in 2 dimensions is the ratio between the side-length of its smallest containing square and its largest contained square. This is an important factor in ...
16
votes
4answers
840 views

Gerrymandering/Optimization of electoral districts for one particular party

I'm asking this on behalf of Zach Weiner (actually it's my own initiative in order to promote this site). Original text is here, and is as follows: Hey-- This is Zach from SMBC, and I have a math ...
16
votes
1answer
412 views

Arnol'd's trivium problem #68

I came across this blog that says that its French version has answers to most of Arnol'd's trivium problems, and I figured I'd try my hand at some of the ones they don't have. Number 68 raised my ...
16
votes
1answer
479 views

Minmax problem for polygons

Let $\text{Pol}_n$ be the set of all convex polygons on a plane with $n$ sides. For $P\in \text{Pol}_n$ denote by $\text{Tr}(P)$ the set of all triangles whose vertices are some vertices of $P$. I ...
16
votes
3answers
413 views

Problem on EU commission

Consider the following problem. A collection of $n$ countries $C_1, \dots, C_n$ sit on an EU commission. Each country $C_i$ is assigned a voting weight $c_i$. A resolution passes if it has the ...
15
votes
2answers
509 views

Does a polynomial that's bounded below have a global minimum?

Must a polynomial function $f \in \mathbb{R}[x_1, \ldots, x_n]$ that's lower bounded by some $\lambda \in \mathbb{R}$ have a global minimum over $\mathbb{R}^n$?
15
votes
4answers
752 views

How find this inequality $\max{\left(\min{\left(|a-b|,|b-c|,|c-d|,|d-e|,|e-a|\right)}\right)}$

let $a,b,c,d,e\in R$,and such $$a^2+b^2+c^2+d^2+e^2=1$$ find this value $$A=\max{\left(\min{\left(|a-b|,|b-c|,|c-d|,|d-e|,|e-a|\right)}\right)}$$ I use computer have this $$A=\dfrac{2}{\sqrt{10}}$$ ...
15
votes
3answers
881 views

Maximizing a sum of inner products

Someone asked this question on a French maths forum here and it caught my attention. The question is the following: let $(E, \langle \cdot, \cdot \rangle)$ be a Euclidean vector space. Find the ...
15
votes
4answers
377 views

Maximize $x_1x_2+x_2x_3+\cdots+x_nx_1$

Let $x_1,x_2,\ldots,x_n$ be $n$ non-negative numbers ($n>2$) with a fixed sum $S$. What is the maximum of $x_1x_2+x_2x_3+\cdots+x_nx_1$?
15
votes
2answers
252 views

Time-optimal control to the origin for two first order ODES - Trying to take control as we speak!

I want to find the time optimal control to the origin of the system: $$\dot{x}_1 = 3x_1+ x_2$$ $$\dot{x}_2 = 4x_1 + 3x_2 + u$$ where $|u|\leq 1$ I ran straight into the problem full strength, hit it ...
15
votes
1answer
665 views

Bath towel on the rope: minimize the area of self-intersection of a folded rectangle

This question is related to my bath towel, which I hang on a rope, so let's have fun (you can use your own towel to do this experiment in bath-o). There is this rectangle with sides $a<b$. The ...
15
votes
2answers
563 views

The Farmyard problem

Problem: There is a farmer who has a $1\text{ mile}\times 1\text{ mile}$ square piece of land. He knows that there is a completely straight pipe underneath some part of his property, but it could ...
14
votes
8answers
2k views

How can I find 3 positive numbers that have a sum of 1 and the sum of their squares is minimum?

How can I find 3 positive numbers that have a sum of 1 and the sum of their squares is minimum? So far I have: $$x+y+z=1$$ $$z=1-(x+y)$$ $$f(x,y)=xyz=xy(1-x-y)$$ But I'm stuck from here. Hints?
14
votes
8answers
5k views

How to prove the sum of squares is minimum?

Given $n$ positive values. Their sum is $k$. $$ x_1 + x_2 + \cdots + x_n = k $$ The sum of their squares is defined as: $$ x_1^2 + x_2^2 + \cdots + x_n^2 $$ I think that the sum of squares is ...
14
votes
2answers
220 views

$|f(x)|\leq \sqrt{\frac{\pi}{3}\int_0^\pi f'^2}$

Let $f\in C^1([0,\pi],\mathbb R)$ such that $\displaystyle\int_0^\pi f(t) dt=0$ Prove that $\forall x\in [0,\pi],\displaystyle|f(x)|\leq \sqrt{\frac{\pi}{3}\int_0^\pi f'^2(t)dt}$ Failed ...
14
votes
1answer
378 views

Searching for tighter bounds

I have to solve an equation $$\sum_{i=1}^N x_i = \sum_{i=1}^N y_i,$$ where $$x_i = \frac{z_i}{1 + (K_i - 1) w}$$ and $$y_i = \frac{K_i z_i}{1 + (K_i - 1) w}.$$ The $z_i$ are all positive and add ...
14
votes
1answer
275 views

Fastest curve from $p_0$ to $p_1$

I'm trying to solve a problem in path planning: Given points $p_0$ and $p_1$ and vectors $v_0$ and $v_1$, find a function $p(t)$ st. $p(0) = p_0$, $p(T) = p_1$, $p'(0) = v_0$ and $p'(T) = ...
14
votes
2answers
478 views

Can a dynamic programming problem be transformed into a linear algebra problem?

Here is a simple standard economic problem: Let Robin Crusoe have an endowment $w_0$ of lembas bread. She is immortal and discounts at a rate of $\beta$ per period. Each period (from $t=0$ on) she ...
14
votes
1answer
1k views

Maximum total distance between points on a sphere

What is the configuration (set of locations) of $n$ points on the surface of a sphere such that the sum of distances is maximum for $n=1,2,3,...$? The sum of distances is measured by summing the ...
13
votes
4answers
10k views

Do dynamic programming and greedy algorithms solve the same type of problems?

I wonder if dynamic programming and greedy algorithms solve the same type of problems, either accurately or approximately? Specifically, As far as I know, the type of problems that dynamic ...
13
votes
4answers
7k views

Gradient Descent with constraints

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 ...
13
votes
3answers
11k views

Lagrange Multipliers with Inequality Constraints

I do not have much experience with constrained optimization, but I am hoping that you can help. My current problem involves a more complex function, but the constraints are similar to the ones below. ...
13
votes
1answer
2k views

Gradient Descent on Non-Convex Function Works But How?

For Netflix Prize competition on recommendations one method used a stochastic gradient descent, popularized by Simon Funk who used it to solve an SVD approximately. The math is better explained here ...
13
votes
2answers
205 views

Find the maximun of the sum $\sum_{k=1}^{n}(f(f(k))-f(k))$

Let $f:\{1,2,3,\cdots,n\}\to \{1,2,3,\cdots,n\}$ such that $$f(1)\le f(2)\le\cdots\le f(n)$$ find the maximum of the $$\sum_{k=1}^{n}(f(f(k))-f(k))$$
12
votes
3answers
14k views

Optimum solution to a Linear programming problem

If we have a feasible space for a given LPP (linear programming problem), how is it that its optimum solution lies on one of the corner points of the graphical solution? (I am here concerned only with ...
12
votes
2answers
1k views

Using math for interior decorating with lamps

When I was in college, I owned three lamps and had a dark apartment. I kept trying to position them in different areas of the room, but it was still dark. Then I decided to model the problem with ...
12
votes
5answers
2k views

Why is convexity more important than quasi-convexity in optimization?

In the mathematical optimization literature it is common to distinguish problems according to whether or not they are convex. The reason seems to be that convex problems are guaranteed to have ...
12
votes
2answers
606 views

the least value for :$\frac{a}{b^3+54}+\frac{b}{c^3+54}+\frac{c}{a^3+54}$

For every $a,b,c$ non-negative real number such that:$a+b+c=1$ how to find the least value for : $$\frac{a}{b^3+54}+\frac{b}{c^3+54}+\frac{c}{a^3+54}$$
12
votes
2answers
694 views

invex functions and their usefulness?

An invex function $f$ is a differentiable function from $\Bbb R^n$ to $\Bbb R$ that for some function $\eta : \Bbb R^n \times \Bbb R^n \to \Bbb R^n$ satisfies for all $x, u$, $f(x) - f(u) \geq \eta(x, ...
12
votes
3answers
595 views

Formula for picking time closest to (but after) target

Let's say you have an arbitrary length of time. You are playing a game in which you want to push a button during this time span after a light comes on. If you do so, you win ($+1$), if not, you lose ...
12
votes
3answers
2k views

Best fit ellipsoid

Given a collection of points $P \subset \mathbb R^3$, a crude characterization of the "shape" of $P$ is sometimes given by the principal components. We construct a covariance matrix, e.g., if $P$ is ...
12
votes
1answer
505 views

Largest rectangle in a convex polygon

What is the least $k > 0$ such that every convex polygon of area $k$ contains a rectangle of area 1? I can prove that $k \le 8$, but surely this can be improved. Let $\mathcal{C}$ be a convex ...
12
votes
3answers
449 views

Combinatorial optimization - improve performance

I am writing a program to solve a combinatorial optimization problem. I have been working on an algorithm that gets the desired results, but I am having difficulties getting the algorithm to perform ...