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)

2
votes
1answer
2k views

Real Life Optimization Problem

You are given a set $A$ of integers of size $n$ and a common divisor $r$ called the "anchor", which isn't in $A$ and isn't necessarily the greatest common divisor, either. Let $M$ be the least common ...
-2
votes
1answer
277 views

Polynomial problem

From http://www.boardofstudies.nsw.edu.au/hsc_exams/hsc2005exams/pdf_doc/maths_ext2_05.pdf: Suppose that $a$ and b are positive real numbers, and let $f(x)=\frac{a+b+x}{3(abx)^{\frac13}}$ for $x ...
2
votes
2answers
247 views

On sums of unitary matrices

Let $J$ be the $n$ by $n$ matrix of all 1's. Let $f(n)$ be the least number $m$ of unitary matrices $U_1,\dots,U_m$ so that $J = U_1 + \cdots + U_m$. What can you say about the growth of the function ...
2
votes
1answer
153 views

A question regarding local minimizer of a function restricted on a circle

I have a quadratic function $f: \mathbb{R}^2 \rightarrow \mathbb{R}$, $f(\mathbf{x}) = (\mathbf{x}-\mathbf{p})^\top \mathbf{Q} (\mathbf{x} - \mathbf{p})$ where $\mathbf{Q}$ is positive definite and ...
2
votes
1answer
72 views

game strategy question

Let's say there are doors each with a lock on the integral points ($0$, $\pm1$, $\pm2$, $\cdots$) of the line. You are given a key which can only open a single lock, but you are not told what lock the ...
2
votes
3answers
536 views

matrix linear optimization problem

I have a problem at work which is the redistribution of man days over a project period. We have it in an EXCEL-sheet and man days are always shifted etc. For each month you have a monthly sum of man ...
2
votes
3answers
247 views

Issue with textbook exercise on vectors

the following is a question from my textbook on vectors: EDIT: Added text, so that the post is self-contained even without the picture. The points $A$ and $B$ have position vectors ...
1
vote
3answers
239 views

A “fast” way to ,find the maximum value of $(x^2) \times (y^3)$,if $3x+4y=12$ for $x,y \ge 0$

If $3x+4y=12$ $\forall x,y \ge 0$,the maximum value of $(x^2) \times (y^3)$ is $6 \times (6/5)^5$ $3 \times (6/5)^5$ $ (6/5)^5 $ $7 \times (6/5)^5$ How to approach this problem?I thought of ...
1
vote
1answer
72 views

The lower bound of the product between two variables

I wonder how I can determine the minimum of the product between variables $x$ and $y$ (in terms of $\theta$), given that both $x < 1 - \theta$ and $y < 1 - \theta$, and $x + y = 1$? So far I ...
0
votes
0answers
164 views

BUE (Best Unbiased Estimator)

Suppose we are given a matrix $V$ and our goal is to find non-negative matrices $W$ and $H$ such that $V \approx WH$. So we want to minimize $K(V || WH)$ (Kullback-Leibler Divergence) where $$K(V||WH) ...
0
votes
1answer
224 views

Payoff of a unilateral deviation in an $n$-player zero-sum game

In a $n$-player zero-sum game, one of the players, say $k$, unilaterally deviates from her Nash equilibrium strategy while all the other players stay on the equilibrium. Now, we all know that $k$'s ...
1
vote
0answers
372 views

Moore–Penrose pseudoinverse reference

Given the eigendecompositions $AA^{\top}=Q \Lambda Q^{\top}$ and $A^{\top}A=P \Lambda P^{\top}$, where $\Lambda$ is a diagonal matrix (of eigenvalues) and $P$ and $Q$ are unitary eigenvectors matrices ...
5
votes
5answers
6k views

How many bananas can a camel deliver without eating them all?

This is a fun puzzle I was assigned on the first day of highschool (over a decade ago). I just dug it up randomly from under my bed and thought I'd share it with the SE community. At the time, I ...
1
vote
1answer
97 views

What is the maximum value of the minimum number of balls per bin?

$S$ people, $N$ bins, each person has a given subset of bins he can cover, each person is given $t$ balls. Question: What is the maximum value of the minimum number of balls per bin? i.e., allocate ...
3
votes
0answers
259 views

Least Square Method with Positive Parameters

this is my first post here in the Stack Exchange. A friend told me about this forum and I'm giving it a try. I searched a bit past threads, but couldn't find what I wanted, so I'm posting the problem ...
1
vote
1answer
964 views

Simple Minimization Problem: A few questions regarding the mechanics of solving

Consider the following elementary minimization problem: Minimize: $\phi = 2700x + 2400y + 2100z$, subject to: $\text{Constraint 1}: 55x + 45y + 35z \geq 41000$ $\text{Constraint 2}: 30x + 35y + 50z ...
1
vote
1answer
127 views

Find the minimum value of $(\frac{x^n}{n} + \frac{1}{x})$ for $n \ge 4$

Find the minimum value of $(\frac{x^n}{n} + \frac{1}{x})$ for $n \ge 4$. One possible approach could be by first writing $$ \left(\frac{x^n}{n} + \frac{1} {x}\right) = \left( \frac{x^n}{n} + ...
0
votes
2answers
204 views

Essential problem

I want to find one method or approach or idea which compute following statement: $$ \sup_{t \in [0,1]} \left( \inf_{X \in C^1([0,1])} \left\| \frac{dX(t)}{dt} - A(t)X(t) - F(t) \right\| \right) $$ ...
3
votes
2answers
140 views

Calculate max/min of $x_1 x_2+y_1 y_2+z_1 z_2+w_1 w_2$

What is a good way to calculate max/min of $$x_1 x_2+y_1 y_2+z_1 z_2+w_1 w_2$$ where $x_1+y_1+z_1+w_1=a$ and $x_2+y_2+z_2+w_2=b$ and $x, y, z, w, a, b \in \mathbb{N} \cup \{0 \}$, and please explain ...
1
vote
1answer
173 views

How to use Euler-Lagrange equation when obj fn integrated over two parameters?

If I want to find the minimizing function $f(t)$ over a single parameter, like time, then I take the integrand of $$\int_{t}L(t,f(t),f'(t))\:\:\:\:dt$$ and substitute it into the Euler-Lagrange ...
2
votes
0answers
260 views

Sharp (Reverse) Harmonic-Arithmetic Mean Bounds

Let $\mathbf{x} =$ {$x_{i}$} be a set of $n$ positive reals. In every good book on inequalities, one finds the classical result \begin{eqnarray} AM(\mathbf{x}) \geq GM(\mathbf{x}) \geq ...
3
votes
1answer
343 views

What's a correct symbolism for “value that maximizes” [duplicate]

Possible Duplicate: Math notation for location of the maximum Given a function $f(x)$, we can normally find $\max_i f(i)$. This expression evaluates to the maximum value of $f(x)$. ...
4
votes
1answer
148 views

Vertex arrangement on the unit sphere

The problem is how can I solve a following in polynomial time? There is a graph $G$ with $n$ vertices, and the goal is to find an arrangement of its vertices on an $n$-dimensional unit-sphere so as to ...
4
votes
8answers
2k views

Maximizing the sum of two numbers, the sum of whose squares is constant

How could we prove that if the sum of the squares of two numbers is a constant, then the sum of the numbers would have its maximum value when the numbers are equal? This result is also true for ...
2
votes
1answer
3k views

Calculus “Word Problem”

Here is the problem: A rectangle has its base on the x-axis and its upper two vertices on the parabola y=12-x^2 What is the largest area the rectangle can have, and what are its dimensions? Well, I ...
3
votes
6answers
330 views

Optimizing $a+b+c$ subject to $a^2 + b^2 + c^2 = 27$

If $a,b,c \gt 0$ and $a^2+b^2+c^2=27$, find the maximum and minimum values of $a+b+c$. How to solve this one? (Here's the source of inspiration for the problem.)
0
votes
1answer
181 views

Positive semidefinite vector $\bar{x}$ as $\bar{x}>0 :=\bar{x} \lambda \bar{x}^{T}>0$?

$A \lambda A^{T} $ (quadratic form?) is used with matrices to check definiteness. What about with vectors? If I see conditions such as $\bar{x} > 0$, how can I know whether it means $\bar{x}_{i} ...
2
votes
1answer
464 views

Lagrangian step for optimizing a concave function

I finding some difficulties in solving the below constrained problem using Lagrangian. Would be great if some one helps me with the steps. $\min_C \sum_i \Psi(c_i)$ subject to $\sum_i c_i = 1$ and ...
2
votes
1answer
116 views

Maximise $L^q$ norm of a vector, for fixed $L^1$ and fixed $L^p$ norms

Consider a vector $x \in \mathbb R_+^n$ and $p,q \in \mathbb R$ such that $1<p<q$. We fix $\sum \limits_{i=1}^{n}|x_i| = 1$ and $ \left(\sum \limits_{i=1}^{n}|x_i|^p \right)^\frac{1}{p} = ...
3
votes
3answers
81 views

Prove that $(2-x)^nx^{n-1}$ decreases with $n$ for $0 <x<1$?

How can I show that: $$(2-x)^nx^{n-1}$$ is decreasing with $n$ when $0<x<1$? I think this is generally true, but specifically I am concerned with $n$ as an integer $\geq 2$ and showing that the ...
3
votes
1answer
329 views

Connected graph solution from IP/LP

I have a problem on a graph (of maximum degree $c$) which looks for a connected subset of edges fulfilling some properties. I have problems formulating the connectedness condition in an IP/LP. The ...
2
votes
2answers
699 views

Minimizing weighted sum of distances

given a set of coordinates and the following function: cost = $\sum \sqrt{(x_i−X)^2+(y_i−Y)^2}w_i$ I would like to find the point (X, Y) for which this function is minimal. A simple example shows ...
0
votes
1answer
237 views

How to apply the simplex method to prove that the following problem is unbounded?

$\max 6t_1 + 4t_2$ $-t_1 + t_2 \leq 6$ $t_1 - t_2 \leq 1$ $t_1 - 2t_2 \leq 8$ $t_1, t_2 \geq 0$ Anyone?
1
vote
1answer
169 views

Multiple solutions for both primal and dual

If matrix $A$ in an LP (or $A^T$ in its dual) has full row (column- in dual) rank, is it possible that both primal and dual have multiple solutions?
0
votes
2answers
317 views

Maxima of bivariate function

[1] Is there an easy way to formally prove that, $$ 2xy^{2} +2x^{2} y-2x^{2} y^{2} -4xy+x+y\ge -x^{4} -y^{4} +2x^{3} +2y^{3} -2x^{2} -2y^{2} +x+y$$ $${0<x,y<1}$$ without resorting to checking ...
-1
votes
1answer
184 views

Minimum for this function

What is the minimum for this function of $x_1,x_2, \ldots, x_n$: $$\sum_{i=1}^n c_i \log x_i + \lambda \; \sum_{i=1}^n d_i x_i, $$ where $\lambda$, $c$ and $d$ series are positive constants, $x_i ...
1
vote
2answers
118 views

Minimum for this function

I thought of writing this question Minimum for this function in a different way, if it helps. I want to minimize $$\sum_{i=1}^n a_ix_i + \nu \sum_{i=1}^n b_i 2^{x_i} ,$$ where $a_i \in [0,1]$, ...
2
votes
1answer
54 views

Finding the minimum for this formula

I think if we want to calculate $\min_x \sum_i (b_i - x)^2$, the answer should be the mean of $b_i$, right? Now if we add a weight to each term and make it $\min_x \sum_i w_i(b_i - x)^2$, what's the ...
4
votes
2answers
213 views

discontinuous optimization

I'm solving the following problem: $$ \max_\rho \;\; \rho \; \min\left[\left( \frac{bn}{an-bm} \right)[(a-m)-\rho], \frac{b}{a}[a-(p+\rho)]\right]$$ where all constants and variables are defined ...
1
vote
0answers
298 views

Notation for limit points of a minimizing sequence: $\arg \inf$

Could you tell me what is the accepted notation for the set of limit points of a minimizing sequence. For example, if I have a function $f(x)$ and a sequence $x_t$ such that $\lim f(x_t) = \inf ...
1
vote
1answer
884 views

Two-Phase Method (Linear Programming)

In Linear programming, when is it beneficial to use the Two-Phase Method? Why not just use the Simplex Method? (edit: typo)
4
votes
1answer
207 views

Min Cost Matching for Random Complete Bipartite Graph

Edited I got this problem when reading Goeman's lecture notes http://www-math.mit.edu/~goemans/18433S11/matching-notes.pdf Problem: Exercise 1-16. ...Take a complete bipartite graph with n ...
4
votes
1answer
779 views

Regarding complementary slackness condition

I have a question regarding complementary slackness, the answer should be true of false. The complementary slackness conditions connect pairs of optimal basic feasible solution of primal and dual ...
2
votes
1answer
1k views

Examine function extreme values

I am studying for multivariable calculus exam and in homework we always had specific task regarding extreme values: find absolute minima, find local maxima, etc. In real exam questions are more like ...
3
votes
3answers
1k views

Dividing a set into two subsets the optimal way (May be similar to the knapsack problem)

We have n stones having weight m[1]..m[n], and two sacks. We put each stone into first or second sack; the resulting sacks ...
1
vote
1answer
586 views

Proof that Hessian matrix of Lagrangian function can not be positive definite

This is a homework problem I have a hard time to understand. Any tips would be appreciated to get me in the right direction. Given functions $f: \mathbb{R}^n \to \mathbb{R}$ and $\boldsymbol{g}: ...
4
votes
3answers
180 views

How is this problem called?

I have a set of integers $\{8, 8, 6\}$. I want to know if It is possible to get $21$ by adding a subset of them. I would like to know how is the problem called so that I can google it.
1
vote
2answers
117 views

A very simple optimisation problem

Given any set of real scalar values $V=\{v_i | 1 \leq i \leq n\}$ and a distinct value $v_p$ define c:- $$ c= \sum_{i=1}^n |v_i-v_p| $$ What is the easiest way to determine $v_p$ such that $c$ is ...
1
vote
1answer
231 views

KKT Condition : Always either a Maxima/minima or Saddle?

For a constrained optimization problem, in general the KKT conditions are a necessary but not sufficient condition for a point to be the local maxima/minima of the objective function. Is it always ...
1
vote
2answers
198 views

How to find the minimum value of $px+qy$ when $xy=r^2$?

The question says: "Find the minimum value of $px+qy$ when $xy=r^2$." No information is given on $p,q,x,\text{and }y.$ However assuming the obvious I tried using this, but I am not able reduce it to ...