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)

10
votes
5answers
6k views

The median minimizes the sum of absolute deviations

Suppose we have a set $S$ of real numbers. Show that $$\sum_{s\in S}|s-x| $$ is minimal if $x$ is equal to the median. This is a sample exam question of one of the exams that I need to take and ...
1
vote
1answer
317 views

Minimization of Variational - Total Variation (TV) Deblurring

Under the Linear Blurring Model - $ f = H \ast u $. I'm trying to calculate the Euler Lagrange of with respect to $ u $ of the functional: $$ E \left( u \right) = {\left\| f - H \ast u \right\|}^{2}_{...
6
votes
6answers
17k views

Find the area of largest rectangle that can be inscribed in an ellipse

The actual problem reads: Find the area of the largest rectangle that can be inscribed in the ellipse $$\frac{x^2}{a^2} + \frac{y^2}{b^2} = 1.$$ I got as far as coming up with the equation ...
5
votes
3answers
856 views

How do you prove ${n \choose k}$ is maximum when k is $ \lceil \frac n2 \rceil$ or $ \lfloor \frac n2\rfloor $?

How do you prove ${n \choose k}$ is maximum when k is $ \lceil \frac{n}{2} \rceil $ or $ \lfloor \frac{n}{2} \rfloor$ ? This link provides a proof of sorts but it is not satisfying. From what I ...
5
votes
3answers
611 views

How to solve $\min \limits_{\mathbf{x}} \| \mathbf{Ax}-\mathbf{b} \|^2$?

Let $\mathbf{x}=[x_1,\ldots,x_K]$. I have the following optimization problem: \begin{array}{rl} \min \limits_{\mathbf{x}} & \| \mathbf{Ax}-\mathbf{b} \|^2 \\ \mbox{s.t.} & x_k\ge 0, \forall ...
6
votes
5answers
205 views

Maximum value of $\sin A+\sin B+\sin C$?

What is the maximum value of $\sin A+\sin B+\sin C$ in a triangle $ABC$. My book says its $3\sqrt3/2$ but I have no idea how to prove it. I can see that if $A=B=C=\frac\pi3$ then I get $\sin A+\sin ...
2
votes
2answers
7k views

Derivation of soft thresholding operator

I was going through the derivation of soft threholding at http://dl.dropboxusercontent.com/u/22893361/papers/Soft%20Threshold%20Proof.pdf. It says the three unique solutions for $\operatorname{arg ...
5
votes
0answers
662 views

Maximum and minimum of an integral under integral constraints.

Find the maximum and minimum of the following integral in terms of $f(x),a,C$: \begin{align}I=\int_{0}^{a} \frac{x}{f(x)}p(x)dx \end{align} s.t.: 1) $\int_{0}^{a} p(x)dx=1$ 2) $\int_{0}^{a} f(x)p(x)...
14
votes
4answers
9k 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 ...
19
votes
4answers
7k views

What does “curly (curved) less than” sign $\succcurlyeq$ 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 ...
16
votes
4answers
800 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}}$$ ...
1
vote
2answers
187 views

What is the derivative of this?

I have a function of the following form: $J = \|W^TW-I\|_F^2$ Where, $W$ is a matrix and $F$ is the Frobenius Norm. How can I find the derivative of $\frac{\partial J}{\partial W}$ ?
3
votes
2answers
2k views

Dimensions of a box of maximum volume inside an ellipsoid

Finding the dimensions of the maximum volume box inside the ellipsoid. I assume that the volume of a box, $V(x,y,z) = xyz$ (they did not give this to me, but this is the volume of a box right?) ...
11
votes
6answers
8k views

Linear Programming Books

Do you know of a good book on linear programming? To be more specific, i am taking linear optimization class and my textbook sucks. Teacher is not too involved in this class so can't get too much help ...
8
votes
3answers
4k views

Maximal order of an element in a symmetric group

If we let $S_n$ denote the symmetric group on $n$ letters, then any element in $S_n$ can be written as the product of disjoint cycles, and for $k$ disjoint cycles, $\sigma_1,\sigma_2,\ldots,\sigma_k$, ...
4
votes
2answers
195 views

Minimum of $|ax-by+c|$

Find the minimum of the function $$ f(x,y)=|ax-by+c|$$ where $a,b,c \in \mathbb N$ and $x,y \in \mathbb Z$. The questions here and here are similar but they are in cases where $x, y$ are ...
4
votes
4answers
156 views

Why does finding the $x$ that maximizes $\ln(f(x))$ is the same as finding the $x$ that maximizes $f(x)$?

I'm reading about maximum likelihood here. In the last paragraph of the first page, it says: Why does the value of $p$ that maximizes $\log L(p;3)$ is the same $p$ that maximizes $L(p;3)$. The ...
5
votes
1answer
760 views

Duality. Is this the correct Dual to this Primal L.P.?

Given a problem: Find the dual: $$ Primal =\begin{Bmatrix} max \ \ \ \ 5x_1 - 6x_2 \\ s.t. \ \ \ \ 2x_1 -x_2 = 1\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ x_1 +3x_2 \leq9\\ ...
5
votes
2answers
3k views

Find the maximum of $f(x)=x^{1/x}$

Find the maximum of the function $$f(x)=x^{1/x}$$ and the value of $x$ which gives the maximum value?
9
votes
1answer
241 views

Minimum of $|az_x-bz_y|$

I am trying to minimize the following function: \begin{align} &f(z_x,z_y)=|az_x-bz_y| \\ &\text{ s.t. } z_x,z_y \in \mathbb{Z},1 \le z_x \le N_x \text{ and } 1 \le z_y \le N_y \text{ and } a,...
4
votes
4answers
208 views

Not so easy optimization of variables?

What is the maximum value of $x^2+y^2$, where $(x,y)$ are solutions to $2x^2+5xy+3y^2=2$ and $6x^2+8xy+4y^2=3$. (calculus is not allowed). I tried everything I could but whenever I got for example $or$...
2
votes
1answer
388 views

The implication of zero mixed partial derivatives for multivariate function's minimization

Suppose $f(\textbf x)=f(x_1,x_2) $ has mixed partial derivatives $f''_{12}=f''_{21}=0$, so can I say: there exist $f_1(x_1)$ and $f_2(x_2)$ such that $\min_{\textbf x} f(\textbf x)\equiv \min_{x_1}...
1
vote
2answers
167 views

Global maximum and minimum of $f(x,y,z)=xyz$ with the constraint $x^2+2y^2+3z^2=6$ with Lagrange multipliers?

The global maximum and the global minimum of the function $f(x,y,z)=xyz$ with the constraint $x^2+2y^2+3z^2=6$ can be found using Lagrange multipliers. $\nabla f = \lambda \nabla g$ $g(x,y,z)=x^2+2y^...
47
votes
7answers
1k views

What is the optimal path between $2$ fixed points around an invisible obstructing wall?

Every day you walk from point A to point B, which are $3$ miles apart. There is a $50$% chance each walk that there is an invisible wall somewhere strictly between the two points (never at A or B). ...
28
votes
4answers
14k 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 ...
8
votes
2answers
8k views

Show that there's a minimum spanning tree if all edges have different costs

Show that there's a unique minimum spanning tree (MST) in case the edges' 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 ...
8
votes
1answer
2k views

Trace minimization with constraints

For positive semi-definite matrices $A,B$, how can I find an $X$ that minimizes $\text{Trace}(AX^TBX$) under 'either' one of these constraints: a) Sum of squares of Euclidean-distances between pairs ...
7
votes
3answers
5k views

gradient descent optimal step size

Suppose a differentiable, convex function $F(x)$ exists. Then $b = a - \gamma\bigtriangledown F(a)$ imples that $F(b) <= F(a)$ given $\gamma$ is chosen properly. The goal is to find the optimal $\...
13
votes
4answers
3k 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 d_i\quad\text{...
12
votes
3answers
275 views

When does a variable leave a basis (in linear programming)?

In the simplex algorithm in linear programming, what are conditions for a variable to leave a basis (not necessarily basis for the/an optimal solution)? I'm supposed to list as many sufficient and ...
2
votes
2answers
6k views

Solving a set of equations with Newton-Raphson

I want to solve this set of equations with Newton-Raphson. Can anybody help me? $$ \cos(x_1)+\cos(x_2)+\cos(x_3)= \frac{3}{5} $$ $$ \cos(3x_1)+\cos(3x_2)+\cos(3x_3)=0 $$ $$ \cos(5x_1)+\cos(5x_2)+\cos(...
2
votes
0answers
79 views

Quasiconvex and lower semicontinuous function

Definition 1. Let $X$ be a Banach space and $f:X\rightarrow\overline{\mathbb{R}}$. The function $f$ is said to be proper if $f(x)>-\infty$ for all $x\in X$ and there exists $x_0\in X$ such that $f(...
4
votes
1answer
42 views

Intuitive understanding of Maximin Principle

From the the book page $324$, does someone could explain to me the Theorem $2$. Maximin principle? I have a bit of difficulties to well understand how works this theorem. A simple example would be ...
2
votes
5answers
1k views

How to find the minimum/maximum distance of a point from elipse

I have the point $(1,-1)$ and the ellipse $$x^2/9 + y^2/5 = 1 $$ How to find the minimum and maximum distance of the point from the ellipse ? from exploring the ellipse I know that $$a = 3$$ , $$b =...
1
vote
0answers
117 views

A maximization problem

I'm trying to find the maximum value of the function $f(x,y)=(ax+by)^p+x^p$ subject to the constraint $x^p+y^p=1$. Here, $a,b$ and $p$ are constants with $a,b>0$ and $p>1$, and $x,y>0$. I ...
5
votes
1answer
288 views

On minimizing the area of an enclosing surface subject to nonnegative Gaussian curvature

This is inspired by this previous question on physical processes that might give rise to convex hulls. Consider the problem of gift-wrapping a three-dimensional object using an inextensible material, ...
4
votes
1answer
3k views

$f$ is convex function iff Hessian matrix is nonnegative-definite.

Let $f: \mathbb{R}^2 \rightarrow \mathbb{R}$, $f \in C^2$. Show that $f$ is convex function iff Hessian matrix is nonnegative-definite. $f(x,y)$ is convex if $f( \lambda x + (1-\lambda )y) \le \...
3
votes
1answer
865 views

Prove optimal solution to dual is not unique if optimal solution to the primal is degenerate and unique.

How do I prove an optimal solution to dual is not unique if an optimal solution to the primal is degenerate and unique? What I tried: Let the primal be $$\max z=cx$$ subject to $$Ax \...
3
votes
1answer
144 views

Maximizing a quadratic subject to $\lVert x\rVert_2 \le 1$

Consider the $n$-dimensional quadratically constrained quadratic optimization problem $$\max \frac12 x^TAx + b^Tx \\ \text{s.t. } \lVert x\rVert_2 \le 1,$$ where $A$ is a symmetric $n\times n$ matrix ...
3
votes
1answer
129 views

minimizing $\sum_{i=1}^n \max(|x_i - x|, |y_i - y|)$

Suppose there are $n$ points $(x_i, y_i)$ for $i = 1,\ldots,n$. Please find another point $(x, y)$ to minimize function: $$\sum_{i=1}^n \max(|x_i - x|, |y_i - y|)$$
2
votes
2answers
6k views

Maximizing volume of a rectangular solid, given surface area

Maximize the volume of a rectangular solid, given that the sum of the areas of the six faces is $6a^2$ for a constant $a$. So basically they tell you it's a rectangle with 6 sides. 2 sides are square,...
2
votes
1answer
341 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
305 views

Some properties of Yosida-Moreau transform

Let $f(x)$ be a continuous function on $\mathbb{R}^n$, $f(x) \geqslant 0$ for any $x$. Define $$ f_{\alpha}(x) = \inf\limits_{y}\left( f(y) +\frac{|x-y|^2}{2\alpha} \right) $$ where $\alpha > 0$....
1
vote
2answers
280 views

Summation notation problem

Any help is greatly appreciated! Outline: Hermione has been thinking about the imminent return of the Dark Lord, so she has been busy packing her bag with all the items required for her survival. ...
44
votes
4answers
1k 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 ...
10
votes
3answers
4k views

Understanding the concept behind the Lagrangian multiplier

I've been trying to understand the principles behind the Lagrangian multipliers and I think I've got a rough understanding of it. Would appreciate it if you guys could help me answer a few questions! ...
10
votes
2answers
2k views

Euler-Lagrange, Gradient Descent, Heat Equation and Image Denoising

For an image denoising problem, the author has a functional $E$ defined $$E(u) = \iint_\Omega F \;\mathrm d\Omega$$ which he wants to minimize. $F$ is defined as $$F = \|\nabla u \|^2 = u_x^2 + ...
15
votes
2answers
533 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$?
4
votes
2answers
335 views

The longest sequence of numbers with a certain divisibility property

EDIT- result. westzynthius(1931) showed that we can create a $p_x$ denizen longer than $p_x \times log(log(log(p_x)))$... Meaning for large enough prime numbers, the maximum denizen is much larger ...
17
votes
4answers
712 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 ...