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)

13
votes
2answers
10k 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 ...
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$. ...
10
votes
1answer
405 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?
9
votes
2answers
3k views

What are the advantages of dual of a problem

I am studying linear programming and I came across primal-dual algorithm in Linear Programming. I understood it but I am unable ...
7
votes
2answers
570 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
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 ...
5
votes
2answers
618 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 ...
5
votes
1answer
343 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 ...
4
votes
1answer
247 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. ...
15
votes
2answers
583 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 ...
12
votes
2answers
349 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 ...
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 ...
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 ...
5
votes
1answer
519 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
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} ...
4
votes
2answers
393 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
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
812 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
857 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 ...
11
votes
1answer
132 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 ...
8
votes
3answers
465 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 ...
8
votes
2answers
823 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 ...
7
votes
4answers
901 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 ...
6
votes
3answers
171 views

Determine the minimum of $a^2 + b^2$ if $a,b\in\mathbb{R}$ are such that $x^4 + ax^3 + bx^2 + ax + 1 = 0$ has at least one real solution

I just wanted the solution, a hint or a start to the following question. Determine the minimum of $a^2 + b^2$ if $a$ and $b$ are real numbers for which the equation $$x^4 + ax^3 + bx^2 + ax + 1 = 0$$ ...
5
votes
2answers
2k 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 ...
5
votes
2answers
880 views

Multilinear optimization

Are there any efficient algorithms to solve, multi-linear objective and multi-linear constraint optimization problems? The multilinear functions are sums of bilinear, trilinear (and so on) terms ...
5
votes
0answers
1k views

Convergence of Gauss-Newton method for piecewise linear functions

Notation for Gauss-Newton method Non-linear least squares problems are often solved by the Levenberg-Marquardt algorithm, which can be viewed as a Gauss–Newton method using a trust region approach. ...
4
votes
1answer
2k views

Converting sum of infinity norm and L1 norm to linear programming

So I'm trying to convert this minimization problem, min $\parallel Ax-y \parallel_{\infty}$ + $\parallel x \parallel_{1}$ where $A$ is $m$ by $n$, $y$ is $m$ by $1$ and $x$ is $n$ by $1$. into a ...
4
votes
1answer
202 views

Angular alignment of points on two concentric circles

I have two concentric circles $C_1$ and $C_2$ with radii $r_1,r_2$ such that $r_1< r_2$and a set of finite points $P=\left \{ p_1,p_2...p_n \right \}$ and $Q=\left \{ q_1,q_2...q_n \right \}$ are ...
4
votes
1answer
608 views

Maximizing distance between points

I asked a similar question on SciComp, but it is a little out of the domain, so I thought I'd give it a try here as well. Give n points, I would like to place them in a periodic box (periodic such ...
4
votes
3answers
781 views

Optimal symmetric rank-1 approximation

I want to find $\mathbf{x}$ that minimizes $\|A-\mathbf{x}\mathbf{x}'\|^2$ where $\|\cdot\|$ is Frobenius norm. Differentiating with respect to $\mathbf{x}$ and setting to $\mathbf{0}$, I get ...
3
votes
2answers
208 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 ...
3
votes
1answer
476 views

How to calculate lim inf and lim sup for given sequence of sets

Let the indicator function be defined as $$I(x) \triangleq \begin{cases} 1, & \quad x \geq 0 \\ 0, & \quad x < 0 \end{cases}$$ and $I_{\nu}(x) \in [0,1]$ be a continuous approximation of ...
3
votes
0answers
91 views

Convergence of sequences of sets

Assume we have the indicator function $$I(x) \triangleq \begin{cases} 1, & \quad x \geq 0 \\ 0, & \quad x < 0 \end{cases}$$ and the sequence of its approximation functions $\{ I_{\nu}(x) ...
3
votes
1answer
202 views

Finding the extrema of $E(\vec{r})=\frac1a x^2+\frac1b y^2+ \frac1c z^2$ with respect to constraints geometrically

I have a function, $$E(\vec{r})=\frac1a x^2+\frac1b y^2+ \frac1c z^2.$$ Where $\vec{r}=(x,y,z)$ and $a>b>c>0$. I wish to find the maximum and minimum of this function with respect to the ...
3
votes
2answers
542 views

Minimize $x^TAx$, subject to $||x||=1$. Show that ${x^*}^TAx^*$ is the smallest eigenvalue of $A$ in magnitude.

I'm solving constrained optimization exercises for preparing my final exam. I got stuck at this question. $$ \begin{array}{ll} \text{min} & \mathbf{x}^T\mathbf{A}\mathbf{x} \\ \text{s.t.} & ...
3
votes
1answer
2k views

Constrained infinity norm minimization

I have a problem like this: $$\min_x |Ax|_\infty \text{ s.t. } \sum_i x_i = c$$ That is, I want to find the vector $x$ whose elements sum to a constant $c$ that minimized the infinity norm of $Ax$. ...
3
votes
1answer
116 views

Proof that $E_n = \int_0^1 \left| \ln t - P_n(t) \right|\mathrm{d}t = 1/(n+1)^2$

Assume one wants to minimize the distance between $f(x)=\ln x$ and $P_n(t)$ where $P_n$ denotes a polynomial of degree $n$. Etc $P_1 = ax 0+ b$. One way to judge whether the polynomial is a good ...
3
votes
3answers
2k views

Why gradient descent works?

On Wikipedia, this is the following description of gradient descent: Gradient descent is based on the observation that if the multivariable function $F(\mathbf{x})$ is defined and differentiable ...
3
votes
1answer
2k views

Strict inequalities in LP

How should we deal with strict inequalities in a linear programming problem? For example: inequalities such as $ax< b$;
2
votes
1answer
52 views

Maximizing and minimizing dot products

Given 2 vectors $u,v \in \mathbb{R^n}$ such that $\|u\| = 1$ and $\sum_{i=1}^n v_i= c$ where $c<1$, I would like to maximize $$\sum_{i=1}^n u_i v_i \log (v_i)$$ and minimize $$\sum_{i=1}^n u_i v_i ...
2
votes
0answers
104 views

What is the best approximate of points on a sphere?

I have a unit radius sphere with a set $S$ of $n$ points on it. How can I find a map $f:S\to \mathbb{R}^4$ which minimizes $$\sum_{x,y\in S} \bigg( d_{\text{geodesic}} (x,y)^{2} - ...
2
votes
2answers
135 views

Gradient and Swiftest Ascent

I want to understand intuitively why it is that the gradient gives the direction of steepest ascent. (I will consider the case of $f:\mathbb{R}^2\to\mathbb{R}$) The standard proof is to note that the ...
2
votes
1answer
1k views

When $\min \max = \max \min$?

Let $X \subset \mathbb{R}^n$ and $Y \subset \mathbb{R}^m$ be compact sets. Consider a continuous function $f : X \times Y \rightarrow \mathbb{R}$. Say under which condition we have $$ \min_{x \in ...
2
votes
2answers
258 views

$\beta_k$ for Conjugate Gradient Method

I followed the derivation for the Conjugate Gradient method from the documents shared below http://en.wikipedia.org/wiki/Conjugate_gradient_method ...