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)

1
vote
4answers
26 views

Why must the determinant of the hessian of a scalar function be positive for there to be a local min/max? Intuition needed

Is there any intuition behind having the determinant of the Hessian matrix being negative corresponding to a saddle point, and positive corresponding to a max/min depending on the sign of $f_{xx}$ for ...
0
votes
0answers
16 views

Optimal Apple Eating Strategy

You hate apples. As a result, you have angered the apple king and are being punished. You will have to eat $n$ apples before the apple king is willing to let you leave. The apples are marked from $1$ ...
2
votes
3answers
122 views
+200

A trigonometric problem when calculating distance to the boundary of a convex hull

Suppose we have a sphere and a point outside of the sphere. We denote the point outside as $v$ and the origin of the sphere as $x$. The convex hull of the sphere and $v$ should be like an ice cream ...
0
votes
0answers
12 views

Best fit curve through several line segements

I have a question about creating a best fit curve that incorporates several lines on a graph. To give some background, I am working on the geometrical design of a solar reflector. The reflector is ...
0
votes
0answers
32 views

Problem of assign $n$ workers to $n$ jobs.

Suppose that you assign $n$ workers to $n$ jobs. If the worker i has the work j, you get a profit of $p_{ij}$. Considere the problem $$\max{\sum_{i=1}^{n}{\sum_{j=1}^{n}{p_{ij}x_{ij}}}}$$ with $\sum_{...
1
vote
0answers
15 views

Quadratic trace minimization with block diagonal constraints?

Given matrix $A$ and symmetric matrix $B$ with $0$'s on the diagonal and nonnegative values off-diagonal (imagine $B$ is a distance matrix), I have trouble solving $$\min_X\operatorname{tr}(A^TX^TAA^...
0
votes
2answers
30 views

On the maximal of polynomial at a point

I faced this problem when I studied polynomial. Let $p(x)=ax^3+bx^2+cx+d$ be a cubic polynomial with real coefficients, and $p(5)+p(25)=1906$. Find the maximal value of $|p(15)|$. I ...
0
votes
0answers
14 views

Optimize an Trace matrix form

In paper " Generalized Low Rank Approximations of Matrixces the Dimension of matrix are follow: $A_i$ is $r$ x $c$ L is $r$ x $l_1$ R is $c$ x $l2$ $D_i$ is $l_1$ x $l_2$ why it says ...
2
votes
1answer
23 views

Trace minimization problem with “block diagonal diagonal” constraints?

I've reduced my optimization problem to the following trace minimization problem: $$\min_X\text{tr}(AXB),$$ subject to that $X$ is a block diagonal matrix whose blocks are all the same -- a diagonal ...
6
votes
2answers
96 views

What is the optimal route for visiting Pokéstops in Pokémon Go?

Okay, I've got a fun problem for you, which was not suited for the gaming stackexchange: Pokéstops are GPS locations with a certain radius. When you are in the radius, you can get certain ingame ...
0
votes
0answers
16 views

Lagrangian fuction for optimization problem

I have an optimization problem \begin{equation}\label{eq:optimi_joint1} \begin{aligned} \text{minimize}_{\mathbf{w_p}\in \mathbb{R}^M,\mathbf{\Lambda_p}\in \mathbb{R}^{M\times M}} \ \ &\kappa \...
0
votes
0answers
32 views

Developed a function optimization strategy - need opinions

I've developed a function optimization strategy which is close to evolutionary optimization strategies. It works fine for various functions, but cannot be used with thorough success for functions with ...
1
vote
0answers
31 views

What would the derivative of this objective function be?

My question comes from image processing community, In our Machine Learning algorithm, we have a predicted value $D$ and its equivalent ground truth $D^*$ where their difference is: $d_i=D-D^*$. (...
1
vote
1answer
70 views

The Jeep Problem and Nash's Friends

The classical jeep problem is the following. A jeep can carry a maximum load of fuel of 1 gallon, and it travels $l$ miles with $l$ gallons of fuel. The jeep moves along a straight line, and is ...
4
votes
1answer
89 views

Show that $(a + b)^4 + (a + c)^4 + (a + d)^4 + (b + c)^4 + (b + d)^4 + (c + d)^4 \le 6$ for $a^2 + b^2 + c^2 + d^2 = 1$.

For $a, b, c, d \in \Bbb R$ such that $a^2 + b^2 + c^2 + d^2 = 1$, show that $$(a + b)^4 + (a + c)^4 + (a + d)^4 + (b + c)^4 + (b + d)^4 + (c + d)^4 \le 6.$$ The answer uses the mysterious identity $$...
0
votes
0answers
20 views

Linear programming optimization problem

I need some hint, where I can find programming algorithm for next optimization problem. I need to write a code to solve some system of equations with several restrictions. Let's assume, we have $N$ ...
0
votes
0answers
25 views

Equivalence between standard optimization problem and Langragian form

Given a problem: $$\min_x f(x)$$ subject to $$g(x) \le C$$ In general, when it is equivalent to the problem $$\min_x f(x) + \lambda g(x)$$ for certain $\lambda$? Here my equivalence means : the ...
0
votes
0answers
17 views

Maximum point of a modulus function

For our project on Maxima and Minima of functions, we have to do functions of type $\frac{k}{|x-a|+|x-b|}$. So, I chose $f(x)=\frac{2}{|x-1|+|x-2|}$ I noticed that the derivative is positive for $x&...
0
votes
0answers
14 views

Optimal way to partition sum of linear equitations

Suppose we know the values of $x_i$, $i=1,2,3,...,n$. How do we choose an integer $k$ such that $\sum_{i=1}^{k-1} (k-1-i)x_i + \sum_{i=k}^{n} (n-i)x_i$ is minimized; $0 \leq k \leq n$? My initial ...
1
vote
0answers
36 views

maximising sinusoidal functions

I have come across a maximisation problem that I do not know how to handle. I have posted the question here in the past. I have the following function to maximise for $x,y$ $$f(x,y)=a_1 \cos(x) +b_1 ...
1
vote
0answers
34 views

The Jeep Problem with Equally Spaced Stations

Consider the following problem. A jeep can carry a maximum load of fuel of 1 gallon, and it travels $l$ miles with $l$ gallons of fuel. The jeep moves along a straight line, and is required to cross a ...
0
votes
0answers
48 views

Maximising sum of sine/cosine functions

I have got a problem and I would appreciate if one could help. I have to maximise following function that is the sum of sine/cosine functions: $$ f(x,y)=a_1 \cos(x) +b_1 \sin(x)+ a_2 \cos(y) +b_2 \...
1
vote
2answers
17 views

Evenly filling spaces for a specific average value

Imagine I have $N$ spaces. Each space can be empty, or occupied. Given a fixed point value $x$ between zero and one, I would like to evenly populate the $N$ spaces such that $\frac{N_{\text{occupied}...
0
votes
0answers
20 views

Solving simple LP problem with Lagrange multipliers

Hi just as a test I'm trying to solve the following LP with Lagrange multipliers. $min -x_1$ $s.t$ $x_2 \leq 1 - x_1$ $x_1, x_2 \geq 0 $ I add slack variables to have a equality constrained LP ...
0
votes
0answers
5 views

Optimisation: mayer, lagrange and bolza problem

Regarding the determination of an optimal curve, can someone please help me and define the mentioned problems in words, i.e. when to use what. I know, that a bolza problem is the combination of mayer ...
0
votes
1answer
31 views

Confusion of a formula about Lagrangian

Recently, I am reading a paper about eigenvalue problems. Consider the following problem, which occurs at the first page of the paper. \begin{align} \text{minimize}\quad &x^TAx \\ \text{subject ...
1
vote
1answer
50 views

Meaning of $Ax \leq b$

I continue to come across $Ax \leq b$ or $Ax= b$ in optimization problem, but I am having trouble interpreting the meaning of this. Does this have a similar meaning to the following (Cramer's Rule) ...
0
votes
0answers
20 views

From constrained to unconstrained optimization

I have the following convex optimization problem: \begin{equation}\label{prob} \begin{aligned} &\underset{{\bf W, \xi}}{\text{min}} & \frac{1}{2} ||{\bf W}||_2^2 + \sum_{i=1}^n C_{y_i}\max(0,...
0
votes
0answers
16 views

Formulation of constraints

I would like to formulate the following constraints in a tractable form so that I can perform an optimization over the decision variables $A,x_i,y_i$: $$ A + \sum_{i=1}^N x_i D_i + \beta \big(\sum_{i=...
2
votes
1answer
31 views

Existence of absolute maxima and minima

In which of the following functions can be guaranteed the existence of absolute maxima and minima? a) $f(x,y,z)=x+y$ with $z\geq x^2+y^2+1$. b) $f(x,y)=\ln (x^2+y^2+1)$, with $x\geq 0$ and $y\geq 0$...
2
votes
2answers
30 views

What is the coordinate of the maximum value of a quadratic function given by two points and axis?

There are only three pieces of information available: the graph passes through (0,0) and (6,0) the symmetry axis is $x$ = 3 the graph is downward My attempt: I've tried to work on ...
6
votes
6answers
18k views

Find the area of largest rectangle that can be inscribed in an ellipse

The actual problem reads: Find the area of the largest rectangle that can be inscribed in the ellipse $$\frac{x^2}{a^2} + \frac{y^2}{b^2} = 1.$$ I got as far as coming up with the equation ...
0
votes
1answer
815 views

Sum of two polyhedra is a polyhedron

I'm reviewing for a midterm next week in an optimization course. Currently, I'm having a great deal of trouble with a review problem. The problem is as follows: Let $P$ and $Q$ be polyhedra in $\...
12
votes
3answers
1k views

Intuitive explanation for formula of maximum length of a pipe moving around a corner?

For one of my homework problems, we had to try and find the maximum possible length $L$ of a pipe (indicated in red) such that it can be moved around a corner with corridor lengths $A$ and $B$ (...
1
vote
2answers
59 views

Subset of Coins with maximal value

Let $ n \in \mathbb{N} $ with $ n\ge 3 $ be given. Assume that you have $ k-1 $ coins of value $ 1/k $ for all $ k \in \lbrace 2,\ldots,n \rbrace $. Now you have to choose a subset of these given ...
1
vote
0answers
57 views

Big Balloon Game

The problem In this game, you are given empty balloons one by one, and for each balloon you are to inflate it with air until you are satisfied. If it does not burst, you gain happiness points ...
0
votes
0answers
10 views

Pythagorean Theorem to Optimize Multiple Variables?

I'm not sure if this is an already established thing or something I just made up that feels good. I have a list of board games that I'm interested in buying based on their price, their overall ranking ...
3
votes
1answer
101 views

Minimize $P(x,y,z)=(2x+3y)(x+3z)(y+2z)$, when $xyz=1$

Find the minimum value of the product $P(x,y,z)=(2x+3y)(x+3z)(y+2z)$, when $xyz=1$ and $x,y,z$ are positive real numbers. I don't know how to go about this. AM-GM got really messy, and I don't know ...
0
votes
2answers
450 views

Maximum and minimum of determinant of matrices with entries from $\{0,1\}$ or $\{-1,0,1\}$

Maximal and Minimal value of $\bf{3^{rd}}$ order determinant whose elements are from the set $\bf{\{0,1\}}$. Maximal and Minimal value of $\bf{3^{rd}}$ order determinant whose elements are from the ...
0
votes
0answers
13 views

Maximum Likelihood Estimation: Multivariate Gaussian function. Matrix calculus

I am reading a paper and trying to understand how the authors estimated the standard errors of a set of parameter estimates $[\delta\ \ \phi \ \ \Sigma]$. Below is the loglikelihood function (sorry I ...
0
votes
3answers
71 views

Maximizing $f(0)$ given that $f(3)=5$ and $f'(x)\ge1$ [on hold]

Let there be $$f:(-1,4)→ R$$ $$\text{differentiable on} (-1,4) , f(3)=5 , f'(x)≥-1$$ $$\text{which is the maximum value of}$$$$f(0)$$
1
vote
1answer
165 views

Find the max volume using polynomials with the sum of the height and perimeter less than 100cm

I have to find out which shape of packaging for a fragile object has the most volume to fit the object and styrofoam packing. The sum of the height and the perimeter must be less than $100cm$. There ...
2
votes
1answer
218 views

What is the difference between projected gradient descent and ordinary gradient descent?

I just read about projected gradient descent but I did not see the intuition to use Projected one instead of normal gradient descent. Would you tell me the reason and preferable situations of ...
1
vote
1answer
96 views

Difference between Gradient Descent method and Steepest Descent

What is the difference between Gradient Descent method and Steepest Descent methods? In this book, they have come under different sections: http://stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf ...
0
votes
0answers
16 views

Gradient descent with multiplication term

Say I have the objective: $\arg \min_{R, T} \|y - RTx\|^2_2$ where, R and T are matrices (not necessarily square) and y and x are known vectors. I wish to try and optimize R and T using Gradient ...
6
votes
2answers
2k views

Gradient descent with inequality constraints

Suppose we are given a convex function $f(\cdot)$ on $[0,1]$. One wants to solve the following optimization problem: \begin{equation} \begin{aligned} & \text{minimize} && \sum_{i=1}^n \...
2
votes
1answer
58 views

Lipschitz Number in Gradient Descent

During gradient descent, if an objective function's value is greater than the previous iteration, would use of an orthogonal vector to the update vector be advantageous? Regarding trust regions, the ...
0
votes
1answer
148 views

Gradient descent for periodic function

Problem: minimize E=$\sum_{t=0}^T [ Y(t)-\sum_{k=0}^K(X(t+k)*cos(k*F+PHI)) ]^2$ where F, PHI - has to be optimized; Y(t), X(t) 1D arrays are given; t=0...T; T=1000; k=0..K; K=10; I can use FFT ...
0
votes
1answer
47 views

Convergence of steepest gradient descent

The description of gradient descent in Wikipedia says: $$x_{n+1} = x_n - \gamma_n\nabla F(x_n)$$ for $n = 0,1,2,...$ Suppose that $x_n$ converges to $x$. Then, is it always true that $\nabla F(x) = ...
4
votes
1answer
994 views

Gauss-Newton versus gradient descent

I would like to ask first if the second order gradient descent method is the same as the Gauss-Newton method. There is something I didn't understand. I read that with the Newton's method the step we ...