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)

187
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. ...
59
votes
1answer
2k views

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

Let $f$ be a continuous, even, positive 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)$. View the ...
41
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 ...
41
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 ...
34
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 ...
29
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 ...
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 ...
21
votes
5answers
814 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 ...
19
votes
5answers
8k 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 ...
19
votes
0answers
291 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 ...
18
votes
5answers
354 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 ...
18
votes
2answers
224 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 ...
17
votes
2answers
687 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
3answers
345 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
4answers
567 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
771 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
474 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
384 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
483 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
3answers
819 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
369 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$?
14
votes
3answers
4k 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 ...
14
votes
2answers
1k 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 ...
14
votes
4answers
644 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}}$$ ...
14
votes
1answer
360 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
266 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
960 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 ...
14
votes
2answers
504 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 ...
13
votes
7answers
3k 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 ...
13
votes
4answers
8k 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
1answer
376 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 ...
13
votes
1answer
412 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 ...
12
votes
2answers
194 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 ...
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
4answers
5k 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 ...
12
votes
2answers
600 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
3answers
8k 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. ...
12
votes
3answers
587 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
1k 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
3answers
433 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 ...
11
votes
6answers
300 views

Maximizing the sum $\sum\limits_{i=1}^nx_ix_{i+1}$ subject to $\sum\limits_{i=1}^nx_i=0$ and $\sum\limits_{i=1}^nx_i^2=1$

Is there an efficient way of solving the following problem? Given $x_i\in \mathbb R$, and that $\sum\limits_{i=1}^nx_i=0$ and $\sum\limits_{i=1}^nx_i^2=1$. I want to maximize ...
11
votes
3answers
10k 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 ...
11
votes
4answers
2k views

Looking to understand the rationale for money denomination

Money is typically denominated in a way that allows for a greedy algorithm when computing a given amount $s$ as a sum of denominations $d_i$ of coins or bills: $$ s = \sum_{i=1}^k n_i ...
11
votes
5answers
1k 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 ...
11
votes
3answers
839 views

Why is $(0, 0)$ not a minimum of $f(x, y) = (y-3x^2)(y-x^2)$?

There is an exercise in my lists about those functions: $$f(x, y) = (y-3x^2)(y-x^2) = 3 x^4-4 x^2 y+y^2$$ $$g(t) = f(vt) = f(at, bt); a, b \in \mathbf{R}$$ It asks me to prove that $t = 0$ is a ...
11
votes
2answers
301 views

Twilight Zelda Guardian Puzzle : Shortest Path (UPDATE: ADDED RULES)

I'm playing a video game right now and in it is a puzzle (see here). There are solutions to solving it (see here) on the Internet, but I'd like to know if this path is the shortest path (least amount ...
11
votes
1answer
511 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, ...
11
votes
5answers
300 views

How find this maximum of the $\sin^2{\theta_{1}}+\sin^2{\theta_{2}}+\cdots+\sin^2{\theta_{n}}$

Question: let $\theta_{1},\theta_{2},\cdots,\theta_{n}\ge 0$,and such $$\theta_{1}+\theta_{2}+\theta_{3}+\cdots+\theta_{n}=\pi$$ find the $P$ the maximum of value $P(n)$ ...
11
votes
1answer
233 views

Largest $n$-vertex polyhedron that fits into a unit sphere

In two dimensions, it is not hard to see that the $n$-vertex polygon of maximum area that fits into a unit circle is the regular $n$-gon whose vertices lie on the circle: For any other vertex ...
11
votes
1answer
143 views

Maximize $\int_0^1 x^2f(x)~\mathrm dx - \int_0^1 xf(x)^2~\mathrm dx$ among continuous $f:[0,1]\to\Bbb R$

For a function $f$, let $$ a = \int_{0}^{1} x^2f(x) \mathrm{d}x\\ b = \int_{0}^{1} xf^2(x) \mathrm{d}x, $$ where $f$ is a continuous function from $[0,1]$ to $\mathbb{R}$. Then find ...