# Tagged Questions

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.

43 views

### Convexity of set

If $C\subset\mathbb{R}^m$ is a convex set, $A$ is an $m\times n$-matrix and $b\in\mathbb{R}^m$, how do I prove that the set $S=\{x\in\mathbb{R}^m|Ax+b\in C\}$ is convex? I know that the definition of ...
75 views

65 views

### If a nonnegative function of $x_1,\dots,x_n$ can be written as $\sum g_k(x_k)$, then the summands can be taken nonnegative

Suppose that $f:\mathbb{R}^n\to [0,\infty)$ is a function that can be written in the form $$f(x_1,\dots,x_n)=g_1(x_1)+g_2(x_2)+\dots+g_n(x_n)$$ Can we also choose all $g_k$ to be nonnegative? ...
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 ...
773 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 K}\...
633 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 ...
7k 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 ...
11k 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 ...
4k 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 an ...
16k 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 ...
429 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 ...
357 views

### Conjugate Gradient Method and Sparse Systems

What is it about conjugate gradient that makes it useful for attacking sparse linear systems. Why would steepest descent be significantly worse? Please keep in mind that I am still trying to fully ...
847 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 ...
725 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 ...
369 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 ...
604 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 (...
8k views

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. ...
591 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 ...
353 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 ...
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 ...
849 views

### Generalization of the Sultan's dowry problem

We know the solution of the Sultan's dowry problem: To reject the first $n/e$ candidates and then to select the first who exceeds the best of the sample. How to find the best strategy if we want ...
472 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 ...
74 views

### Proving the existence of $b$ such that $\prod_{k=1}^n(1-\cos(a_k-b))=\frac{1}{2^n}$

Let $n>0$ and $a_1,\ldots,a_n\in \mathbb R$. Prove there is some $b$ such that $\prod_{k=1}^n(1-\cos(a_k-b))=\frac{1}{2^n}$ This is motivated by this question Finding a point on the unit circle ...
90 views

### Proving that the eigenfunctions of the Laplacian form a basis of $L^2(\Omega)$ (and of $H_0^1(\Omega)$)

I am studying the eigenfunctions and eigenvalues of the Laplacian on an open, bounded domain $\Omega \subset \mathbb{R}^n$ with homogeneous Dirichlet boundary conditions. I have read about the the ...
558 views

### Newton's method vs. gradient descent with exact line search

tl;dr: When is gradient descent with exact line search preferred over Newton's method? I simply don't understand why exact line search is ever useful, and here's my reasoning. Let's say I have a ...
394 views

112 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.
839 views

### Max and min value of $7x+8y$ in a given half-plane limited by straight lines?

So, there are four inequalities: $$\begin{eqnarray*} y &\geq &-3x+15; \\ y &\leq &-11/3x+56/3; \\ x &\geq &0; \\ y &\geq &0. \end{eqnarray*}$$ If we draw all those ...
96 views

### Which optimization class does the following problem falls into (LP, MIP, CP..) and which solver to use

I have the following optimization problem. I want to solve it using a computer solver. But I am not sure which problem class it falls into or which solver to use. Problem: There is a set of objects ...
866 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 ...
461 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 ...
### Using a compass and straightedge, what is the shortest way to divide a line segment into $n$ equal parts?
Question: A rectangle and an ellipse are both centred at $(0,0)$. The vertices of the rectangle are concurrent with the ellipse as shown Prove that the maximum possible area of the ...