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
0answers
375 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 ...
56
votes
1answer
2k views

What's the largest possible volume of a taco, and how do I make one that big?

Let $f$ be a continuous, even, positive function over some interval $I=[-a,a]$ such that the total arc length of $f$ over $I$ is at least $2$, $f(0)=0$, and $f$ is increasing on $(0,a)$. View the ...
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} = ...
0
votes
1answer
257 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?
2
votes
1answer
483 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
2answers
748 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
1k views

Differences behind different methods of fminunc in MATLAB?

Assume I have some .m file with a function (and it's gradient) to be used by fminunc() in MATLAB for some unconstrained optimization problem. To solve the problem ...
0
votes
1answer
260 views

Underlying assumption in a Primal/Dual table

I just read in one of the questions answered by @MikeSpivey that the following table is provided in Sierksma's Linear and Integer Programming: Theory and Practice, Volume 1, page 144. ...
1
vote
1answer
175 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?
4
votes
2answers
197 views

Finding the position of a person on a grid, when you know the $(x,y)$ coordinates of transmitters and the signal strength at the person

I have a $100\times100$ grid. I have a transmitter on each corner, $4$ in total. $$\begin{array}{rl}\text{Transmitter (a) is at}&(0,0);\\ \text{(b) is at}&(100,0);\\ \text{(c) is ...
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 ...
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 ...
15
votes
1answer
461 views

Minmax problem for polygons

Let $\text{Pol}_n$ be the set of all convex polygons on a plane with $n$ sides. For $P\in \text{Pol}_n$ denote by $\text{Tr}(P)$ the set of all triangles whose vertices are some vertices of $P$. I ...
3
votes
0answers
263 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
0answers
305 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 ...
2
votes
1answer
200 views

Approximate Set Cover Problem by Rounding

Here is the simple algorithm for approximating set cover problem using rounding: Algorithm 14.1 (Set cover via LP-rounding) Find an optimal solution to the LP-relaxation. Pick all sets ...
1
vote
1answer
906 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)
2
votes
0answers
631 views

Convex minimization over the Unit Simplex

I have a simple (few variables), continuous, twice differentiable convex function that I wish to minimize over the unit simplex. In other words, $\min. f(\mathbf{x})$, $\text{s.t. } \mathbf{0} \preceq ...
4
votes
1answer
218 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 ...
3
votes
1answer
343 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
1answer
2k 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 ...
4
votes
3answers
186 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.
4
votes
1answer
792 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 ...
4
votes
1answer
192 views

Book on advanced topics of Network Flows

I am taking linear optimization class. Could you suggest me good fundamental textbook on advanced topics of network flows. To be more specific I am interested in: Multicommodity flow and multicut, the ...
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
2answers
122 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
123 views

Complicated “functional integral”

I came across the following "functional" at work: $$ \Pi [b]=\int_0^\infty\int_0^{\lambda b(v,\lambda)} vf(v,\lambda) \; dv \; d\lambda $$ it's part of an optimization problem that tries to find ...
4
votes
2answers
334 views

Maximizing symmetric matrices v.s. non-symmetric matrices

Quick clarification on the following will be appreciated. I know that for a real symmetric matrix $M$, the maximum of $x^TMx$ over all unit vectors $x$ gives the largest eigenvalue of $M$. Why is the ...
1
vote
1answer
233 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
201 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 ...
1
vote
2answers
692 views

bird traveling to a nest wants to save energy

This is a multiple choice question in one of tests I just wrote and I did not know the answer to it. I was just stuck on this during the test. It is a very weird question, one I find to be impossible. ...
11
votes
6answers
291 views

Maximizing the sum $\sum\limits_{i=1}^nx_ix_{i+1}$ subject to $\sum\limits_{i=1}^nx_i=0$ and $\sum\limits_{i=1}^nx_i^2=1$

Is there an efficient way of solving the following problem? Given $x_i\in \mathbb R$, and that $\sum\limits_{i=1}^nx_i=0$ and $\sum\limits_{i=1}^nx_i^2=1$. I want to maximize ...
0
votes
3answers
682 views

find the area of the largest rectangle that can fit inside a semi circle of radius 2 cm

find the area of the largest rectangle that can fit inside a semi circle of radius 2 cm I have absolutely no idea where to get started on this...What I did do is $A=(\pi r^2)/2$ (its a semi circle) ...
3
votes
1answer
89 views

Relation between bounded quadratic and linear complementary problems

In a paper, it says that Given a bounded quadratic problem (BQP) $$ \min_{x \in \mathbb{R}^n} \frac{1}{2} x^T A x + b^T x $$ subject to $$ x \geq 0, \quad i.e. \quad x_i \geq 0, i=1,...,n$$ ...
2
votes
2answers
2k views

What does “subject to” mean in math?

For instance, I saw the expression in the Wikipedia article on Lagrange multipliers: maximize $f(x, y)$ subject to $g(x, y) = c$ What does "subject to" mean?
2
votes
0answers
473 views

Is there any relation between the principal eigenvalue of sub matrix and the original matrix?

I am wondering whether there is any relation between principal eigenvalue of sub matrix and the original matrix. In fact I am facing a problem which is to select $n$ rows and $n$ columns from the ...
2
votes
1answer
87 views

Linear programmimg

If we are solving a linear programming question using graphical method, it is said that the optimum point will be one of the extreme points. I want to make clear how this happens always (assume that ...
2
votes
1answer
89 views

Game Theory Moving Around Coins

To start off, we have coins arranged in the following order: ..C.. A F.. D.. B ..E.. G The goal of this game is to return these letters into alphabetical order: A, B then C, D, E then F, G in the ...
4
votes
2answers
832 views

Maximize the Area of a Quadrilateral given Three Sides

We have three sides of a quadrilateral given, each of side length 20.The third side length is known to be less than length 100. Determine the maximum area of such a quadrilateral. I would guess the ...
2
votes
3answers
195 views

Find the minimum of $x^{2}+5y^{2}+8z^{2}$ if $xy+yz+zx=-1$

If $xy+yz+zx=-1$,find the minimum of $x^{2}+5y^{2}+8z^{2}$. How to solve it use Elementary mathematics methods?
3
votes
0answers
262 views

Connecting points while minimizing path distance between them and the total distance of the paths

Say I'm building n highway system for $N$ cities on a Euclidean plane. I want to minimize the ratio of the average highway distance between each pair of cities, i.e. $\sum_{i \in P, j \in P} \| i - j ...
0
votes
2answers
54 views

Upper bound of the optimal value in one particular maximization problem

Suppose that we have a integer $m$, and we need to choose $n\le m$ and $x_1,x_2,...,x_n$ such that $\sum_{i=1}^nx_i=m$ and $\prod_{i=1}^nx_i$ is maximized, where $n$ and all $x_i$'s are integers. In ...
1
vote
1answer
122 views

An interesting eigenvalue problem

Let $A\in\mathbb{R}^{d\times d}$ and $B\in\mathbb{R}^{d\times d}$ be two positive definite matrices. $k$ is a real coefficient. Suppose the largest eigenvalue of $A-kB$ is $\lambda_1$. Is it possible ...
2
votes
1answer
580 views

Greedy Algorithm Proof

My problem seems similar to the Interval Scheduling problem (processing as many jobs as possible), which I understand but can't seem to apply properly in this case. I've tried to simplify the problem ...
2
votes
1answer
392 views

Optimization Problem

I am stuck on the following question: Consider a profit maximizing monopoly. The demand for the monopoly's product is given by $Q=\ln(a-bP)$ and its cost function is $C(Q)=ce^{Q}$, where the ...
2
votes
1answer
371 views

Properties of Parabola / Optimization

I've been working through some past papers for an exam which I am due to be sitting tomorrow. In the Conic Sections paper from a couple of years ago, the following question came up: The path of a ...
0
votes
2answers
1k views

Basic Optimization Problem

I sat for an exam a few days ago. I managed to answer every question except for question $1$c in the calculus paper. Provided that I got question $2$d correct (my answer was $m=0.5$), the absence of ...
4
votes
1answer
770 views

Questions about constraints and KKT conditions

KKT conditions from Wikipedia: We consider the following nonlinear optimization problem: $$ \text{Minimize }\; f(x) $$ $$ \text{subject to: }\ g_i(x) \le 0 , h_j(x) = 0 $$ ...
0
votes
1answer
79 views

How do I set up the following problem to arrive at the answer?

A warehouse has 10 unlabelled rows of pallets. Each row of pallets contains thousands of cell phones destined for different countries. Each 100 gram cell phone is exactly the same except for those in ...
5
votes
1answer
28 views

Mechanism to auction off multiple resources given fixed budgets

I am trying to sell ad time on a screen to a bunch of advertisers. The advertisers tell me (or a salesperson keys in) how much a given advertiser is willing to pay for time in a one hour block. Each ...