Questions tagged [optimization]
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.
20,118
questions
0
votes
1
answer
19
views
The requirement of compactness for the Strict Separation Theorem
In class I learned about the following theorem:
Strict Separation Theorem: Let $A$ and $B$ be two closed convex subsets of $\mathbb{R}^n$ with that $A \cap B = \emptyset$. Furthermore assume that $A$ ...
- 2,452
0
votes
0
answers
12
views
Show that the logaritmic primal barrier $B(x,\rho)$ is not bounded from above (for $x\in \Omega$) for any fixed $\rho>0$
Let $x\in\mathbb{R}$. Consider the problem
$$\text{minimize}\quad \frac{1}{1+x^2}\quad\text{s.t}\quad x\geq 1$$
Show that the logaritmic primal barrier $B(x,\rho)$ is not bounded from above (for $x\...
- 1,382
1
vote
1
answer
42
views
Why does least-squares need regularization?
If I understand regularization correctly, it helps if a least-squares problem is not well-posed thus...
the problem has no solution
the problem has multiple solutions
a small change in the input ...
- 87
1
vote
1
answer
16
views
Theorem of Alternatives proof only one of the systems is solvable
Let $ A \in R^{nxm}$, $x \in R^n$, $c,y \in R^m$ show that, either
I) $Ax=c$
II) $A^Ty=0, c^Ty=1$
is solvable
I'm completely new to the theorem of alternatives, so my attempt is:
If I is solvable ...
0
votes
1
answer
12
views
A square on the equator of a sphere is a critical point of the electrostatic potential
$\newcommand{\S}{\mathbb{S}^2}$
This is a self-answered question. I learned something from spelling out the details, and I hope this could be interesting to others. I would welcome alternative ...
- 23k
1
vote
0
answers
15
views
The effect that slightly increasing a variable has on the optimal solution
I am going through a past exam paper that doesn't have a mark scheme provided. I am struggling to figure out how you would do part b. Can anyone explain how you would go about getting an answer for ...
- 577
0
votes
0
answers
7
views
Proof the Moreau Envelope of a proper convex function h is minimised at x iff h is minimised at x
Let h:$\mathbb{R} ^n \rightarrow \mathbb{R}\cup {+\infty}$ be proper convex (i.e convex and has at least 1 finite element in it's range) and differentiable at $prox_{\lambda h}(x)$ (the minimiser of $...
- 65
3
votes
5
answers
83
views
Is it possible to compute $-\log\left({\sqrt{1.8\times 10^{-5}\times 0.1}}\right)$ without a calculator?
The following question is part of a chemistry problem that came in the Dhaka University admission exam 2013-14.
What is $-\log\left({\sqrt{1.8\times 10^{-5}\times 0.1}}\right)$?
(a) 2.672
(b) 2....
- 2,207
1
vote
0
answers
22
views
How is the Wilson-Han-Powell SQP algorithm applied?
Say for example we need to minimize $x_2$ subject to $x_1^2+x_2^2-1=0$ starting at $x_1=x_2=1/2$ and using $B=\nabla^2[x_2+\lambda(x_1^2+x_2^2-1)]$ with $\lambda=1$.
Now, the WHP-SQP algorithm goes ...
- 365
1
vote
1
answer
37
views
Is a planar square on the equator a locally energy minimizing configuration of electrons on $\mathbb{S}^2$?
$\newcommand{\S}{\mathbb{S}^2}$Let$$M=\{(x_1,x_2,x_3,x_4) \in \mathbb{S}^2 \times \mathbb{S}^2 \times \mathbb{S}^2 \times \mathbb{S}^2 \, |\,\, \text{ all the } x_i \, \text{ are distinct}\} $$
Let $...
- 23k
0
votes
0
answers
20
views
convergence of maximum value of a function
Suppose $(\Theta^n)_{n\in \mathbb{N}}$ is a monotone sequence of sets in $\mathbb{R}^d$ and $\Theta^{\infty}$ is its limit. Also, let $f:\mathbb{R}^d \to \mathbb{R}$ be a continuous function. I want ...
0
votes
1
answer
29
views
Binary matrix multiplication optimization problem
I am looking for pointers to and names of computational approaches to solve a binary matrix optimization problem of:
$$ minimize: ||\mathbf{X}\mathbf{Y} - \mathbf{T}||_{L1} $$
where $\mathbf{X}$ and $\...
- 101
1
vote
1
answer
48
views
how can I linearize a constraint of the form sum(min(x(i),y(i))) for a linear optimisation problem?
I have an linear optimisation problem and I'd like to impose a constraint of the following form:
$∑_{i=0}^N min(x_i,y_i)≥C$
where x_i,y_i are rational numbers greater or equal to 0.
how can I ...
- 11
0
votes
0
answers
11
views
Find Matrix A such that $\operatorname*{argmin}_A ||H-A||^2_F + |A|_1$ from given matrix H [closed]
Question
I have matrix H, I want to find Matrix A such that:
$$
\operatorname*{argmin}_A ||H-A||^2_F + |A|_1
$$
How can I do that?
What's the updating rule for A?
Can someone please guide?
1
vote
0
answers
19
views
Lagrange multipliers: discrepancy between optimization and adjoint sensitivity results
Consider the constrained optimization problem: $min_x f(x)$ s.t. $g(x)=0$.
For simplicity, let $f$ and $g$ be scalar functions.
Under suitable conditions, the Lagrange multiplier theorem gives: $\...
- 63
0
votes
1
answer
32
views
Largest area with given perimeter, one straight edge
A common example to introduce quadratic functions is to ask for a rectangle with the largest area when the perimeter is given and you are allowed to use one additional edge that does not count towards ...
- 314
4
votes
0
answers
52
views
Maximizing $P(t):=\frac{A^{2}}{N} \sum_{j=1}^{N} \sum_{k=1}^{N} x_{k} x_{j} \exp \left(2 \pi i \frac{B}{N}(k-j) t\right)$
$$P(t):=\frac{A^{2}}{N} \sum_{j=1}^{N} \sum_{k=1}^{N} x_{k} x_{j} \exp \left(2 \pi i \frac{B}{N}(k-j) t\right)$$ Could any one tell me how to maximize $P(t)$? $t\in [0,T)$.
I have done the ...
- 4,573
2
votes
1
answer
40
views
Unconstrained minimizer as a linear combination
I'm given the following function:
$$f : R^n \rightarrow R$$
$$f(x)=\frac{||Ax-b||^2}{c^Tx+d}$$ where x $\in R^n$ and $dom(f) = \{x|c^Tx+d > 0\}$
Also it's given that $rank(A)=n$ and vector b is ...
- 147
1
vote
2
answers
62
views
Find the minimum of $f(x)=x^2-x+1+\sqrt{2x^4-18x^2+12x+68}$.
WA gives the result $9$. But how to solve it by applying inequalites?
- 12.7k
0
votes
1
answer
37
views
Using an equation as a constraint and building a constraint matrix
Given a list of points $(x_1, x_2) \in \Bbb R^2$, I would like to find the ellipse that best fits the given points in the least-squares sense. I have a general function $f :\Bbb R \times \Bbb R \to \...
- 9
0
votes
0
answers
18
views
Solutions of Two Similar Quadratic Programs
I am solving a very large number of quadratic programs with the same objective function, and very similar constraints. Given a positive definite matrix $\Sigma$ and constraints $A,B,a,b$, let
$$ x = \...
- 1,846
1
vote
1
answer
54
views
Find the cheapest arrangement of non-overlapping colored rectangles necessary to achieve a sequence of colors behind holes
Input
Let the input be a sequence of colors with any length at least 1. For example, (red, blue, red, green, blue). Each color is represented in the input as a string, not as any abstract notion of a ...
- 111
0
votes
0
answers
17
views
Optimality of some Algorithm under Non-Convexity - "Pie in the Sky"?
I always come across mathematical proofs that show some optimization algorithms are guaranteed to converge to a global minimum, provided the function is Convex (and deterministic). For example:
In ...
- 1,698
0
votes
0
answers
11
views
How to convert Hessian of Barrier function into matrices in order to find equation for inverse of the Hessian?
So I derived this from the barrier function $B(x,r)=F(x)-r\sum_{i=1}^m\log(c_i(x))$ and so $\nabla^2B(x,r)=\nabla^2F(x)-r\sum_{i=1}^m\{\frac{\nabla^2c_i(x)}{c_i(x)}-[\frac{\nabla c_i(x)}{c_i(x)}]^2\}$....
- 365
4
votes
1
answer
73
views
Spider and fly problem on a Teserract.
In the spider and fly puzzle, there is a spider on the inside of a cuboidal room wondering how it would get to a fly on another point on the inside of the cuboid. Here, we just "flatten out" ...
- 5,469
0
votes
1
answer
11
views
Theorem of the Maximum for discrete sequences of constraint sets?
Suppose that $\{X_{n}\}_{n=1}^{\infty}$ is a sequence of sets that converges to $X$ in some sense. Let $f$ be a real-valued function.
I am interested in conditions under which
$$ \lim_{n \rightarrow \...
- 321
0
votes
2
answers
29
views
What does it mean that a function is unbounded below in every neighborhood?
In this paper Strong Convexity Does Not Imply Radial Unboundedness
In [3], Tapia gives this result showing that a strongly convex functional is either
radially unbounded (and so minima-existence ...
- 403
0
votes
0
answers
5
views
Ensure continuity on the first-order derivative while minimizing functional
Consider the problem of minimizing a functional $F[x,u(x),u'(x)]$ subjected to $N$ constraints of the type $g_i(x,u,u')=0$ at different positions $x=x_i$, such that the first-order optimality criteria ...
- 23
-1
votes
2
answers
54
views
Find the point on the plane $x+2y+3z=13$ that is closest to the point $(1,1,1)$ [closed]
Recently, I received the following task. I would be very grateful for your help.
Find the point on the plane $x+2y+3z=13$ that is closest to the point $(1,1,1)$. How would you minimize the function?
0
votes
0
answers
15
views
Is there any relation between Wasserstein metric and the expectaion value? [closed]
I need to find an upper bound for Wasserstein between two distributions, $u$ and $v$. I have a bound for their expectation value ($E(u-v)<\delta$), I was wondering can I say
$W_2(u,v)\leq E(u-v)<...
0
votes
1
answer
45
views
Determine the location of a logistics center which is optimally close to its providers
Excuse me if my question is not worded perfectly in mathematical terms. I don't have a strong math background.
So, here's the problem which has been brought up by a real-life situation:
For simplicity,...
0
votes
1
answer
32
views
Is this shorter attempt on the existence of the maximizer in Kantorovich duality is correct?
I'm reading section 3.4 Existence of Maximisers to the Dual Problem in this lecture notes. The proof is quite involved and requires a complicated approximation argument.
Below is my straightforward ...
- 10.1k
0
votes
1
answer
27
views
Bad choice of path in maximum-flow algorithm
I'm currently studying the maximum-flow algorithm and encountered the following problem:
The number on each edge is the capacity. I wonder what kind of bad choice can cause so many iterations. Thanks....
- 698
3
votes
2
answers
94
views
Maximum rectangle within a parallelogram
There is a quadrilateral with equal-length for opposite sides but the diagonals are different (and I hope the word parallelogram is correct here), what would be the biggest rectangle I can inscribe, ...
- 133
0
votes
0
answers
14
views
necessary condition of strict local minimizer
Given a function $f(x)$ which has up to 2 order continuous derivatives.
It is known that if $f(x)$ attains local minimum at $x=x_0$, then $f'(x_0)=0$ and $f''(x_0)\geq 0$.
I am wondering what is the ...
- 403
2
votes
2
answers
53
views
Finding minimum value of $x^2+y^2+xy+x-4y+9$
What is the minimum value of $f(x,y)=x^2+y^2+xy+x-4y+9$ ?
I tried completing squares,
$$x^2+y^2+xy+x-4y+9=\frac12(x^2+2xy+y^2+x^2+2x+1+y^2-8y+16+1)=\frac12[(x+y)^2+(x+1)^2+(y-4)^2+1]$$But not sure ...
- 5,543
1
vote
1
answer
41
views
Comparison of Wolfe conditions to other "weaker" conditions or facts about optimization techniques for conceptual understanding
So in the book, it states that the first wolfe condition is the following,
$\begin{equation}p^Tg_k\leq-\eta_0|||p|||g_k||\end{equation}$, where $g_k=\nabla F(x_k)$.
Here it states that this is a ...
- 365
0
votes
1
answer
43
views
How can I optimize an experimentally derived objective function?
I have to optimize the result of a process that depends on a large number of variables, e. g. a laser engraving system where the engraving depth depends on the laser speed, distance, power and so on.
...
0
votes
1
answer
64
views
Maximize $\sum_{i=1}^N \log\left( 1+a_i b_i c_i \right)$ under $\sum_{i=1}^N a_i \to \infty$ and $\sum_{i=1}^N a_i \to 0$
I have a log-sum maximization problem of the form:
$$
\max_{\left\{ a_i \right\},\left\{ b_i \right\},\left\{ c_i \right\}} ~ \sum_{i=1}^N \log\left(1+ a_i b_i c_i \right)
$$
subject to
$$
\sum_{i=1}^...
- 11
-3
votes
2
answers
24
views
How do I calculate the largest height of a cylinder with a given surface area? [closed]
I have encountered a problem where I am given a surface area of $24\pi\, \mathrm{in}^2$ and must find the largest height and radius that could be supported.
3
votes
0
answers
45
views
How many rounds does an Elo Rating System require to stabilise?
the questioner is not a mathematician
Using an Elo Rating System, or a 'modified' Elo Rating system ...
If I start a competition not knowing participants' relative ability
How many rounds are required ...
- 31
0
votes
1
answer
47
views
Determining best path for lighting up my bookshelf
I'm having an issue determining the best pathway. I have a bookshelf custom-made and here's a photo of it:
And here are the measurements of the same bookshelf. Other than the topmost rectangle which ...
0
votes
0
answers
10
views
Recommendations to minimize unknown function with categorical variables
Goal
The goal is to minimize an output variable of a computer code whose function is unknown, we will call it F. There are 25 input variables, xij, and 5 output variables, yk.
xij, where i ∈ [1,5] ...
- 101
0
votes
2
answers
31
views
Maximizing $f(x)=\frac{1}{1+\left|x\right|}+\frac{1}{1+\left|x-1\right|}$
Find the maximum value of the function
$$f(x)=\frac{1}{1+\left|x\right|}+\frac{1}{1+\left|x-1\right|}$$
For $1<x$, when $x$ increase both fractions decrease hence $f(x)$ decrease. Similarly for $x&...
- 5,543
0
votes
0
answers
13
views
The combination of partition solution of an optimization problem
Problem: min f(x), $x \in R^n$. If I have already got $x_1$ which is the optimized solution in space $[*, 1, 1, 1, \cdots]$, $x_2$ is the optimized solution in space $[1, *, 1, 1, \cdots]$, $x_3, x_4, ...
- 51
1
vote
0
answers
31
views
Which $n^2$ points of a finite grid minimize average $L^1$ distance to a uniformly drawn point?
This is a correctly tagged repost of my question I asked yesterday.
I came across the following problem:
Given a finite grid in $\mathbb{N}^2$ (or equivalently $\mathbb{Z}^2$) consisting of $a$ rows ...
- 459
0
votes
0
answers
13
views
Minimum distance between an ellipse and a hyperbola
An ellipse is specified in vector form as follows
$P_1(t) = C_1 + V_1 \cos(t) + V_2 \sin(t) $
where $C_1$ is the center of ellipse, and $V_1, V_2$ are mutually orthogonal, and extend along the semi-...
- 8,963
0
votes
0
answers
8
views
Minimum distance between two general parabolas specified in vector form
Two parabolas are specified in vector form as follows
$P_1(t) = C_1 + V_1 t + V_2 t^2 $
where $C_1$ is the vertex of the first parabola, and $V_1, V_2$ are mutually orthogonal, and extend $V_2$ along ...
- 8,963
1
vote
0
answers
17
views
Minimum distance between an ellipse and a parabola
An ellipse is specified in vector form as follows
$P_1(t) = C_1 + V_1 \cos(t) + V_2 \sin(t) $
where $C_1$ is the center of ellipse, and $V_1, V_2$ are mutually orthogonal, and extend along the semi-...
- 8,963
0
votes
0
answers
18
views
Minimum/Maximum distance between two ellipses
Two ellipses are specified in vector form as follows
$P_1(t) = C_1 + V_1 \cos(t) + V_2 \sin(t) $
where $C_1$ is the center of the first ellipse, and $V_1, V_2$ are mutually orthogonal, and extend ...
- 8,963