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.
1
vote
3answers
78 views
Exponential extrapolation
Given a set of points on 2D surface $(x_1,y_1),(x_2,y_2),\ldots,(x_n,y_n)$ and a function $f(x)=k+ab^x$, the task is to find values of $k,a$ and $b$ that minimize the following sum:
$$\sum_{i=1}^n ...
0
votes
3answers
90 views
How to write “the parameter maximizing the maximum of the maximum value of two functions continuous in the domain of maximization”
Say you have $f(x),g(x)$ continuous where they need to be and you want to express the following:
Give me the biggest value of $f$ for $x \leq X_f$ , give me the biggest value of $g$ for $x \leq X_g$, ...
0
votes
0answers
39 views
How to solve total variation problem when the feature of points is a vector?
I'm trying to implement a total variation problem described in the paper "l1-sparse Reconstruction of Sharp Point Set Surfaces". It's different from the case of total variation in image, the feature ...
0
votes
1answer
22 views
What is the optimal stopping point for an experiment when expecting unknown event
Assume we notice that stock prices are rising and we can deduce we are in a bubble. Assume we start at $w(0)=0$ worth at time $t=0$ and the value grows linearly with time $(w(t)=t)$. We know that ...
1
vote
0answers
50 views
How to effectively detect negative cycles in graph?
I proposed to check the edge weighs and then run shortest path and check if the shortest path weight is not going to $-\infty$. Any better ideas?
0
votes
1answer
36 views
Proof of matroids
We have set $S$ and subset $I = 2^S \setminus \{S\}$. Show that $M=(S,I)$ is a matroid.
Is it graphic, linear or a matching matroid?
I am little struggling how to prove this, there should be 3 things ...
1
vote
1answer
57 views
Show that Minimum Spanning Tree is unique
Show that MST is unique in case the edge weights are pairwise different $(w(e)\neq w(f) \text{ for } e\neq f)$.
I thought that the proof can be done for example by contradiction,
saying that we ...
0
votes
2answers
29 views
Finding a minimum
I would like to minimize the function $f(x_1,\dots,x_k) = x_1 + x_2 / x_1 + \dots + x_k / x_{k-1} + M / x_k$ where $M>0$ and $x_k \ge \dots \ge x_1 \ge 1$.
First I looked at a simpler function ...
1
vote
0answers
46 views
Linear Programming: Modifying Coefficients of the Objective Function
Consider a final tableau with entries:
Row 1: 0,(-1/2),1,1,2,0,-1
Row 2: 1,(1/2),0,2,-1,0,-2
Row 3: 0,2,0,-1,(-1/2),1,3
Basic variable values (4,2,1)
and objective function coefficients ...
4
votes
2answers
79 views
Minimizing the length of a pipeline between cities
I have been trying to minimize piping going to two different cities. City A is located at $(0,4)$ and city B is located at $(6,3)$. The cities must connect to the $x$-axis (the main pipe line.) It ...
0
votes
1answer
79 views
Finding the minimum of $N = \frac{(a+3c)}{(a+2b+c)}+\frac{(7a+6b+3c)}{(a+b+2c)}+\frac{(c-a)}{(2a+b+c)}$ if $a, b, c \in \Bbb R$
Find the minimum of $$N = \frac{(a+3c)}{(a+2b+c)}+\frac{(7a+6b+3c)}{(a+b+2c)}+\frac{(c-a)}{(2a+b+c)}. \qquad (a,b,c \in \Bbb R^+)$$
1
vote
0answers
23 views
Approximating maxmimal value of Rayleigh Quotient in a set by minimizing distance towards the largest eigenvector.
Is the solution of the following two problems equal?
If no, under what circumstances they will be equal?
$P_1: argmax_{x\in S,x^Tx=1} x^TAx$
$P_2: argmax_{x\in S,x^Tx=1} ||x-\bar{x} ||_2$, where ...
1
vote
1answer
50 views
Hessian of a function that takes matrix arguments
I have a function that that takes a matrix and returns a scalar, $f : \mathbb{R}^{m\times n} \rightarrow \mathbb{R}$. I know how to calculate the derivative of this function with respect to the matrix ...
3
votes
0answers
84 views
How to minimize $\min_k k \frac{b^k/n}{\lfloor b^k/n \rfloor}$
This problem looks familiar, but I don't remember its solution:
$$ \min_k \ \ \frac{b^k/n}{\lfloor b^k/n \rfloor}k $$
subject to
$$ b^k \ge n \\ b,n,k \in \mathbb{N} $$
Does it have a name? What's ...
0
votes
0answers
100 views
Optimization problem given a known solution space
Here is my problem.
I have to find four points in 3D (x1,y1,z1; x2,y2,z2; x3,y3,z3; x4,y4,z4) that satisfy some given quadratic constraints. In addition, I have a solution space in the form of a set ...
2
votes
1answer
42 views
Determining the Existence of Global Minimum/Maximum
Determine whether the function defined as $$f(x,y,z)=x+y+z$$ has a maximum or a minimum value on the set $xy+yz=1$, $xz+yz=4$, $x>0$, $y>0$, $z>0$.
It is clear to me that it does have a ...
1
vote
1answer
32 views
Symbolic evaluation of an optimization problem
I'm looking at the following problem: Minimize $\sum_{i=1}^{m} \frac{x_i}{x_{i-1}}$ under the constraints $-x_0 \le -1$, $x_{i-1} - x_i \le 0$, and $x_m \ge N$ where $N>0$ and $m>0$ are some ...
0
votes
1answer
33 views
Prove a set in $\mathbb{R}^2$ is convex.
Let $$\Omega = \{(x_1,x_2)\in\mathbb{R}^2:x_1^2-x_2\leq 6\}$$
Prove that $\Omega$ is a convex set from first principles using the convex combination.
edit: Thanks Ewan for that, but I am trying ...
1
vote
1answer
75 views
Minimizing total cost function
In today's test (question c) I had to minimize equation $(3)$ and solve for N*.
I did it through deriving, setting to $0$ and solve for N (no doubts about that).
My question is, in this image it ...
1
vote
1answer
107 views
Property of strictly convex polynomial
I have some difficulties in the following problem.
Thank you for all comments and helping.
Let $f:\mathbb{R}^n\rightarrow \mathbb{R} (n\in \mathbb{N})$ be a polynomial.
Suppose that $f$ is strictly ...
0
votes
0answers
53 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 ...
0
votes
2answers
62 views
Anyone saw this interesting function before?
Say $\theta\in\Re^n$ and $\theta_i\in(0,1)$ for all $i$. Define
$$
f(\theta) = \frac{1}{n}\sum_i^n\{(1-\theta_i)\log(1-\theta_i)+\theta_i\log\theta_i\}
$$
It is easy to see the minimizer of ...
2
votes
1answer
42 views
Proof there exists a vector under certain constraints
This question is a basic optimization problem, also a linear algebra question:
Let $x$ be a feasible point for the constraints
$Ax=b$, $x\geq0 $
that is not an extreme point. Prove that there exists ...
3
votes
1answer
59 views
Optimization Problem.
I'm working on some calculus homework, which deals with optimization problems, we have the solution posted for us and when looking over it I got a bit confused. Here's the question:
An open ...
0
votes
1answer
53 views
Minimizing the function $\sqrt{2x} - \left\lceil \frac{\sqrt{1+8x}}{2} \right\rceil$ for $x > 0$
How can you find the minimum of $\sqrt{2x} - \left\lceil \frac{\sqrt{1+8x}}{2} \right\rceil$ for positive integer values of $x$?
1
vote
1answer
58 views
Maximize $x_1$ and $x_2$
I have the following question to tackle:
Maximize $x_1$ and $x_2$ for:
$$ x_1, x_2 \geq 0$$
$$ -x_1 + x_2 \leq 5$$
$$ x_1 + 4x_2 \leq 45$$
$$ 2x_1 + x_2 \leq 27$$
$$3x_1 - 4x_2 \leq 24$$
So I ...
0
votes
0answers
27 views
Non linear optimization Gradient method
Let $f(x)= x^2 -\frac{x^3}{3}$. Ok so i found the local min is at 0 and i was given $x_0=1,\alpha = \frac{1}{2}$, I dont understand how i am suppoused to find $x_k$ such that $x_{k+1}=x_k-\alpha ...
3
votes
2answers
62 views
In Search of a More Elegant Solution
I was asked to determine the maximum and minimum value of $$f(x,y,z)=(3x+4y+5z^{2})e^{-x^{2}-y^{2}-z^{2}}$$ on $\mathbb{R}^{3}$.
Now, I employed the usually strategy; in other words calculating the ...
1
vote
2answers
43 views
Finding absolute max and min values of function
Function given as $f(x,y) = 3x^2 + 2xy^2$. If $(x,y)$ lies in the region inside including edges of the triangle in the first quadrant given by $x\ge0, y\ge0, y\le2-x$. Reduce $f$ to a single variable ...
2
votes
1answer
79 views
Minimise $\sum_{i=1}^n \frac{1}{a_i + x_i}$ subject to constraint using Lagrange multipliers
Minimise $\displaystyle \sum_{i=1}^n \frac{1}{a_i + x_i}$ subject to $\displaystyle \sum_{i=1}^n x_i =b$, $x_i\geq 0$ for $i=1,\cdots , n$, where $a_i >0$ for $i=1,\cdots , n$ and $b>0$.
I know ...
1
vote
3answers
111 views
A constrained linear least Frobenius norm problem:$\min_{X} \|A-XB\|_F$ subject to $Xv=0$?
Assume we are given two matrices $A, B \in \mathbb R^{n \times m}$ and a vector $v \in \mathbb R^n$. $\|\cdot\|_F$ is the Frobenius norm of a matrix. How can we solve
$$\min_{X \in \mathbb R^{n ...
2
votes
1answer
67 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 + ...
0
votes
1answer
24 views
inequalities for optimization over psd matrices with constraints
Consider two p.s.d. matrices $A$ and $B$ both in $\mathbb{R}^{d \times d}$. Define $$a = argmax_{x \in \mathbb{R}^d} x^\top A x $$ and $$b = argmax_{x \in \mathbb{R}^d} x^\top B x $$ both subjected to ...
3
votes
3answers
107 views
Max and Min of $f(x,y)$
Let $f(x,y)=x(y \log y-y)-y \log x$. Find $\smash{\displaystyle\max_{\frac{1}{2} \leq x \leq 2}}(\smash{\displaystyle\min_{\frac{1}{2} \leq y \leq 1} f(x,y)})$.
2
votes
3answers
50 views
Packing radios into cartons - why is my solution wrong?
A manufacturer of car radios ships them to retailers in cartons of $n$ radios. The profit per radio is $\$59.50$, minus shipping cost of $\$25$ per carton, so the profit is $59.5n-25$ dollars per ...
3
votes
1answer
49 views
Some basic questions about minima of a real-valued functions
The following theorem is basically from the Fermat's Theorem page of wikipedia.
Let $X$ denote a subset of $\mathbb{R}$, and suppose $f : X \rightarrow \mathbb{R}$ attains
a global minimum at $x ...
2
votes
4answers
125 views
Minimize $\sum a_i^2 \sigma^2$ subject to $\sum a_i = 1$
$$\min_{a_i} \sum_{i=1}^{n} {a_i}^2 \sigma^2\text{ such that }\sum_{i=1}^{n}a_i=1$$ and $\sigma^2$ is a scalar.
The answer is $a_i=\frac{1}{n}$.
I tried Lagrangian method. How can I get that ...
0
votes
2answers
53 views
Please help to make me understand why I cant optimize this function: $U=x^{1/3}*y^{2/3}$ ?
If I want to maximize a production the function of which is given by $$L=-x^2+10x-2y^2+12y$$ I know I have to take the partial derivatives of of the function in respect to X and Y, so $$\frac ...
0
votes
0answers
28 views
Example of delayed column generation
Can someone point me to a small example of how delayed column generation works for the cutting stock problem. I have found several sources that describe it abstractly but I still don't understand ...
0
votes
0answers
56 views
Minimum of some functions
Denote $U=\{(x_1,x_2,...,x_n):0<x_j<1 (1\leq j\leq n),\sum_{j=1}^nx_j=1\}$.
Let $f_i=f_i(x_1,x_2,...,x_n)$ ($1\leq i\leq n-1$) be $n-1$ real functions which satisfy:
...
5
votes
5answers
237 views
Minimum of $x^2 + 3x - 1$ on $[0,1]$ and $[-2,2]$
Consider the problem of finding the absolute minimum of the function $f : [0,1] \rightarrow \mathbb{R}$ that satisfies $f(x)=x^2 + 3x - 1$ everywhere.
Suppose we suspect, by graphical methods, that ...
1
vote
4answers
151 views
How to get from high school math to optimization?
What are the math subjects that a person with high-school math background needs to learn to reach the point of learning and understanding different techniques of mathematical optimization? It would be ...
0
votes
1answer
37 views
Distributed Robust Optimization
Consider the following constrained optimization problem $\mathcal{P}$.
$$ \min_{x \in X \subseteq \mathbb{R}^n} f(x) \ \text{sub. to: } g(x,y) \leq 0 \ \forall y \in Y \subseteq \mathbb{R}^m $$
...
0
votes
1answer
57 views
HELP please with Optimization with constrain using lagrangian
I am reading this book on optimization and they present the following problem: Lisa wants to maximize her utility U(q1,q2) subject to a budget constrain, budget constrain is $p1*q1+p2*q2=I$.
Ok , I ...
1
vote
1answer
39 views
Distance between a point to a $2d$ ellipse in $3d$ ambient space
Suppose we are working in the 3D Euclidean space. We are given an arbitrary point $p$ and a 2d ellipse:
$$E=\{x:x^TQx\leq1,x^Tq=0\},$$
where $Q$ is a positive definite matrix and $q$ is an ...
1
vote
1answer
56 views
Non-trivial solution for $2*a^k = b^k + c^k$
I have a data set where I want its median to be the arithmetic average of maximum and minimum by multiplying every value with a factor $k$ and then applying the exponential function. This leads to the ...
4
votes
2answers
123 views
Wolves and chicks puzzle
This problem is from the handheld video game, Professor Layton and the Curious Village.
I think the solution is very cool, but more than that, I want to know how to show that the minimum number of ...
2
votes
1answer
61 views
Algorithm to find optimal cuts of pipe
I have varying lengths of pipe in inventory. When a customer requests various lengths I want to find the optimal way of cutting what I have in inventory. I need to make a program that does this.
This ...
0
votes
1answer
38 views
Find a number that minimizes distance to a vector of sets of numbers
Assumptions
$V$ is a vector of sets $V_1,V_2,...,V_n$ of numbers:
$V=[V_1, V_2,..., V_n]^T, \forall_{i=1..n}V_i\subset\mathbb{R}$
$c\in\mathbb{R}$ is constant
$d(V,c)$ is an error metric: ...
0
votes
1answer
37 views
Why do we use gradient descent in the backpropagation algorithm?
The common approach for training neural networks, as far as i know, is the backpropagation algortihm, which uses gradient descent to reduce the error.
(i) why should one use a fixed learning rate / ...
