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)

0
votes
1answer
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 ...
0
votes
1answer
75 views

Trust region sub-problem with Jacobi Condition

Consider the $2 \times 2$ trust region sub-problem. Given $Q$ symmetric $2 \times 2$, vector $\mathbf b$ and $\Delta > 0$, find $\mathbf x$ that minimizes $f(x)=\frac {1}{2} \mathbf x^T Q \mathbf x ...
0
votes
1answer
34 views

Optimizing expected sale price by dynamic programming

I would like to sell my computer to the highest bidder. I have studied the market, and concluded that I am likely to receive three types of offers: an offer of \$200 dollars with probability $2/7$, ...
-1
votes
2answers
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? ...
67
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 ...
35
votes
1answer
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}\...
25
votes
1answer
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 ...
8
votes
7answers
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 ...
16
votes
4answers
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 ...
14
votes
3answers
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 ...
12
votes
3answers
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 ...
16
votes
1answer
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 ...
5
votes
1answer
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 ...
22
votes
5answers
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 ...
18
votes
2answers
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 ...
17
votes
5answers
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 ...
12
votes
3answers
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 (...
12
votes
2answers
8k views

Taking derivative of $L_0$-norm, $L_1$-norm, $L_2$-norm

I am a little confused about taking derivatives w.r.t. the norms. $L_0$-norm: $L_0$ means number of non-zero elements in a vector. Say, I am interested in an $x_i$. $$\displaystyle\min_{i}(y_i-...
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 ...
10
votes
5answers
15k views

How many bananas can a camel deliver without eating them all?

This is a fun puzzle I was assigned on the first day of highschool (over a decade ago). I just dug it up randomly from under my bed and thought I'd share it with the SE community. At the time, I ...
6
votes
2answers
666 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 ...
5
votes
2answers
693 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 ...
2
votes
1answer
2k views

Lasso - constraint form equivalent to penalty form

We know that there are two definitions to describe lasso. Regression with constraint definition: $$\min\limits_{\beta} \|y-X\beta\|^2, \sum\limits_{p}|\beta_p|\leq t, \exists t $$ Regression with ...
16
votes
2answers
11k views

What is the best strategy for Cookie-Clicker-esque games?

Today, I stumbled across the game Cookie Clicker, which I recommend you avoid until you have at least a few hours of time to waste. The basic idea behind the game is this: You have a large stash of ...
15
votes
2answers
269 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 ...
10
votes
1answer
413 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 ...
9
votes
6answers
3k views

Finding the largest triangle inscribed in the unit circle

Among all triangles inscribed in the unit circle, how can the one with the largest area be found?
7
votes
4answers
3k views

Is it possible for the Lagrange multiplier to be equal to zero?

I would like to find the extrema of the function $f(x,y)=x^2+4xy+4y^2$ subject to $x^2+2y^2=4$ using Lagrange Multipliers. Is it possible to get for the Lagrange multipliers the value zero? I don't ...
7
votes
1answer
9k 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 ...
7
votes
2answers
575 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 ...
4
votes
1answer
251 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 a+\frac{a+b}{2}+\frac{a+b+c}{...
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. ...
15
votes
2answers
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 ...
13
votes
2answers
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 ...
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
2answers
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 ...
8
votes
3answers
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 ...
6
votes
1answer
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 ...
5
votes
2answers
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 ...
5
votes
1answer
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 ...
4
votes
2answers
394 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 f(Y,x)}{\...
4
votes
0answers
65 views

Convex combination of independent random variables, that minimizes the $p$th moment

Suppose $V$ and $W$ are independent. Let \begin{align} f(x)=E[ ((1-x)V+xW )^p] \end{align} for $x \in [0,1]$ and some even $p \ge 2$. Find \begin{align} \min_{0 \le x \le 1} f(x) \end{align} ...
3
votes
2answers
1k views

Gradient-descent algorithm always converges to the closest local optima?

Assume $f(\vec x)$, which is Lipschitz continuous, has two local optima $\vec x_1^*$ and $\vec x_2^*$( $\vec x_1^*$ is the global minimum). We start the gradient-descent algorithm from $\vec x_0$ and $...
3
votes
2answers
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.
1
vote
2answers
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 ...
0
votes
1answer
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 ...
16
votes
4answers
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 ...
12
votes
1answer
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 ...
11
votes
1answer
134 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
4answers
307 views

Finding Maximum Area of a Rectangle in an Ellipse [duplicate]

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 ...