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
1answer
170 views

How to normalize distances for use as weight coefficients?

I trade on the FOREX market. Currently I am attempting to use the FLANN library (Fast Library for Approximate Nearest Neighbors) to find N similar situations to the ...
3
votes
3answers
854 views

How do you find the optimal value for this function?

Given $$\sum_{i=1}^n x_i = 1,$$ what values of $x_i$ minimize the sum $$\sum_{i=1}^{n}x_i^2\ ?$$
4
votes
0answers
783 views

Convergence of Gauss-Newton method for piecewise linear functions

Notation for Gauss-Newton method Non-linear least squares problems are often solved by the Levenberg-Marquardt algorithm, which can be viewed as a Gauss–Newton method using a trust region approach. ...
0
votes
1answer
116 views

Getting linear regression of huge numbers

I'm trying to get a linear regression slope and intercept for a large set of huge numbers. I'm doing this on a computer, but I keep getting overflow errors (attempting to calculate a number too large ...
3
votes
1answer
62 views

Library Branch Circulation Problem - Terminology and References

This is a bit general, but is there a name to this type of problem? It looks like a directed graph traversal problem, but you have multiple paths going on, and timing may be important. You operate ...
3
votes
1answer
2k views

Choosing Pivot differently in maximization Simplex- and minimization Simplex method?

In maximization simplex, the pivot is the smallest element in the column divided by the rightmost corresponding number. I am stumbling with the Example 3 here with solution that choose the pivot with ...
4
votes
4answers
110 views

Optimizing the expectancy

The following problem is about optimization. It is not a homework, but rather a natural question to ask to oneself afterwards. Here it is. Consider a road of length $L$ between two cities $A$ and ...
4
votes
1answer
486 views

Unscramble images without trying all permutations

I try to write an algorithm that unscrambles images that were before scrambled by mixing up small blocks: My idea is that in the bottom image there are more "sharp" corners compared to the image ...
1
vote
1answer
354 views

extreme points and hyperplanes

I know the algebraic notion of an extreme point. I am confused about the geometerical aspect of an extreme point in terms of the hyperplanes as mentioned below. The point $x'$ lies on $n$ of ...
7
votes
3answers
413 views

Optimization problem for a parity-check code

I have $n$ data blocks and $k$ parity blocks distributed across $m$ boxes where each box can contain atmost $b$ blocks. Each parity block is Ex-or of some data blocks (for ease of understanding we can ...
6
votes
0answers
228 views

Is this minimization problem NP-Complete?

We are given an $n\times(n+k)$ matrix $A$, with entries in $GF(2)$, of the form $A=\begin{pmatrix}I_n & B\end{pmatrix}$, where $I_n$ is the $n\times n$ identity matrix, and $B$ has no "zero" rows ...
2
votes
1answer
304 views

Optimization over union of convex sets

Let's say I would like to minimize a convex function $f(x)$ over a set $C$. $C$ is not convex but a union of a finite number of convex sets $C_i$: $C = C_1 \cup \dots \cup C_m$ where each $C_i$ is ...
3
votes
1answer
412 views

Quadratic minimization in a Hilbert space

If $A$ is a positive definite matrix, then the solution to the minimization problem $(1/2)x^TAx - b^Tx$ is given by $A^{-1}b$. I'm interested in the generalization of this to a Hilbert space. What ...
5
votes
2answers
1k views

Berlin Airlift Linear Optimization Problem

I am trying to learn more about the Berlin Airlift transport problem. Two links I could find are here: http://drmohdzamani.com/notes/file/Simplex%20Method.pdf ...
1
vote
0answers
173 views

Optimisation of Cost Functions with step functions

Hi I would like to know which algorithm is best suited to solve this Cost Minimisation problem: Total Cost = ...
6
votes
1answer
177 views

Difficulties in Writing the Dual of a Primal Program

I am a student and I am studying the following problem during my spare time. Your comments and suggestions would be helpful. Given the following primal program: (Decision variables are $\xi_{v}$, ...
1
vote
1answer
188 views

Multivariate Maximization

For fixed $g$, I want to find maximum $b$ with $$-2b(3t^2(s+1)+6t(s+1)+3s+2)-2g(6ts+3t+6s+2)-3ts^2+6ts+3t-3s^2+3s+1>0$$ for some nonnegative reals $t,s$. Here $g, b$ are also $\geq 0$. Can it be ...
2
votes
2answers
2k views

Looking for numerical methods for finding local maxima and minima of a function

In derivative, If $f'(x)$ is rising at $f'(x)$ = 0, there's a local minima in $f(x)$. If $f'(x)$ is falling at $f'(x)$ = 0, there's a local maxima in $f(x)$. If $f''(x)$ is ...
4
votes
1answer
152 views

maximization over a simplex

Suppose I am given two sets of real numbers $\{a_i\}_{i=1}^N$ and $\{w_i\}_{i=1}^N$ with $w_i>0$. I am trying to find the maximum of the expression $$\left\lvert \sum_i a_i \left(\frac{w_i ...
11
votes
3answers
4k views

Gradient Descent with constraints

In order to find the local minima of a scalar function $p(x), x\in \mathbb{R}^3$, I know we can use the gradient descent method: $$x_{k+1}=x_k-\alpha_k \nabla_xp(x)$$ where $\alpha_k$ is the step size ...
3
votes
2answers
412 views

linear least squares minimizing distance from points to rays - is it possible?

I'm writing a tool whose purpose is to process data from a sensor that provides the true bearing to a target, and combine measurements taken at various times into an estimate of the target's position ...
3
votes
2answers
268 views

Lagrange multipliers with non-smooth constraints

I read in a textbook a passing comment that Lagrange multipliers are not applicable if there are points of non-differentiability in the constraints (even if the constraints are continuous). For ...
0
votes
1answer
260 views

Binary Integer Programming Problem

Below I need solve for the binary variables $x_1,x_2,y_1,y_2,z_1,z_2$ that minimize the functions $f(x), f(y), f(z)$, subject to the 5 constraints that follow. By binary I mean they can only be 1 or ...
0
votes
2answers
64 views

Optimizing duration of activities

I would like to understand optimization through a simple application, and then progressing towards understanding more general concepts. My inquiry starts with its application: Optimizing duration of ...
5
votes
5answers
875 views

Local minimum and maximum of the function

Can anyone help me to solve the following question? maximize and minimize the function $(10-x)(10-\sqrt{9^2-x^2})$ over $x\in[0,10]$ This is a high school question, so is there any simple trick help ...
1
vote
0answers
222 views

Point-wise error estimate in polynomial regression

In our application we wish to estimate the actual path of objects. We have a set of samples of object locations $(t_i, x_i, y_i, P_i)$ where $t_i$ is the sample time, $(x_i, y_i)$ is the 2D location, ...
5
votes
1answer
480 views

Find minimum in a constrained three-variable equation

After my last question I have worked through the math quite a bit and now I'm stuck again. This time my question is less wordy. I have two equations for $t$, one with respect to each $a_{x}$ and ...
5
votes
2answers
366 views

Question about path-finding

It is possible to find the shortest route thanks to algorithms like A*, bread first search, depth first search, etc.. Is there any known algorithm to find how many routes are available if there are ...
5
votes
2answers
2k views

Linear regression for minimizing the maximum of the residuals

We know that simple linear regression will do the following thing: Suppose there are $n$ data points $\{y_i,x_i\}$, where $i=1,2,\dots,n$. The goal is to find the equation of the straight line ...
5
votes
1answer
112 views

Minimize and maximize length of a polygonal chain with certain boundary conditions

let $P_0,\ldots, P_k\in \mathbb{R}^2$ be a set of points. Furthermore let $\epsilon\in \mathbb{R}$. Now I am trying to find non-trivial lower and upper bounds for $$ \sum_{i=1}^k ...
6
votes
1answer
2k views

Split a set of numbers into 2 sets, where the sum of each set is as close to one another as possible

Given a set of numbers, I'd like to split this set into 2 sets, where the sum of each set is as close to equal as possible. How would I go about doing this in a programmatic way? Thanks in advance ...
1
vote
0answers
172 views

Minimize submatrix having the same number of distinct columns as given matrix

Let M be an n by m matrix. For a subset S of {1,...,n} let M(S) be the submatrix of M with row indices in S. I would like to find an S of smallest size such that M(S) has the same number of distinct ...
4
votes
2answers
977 views

Math notation for location of the maximum

My question is about notation. I have maximum of the function $f(x)$. This can be expressed as $\max(f)$ How can I express in compact form that $x_0$ is the location of that maximum.
1
vote
1answer
214 views

question about Lagrange multiplier

I was reading about the problem of maximizing $x^2+y^2+z^2$ on the intersection of the two surfaces $xyz=1$ and $x^2 + y^2 + 2z^2 = 4$. The author wrote that $\nabla F=a \nabla g+b \nabla h$ (for ...
1
vote
0answers
147 views

Modeling propositional formulas in integer programming

Say I have an binary integer programming problem: \begin{equation*} \begin{aligned} & \underset{\mathbf{x,y}}{\text{minimize}} & & f_0(\mathbf{x,y}) \\ & \text{subject to} & ...
3
votes
2answers
112 views

Maximum uniqueness

Consider the function $g:\left(0,1\right)\rightarrow\mathbb{R}$ defined by $$ g\left(x\right)=\left(1-x\right)\left(1-\frac{1}{1+f\left(x\right)}\right), $$ where $f\left(x\right)$ is a continuously ...
8
votes
1answer
287 views

Simple question: the double supremum

Let $f:A\times B\to \mathbb R$. Is it always true that $$ f^* = \sup\limits_{a\in A,b\in B}f(a,b) = \sup\limits_{a\in A}\sup\limits_{b\in B}f(a,b). $$ I proved it by the $\varepsilon$-$\delta$ ...
2
votes
1answer
136 views

a problem on optimization having a good looking

$$\min_{x\geq 0}\sum_{i=1}^n (a_i-x b_i)^2 [a_i-x b_i\leq 0],\quad a_i,b_i\in\mathbb R,n\in\mathbb N$$ where $[p]$ is an Iverson bracket. The objective function seemed easy (convex). 1.Is there any ...
2
votes
0answers
111 views

An optimization problem involving Latin Squares

Let $C$ be a given $n \times n$ matrix of real numbers and let $p$ be a given $n$ vector of non-negative numbers such that wlog $\sum_i p_i = 1$ and wlog the $p_i$ are non-increasing. I'll write ...
0
votes
2answers
151 views

Finding the “best” way to map set of points to another set

I've got a set of points (currently 4, but I can increase the number for better accuracy), and I want to find the optimal transformation so that they can be mapped to another set of points. For ...
4
votes
2answers
296 views

Optimization without knowing function's form or derivative

I understand that this question may not have a corresponding answer. We are developing a control algorithm using dynamic programming. Effectively we are change one input variable and then plot the ...
7
votes
2answers
1k views

Euler-Lagrange, Gradient Descent, Heat Equation and Image Denoising

For an image denoising problem, the author has a functional $E$ defined $$E(u) = \iint_\Omega F \;\mathrm d\Omega$$ which he wants to minimize. $F$ is defined as $$F = \|\nabla u \|^2 = u_x^2 + ...
0
votes
0answers
247 views

notation for defining variables in objective function

Sorry, very basic question on notation. If I have an expression, for example (essentially a case where "long expression" corresponds to the predicted/estimated/computed value of $x$ and appears ...
2
votes
0answers
62 views

Accurate computation for Linear Regression case

I am writing a program that inputs a sequence of points $(x_i,y_i)$ based on the user clicking on certain pixels in an image shown. The program should then find the "best -fitting" line in the least ...
10
votes
3answers
6k views

Lagrange Multipliers with Inequality Constraints

I do not have much experience with constrained optimization, but I am hoping that you can help. My current problem involves a more complex function, but the constraints are similar to the ones below. ...
2
votes
2answers
84 views

Prove that this is the solution to the given minimization problem

I have the minimization problem minimize $\displaystyle f_0 = \sum_{i=1}^{N} \mu_i \left( \left( 2^\frac{R_i}{\mu_i} - 1 \right) \right)$ with constraint $\displaystyle\sum_{i=1}^{N} \mu_i = 1$ ...
1
vote
0answers
58 views

A complex minimization problem

Let $M_a(\mathbf{C})$ the space of all symmetric (w.r.t conjugation) probability measures $\mu$ on $\mathbf{C}$ such that the support of $\mu$ is included in $R_a:=\{z\in\mathbf{C};\ Re(z)\leq a\}$, ...
3
votes
1answer
103 views

Matroids and Optimization

I'm in the process of learning about Matroid Theory (I'm reading Oxley's book). I came to this from combinatorics and topology. Now, I just read of connections between matroids and combinatorial ...
10
votes
2answers
1k views

Derivation of the method of Lagrange multipliers?

I've always used the method of Lagrange multipliers with blind confidence that it will give the correct results when optimizing problems with constraints. But I would like to know if anyone can ...
3
votes
1answer
284 views

Formula for the largest distance to a set of points

I have $n$ points $(x_1, y_1), (x_2, y_2), \ldots, (x_n, y_n)$ all located in the unit square $[0,1] \times [0,1]$. I am trying to compute the largest distance from a point in the unit square to the ...