Tagged Questions

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
2answers
27 views

Minimum of a function $f(x,y)=\frac{(1+2y)(1+\frac{x}{2})}{(1+y)(1+x)+x}$

what is the minimum of a function \begin{align} f(x,y)&=\frac{(1+2y)(1+\frac{x}{2})}{(1+y)(1+x)+x}\\ \text {s.t. }& 1 \le y \le x \le y(1+y) \end{align} I asked Wolfram and Alfa and it says ...
1
vote
0answers
13 views

Minimizing sample variance of $n$ functions

$f_n$, $i=1,\dots, n$ are $n$ functions. I would like to minimize the sample variance of these functions subject to a linear constraint: $$\text{minimize}\quad \frac{1}{N}\sum (f_i(x_i) - ...
0
votes
1answer
26 views

LP with a linear cost function $c^Tx$: Prove optimal value is $-\infty$ or there exist some $v \in P$ such that $c^Tv \le c^Tx$ for all $x \in P$

Suppose I have a LP with a linear cost function $c^Tx$, where $P=\{x \in \mathbb R^n : Ax \ge b\}$ is the polyhedron I want to minimize over. How do I see that either the problem is unbounded, that ...
0
votes
1answer
22 views

multivariate piecewise-linear equality constraint in optimization problem

I have an optimization problem of the type: $\min f(x) \\ s.t. Ax \le b \\ g(x)=0 $ where $g(x)$ is a piecewise-linear function defined as: $g(x) = \begin{cases} c_1^Tx & \text{if $x_1+x_2-x_3 ...
3
votes
2answers
97 views

Maximization of $x+y$ when each is greater than $1$ and $xy = 16$.

The product of two numbers $x$ and $y$ is $16$. We know $x\ge 1$ and $y\ge 1$. What is the greatest possible sum of the two numbers?
1
vote
0answers
11 views

Homework-Second derivative of a multivariate function

Let $f(x):\mathbb{R}^n\rightarrow\mathbb{R}$, and let $\theta(\alpha)=f(x+\alpha s)$ where $\alpha\in\mathbb{R}$ and $x,s\in\mathbb{R}^n$, the goal is to find $\theta''(\alpha)$. I guess that the ...
0
votes
0answers
11 views

Stage wise optimization

Are the following two optimization problems equivalent $$ \min_{x\in\{0,1\}} c^T x+ \min_{y\geq 0} \bigg\{q^T y | Ty+Wx\leq h\bigg\}\\ s.t., \\ Ax\leq b$$ and $$ c^T x +q^T y\\ s.t,\\ Ax\leq b\\ ...
1
vote
1answer
40 views

How to show that these two versions of Farkas lemma are equal?

One version of Farkas lemma is that Let $A$ be a real $m\times n$ matrix and $b$ an $m$-dimensional real vector. Then, exactly one of the following statements are true. There exists an ...
0
votes
1answer
27 views

Optimization Problem of Two Variables, One Dependent

I am actually working on a program of sorts. This program takes a user entered value that specifies how many white keys they can span with one hand on a piano. It then computes (based on research) the ...
0
votes
0answers
18 views

how i could show that $f$ is a constant if it has intermediate value and local extremum properties? [duplicate]

let $ f\colon R\to R $ be a function with intermediate value property . if $f$ has a local extremum at every point $x\in R $ . my question is how i could show that $f$ is constant ? I would be ...
0
votes
0answers
75 views

Ellipsoidal Decomposition: Finding ellipsoids whose sum contains a given ellipsoid

We have a known ellipsoid $E\left(q,Q\right)$ in a 2D space. $q$ represents the center of the ellipsoid and $Q^{-1}$ is the weight matrix. The general equation of the ellipsoid is given as: ...
1
vote
1answer
28 views

Number of Integer solutions for this optimization problem

What is the number of integer solutions to the problem $$\sum_{i=1}^{i=k}x_i = n$$ subject to $\forall_i\ \ x_i \ge 0 $ note This should hold for both cases $k < n$ and $k \ge n$
1
vote
1answer
34 views

Do lagrangian multipliers converge to dual variables in LPs?

Can anybody clarify the following to me? Consider an LP, say a maximization problem, with solution x* and optimal value Z*. Its dual will have optimal value W*=Z* (by strong duality) and optimal ...
0
votes
0answers
13 views

Multiplicative gradient descent?

The normal gradient descent is additive: $w_{t+1}=w_t-\lambda_t\nabla f(w_t)$, but is there a multiplicative gradient descent that looks something like $w_{t+1}=w_t[-\lambda_t\nabla f(w_t)]$? I know ...
2
votes
2answers
60 views

Find the smallest $a>1$ such that $\frac{a+\sin x}{a+\sin y} \leq e^{(y-x)}$ for all $x \leq y$

Can anyone please help me with the following question: Find the smallest $a>1$ such that $$\frac{a+\sin x}{a+\sin y} \leq e^{(y-x)}$$ for all $x \leq y$ My attempt: I think we should rearrange ...
0
votes
0answers
28 views

Let $P$ be a polyhedron. Prove, $P$ has at least one extreme point $\iff$ $P$ does not contain a line, by using a lemma.

Let $P$ be a polyhedron. Prove, $P$ has at least one extreme point $\iff$ $P$ does not contain a line, by using a lemma. I've a Lemma saying: Suppose $P=P(V,E)$ where $V,E \in \mathbb R^n$ are ...
0
votes
1answer
27 views

Why Am i standing in a global minimum?

I`been asked the following in optimization If I am located in a point where all the possible factible directions turn out to be worse for the function, Am I located in a global minimum? The answer is ...
2
votes
1answer
23 views

How to orthogonalize a set of 2x2 matrices?

I have set of 2D affine transformations of images and I need to modify the transformations such way that they become as close to rotations as possible to minimize distortions of images. Let the ...
0
votes
0answers
14 views

Optimize the distribution if it is left unsmoothed

I have a question about distribution. Let see my problem The paper said that the distributions p and q are left unsmoothed, so we can ignore Kernel density. But I don't understand what is left ...
2
votes
4answers
101 views

Minimizing $\tan^2 x+\frac{\tan^2 y}{4}+\frac{\tan^2 z}{9}$

Given that $\tan x+2\tan y+3\tan z=40 , \ \ \ x,y,z \in \left(\dfrac{\pi}{2},\dfrac{3\pi}{2}\right),$ We need to find the minimum value of $ \tan^2 x+\dfrac{\tan^2 y}{4}+\dfrac{\tan^2 z}{9}$ ...
0
votes
1answer
20 views

minimising total cost

A publishing company sells 75000 books during a year It costs a publishing company 0.6 dollars to store a book for a year. Each time they print additional copies, setting up the printers cost $2500. ...
1
vote
2answers
51 views

minimal value of $x^2+2y^2+5z^2$ with constraint.

$x,y,z>0$, and $xy+yz+zx=1$. I need to find the minimum value of $x^2+2y^2+5z^2$ In general what can we say about the minimal value of $\frac{ax^2+by^2+cz^2}{xy+xz+yz}$, over all positive numbers ...
0
votes
1answer
55 views

Solving LP with two $L_1$ inequality constraints

Is there a "fast" way to solve the following LP formulation with the following constraints: $$ \max_{\mathbf{f}} \mathbf{f}'.\mathbf{g} \\ \mathbf{1}'\mathbf{f}=1\\ \|\mathbf{f}-\mathbf{h}\|_1\le ...
2
votes
1answer
52 views

min : sum of L2 norm and squared-L2 norm.

Is there a closed-form solution of the following convex problem: $$\min_x \| x - u \| + C \| x - v \|^2$$ where $\| \cdot \|$ is the L2 norm.
1
vote
2answers
85 views

How do you maximize a polynomial over an integer domain?

I am working on maximizing the polynomial $f:\mathbb{R}^N \rightarrow \mathbb{R}$ $$f(v):=\prod_{i=1}^{N}( v_i+\alpha_i^2)$$ over integer $n$-partitions of $P$, $n\leq N$: $$\left\{v \left|\, v_i \in ...
2
votes
1answer
29 views

Solving first order constraints; lagrangian function and utility maximisation

I am supposed to find the demand curve if the following is given; $U(x,y) = xy$ price of $x * x$ + price of $y * y = m$ (so a general case, and I will be adding certain prices and income levels ...
1
vote
0answers
22 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
0answers
35 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 ...
3
votes
3answers
47 views

linear solution of curve fitting on multiple linear functions differing by a multiplier

I recently posted this question here but I thought this could be of interest also in mathematics, given I found a partially related question here I am facing the following problem. I know nonlinear ...
1
vote
2answers
24 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 ...
1
vote
1answer
35 views

Why don't we go beyond the Hessian in multivariate optimization?

In univariate optimization, we perform the first derivative test to identify stationary points and the second derivative test to classify the stationary points as minima, maxima and inconclusive. When ...
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 ...
2
votes
3answers
75 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} = ...
2
votes
1answer
96 views

Framing a travelling salesman problem

I have an optimization(optimisation) problem, I think it is travelling salesman, where I want to find an answer to the question: "What is the best coffee shop for person x within a 50km radius?" The ...
1
vote
1answer
46 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
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$, ...
0
votes
2answers
63 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 ...
0
votes
0answers
14 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
91 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$. ...
0
votes
0answers
43 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 ...
2
votes
2answers
66 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 ...
3
votes
0answers
30 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$) ...
-8
votes
3answers
99 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
53 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
84 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
33 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) ...
1
vote
1answer
69 views

Maximal intersection of slabs in $\mathbb{R}^n$ with a compact convex centrally symmetric set

Let $K \in \mathbb{R}^n$ be a compact convex set containing the origin and symmetric with respect to the origin. Let $S_i(t_i)$ be a finite set of slabs of various widths and orientations, translated ...
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
1answer
25 views

Shared groceries expenses between roommates to be divided as per specific consumption ratio and attendance

My apologies if this question is in the wrong section. Couple of my roommates & I (total 5 people) share the groceries expenses. We record the purchases in an Excel sheet, and also have the ratio ...
3
votes
1answer
97 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. ...