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)

7
votes
5answers
3k 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 ...
1
vote
1answer
270 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 ...
5
votes
3answers
575 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 ...
4
votes
3answers
471 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 ...
13
votes
4answers
7k 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
636 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} ...
17
votes
4answers
6k 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 ...
15
votes
4answers
752 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}}$$ ...
7
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 ...
14
votes
8answers
5k 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 ...
8
votes
3answers
3k 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$, ...
6
votes
3answers
5k 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 ...
4
votes
3answers
13k 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 ...
3
votes
1answer
2k 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 ...
1
vote
2answers
183 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}$ ?
2
votes
1answer
289 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 ...
9
votes
6answers
7k 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 ...
2
votes
2answers
6k 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 ...
7
votes
2answers
5k 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 ...
4
votes
4answers
140 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 ...
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
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 ...
1
vote
1answer
282 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 > ...
1
vote
0answers
96 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)} ...
0
votes
2answers
209 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) $$ ...
24
votes
4answers
13k 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 ...
7
votes
3answers
4k 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 ...
4
votes
1answer
349 views

Convert Semidefinite program forms

How do I convert the following SDP problem (written in the standard inequality form): $$\min c^T x$$ $$\text{s.t. }F(x)\succeq0$$ When $F(x)\equiv F_{0}+\sum_{i=1}^{m}x_{i}F_{i}$ when $F_{i}\in ...
2
votes
2answers
577 views

A Seating Optimisation Problem

Suppose that you have a cinema hall of size $n\times m$ (where $n$ is the number of rows and $m$ the number of seats in a row). Now, given that there are exactly $l$ people who need only the left ...
4
votes
1answer
647 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
2answers
435 views

find maximum area

Consider a problem here : There is a wall in your backyard. It is so long that you can’t see its endpoints. You want to build a fence of length L such that the area enclosed between the wall and the ...
2
votes
0answers
61 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 ...
9
votes
1answer
457 views

Simple question: the double supremum

Let $f:A\times B\to \mathbb R$. Is it always true that $$ f^* = \sup\limits_{a\in A,b\in B}f(a,b) = \sup\limits_{a\in A}\sup\limits_{b\in B}f(a,b). $$ I proved it by the $\varepsilon$-$\delta$ ...
5
votes
1answer
275 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
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?
2
votes
1answer
516 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
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
115 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
202 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 } ...
7
votes
1answer
3k views

The composition of two convex functions is convex

Let $f$ be a convex function on a convex domain $\Omega$ and $g$ a convex non-decreasing function on $\mathbb{R}$. prove that the composition of $g(f)$ is convex on $\Omega$. Under what conditions is ...
3
votes
2answers
1k 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
124 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
331 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 ...
2
votes
2answers
5k 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
215 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
72 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
288 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 ...
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 ...
13
votes
3answers
11k 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. ...