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)

44
votes
7answers
974 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). ...
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
12k 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. ...
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! ...
14
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
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
15k 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 ...
15
votes
2answers
519 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
333 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
693 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
1k 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 ...
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
182 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} ...
14
votes
1answer
1k views

Maximum total distance between points on a sphere

What is the configuration (set of locations) of $n$ points on the surface of a sphere such that the sum of distances is maximum for $n=1,2,3,...$? The sum of distances is measured by summing the ...
10
votes
3answers
693 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 ...
6
votes
2answers
172 views

Optimal path around an invisible wall [duplicate]

The Problem On an infinite plane there are two points, $A$ and $B$, a unit distance apart. There is a $50\%$ probability that there is an invisible wall somewhere between the two points. The ...
6
votes
5answers
887 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
66 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
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 ...
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
180 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
40 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
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 $$ $$ ...
5
votes
2answers
450 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
467 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
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 ?
3
votes
1answer
147 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
338 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
284 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
3k 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
157 views

Martingale formulation of Bellman's Optimality Principle

Related question: Deducing an optimal gambling strategy (using martingales). What I tried: For no 2, if $\ln Z_n - n \alpha$ is a supermartingale, then for $m < n$, $$E[\ln Z_n - n \alpha ...
2
votes
1answer
72 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
206 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
1answer
445 views

Is Minimax equals to Maximin?

Consider a loss funcation $\ell(x,y)$ with a penalty $g(x,y)$ If I want to consider the worst case robust scenario, that is \begin{equation} \min_x \max_y \ell(x,y) + g(x,y) \end{equation} Is it ...
2
votes
4answers
754 views

Optimization Problem - a rod inside a hallway

The question: I'm given the figure shown above, and need to calculate the length of the longest rod that can fit inside this figure and rotate the corner. My thoughts: I have tried doing the ...
2
votes
0answers
343 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
4answers
177 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
1answer
964 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
198 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
428 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
1answer
58 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
0answers
23 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
2answers
113 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
3answers
8k 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
3answers
5k views

Maximize volume of box in ellipsoid

I need to find the dimensions of the box with maximum volume (with faces parallel to the coordinate planes) that can be inscribed in ellipsoid $$\frac{x^2}{4} + \frac{y^2}{9} + \frac{z^2}{16} = 1$$ ...
1
vote
0answers
198 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
95 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
774 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 ...