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)

3
votes
2answers
79 views

a plausible maximum or minimum

Is the following statement true? Let $a_1\ge a_2\ge \cdots \ge a_n>0$, $b_1\ge b_2\ge \cdots \ge b_n>0$, then $$\max\limits_{\sigma\in S_n}\;\;\prod\limits_{i=1}^n(a_i+b_{\sigma ...
0
votes
1answer
64 views

how to compute this optimization problem

Given $A,B$ are positive semidefinite matrices, how to compute $\max_{0\leq P\leq I}\|APBPA\|$, where the norm is spectral norm, i.e. the largest singular value.
3
votes
2answers
149 views

Distance saved by shortening the road

A long distance drivers technique for saving time is to drive the width of the road you are on. To do this you drive so that you are placing you car on the inside of all turns as much as possible. I ...
4
votes
1answer
5k views

Degeneracy in Linear Programming

Consider the standard form polyhedron, and assume that the rows of the matrix A are linearly independent. $$ \left \{ x | Ax = b, x \geq 0 \right \} $$ (a) Suppose that two different bases lead to ...
1
vote
2answers
470 views

Max f(x,y,z) = min{x, 5y+2z} subject to x+15y+7z=44

Max f(x,y,z) = min{x, 5y+2z} subject to x+15y+7z=44 As well, $x,y,z \geq 0$ I have guessed that the extrema point will be a point such that x=5y+2z and tried solving for the curve of intersection of ...
3
votes
1answer
238 views

Optimal solution to a matrix equation, linear system

This problem has me completely stumped. Given: $A$ is a symmetric $n \times n$ matrix $r = b - Ax$ with $r, b, x \in \mathbb{R}^n$ and $x$ is nonzero. Show how to compute a symmetric $E \in ...
1
vote
1answer
674 views

Simple non linear fitting question(Least Squares Fitting--Exponential) [duplicate]

Possible Duplicate: easy to implement method to fit a power function (regression) I have the following simple function: $h = cV^n$ h and V being the variables and $c$ and $n$ are ...
2
votes
1answer
956 views

In Simplex Method, if the leaving variable fails for all candidates of MRT, what's wrong?

I'm facing a problem programming a full tableau solver for some LP problems. The difficulty is when the test for leaving (line) variable cannot find a single positive value on the pivot column for ...
1
vote
0answers
132 views

Lagrange Multiplier question

Given a utility function $R(x,y) = x(100-6x) + y(192-4y)$ and a constraint equation $C(x,y) = 2x^2+2y^2+4xy-8x=-20$, maximize. As usual with Lagrange, I got stuck on the juicier part of solving a set ...
0
votes
1answer
42 views

Equivalent optimization problems

I am reading about optimization and I am having difficulty in understanding the following: If a matrix A is $n\times n$ Hermitian, then $\max_{x^{*}x=1} x^{*}Ax$ is solution equivalent to ...
5
votes
1answer
1k views

Optimization and Tangent Line Question

I'm stuck on a question involving maximizing the area of a triangle: What is the area of the largest triangle that can be formed in the first quadrant by the x-axis, the y-axis, and a tangent line ...
7
votes
1answer
936 views

Looking to find the largest rectangle, by area, inside a polygon

I'm looking to print text inside a polygon, programmatically. I'd like to find the largest rectangle to position the text inside the polygon out of a sub set of rectangles, ie those oriented with ...
1
vote
2answers
99 views

Maximum Value Question

I have a question about this following question: Let $a>0$. Show that the maximum value of $f(x):=\frac{1}{1+|x|}+\frac{1}{1+|x-a|}$ is $\frac{2+a}{1+a}$ I am wondering if I am headed ...
2
votes
4answers
5k views

Difference between maximum and minimum?

If I have a problem such as this: We need to enclose a field with a fence. We have 500m of fencing material and a building is on one side of the field and so won’t need any fencing. Determine the ...
2
votes
3answers
178 views

Linear inequalities to make a specific solution infeasible

Say we have a binary linear programming problem: \begin{equation*} \begin{aligned} & \underset{\mathbf{x}}{\text{minimize}} & & c\cdot\mathbf{x} \\ & \text{subject to} & ...
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 ...
-1
votes
1answer
208 views

Difficult Geometry Problem--Circular Arcs

Good Afternoon, I have spent a couple of hours trying to solve this problem, but it appears that I have not gotten anywhere. Let $R$,$P$,$Q$ be points such that $\angle RQP=75^\circ$. Also we are ...
1
vote
1answer
267 views

Sudoku mathematically, MILP?

My homework contains a word (freely-translated) "target-function" that I should generate somehow for 9x9 sudoku solver with some MILP problem. But I am bit lost what they mean. I have sofar described ...
1
vote
0answers
72 views

Finding extrema of a function depending on parameter

The question might seem basic and perhaps I am overlooking something. I'm looking at the development of the extremum of $$ f(x)=\left|\frac{ A \mathbf{x} \sin\left[B\sqrt{x^2 -a^2+2 i \cos[\Phi ] a ...
2
votes
1answer
156 views

Simplify the Hungarian Algorithm for cases of an extremely sparse cost matrix?

I have an optimization problem on a set of data that is solvable with the Hungarian Algorithm and works well on small sets. But the full set of data is large and only 0.1% of the cost matrix is even ...
1
vote
1answer
130 views

Explain the minus before the nabla, $- \nabla f_{0}(x)^{T} (y -x)$

Reading page 4-9 here, I cannot understand the minus and the direction of the inequality. $f$ is convex. Why it is required that $\nabla f_{0}(x)^{T}(y-x) \geq 0$, why not $\nabla f_{0}(x)^{T}(y-x) ...
0
votes
1answer
42 views

Relation of $\max_P \; x^T \cdot Py$ and $\min_P \; \|x-Py\|_2$

Consider a permutation matrix $P$ and two vectors $x$, $v$ with 2-norm = 1 and all positive entries. Are the optimal solutions $P^\ast$ of $\max_P \; (x^T \cdot Py)$ and $\min_P \; \|x-Py\|_2$ the ...
1
vote
1answer
380 views

Moreau-Yosida regularization problem

Let $$F(x)=\min\limits_{y\in \mathbb R^n}\{f(y)+\|x-y\|^2\} ,$$ where $f(y)$ is convex and bounded below. How to show that if $x^*\in \arg \min \{F(x)\}$, then $x^*$ is in the closure of the ...
0
votes
1answer
668 views

Finding minimum of multidimensional function

My calculus knowledge is pretty limited, but unfortunately I need to solve a problem of the following kind: I'm given a 2 dimensional function $f(x,y)$ from $\mathbb{R}^2$ to $\mathbb{R}$ and I want ...
7
votes
2answers
623 views

Difference between Bellman and Pontryagin dynamic optimization?

Can someone please explain the difference between dynamic optimization via the Bellman equation and dynamic optimization via Pontryagin's maximization principle? Thanks
5
votes
1answer
332 views

Find extremes of function $f(x,y,z) = x^2y + y^2z + x - z$

I am preparing for an exam tuesday morning and I would like to ask you, if someone could please review my solution for the following excercise. I don't have the correct answer so I am unable to check ...
1
vote
1answer
123 views

Strategy to maximize no. of balls from N boxes

If you have N boxes each containing distinct number of balls and you are allowed to choose at most ...
10
votes
3answers
735 views

Why is $(0, 0)$ not a minimum of $f(x, y) = (y-3x^2)(y-x^2)$?

There is an exercise in my lists about those functions: $$f(x, y) = (y-3x^2)(y-x^2) = 3 x^4-4 x^2 y+y^2$$ $$g(t) = f(vt) = f(at, bt); a, b \in \mathbf{R}$$ It asks me to prove that $t = 0$ is a ...
3
votes
1answer
176 views

Testing constrained linear least squares for optimality

I've written a C# solver for linear least squares problems with inequality constraints. That is, given $A$, $b$, $G$, $h$ $$\min\|Ax-b\|^2\text{ s.t. }Gx\ge h$$ I have a few hand crafted test ...
1
vote
1answer
190 views

minimise no. of resistors in circuit

A circuit contains a 1V cell and some identical 1 ohm resistors. A voltage of a/b, where $a\leq b$, is to be made across a voltmeter using the minimum number of resistors in the circuit. The voltage ...
4
votes
1answer
445 views

Algorithm for solving sparse equality-constrained least squares

I have a diagonal, positive-definite inner product matrix $M$ and want to find a minimizer of $$\min_q \frac{1}{2} \|q-q_0\|_M^2\qquad \text{s.t.}\qquad C^Tq+c_0 = 0,$$ where $q_0, c_0$, and $C$ are ...
1
vote
2answers
47 views

Least-effort way from A to B via X

Points A, B and X form a rougly equilateral triangle. I need to pull a cart from A to B, and also need to visit X, but I don't need to have the cart with me there. Walking with the cart costs me ...
6
votes
2answers
492 views

Mathematical versus computer “Dynamic Programming”

I heard the term "dynamic programming" and naively assumed it had to do with programming in the sense of computer programming (as that's the only way I've heard the word used before. Used to work ...
2
votes
2answers
121 views

Is this question written incorrectly, or am I wrong?

Here is the question: A rancher has 300 feet of fencing and needs to make three pens for his animals in the following shape: a) Write a formula for the total fencing needed. b) Find a formula ...
0
votes
2answers
115 views

A fencing problem

So the problem is: I have bought a fence 30 meters long and I need to put it around three of my rectangular fields sides. How long should be each of the field sides, to create the biggest ...
4
votes
1answer
97 views

good approach to solving this nonconvex quadratically-constrained program

I want to find a (local) minimizer $x, y$ to the following optimization problem: $$ \min_{x,y}\ x^T x + a^T x \qquad \mathrm{s.t.} \qquad \begin{array}{r}x^T M_i y + c_i = 0 \\ y \geq 0\end{array}.$$ ...
1
vote
1answer
567 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}: ...
1
vote
2answers
601 views

Optimizing with Absolute Value Objective Function

max : $w = |q^T y|$ subject to $A y \leq b$ $y \geq 0$ Please describe how one could solve the non-linear programming prob. above by using linear programming methods. I tried changing $y$ to $y' ...
3
votes
1answer
211 views

Optimization with constraint on solution of a linear system

I'm facing this optimization problem: $$\text{minimize} \quad a^T x$$ $$\text{s.t. the solution of $A(x) z + B(x) = 0$ belongs to a convex set $S$}$$ Here $A(x)$ is a linear matrix function of $x$ ...
4
votes
1answer
413 views

An optimization problem involving orthogonal matrices

Let $X\in\mathbb{R}^{3\times 3}$ be an orthogonal matrix. Then $\mathrm{vec}X\in\mathbb{R}^9$ is a 9 by 1 vector formed by stacking the columns of the matrix $X$ on top of one another. Given a matrix ...
1
vote
1answer
203 views

Economic optimisation problem

Here is the question: Consider a car-owning consumer with utility function $$u (x) = x_1x_2 + x_3 (x_4)^2 ,$$ where $x_1$ denotes food consumed, $x_2$ denotes alcohol consumed, $x_3$ denotes kms of ...
1
vote
0answers
46 views

Algorithm for optimizing width length of classes of an ordered list of data points under certain conditions

I have the following problem: I have an ordered list of $n$ data points jiggling around $0$ with no apparent order. The order this list is in should not be affected by the following procedure. I want ...
2
votes
2answers
386 views

Maximization over vectors (seen as column matrices)

I am trying to solve the following question: $$\text{Maximize } f(x_1,x_2,\ldots, x_n)=2\sum\limits_{i=1}^n x_i^t A x_i+\sum\limits_{i=1}^{n-1}\sum\limits_{j>i}^n (x_i^tAx_j+x_j^tAx_i)$$ subject ...
1
vote
1answer
524 views

Need help with Lagrange Multipliers

I need to maximize $U = BM$ with constraits: $6B +3M = 60$, $B>0$ and $M>0$. The Lagrange function is $L=U + \lambda (6B+3M-60) + KB + HM$. So $$\partial_{\lambda}L= 6B+3M-60=0$$ ...
2
votes
1answer
103 views

Vector Theory Question

I am having trouble getting started on this multi-part problem. Could anyone take a look and provide some insight on how I might go about coming to a solution for the first part. Q: Assume for two ...
1
vote
1answer
160 views

Voronoi diagram with different metric functions

Given a metric space $(X,d)$ and finite number of points $(x_i)_{i=1}^n$ the Voronoi diagram (or the Dirichlet cell) $C_i$ is given by $$ C_i = \{x\in X:d(x,x_i)<\min\limits_{j\neq i}d(x,x_j)\}. ...
3
votes
1answer
412 views

Question about the simplex method complexity

So I know that in general the simplex method for linear and convex quadratic programming can require exponential time. But assuming a positive semidefinite quadratic program that is solvable by the ...
0
votes
1answer
131 views

Optimization - Get value of Lagrangian

We know that $f(x) \to \min$ subject to $g(x) = t$ and $h(x) \leq m$ can be written as $f(x) + \lambda g(x)\to\min$ subject to $h(x) \leq m$. How do we get value of lambda so that the two problems ...
2
votes
1answer
160 views

Linear Programming - Single Optimal Solution

Is it correct to state that if a linear objective function is not in parallel with any of the constraints, than there is a single optimal solution at some vertex of the polytope?
0
votes
1answer
126 views

invex functions - optimality functions

For a general convex program, a feasible point is an optimal solution if and only if it lies in a hyperplane whose a normal vector is the gradient to the objective function at this point. Please ...