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)

5
votes
1answer
2k views

The composition of two convex functions is convex

Let $f$ be a convex function on a convex domain $\Omega$ and $g$ a convex non-decreasing function on $\mathbb{R}$. prove that the composition of $g(f)$ is convex on $\Omega$. Under what conditions is ...
4
votes
2answers
1k views

Math notation for location of the maximum

My question is about notation. I have maximum of the function $f(x)$. This can be expressed as $\max(f)$ How can I express in compact form that $x_0$ is the location of that maximum.
3
votes
1answer
104 views

Extrema homework — maximizing the viewing angle of a picture on a wall

I have hit a problem in my homework and don't know how to solve it. Here it is: "A picture with height of 1.4 meters hangs on the wall, so that the bottom edge of the picture is 1.8 meters from the ...
3
votes
1answer
2k views

Show that Minimum Spanning Tree is unique

Show that MST is unique in case the edge 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 contradiction, saying that we ...
3
votes
1answer
95 views

Simple optimization trick

Let $f,g:X\to\Bbb R$ be two functions where $X$ is any set. Then $$ \left|\sup_x f(x) - \sup_x g(x)\right|\leq \sup_x|f(x) - g(x)|. $$ This fact is fairly easy to prove, but it seems to be a ...
2
votes
1answer
146 views

Optimisation Problem on Cone

The problem I've got here is to prove that semi vertical angle of a cone with maximum volume with total surface area constant is equal to $arcsin(\frac{1}{3})$ I am trying to do that by making some ...
2
votes
1answer
237 views

Simple resource for Lagrangian constrained optimization?

Just had an optimization lecture. I understand unconstrained methods like Newton and Gradient descent just fine, as well as the ideas that give rise to them. I don't really understand the ideas that ...
1
vote
1answer
52 views

Binomial Coefficient: monotonically decreasing in this range?

relating to this question, I'd like to ask a further one. Again we have $$f(x)={k-1 \choose x-1} p^x (1-p)^{k-x}$$ We know that this term is maximal for $x=kp$, before increasing, afterwards ...
1
vote
3answers
285 views

Ladder Optimization Problem

A fence 4 feet tall runs parallel to a tall building at a distance of 4 feet from the building. What is the length of the shortest ladder that will reach from the ground over the fence to the wall of ...
1
vote
0answers
36 views

Maximizing a given function?

I have a function as below, $f(\alpha) = \frac{{1 - \alpha }}{2}\ln \left( {1 + \frac{{AB}}{{B + \frac{{1 - \alpha }}{{C\alpha }}}}} \right)$, where $A$, $B$, $C$ are constant, and $0 < \alpha ...
1
vote
1answer
41 views

A non-linear optimization problem

I have the following optimization problem on the variables $a_1, ..., a_n$: $$ minimize \frac{\sum_{k=1}^{n}\max(k\cdot a_{k},1)}{\sum_{k=1}^{n}a_{k}} $$ $$ such\ that\ \ 0\leq a_k\leq 1\ \ \ (k=1, ...
1
vote
1answer
139 views

Find the minimum of this expression

This is a problem in my exam and I can't find the solution using elementary inequality knowledge. Can anyone here help me solve this. Thanks $a,b,c $ are positive real numbers which satisfy ...
0
votes
1answer
973 views

How to find the speed that minimizes the total cost of a trip?

Here are some facts about semi-trucks and a trip between Chicago and New Orleans. (a) The trip is 750 miles. (b) Running at 50 mph, the truck gets around 4 miles per gallon. (c) For each mph ...
0
votes
0answers
41 views

How to solve non-linear optimization problem with division

I am trying to solve the below mentioned optimization function. Here W_ck and W_lk have the same range but their positioning is such that for one calculation in k domain, one decision variable is in ...
0
votes
0answers
59 views

Linear Programming - Tableau Condition

The following tableau corresponds to an iteration of the simplex method: ...
0
votes
1answer
84 views

Finding Shortest distance between a Sphere and Ellipsoid?

Suppose that ,I have a Sphere and an ellipsoid as Sphere: $(x-x_1)^2 + (y-y_1)^2 + (z-z_1)^2 = R_1^2$ Ellipsoid: $\large\frac{(x-x_2)^2}{a^2} + \frac{(y-y_2)^2}{b^2} + \frac{(z-z_2)^2}{c^2} = 1$ ...
0
votes
2answers
52 views

To prove the existing and uniqueness of a solution

Let function $f$ be differentiable and convex in $R^{n}$. How can it be proved that $\forall \lambda > 0$ solution of system equations $f'(x) = -\lambda x$ exists exclusively ($\exists \hspace{3mm} ...
0
votes
0answers
56 views

Distance metrics with kmeans

Context: I'm trying to derive some formulas for computing the "mean" in the K-means algorithm. So given an assignment of $m$ data points to $k$ clusters, find a formula to recompute the mean of the ...
0
votes
1answer
67 views

How to solve this optimization problem?

Suppose I have the following problem: Maximize: $\quad\quad x_1+x_2+x_3+x_4$ Subject to: $\quad\quad \dfrac{\gamma\;a_1\;x_1}{\gamma\;a_2\;x_4+1}\geq1$, $\quad\quad\quad\quad\;\;\quad\quad ...
0
votes
1answer
103 views

How to minimize cost of group of items given that weights of item sums up to fixed value and atmost 'n' number of items are allowed?

Given that we have a set of items :- { (c1, w1) , (c2, w2), (c3, w3) , ... } where (ci, wi) are the respective cost and weight of the ith item. Its required to minimize total cost of items C such ...
56
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 ...
6
votes
7answers
3k views

Operations research book to start with

for somebody having a quite strong background in Mathematics, which are some good books for the domain of Operations research? I guess there are textbooks covering topics like linear and nonlinear ...
21
votes
5answers
784 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
214 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 ...
18
votes
5answers
345 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 ...
12
votes
3answers
575 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
4answers
7k 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 ...
9
votes
3answers
8k 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 ...
16
votes
4answers
513 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 ...
12
votes
1answer
361 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 ...
10
votes
1answer
337 views

Maximum subset sum of $d$-dimensional vectors

This is a $d$-dimensional generalisation of the post Inequality with Complex Numbers. (See my comment under Robert Israel's answer.) Generalising Potato's proof for $d$-dimensions, we can show the ...
8
votes
1answer
403 views

Graph theory problem (edge-disjoint matchings)

Find the smallest number $x$ so that if an $n$-vertex simple graph has at least $x$ edges then it contains $k$ pairwise edge-disjoint perfect matchings* ($k$ is a positive integer, $n$ is an even ...
7
votes
1answer
1k views

Why are additional constraint and penalty term equivalent in ridge regression?

Tikhonov regularization (or ridge regression) adds a constraint that $\|\beta\|^2$, the $L^2$-norm of the parameter vector, is not greater than a given value (say $c$). Equivalently, it may solve ...
6
votes
2answers
309 views

How to explain lagrange multipliers to a lay audience?

So I will be giving a seminar to a scientifically mature lay audience (think bio/social science undergrad level). I have been told that I should count on less than half the audience to have experience ...
4
votes
1answer
167 views

$a,b,c>0,a+b+c=21$ prove that $a+\sqrt{ab} +\sqrt[3]{abc} \leq 28$

$a,b,c>0,a+b+c=21$ prove that $a+\sqrt{ab} +\sqrt[3]{abc} \leq 28$ I have tried to use AM-GM inequality, but get no result as follows: $$a+\sqrt{ab}+\sqrt[3]{abc}\leq ...
2
votes
4answers
1k views

Calculating the max and min of $\sin(x)+\sin(y)+\sin(z)$

I took the partial derivatives of $\sin(x)+\sin(y)+\sin(z)$ and it didn't work out, so I am trying to use Lagrange's method (with the constraint: $x+y+z=\pi$)... I am not sure how to set this up. ...
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 ...
10
votes
5answers
945 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 ...
5
votes
1answer
1k views

Maximizing the volume of a rectangular prism

A rectangular prism has a surface area of $300$ square inches. What whole number dimensions give the prism the greatest volume? This is a math olympiad problem. It involves the volume and surface ...
4
votes
1answer
307 views

Derivation of Euler-Lagrange equation

Here is a simple (probably trivial) step in the derivation of the Euler-Lagrange equation. If we denote $Y(x) = y(x) + \epsilon \eta(x) $, I want to know why is $\dfrac{\partial ...
3
votes
2answers
155 views

What numerical methods are known to solve $L_1$ regularized quadratic programming problems?

What numerical methods are suitable to solve the following problem $$\min_x \tfrac{1}{2}x^T A x + b^Tx + \lambda ||x||_1$$ where $x,b\in\mathbf{R}^n$, and $A\in \mathbf{R}^{n\times n}$ is positive ...
3
votes
2answers
107 views

Find the values of $x$, $y$ and $z$ minimizing $\frac{r^2x}{y+z}+\frac{s^2y}{x+z}+\frac{t^2z}{x+y}$

$$\frac{r^2x}{y+z}+\frac{s^2y}{x+z}+\frac{t^2z}{x+y}$$ $r$, $s$, $t$ are positive coefficients. Find the values of non-negative variables $x$, $y$ and $z$ so that the above expression is a minimum.
14
votes
2answers
830 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 ...
12
votes
3answers
3k 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
1answer
102 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 ...
7
votes
5answers
582 views

Arithmetic mean is less than geometric mean (Spivak Calculus 3rd Chapter 2 Problem 22)

If $a_1, \ldots, a_n \ge 0$, the arithmetic mean $$A_n={a_1 + \cdots + a_n \over n}$$ and the geometric mean $$G_n = \sqrt[n]{a_1 \cdots a_n}$$ satisfy $G_n \le A_n$. As a first step to prove this ...
7
votes
3answers
423 views

Optimization problem for a parity-check code

I have $n$ data blocks and $k$ parity blocks distributed across $m$ boxes where each box can contain atmost $b$ blocks. Each parity block is Ex-or of some data blocks (for ease of understanding we can ...
7
votes
3answers
672 views

Decomposing a discrete signal into a sum of rectangle functions

Hello math@stackexchange community ! I have a simple question that seems to have a non trivial answer. Given a discrete one dimensional signal $w(x)$ defined in a finite range, and the boxcar ...
5
votes
1answer
6k views

Degeneracy in Linear Programming

Consider the standard form polyhedron, and assume that the rows of the matrix A are linearly independent. $$ \left \{ x | Ax = b, x \geq 0 \right \} $$ (a) Suppose that two different bases lead to ...
4
votes
2answers
178 views

Least sum of distances

Problem: Let $A, B, C, D$ be points in a $3$-dimensional space. Find the point $X$ that minimizes the sum of the distances $AX+ BX + CX + DX$. Context: During a course, I was assigned a ...