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.
2
votes
0answers
22 views
Formulate optimization problem
My research area has "nothing to do with mathematics" but I still find it full of optimization problems. Therefore, I would like to learn to formulate and solve such problems, even though I am not ...
0
votes
1answer
23 views
l1 norm and Frobenius norm
I would like to maximize the frobenius norm of a matrix product
$max_{X\in S}||B^TXA ||_F$
As this is too difficult so I relaxed it into l1-norm, that is
$max_{X\in S}||B^TXA ||_{l1}$
Yet I ...
1
vote
0answers
18 views
need help with raw distance function
I need help with the following function:
$$ \rho(x,\theta)=\min_{\lambda\in [0,\infty]} d(x ,x+\lambda[\cos \theta, \sin \theta]^T),$$
such that $$ x+\lambda[\cos \theta,\sin \theta]^T\in \bigcup_i ...
0
votes
1answer
23 views
Time bound for gradient descent
Have you seen any analytic bound on gradient descent (for number of iterations to achieve to $\epsilon$ error, and possibly based on the form of cost function and initial value)?
Here is the problem; ...
1
vote
2answers
24 views
gradient descent optimal step size
Suppose a differentiable, convex function $F(x)$ exists. Then $b = a - \gamma\bigtriangledown F(a)$ imples that $F(b) <= F(a)$ given $\gamma$ is chosen properly. The goal is to find the optimal ...
0
votes
1answer
28 views
Infeasible start Newton's method
I am implementing infeasible start Newton's method from the information in the slides (slide 11 of the link) posted here. It requires us to calculate primal and dual Newton steps, denoted by, $\Delta ...
2
votes
0answers
33 views
Least Squares Fit for Accelerometer Data
I am in the process of calibrating a triaxial Accelerometer. I have placed the Accel into 12 positions, each position should give the following 'ideal' G Values (X,Y,Z):
$0.7071000, 0.0000000, ...
0
votes
1answer
32 views
on the sufficiency of Lagrange multipliers
Suppose that we have a nonnegative polynomial $f(x) \in \mathbb{R}[x_1,\cdots,x_n]$ and we want to minimize it subject to the polynomial constraint $h(x)=0$ with $h(x) \in \mathbb{R}[x_1,\cdots,x_n]$. ...
0
votes
3answers
70 views
Maximizing triangle area
Here is the problem:
We start with a triangle ABC with area 1. We choose a point (F) on side AB, then someone else chooses a point (G) on side BC. We then choose the last point (H) on side CA. Our ...
1
vote
1answer
41 views
Optimal strategy puzzle
Play a game with an urn. $75$ blue balls. $25$ red balls. $1$ yellow ball. you get a dollar for every red and if you select the yellow you lose everything. what should be your strategy in the game. ...
1
vote
0answers
31 views
Where does this optimisation problem belong to?
I have the following optimisation problem:
Objective: to find $p_t, q_t$ that
$$
\max_{p_t, q_t} \sum_t^T (c p_t u_t - k q_t^2) e^{-\beta t} \tag{1}
$$
Constraints (for all $t$):
$$p_t+q_t=1 ...
2
votes
0answers
31 views
Optimization with symmetric matrix constraint
Consider the following optimization problem:
''Minimize some objective $f(A)$ over all matrices $A$ s.t. $A \mathbf{1} = \mathbf{1}$ and $A = A^T$.''
I wonder in which ways one can handle the ...
0
votes
2answers
35 views
Transpose of matrix inverse: $(AA^T)^{-1}A^Tb \stackrel{?}{=} (A^TA)^{-1}A^Tb$
Given the matrix equation:
$$ x^TA^TA = b^TA $$
I'm trying to find the least squares solution (i.e.; trying to minimize $r=||Ax-b||$). The matrix $A$ is not necessarily symmetric.
When I solve it ...
1
vote
0answers
15 views
Revised Simplex: reduced cost and related constraint
In the revised simplex method, you can get the reduced costs straightforward from the tableau. I know which they are, but I don't know which reduced cost I should "relate" to which constraint.
Will ...
1
vote
2answers
43 views
find maximum and minimum for any function
I'm writing an optimization algorithm thats supposed to find the maximum and minimum value of any given function. Whats the fastest numerical approuch to do so?
0
votes
0answers
30 views
How to calculate the hessian of a matrix function
I am estimating a model minimizing the following objective function,
$ M(\theta) = (Z'G(\theta))'W(Z'G(\theta))$
$Z$ is an $N \times L$ matrix of data, and $W$ is an $L\times L$ weight matrix, ...
2
votes
2answers
55 views
What is going on with this constrained optimization?
I'd like to figure out what is going on when trying to maximize a function (below $a_i$ are real numbers)
$F = a_1a_2 + a_2a_3 + \cdots + a_{n - 1}a_n + a_na_1;$
When we have active constraints
...
3
votes
4answers
111 views
Maximum surface inside a triangle
If I have a triangle with sides of length a, b, c and I have a rope of length L,
what is the maximum surface of a boundary I can form with that rope that is entirely
inside the triangle.
Normally, ...
1
vote
2answers
33 views
genetic algorithm binary encoding
I am trying to write a program for maximizing a function using a genetic algorithm. The function has $n$ integer variables $x_1 \dots x_n$, such that each variable is in the range [-n,n].
What is ...
3
votes
1answer
23 views
Maximizing a convex function
The following problem is exercise I.6 from Bellman's Dynamic Programming.
Consider the problem of maximizing the function
$$
F(x_{1} , \ldots , x_{N}) = \sum_{i = 1}^{n} \varphi(x_{i}),
$$
subject to ...
1
vote
0answers
33 views
How to project points in 3-space into a 2D subspace while minimizing the maximum change in Euclidean distance?
We have a small set of points in $\mathbb{R}^3$ (around 4 to 10 points, say). I would like to project these points onto a 2D subspace such as to minimize the maximum change in Euclidean distances.
...
-2
votes
2answers
64 views
What is the maximum of these expressions? [closed]
Let $0\le x_1,x_2,x_3,x_4,x_5\le 1$. What is the maximum of
$$|x_1-x_2|^3+|x_2-x_3|^3+|x_3-x_4|^3+|x_4-x_5|^3+|x_5-x_1|^3?$$
Let $0\le x_{i}\le 1$. What is the maximum of
...
0
votes
0answers
19 views
Understanding the Hamiltonian function
Based on this function:
$$\text{max} \int_0^2(-2tx-u^2) \, dt$$
We know that $$(1) \;-1 \leq u \leq 1, \; \; \; (2) \; \dot{x}=2u, \; \; \; (3) \; x(0)=1, \; \; \; \text{x(2) is free}$$
I can ...
-1
votes
2answers
29 views
Minimum ladder over wall optimization
A fence 6 feet tall runs parallel to a tall building at a distance of 2 feet from the building. We want to find the the length of the shortest ladder that will reach from the ground over the fence to ...
0
votes
1answer
28 views
Epigraph of a function f: D $\rightarrow$ R is convex iff epif(f) is a subset of D*R which is a convex set
As in the topic, how to show that $epi(f)$ is convex iff $epi(f)$ belongs to D*R which is a convex set.
0
votes
1answer
19 views
Strict local minimiser
Let $\Omega$ be a convex subset of $R^n$ adm f is a real valued, twice differentiable function. Let $x^*$ to be a point in $\Omega$ and suppose that there exists $c \in R \, c >0$ s.t. for all ...
1
vote
3answers
60 views
What is the dual of this optimization problem?
Consider the points $x_1, \ldots, x_N \in \mathbb{R}^n$, and a (locally bounded, convex) function $f: \mathbb{R}^n \rightarrow \mathbb{R}$.
I am looking for the dual of the following optimization ...
1
vote
1answer
51 views
Optimization: Minimize cost of pipeline
A small resort is situated on an island off a part of the coast of Mexico that has a perfectly straight north-south shoreline. The point P on the shoreline that is closest to the island is exactly 6 ...
0
votes
1answer
28 views
Optimization and distance (minimum time)
A small island is 5 miles from the nearest point P on the straight shoreline of a large lake. If a woman on the island can row a boat 2 miles per hour and can walk 3 miles per hour, where should the ...
2
votes
1answer
39 views
Minimum distance between $x = -y^2$ and $(0,-3)$
Find the minimum distance from the parabola $x + y^2 = 0$ (i.e. $x = -y^2$) to the point $(0,-3)$.
This is a homework question. When I try to use the derivative and substitute $-y^2$ for $x$, I ...
0
votes
2answers
38 views
Optimization and window area
A Norman window has the shape of a rectangle with a semi circle on top; diameter of the semicircle exactly matches the width of the rectangle. Find the dimensions of the Norman window whose perimeter ...
0
votes
2answers
25 views
Optimization and Rent
The manager of a large apartment complex knows from experience that 110 units will be occupied if the rent is 342 dollars per month. A market survey suggests that, on the average, one additional unit ...
1
vote
1answer
17 views
Optimization and fence size
A fence is to be built to enclose a rectangular area of 250 square feet. The fence along three sides is to be made of material that costs 6 dollars per foot, and the material for the fourth side costs ...
0
votes
0answers
27 views
Facets of the convex hull as solution of an optimization problem?
Given $N$ points $x_1, x_2, ..., x_N \in \mathbb{R}^n$, consider their convex hull $$\mathcal{C} = \text{conv}( \{ x_1, ..., x_n \} ) = \bigcap_{j=1}^{J} \{ x \in \mathbb{R}^n : \ A_j x \leq b_j \} ...
0
votes
0answers
21 views
Calculus of variations-fields and weierstraß excess function.
if i have a lagrangian $$L (t,x(t),y(t),\dot{x}(t),\dot{y}(t))$$ that depends on two functions and one parameter.
Then I will get two Euler-Lagrange equations as a test for extrema. Let us assume ...
1
vote
1answer
35 views
What is the minimal isoperimetric ratio of a polyhedron with $5$ vertices?
I'm asking and answering this question to provide a partial answer to this question and a comment on this answer at MO.
The isoperimetric ratio $\mu$ of a solid is the ratio $A^3/V^2$, where $A$ is ...
1
vote
3answers
45 views
Constrained optimization max $ f(x,y) = x+y$ subject to $x^2+y^2 \leq 4, x \geq0, y \geq0$
max $ f(x,y) = x+y$ subject to $x^2+y^2 \leq 4, x \geq0, y \geq0$
I need to solve this by the Kuhn Tucker conditions without using concavity of the Lagrangian.
0
votes
0answers
12 views
Submodular Function Maximization (poly-time approximations)
I have recently started to dive into the field of submodular function maximization. To be more specific, I consider functions that are non-monotone and non-negative. I am aware of recent work (Feige, ...
0
votes
1answer
60 views
Optimization. I need help finding the maximum profit
Josh wants to start a cell phone repair business. Josh determines that $x$ phones can be repaired daily at $p$ dollars per repair, where $x=175-p$. The cost of repairing $x$ phones per day is ...
0
votes
1answer
48 views
hessian matrix not positive definite at a minimum?
I have a function for which I want to find the global minimum. The function is:
...
0
votes
1answer
29 views
Optimizing the area of a triangle in space.
A triangle has two corners, $(8,0,3)$ and $(0,8,3)$ and a third curve in space that consists of all points $(8,8,a^{2}+3)$, where $a$ is a real number. Calculate the area of the triangle as a function ...
1
vote
0answers
33 views
Formulation of a problem as semidefinite programming
I would appreciate some help with this problem:
$R$ is a positive semidefinite matrix $\in{R}^{n\times n}$, $A \in{R}^{n\times m}$.
I need to formulate this optimization problem as semidefinite ...
0
votes
1answer
28 views
$(a - b \cot \theta) \cos^2 \theta = -\frac{b}{2} \cot \theta$ ,$\theta=$?
This question is a follow up question to this answer.
In the equation:
$$(a - b \cot \theta) \cos^2 \theta = -\frac{b}{2} \cot \theta.$$
$a$ and $b$ are given. What is the best way to solve for ...
2
votes
0answers
43 views
Find argmax_x corr(Ax, Bx) for vector x, matrices A and B
This is similar to, but not the same as, canonical correlation: For (n x m) matrices A and B, and unit vector (m x 1) x, is there a closed-form solution to maximize the correlation between Ax and Bx ...
0
votes
1answer
34 views
3-D Absolute Max/Min over closed&bounded region
Find the absolute max and min values of $f(x,y)=2x+y^2-2$ on the closed and bounded region that lies outside the upper half-circle of $\{(x,y)| x^2+y^2=1\}$, and inside the rectangle given by ...
2
votes
0answers
40 views
SDP relaxation of non-convex QCQP and duality gap
Short version
Is there a duality gap between a QCQP problem and the SDP problem obtained through lagrangian relaxation?
A paper I'm studying is using this fact, but I cannot achieve the authors' ...
0
votes
1answer
66 views
Find maximum of the function $f(x)=\dfrac{e^{\frac{2x}{x+1}}-1}{x}$
Let $x\ge0$. Find maximum
$$f(x)=\dfrac{e^{\frac{2x}{x+1}}-1}{x}$$
I think this maximum is $2$, I hope this problem have some nice solution,Thank you
0
votes
0answers
19 views
proof of convergence theory
The question is:
Suppose that lim $x_k=x_*$, where $x_*$ is a local minimizer of the nonlinear function $f$. Assume that $\triangledown^2 f(x_*)$ is symmetric positive definite. Prove that the ...
0
votes
3answers
40 views
Finding the max/min distance from an ellipse to a line (Lagrange Multiplier Method)
An ellipse is specified $ x^2 + 4y^2 = 4$, and a line is specified $x + y = 4$. I need to find the max/min distances from the ellipse to the line.
My idea is to find two points $(x_1, y_1)$ and ...
2
votes
0answers
39 views
Use of low rank approximation of a matrix
I am trying to figure out why do we need a low rank approximation of a matrix. Why is it used and where? Any insights?
