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
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 + ...
12
votes
3answers
14k 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 ...
11
votes
3answers
3k 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 ...
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! ...
15
votes
2answers
509 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
324 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
645 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 ...
8
votes
3answers
925 views

Newton's method in higher dimensions explained

I'm studying about Newton's method and I get the single dimension case perfectly, but the multidimensional version makes me ask question... In Wikipedia Newton's method in higher dimensions is ...
10
votes
2answers
630 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 ...
2
votes
1answer
143 views

Maximum of the sum of cube

(1) $-2\leq a_{i} \leq 2$ $~(i=1,2,3,4,5)$ (2) $\displaystyle\sum_{cyclic}a_{i}=0$ then, find the maximum value of $\displaystyle\sum_{cyclic}a_{i}^{3}$ also, can it be generalized as for ...
1
vote
1answer
76 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 ...
0
votes
0answers
178 views

Reformulation of Goldbach's Conjecture as optimization problem correct?

Question I think I managed to reformulate a stronger version of Goldbach's conjecture as an optimization problem: $$ \frac{\partial F_n}{\partial a_n} = \frac{\partial F_n}{\partial \overline a_n} ...
6
votes
5answers
865 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
191 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} + ...
2
votes
1answer
63 views

Show that if $ A(t) \in \mathbb{R ^{n×n}}$ is a differentiable function of $t$ then $\frac{d(det A(t))}{dt}$ [duplicate]

Let $\mathbb{R^{ n×n}}$ be the space of n × n real matrices. Show that if $ A(t) \in \mathbb{R ^{n×n}}$ is a differentiable function of $t$ then $\frac{d(det A(t))}{dt}$ is the sum of the determinants ...
2
votes
4answers
176 views

Three Variables-Inequality with $a+b+c=abc$

$a$,$b$,$c$ are positive numbers such that $~a+b+c=abc$ Find the maximum value of $~\dfrac{1}{\sqrt{1+a^{2}}}+\dfrac{1}{\sqrt{1+b^{2}}}+\dfrac{1}{\sqrt{1+c^{2}}}$
2
votes
3answers
2k views

How to interpret Hessian of a function

I know that gradient of a function gives the direction in which the directional derivative of the function is maximum. Is there any similar interpretation of Hessian ?
2
votes
2answers
1k views

satisfy the Euler-Lagrange equation

Two circles of unit radius, each normal to the line through their centers are a distance d apart. A soap film is formed between themas shown below; energetic considerations require the filem to ...
2
votes
1answer
171 views

Control on Conformal map

Let $\Omega$ be smooth simply connected open set of $\mathbb{R}^2$ such that $\overline{\Omega}$ is compact. We know that there exists a conformal diffeomorphism $\psi$ from $\mathbb{D}$ to $\Omega$. ...
1
vote
1answer
56 views

Min problem by using Lagrange method

$$\min x^2+y^2 $$ $$\text{s.t.}\ \ (x-2)^2+(y-3)^2\le 4 \ \ \ \text{and} \ \ \ x^2=4y$$ Please explicitly solve this question by using Lagrange multiplier method. I accept $(x-2)^2+(y-3)^2=4$ ...
1
vote
1answer
36 views

Maximize the sum of numbers subject to an upper bound on their sum of squares

I want to find a maximum for $\sum_i^n x_i$ subject to $\sum_i^n x_i^2 \leq c$, where c is some constant. I've done some searching and that's hinted at using the Cauchy-Schwarz inequality, but I ...
1
vote
2answers
111 views

Minimizing $f(x,y,z)=\dfrac{|x|+|y|+|z|}{xyz}$ on a sphere

I need to find the minimum of the function: $$f(x,y,z)=\dfrac{|x|+|y|+|z|}{xyz}$$ with the condition: $$x^2+y^2+z^2=r^2$$ Using numerical methods it's quite easy to solve the problem. How can I ...
1
vote
2answers
5k 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 $$ $$ ...
0
votes
2answers
94 views

Explain this statement $\bar 0 \in \partial f(x^*)$ where $\partial f(x^*)$ is subgradient

I haven't understood this theorem "$x^*$ is global minimum iff $\bar 0\in \partial f(x^*)$". What does it mean? Visually? P.s. Studying Nonlinear-optimization -course, 2.3139.
10
votes
5answers
691 views

Are derivatives defined at boundaries?

Given a differentiable function $f : [-5,5] \rightarrow \mathbb{R},$ I was under the impression that the derivative $f'$ has domain $(-5,5).$ However, according to Wikipedia ...a differentiable ...
5
votes
2answers
400 views

How to find the shift that minimizes the difference between two vectors?

I am looking for a efficient way to find the value of k that minimizes $\sum(s_t - b_{t+k})^2$ where $s$ and $b$ are N-dimensional vectors and the values are wrapped around like this: $b_{t+k} := ...
5
votes
5answers
464 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
8answers
4k views

Maximizing the sum of two numbers, the sum of whose squares is constant

How could we prove that if the sum of the squares of two numbers is a constant, then the sum of the numbers would have its maximum value when the numbers are equal? This result is also true for ...
3
votes
1answer
143 views

Equivalence of following statements about shortest path problem

We formulate the shortest path problem as follows: We have a directed graph $D=(V,A)$ with length $c_{j}$ for each arrow $e_j$ in $A$ and two special points $s,t\in V$. The node-arc incidence ...
3
votes
1answer
298 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 ...
3
votes
2answers
272 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 ...
3
votes
1answer
98 views

Simple optimization trick

Let $f,g:X\to\Bbb R$ be two functions where $X$ is any set. Then $$ \left|\sup_x f(x) - \sup_x g(x)\right|\leq \sup_x|f(x) - g(x)|. $$ This fact is fairly easy to prove, but it seems to be a ...
3
votes
1answer
2k views

Prove the supremum of the set of affine functions is convex

Let $\langle f_i \rangle _{i \in I}$ be a family of affine functions on a convex and compact set $\Omega \subset \mathbb{R^d}$ such that $f_i = a_i.x +b_i$ for $x \in \Omega$. Prove that f, defined by ...
2
votes
1answer
68 views

Conjugacy relation in the primal and dual problem

The following is my derivation in the Conjugacy relation in the primal and dual problem. I am shaky in it; so hope for some advices. Consider the following problem, $f(x),g(x)$ are convex ...
2
votes
1answer
148 views

Proximal mapping of $f(U) = -\log \det(U)$

This is an assignment problem which I failed to solve in a couple of days. Denote the set of all $n \times n$ symmetric matrices and the set of all $n \times n$ symmetric positive definite matrices ...
2
votes
0answers
308 views

Real approximation to the maximum using Laplace's method integral

The Laplace's Method states that under some conditions, it holds that: $ \sqrt{\frac{2\pi}{M(-g''(x_0))}} h(x_0) e^{M g(x_0)} \approx \int_a^b\! h(x) e^{M g(x)}\, dx \text { as } M\to\infty$ Where ...
2
votes
1answer
784 views

Maximum of product of numbers when the sum is fixed

This is the problem I'm working on. $$\begin{array}{rl} \text{maximize} & (n+\ell+x_1)\cdots (n+\ell+x_{k-1})(\ell + x_k) \\ \text{subject to} & 0 \leq x_1, ..., x_k \leq n \\ & x_1 + ...
2
votes
2answers
191 views

Maxima and minima of multivariable function $f(x,y)=6x^3y^2-x^4y^2-x^3y^3$

$$f(x,y)=6x^3y^2-x^4y^2-x^3y^3$$ $$\frac{\delta f}{\delta x}=18x^2y^2-4x^3y^2-3x^2y^3$$ $$\frac{\delta f}{\delta y}=12x^3y-2x^4y-3x^3y^2$$ Points, in which partial derivatives ar equal to 0 are: ...
2
votes
1answer
89 views

Cubes, squares and minimal sums

I have trouble solving the following task: i need to find positive integers a and b such that 1) $a \neq b$ 2) $ \exists c \in \mathbb{N} : ~ a^2 + b^2 = c^3$ 3) $\exists d \in \mathbb{N}: ~ a^3 + ...
2
votes
2answers
369 views

Multiple solutions for both primal and dual

If matrix $A$ in an LP (or $A^T$ in its dual) has full row (column- in dual) rank, is it possible that both primal and dual have multiple solutions?
1
vote
2answers
37 views

If a nonnegative function of $x_1,\dots,x_n$ can be written as $\sum g_k(x_k)$, then the summands can be taken nonnegative

Suppose that $f:\mathbb{R}^n\to [0,\infty)$ is a function that can be written in the form $$f(x_1,\dots,x_n)=g_1(x_1)+g_2(x_2)+\dots+g_n(x_n) $$ Can we also choose all $g_k$ to be nonnegative? ...
1
vote
0answers
22 views

How to optimize a singular covariance-weighted residual?

Definitions: $$v(x)\equiv\{g_1(x),g_2(x),\ldots,g_n(x)\}^T$$ $$C\equiv \operatorname{cov}(v)=\langle vv^T \rangle -\langle v\rangle \langle v^T \rangle =\int f(x)v(x)v(x)^T \, dx-\int f(x)v(x) \, dx ...
1
vote
3answers
7k views

How to plot a phase portrait for this system of differential equations?

I beg your help.. I'd like the phase portrait for this system. I don't know how to use Mathematica/Matlab ... :( If anyone can make this portrait and post a print screen here, I would thank you ...
1
vote
1answer
57 views

A non-linear optimization problem

I have the following optimization problem on the variables $a_1, ..., a_n$: $$ minimize \frac{\sum_{k=1}^{n}\max(k\cdot a_{k},1)}{\sum_{k=1}^{n}a_{k}} $$ $$ such\ that\ \ 0\leq a_k\leq 1\ \ \ (k=1, ...
1
vote
2answers
240 views

Applying the Lagrangian function to find critical points

So I have the following function $$ f(x,y) = x^2+y^2 $$ subject to $$ g(x,y) = x+y-1 = 0. $$ And I have to use the Lagrangian to find the critical points, and determine wether they are ...
1
vote
1answer
148 views

Find the minimum of this expression

This is a problem in my exam and I can't find the solution using elementary inequality knowledge. Can anyone here help me solve this. Thanks $a,b,c $ are positive real numbers which satisfy ...
1
vote
0answers
194 views

Duality for Support Vector Machines

SVM classifier for two linearly separable classes is based on the following convex optimization problem: \begin{equation*} \frac{1}{2}\sum_{k=1}^{n}w_k^2 \rightarrow \min \end{equation*} ...
0
votes
2answers
58 views

minximum and maximum of $P=x+y+z$

Let $x,y,z \in R;x \ge 1,y \ge 2,z \ge 3$ and $$\sum\limits_{\large{\text{cyc}}} {\frac{{{x^2} - x + 1}}{{x + \sqrt {x - 1} }} = 12} $$ Search minximum and maximum of $P=x+y+z$
6
votes
2answers
145 views

Find the minimum value of $A=\frac{2-a^3}{a}+\frac{2-b^3}{b}+\frac{2-c^3}{c}$

Let $a, b$ and $c$ three positive real numbers such that $a+b+c=3$. Find the minimum value of $$A=\frac{2-a^3}{a}+\frac{2-b^3}{b}+\frac{2-c^3}{c}.$$ Here is my attempt. By symmetry we can assume that ...
6
votes
1answer
941 views

Why is Dantzig's solution to the knapsack problem only approximate

For a bunch of items with values $v_i$ and weights $w_i$, and with a total weight $W$ that our bag can carry, how do we achieve maximum total value without breaking the bag? Dantzig proposed that we ...