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)

1
vote
1answer
152 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 ...
4
votes
4answers
611 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 I ...
12
votes
4answers
5k 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 ...
5
votes
0answers
591 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} ...
14
votes
4answers
646 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}}$$ ...
5
votes
3answers
4k views

Primal- degenerate optimal, Dual - unique optimal

Simple question- Is it possible for a linear programming optimization problem possible to have a degenerate optimal solution whereas the dual has a unique optimal solution? I can't find a scenario ...
6
votes
3answers
2k 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
3answers
291 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 ...
8
votes
6answers
5k 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 ...
6
votes
1answer
1k 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 ...
14
votes
3answers
4k 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 ...
13
votes
7answers
3k views

How to prove the sum of squares is minimum?

Given $n$ positive values. Their sum is $k$. $$ x_1 + x_2 + \cdots + x_n = k $$ The sum of their squares is defined as: $$ x_1^2 + x_2^2 + \cdots + x_n^2 $$ I think that the sum of squares is ...
11
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 ...
4
votes
4answers
199 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 ...
1
vote
0answers
82 views

optimization problem gaussian maximizes entropy

Let $X_1, X_2, Z_1$ be random variables and define $$Y=aX_1+bX_2+Z_1$$ I have the following optimization problem of difference of entropies, $$f=\max_{p(x_1x_2)} h(Y) - h(Y|X_2)= \max_{p(x_1,x_2)} ...
1
vote
1answer
221 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
votes
2answers
207 views

Essential problem

I want to find one method or approach or idea which compute following statement: $$ \sup_{t \in [0,1]} \left( \inf_{X \in C^1([0,1])} \left\| \frac{dX(t)}{dt} - A(t)X(t) - F(t) \right\| \right) $$ ...
19
votes
5answers
8k 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 ...
2
votes
2answers
3k 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 ...
4
votes
1answer
498 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\\ ...
3
votes
3answers
2k 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 ...
1
vote
2answers
101 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}$ ?
1
vote
0answers
112 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 ...
10
votes
2answers
1k views

Augmented Reality Transformation Matrix Optimization

i am a software developer, i'm working on an Augmented Reality system. I'd like to receive some advice in order to optimize my math model. My program has to be slim and fast. Here's the situation: ...
9
votes
1answer
198 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 } ...
5
votes
1answer
243 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
2answers
2k 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?
3
votes
2answers
856 views

Finding the widest angle to shoot a soccer ball from the sideline using optimization

I'm trying to do an independent project for my Math class, but I was stuck and couldn't figure out how to use optimization to find position along the sideline that gives the widest angle to shoot. ...
3
votes
1answer
119 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
1answer
171 views

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

How do I prove an optimal solution to dual is not unique if an optimal solution to the primal is degenerate? I have no idea how to start this. Anyone know any books with these kinds of questions (and ...
2
votes
2answers
4k 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 ...
1
vote
2answers
167 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. ...
0
votes
1answer
70 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
227 views

Surf Rescue - word problem - pythagoras

Angela works at the local beach as a part of a surf patrol unit. During her patrol, she notices that an old lady is having difficulty in the surf. She estimates that the distance is approxiamtely 220 ...
41
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 ...
12
votes
3answers
9k views

Lagrange Multipliers with Inequality Constraints

I do not have much experience with constrained optimization, but I am hoping that you can help. My current problem involves a more complex function, but the constraints are similar to the ones below. ...
9
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 + ...
10
votes
3answers
2k 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 ...
15
votes
2answers
486 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$?
11
votes
3answers
10k 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 ...
10
votes
3answers
2k 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! ...
17
votes
4answers
569 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 ...
1
vote
1answer
72 views

Find minimum of $P=\frac{\sqrt{3(2x^2+2x+1)}}{3}+\frac{1}{\sqrt{2x^2+(3-\sqrt{3})x +3}}+\frac{1}{\sqrt{2x^2+(3+\sqrt{3})x +3}}$

For $x\in\mathbb{R}$ find minimum of $P$. $P=\dfrac{\sqrt{3(2x^2+2x+1)}}{3}+\dfrac{1}{\sqrt{2x^2+(3-\sqrt{3})x +3}}+\dfrac{1}{\sqrt{2x^2+(3+\sqrt{3})x +3}}$ Source : Viet Nam national test for high ...
10
votes
2answers
510 views

Explain a surprisingly simple optimization result

The following optimization problem came to my attention as an idealization of the silly browser game Cookie Clicker, but is representative of a range of strategy games: You have an initial ...
7
votes
5answers
727 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 ...
3
votes
2answers
190 views

Find maximum of $P$

Let $$P = \frac{{{x^2}}}{{{x^2} + yz + x + 1}} + \frac{{y + z}}{{x + y + z + 1}} - \frac{{1 + yz}}{9}.$$ Find maximum of $P$ where $x, y,z$ are nonnegative real numbers such that ${x^2} + {y^2} + ...
5
votes
5answers
446 views

How to find the minimum of $a+b+\sqrt{a^2+b^2}$

let $a,b>0$, and such $$\dfrac{2}{a}+\dfrac{1}{b}=1$$ Find this minimum $$a+b+\sqrt{a^2+b^2}$$ My try: since $$2b+a=ab$$ so ...
4
votes
2answers
3k 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
2answers
221 views

How is $L_{2}$ Minkowski norm different from $L^{2}$ norm?

I am reading the book Multidimensional Particle Swarm Optimization for Machine Learning and Pattern Recognition. They use $L_{2}$ Minkowski norm (Euclidean) as the distance metric in the feature space ...
2
votes
1answer
135 views

Positive semidefinite cone is generated by all rank one matrices.

The positive semidefinite cone is generated by all rank one matrices $xx^T$ . They form the extreme raysof the cone. The positive definite matrices lie in the interior of the cone. The positive ...