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)

0
votes
0answers
34 views

Vertices of Polyhedral

Suppose there are matrix $A\in\mathbb{R}^{n \times m}$ and vector $b\in\mathbb{R}^n$. Consider a non-empty polyhedron $P = \{Ax \leq b\} $. Then, there exists a vector $\bar{x}\in P $ such that ...
1
vote
1answer
39 views

Constrained Optimization : Minimize sum of dot products

I am working on a problem to minimize sum of dot product. The problem can be stated as following. Given a matrix where each element is either 0 or 1. $$ \ A_{ij} = \{0,1\}; $$ with the constraint ...
1
vote
0answers
20 views

Lagrange multipliers for minimax optimization

Does the equally constrained minimax optimization can be solved by using Lagrange multiplier method? Thanks in advance.
0
votes
2answers
50 views

Cost per item. Diminishing marginal discount, if you will. (Bigger discount for first few items) Optimal number of units to buy?

The graph above shows price per unit. Say they are cupcakes. When you buy a higher quantity, you get a lower price per unit. Say it levels off like this graph. Obviously, buying 2 nets a nice ...
13
votes
1answer
354 views

Can a dynamic programming problem be transformed into a linear algebra problem?

Here is a simple standard economic problem: Let Robin Crusoe have an endowment $w_0$ of lembas bread. She is immortal and discounts at a rate of $\beta$ per period. Each period (from $t=0$ on) she ...
1
vote
2answers
21 views

How to mathematically prove the optimality conditions for a univariate function?

Consider a univariate function $f(x)$. I know the graphical intuition behind why $f'(x)=0$ at the extrema of $f$. But how do you prove it mathematically? I start with the assumption of $x^*$ being a ...
2
votes
3answers
73 views

Maximum value of $a+b$ given that $\frac{1}{a} + \frac{1}{b} = \frac{1}{20}$

What is the maximum value of $a+b$ given that $\frac{1}{a} + \frac{1}{b} = \frac{1}{20}$ here $a,b \in \mathbb{Z^+}$? What I have gotten so far: From the above, $\frac{a+b}{ab} = ...
0
votes
0answers
11 views

How does the Lagrangian multipliers equation for multiple equality conditions follow?

I understand the intuitive narrative that wikipedia gives. I understand until the part that says: $\triangledown f \in S$, which means $\triangledown f$ is also an "illegal" direction, along with the ...
0
votes
0answers
24 views

Cost optimization subject to constraints

I am having trouble coming up with a solution (I don't even know where to start) for a cost optimization scenario. I need to minimize the cost of purchasing x number of different products (prices of ...
1
vote
0answers
21 views

Reconstruct a vector with a known vector and residual

I observe $\vec y \in \mathcal R^n$ and know $\vec x$. I assume that $\vec y$ mostly consists of $\vec x$, with some added residual $\vec r$. This gives me the problem $\vec y = a\vec x + \vec r$, ...
2
votes
2answers
62 views

The minimum of $x^2+y^2$ under the constraints $x+y=a$ and $xy=a+3$

I solved the following problem: If $x,y,a \in \mathbb{R}$ such that $x+y=a$ and $xy=a+3$, find the minimum of $x^2+y^2$ Here is my solution. $x^2+y^2=(x+y)^2 -2xy= a^2-2a-6$. The minimum value is ...
-7
votes
3answers
85 views

Can you provide an alternative formula for the minimum of two numbers?

Today I've done a wonderful discovery. I've found out that the following operation between two real numbers actually is the maximum of those two numbers: $$ \max(a,b) = \log(\log(\exp(\exp(a))) + ...
0
votes
0answers
35 views

Can a polygon with minimal perimeter self-intersect?

Recipe. Do the following. Throw $N$ random points $(x_0,y_0),(x_1,y_1),x_2,y_2),\cdots,(x_{N-1},y_{N-1})$ in the plane.Define $(x_N,y_N)=(x_0,y_0)$ : enumeration is $\mod N$ . These points are joined ...
3
votes
1answer
85 views

Optimization with probability densities - Lagrange multipliers

This question is concerned with the paper "A Lower Bound for a Probability Moment of any Absolutely Continuous Distribution with Finite Variance" by Sigeiti Moriguti appeared in Ann. Math. Statist. ...
0
votes
0answers
11 views

Nonlinear programming-separable programming

i have this function: $$5x_1x_2+4x_2x_3$$ and i need yo know if is separable or not I guees is not separable, because i can´t write the function in form: $$f_1(x_1)=x_1$$ and $$f_2(x_2)=x_2$$ ...
1
vote
0answers
90 views

How can I find the unit vector that minimizes the number of nonzero projections that a set of points has on it?

$\underset{\mathbf{w}}{\min} ~ \|\mathbf{X}^T\mathbf{w}\|_1~~~\text{subject to:}~ \|\mathbf{w}\|_2^2=1$ where $\mathbf{X}\in\mathbb{R}^{d\times m}$ is a set of $d$-dimensional points and $m>d$. ...
3
votes
0answers
29 views

Compactness in minimax theorem

According to Von Neuman's minimax theorem we have $$\max_{x\in X} \min_{y\in Y}f(x,y)=\min_{y\in Y} \max_{x\in X} f(x,y)$$ for some compact sets $X$ and $Y$ and a convex (in $y$), concave (in $x$) ...
0
votes
0answers
47 views

How can we find $\frac{2^m}{e^n}$ with an accuracy of $10$ decimal digits?

If $n$ and $m$ extremely large (1000 digits) and $1 <\frac{2^m}{e^n} < e$, how can we create an effective algorithm to find $\frac{2^m}{e^n}$ with an accuracy of $10$ decimal digits (10 digits ...
1
vote
0answers
56 views

Efficient calculation of minimal expected number of inversions

Problem: I have an array of size n with Z inversions initially and I am allowed to perform K operations where each operation can be decrease the number of inversions by 1. make a random shuffle of ...
1
vote
1answer
313 views

Using gradient descent and Newton's method combined

I have this function $f(\mathrm{X})$ where $\mathrm{X=A+B+C}$ where $\mathrm{A}$ is a diagonal element with variable $a$ on its diagonal. $\mathrm{B}$ is another diagonal matrix with variable $b$ on ...
1
vote
1answer
29 views

Exchanging max and expectation

If $X$ is a random variable and $\rho$ is a parameter, and $L$ is a concave function of $(\rho,X)$, under what conditions is the following statement true? $$\mathbb{E}\max_{\rho} L(\rho,X) ...
5
votes
1answer
159 views

Is this function concave or can it be made concave?

I am working with a point process with an event arrival rate of: $$ \lambda(t) = \mu + \sum\limits_{t_i<t}{\alpha e^{-\beta(t-t_i)}}$$ where $ t_1,..t_n $ are the event arrival times. The log ...
3
votes
3answers
133 views

Distributed Convex Optimization Algorithm

Consider the convex optimization problem $$ \min_{x_1, \cdots, x_N, y} \sum_{i=1}^{N} f_i(x_i,y) $$ $$ \text{subject to: } x_i \in X_i \ \ \forall i, \ \ y \in Y, \ \ y = \sum_{i=1}^{N} x_i $$ ...
0
votes
2answers
66 views

How to write such a constraint?

I have the following constraint that I need to write in an optimization problem but I failed to do it. Let $x_{ij}$ be a binary variable. So that: $$ x_{ij} = \begin{cases} 1, & \text{if $i$ ...
1
vote
2answers
165 views

Prove that if all edge-costs are different, then there is only one cheapest tree.

Prove that if all edge-costs are different, then there is only one cheapest tree (minimum spanning tree). (Use contradiction and make sure to keep track of the costs of the different trees involved.) ...
3
votes
2answers
2k views

Maximum area of a triangle in a square

For a given square, consider 3 points on the perimeter to form a triangle. How to prove that: The maximum area of triangle is half the square's. The maximum area of triangle occurs if and only if ...
1
vote
1answer
133 views

How to solve this optimization problem with equality constraints?

I want to find $\delta_j$ in the following optimization problem. My variables are $\gamma_i$ and $\delta_j$ (all other symbols are known parameters). Assume $i\in\{1,\ldots,9\}$ and ...
3
votes
0answers
116 views

Finding optimal velocity profile using Dynamic Programming

This question has been asked on scicomp but I thought maybe it's more a mathematical problem of how Bellman's idea is to be applied here. The main problem for me is: How to introduce the time ...
2
votes
0answers
21 views

Adding a constant to a list of numbers so that the sum of distances to integer values is minimal

I have a list of numbers {$x_i$} and I want to shift them (add a constant $\delta$) so that they are as close as possible to integer numbers in the sense that the summed distance to integer numbers ...
2
votes
2answers
271 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 ...
0
votes
1answer
721 views

How do I construct the Jacobian for use in a Levenberg-Marquardt algorithm.

I am working on a 3D reconstruction system and I am looking to use a Levenberg-marquardt algorithm to do bundle adjustment. I am not too sure about how LM works and what it requires. The model I am ...
0
votes
0answers
11 views

Question on simple quadratic word problem regarding weekly revenue when price of merchandise is lowered

A store owner sells headphones at 24 dollars a piece with roughly 1000 sold per week. The store owner finds that for every 1 dollar decrease on the price per headphone he sells 100 more headphones per ...
0
votes
1answer
30 views

Minimizing a non-convex rational function of two variables

I need to minimize the following function $$f(x,y)= \frac{a}{x}+\frac{bx}{y}+\frac{cy}{x}+dy+\frac{e}{y}$$ where $a,b,c,d$, and $e$ are positive constants, and $x$ and $y$ are both strictly positive. ...
0
votes
1answer
27 views

closed form vs gradient descent baseed methods

I am a beginner to optimization. Could anybody give me a simple example to illustrate when I should use closed form and when I should use iterative methods like gradient descent? Thanks in advance.
0
votes
1answer
103 views

Closed form solution

I have the following optimization problem: $$\min_{\mathbf{G}} \|\mathbf{B(A+G)\|_F^2} \quad{} \\\text{subject to} \quad{} \mathbf{\|C^T(A+G)\|_F^2\leq \gamma \|A^T(A+G)\|_F^2 } \quad{}, \\ ...
1
vote
1answer
79 views

maximizing a quadratic over linear function

Recently I am trying to solve the following optimization problem: $$ \begin{array}{cl} \text{maximize} & \frac{\left(c_1^T x\right)\left(c_2^T x\right)}{d^T x}\\ \text{subject to} & a^Tx\leq b ...
0
votes
0answers
24 views

Simple Optimization Problem with linear Algebra

I'm asked to find that the solution of $\displaystyle S(\mathbf{c})=\max_{\mathbf{c}}\frac{\mathbf{X' Z c}}{||\mathbf{X}||\cdot||\mathbf{Z c}||}$, where $\mathbf{X}$ is a $n\times1$ vector, and ...
16
votes
4answers
484 views

How fat is a triangle?

The slimness factor of a geometric shape in 2 dimensions is the ratio between the side-length of its smallest containing square and its largest contained square. This is an important factor in ...
0
votes
0answers
17 views

How to find a separating hyperplane?

I know about support vector machine, and it's quadratic programming approach which delivers the best separating hyperplane. My question is: is there a relatively simple algorithm to find a ...
0
votes
1answer
13 views

On the optima of probabilistic bounding functions

I have a function $f(x)$ for which finding the optimum (maximum) appears to be analytically intractable and numerically difficult. I have simple expressions for upper and lower bounds on this ...
0
votes
0answers
20 views

Are iterations involving quantization going to converge?

For $i = 1,2,3$, let $~f_i(y_i)~$ be a convex and differentiable function and $y_i$ a scalar variable. Consider the following iteration $$\left[ \begin{array}{c} \nabla f_1(y_1^{k+1}) \\ \nabla ...
2
votes
0answers
24 views

Constrained Quadratic Optimization(Reproducing Kernel)

I am attempting to use a constrained quadratic optimization to find the coefficients of a reproducing kernel. The problem is as follows: $y(t)=\sum_{i=0}^J\alpha_iK(t, t_i)$ $Q(\alpha)= ...
0
votes
1answer
21 views

how to differentiate to optimize this function?

I have an optimization function in the following form: $E = \operatorname*{argmin}_{A} \sum_j \| A\bf{x}_j - B \|_2^2 + \mu\sum_i a_{ii}^2$ Where, A is an unknown diagonal matrix with elements ...
-1
votes
1answer
21 views

Application of a derivative [closed]

A spherical projectile 40 cm in diameter and weighing 32kg is shot directly upward from ground level at 196m/sec. Ignoring air resistance during its flight, what is the max height the ball will ...
3
votes
0answers
57 views

What is the 'optimal' equal-area partition of a circle?

What is the (an?) n-partition of a circle that meets the following criteria: The boundaries of each partition can be represented as a union of finitely many finite-piecewise-smooth simple closed ...
2
votes
1answer
37 views

Minimum of $f(x,y)=|ax-by|$.

What is the minimum of function \begin{align} f(x,y)=|ax-by| \end{align} subject to constrains \begin{align} 0 \le x \le C_1\\ 0 \le y \le C_2 \end{align} I found a similar question here Minimum of ...
0
votes
1answer
21 views

Finding extremal of a fixed end point problem. Optimisation

I want to find the extremal of the fix-end point problem $\int_1^2 \frac{\dot{x}^2}{t^3}$ with $x(1)=2,x(2)=17$ First I check the euler-lagrange equation is equal to $0$. We have: ...
1
vote
0answers
9 views

Minimizing matrix norm with quotient constraint.

Is there a systematic method of solving the following? $$ \begin{equation*} \begin{aligned} & {\text{minimize}} & & \left\|A \right\|_2 \\ & \text{subject to} & ...
0
votes
1answer
29 views

Why is alternative sign in Hessian subdeterminant a necessary and sufficient condition for multivariable maxmization

The necessary and sufficient condition for a maximal point in a multivariable function is the following $$\text{i. } x \text{ must satisfy first order condition}$$ $$\text{ii. } |H|_1 < 0 \text{ ...
1
vote
0answers
14 views

Local minima: Sufficient conditions. Comparison of Calculus verses Calculus of Variations

My lecturer has written: Let $y=x^*+\epsilon \eta$ where $x^*,\eta,y\in \mathbb{R}^2$ $0\leq f(y) - f(x^*) = \epsilon V_1 + \epsilon^2 V_2 + O(\epsilon^3)$ $V_1 = \nabla f(x^*)\eta$ $V_2 = ...