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.

Filter by
Sorted by
Tagged with
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$ ...
user avatar
  • 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\...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 $...
user avatar
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....
user avatar
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 ...
user avatar
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 $...
user avatar
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 ...
user avatar
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 $\...
user avatar
  • 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 ...
user avatar
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?
user avatar
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: $\...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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?
user avatar
  • 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 \...
user avatar
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 = \...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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\}$....
user avatar
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" ...
user avatar
  • 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 \...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
-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?
user avatar
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)<...
user avatar
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,...
user avatar
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 ...
user avatar
  • 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....
user avatar
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, ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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. ...
user avatar
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}^...
user avatar
  • 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.
user avatar
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 ...
user avatar
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 ...
user avatar
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] ...
user avatar
  • 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&...
user avatar
  • 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, ...
user avatar
  • 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 ...
user avatar
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-...
user avatar
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 ...
user avatar
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-...
user avatar
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 ...
user avatar

1
2 3 4 5
403