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)

9
votes
5answers
5k 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
296 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
782 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
551 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
16k 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 ...
13
votes
4answers
8k 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
655 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
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 ...
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 ...
16
votes
4answers
788 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}}$$ ...
8
votes
2answers
7k 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 ...
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$, ...
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 ...
16
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 ...
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 ...
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}$ ?
4
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 ...
2
votes
1answer
346 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 ...
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 ...
4
votes
4answers
150 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 ...
12
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 ...
5
votes
1answer
731 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\\ ...
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 ...
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?
1
vote
0answers
97 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
296 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
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) $$ ...
44
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). ...
26
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 ...
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 ...
4
votes
1answer
402 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
592 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 ...
3
votes
2answers
467 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
72 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 ...
7
votes
1answer
4k 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 ...
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 ...
10
votes
2answers
2k 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
204 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 } ...
9
votes
1answer
490 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
283 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, ...
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
128 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|)$$
3
votes
1answer
141 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 ...
2
votes
1answer
689 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
1answer
339 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
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 ...
1
vote
2answers
267 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
33 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$, ...
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 ...