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)

177
votes
17answers
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. ...
54
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 ...
38
votes
4answers
942 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 ...
38
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 ...
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 ...
28
votes
5answers
990 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 ...
21
votes
5answers
763 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
5answers
330 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
2answers
658 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
299 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 ...
15
votes
2answers
435 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
640 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 ...
15
votes
3answers
747 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
362 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
4answers
526 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
5answers
5k 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 ...
14
votes
1answer
455 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 ...
14
votes
1answer
252 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
712 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
467 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
1answer
315 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 ...
12
votes
7answers
2k 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 ...
12
votes
2answers
161 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
4answers
6k 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 ...
12
votes
2answers
588 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
554 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
1answer
343 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 ...
11
votes
6answers
289 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
2answers
978 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 ...
11
votes
3answers
4k 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 ...
11
votes
5answers
292 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
3answers
414 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
1answer
132 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 ...
11
votes
2answers
135 views

Fastest way to get \$1 million of two different currencies in a video game

This question actually relates to a video game, I came across the scenario and I realized I had no idea how to go about solving something like this or even what branch of mathematics it falls under. ...
11
votes
2answers
472 views

2 circles and one ellipse and minimum area problem.

2 circles ($r_1 \neq r_2$) and one ellipse touch each other as shown in Figure-1. What is the minimum area (A) among them ? Please consider $a,b,r_1,r_2$ given values(constants). Let's imagine we ...
11
votes
1answer
330 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 ...
10
votes
3answers
2k views

What do curly less than sign 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 ...
10
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 ...
10
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 ...
10
votes
5answers
790 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 ...
10
votes
3answers
735 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 ...
10
votes
2answers
352 views

Can there be a cubical bubble?

Although not physically perfect, a reasonable mathematical model for a bubble's shape is that it minimizes surface area subject to fixed volume. A single floating bubble is usually a sphere, but ...
10
votes
2answers
132 views

How to find the minimum of $f(x)=(\sin(x)+\cos(x)+\tan(x)+\cot(x)+\sec(x)+\csc(x))^2$?

I need to find the minimum of $f(x)$ with $$f(x)=(\sin(x)+\cos(x)+\tan(x)+\cot(x)+\sec(x)+\csc(x))^2$$ Could you help me with some clues?
10
votes
1answer
387 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, ...
10
votes
3answers
6k 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. ...
10
votes
3answers
295 views

Find the maximum and minimum of $\sum_{i=1}^{n-1}x_ix_{i+1}$ subject to $\sum_{i=1}^nx_i^2=1$.

Find the maximum and minimum of $$ \sum_{i=1}^{n-1}x_ix_{i+1} $$ subject to $$ \sum_{i=1}^nx_i^2=1 $$ for all $n\in\mathbb{N}-\{1,0\}$.
10
votes
1answer
241 views

Split up $n \in \mathbb{N}$ into sum of naturals with maximum LCM

Question: Given some natural number, we can of course split it up into various sums of other naturals (e.g. $7 = 6 + 1 = 1 + 4 + 2 = \ldots$) More precisely, for $n \in \mathbb{N}$, we can a find ...
10
votes
1answer
81 views

Using a compass and straightedge, what is the shortest way to divide a line segment into $n$ equal parts?

Sometimes I help my next door neighbor's daughter with her homework. Today she had to trisect a line segment using a compass and straightedge. Admittedly, I had to look this up on the internet, and ...
10
votes
2answers
904 views

Augmented Reality Transformation Matrix Optimization

i am a software developer, i'm working on an Augmented Reality system. I'd like to receive some advice in order to optimize my math model. My program has to be slim and fast. Here's the situation: ...
10
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 ...