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)

5
votes
2answers
82 views

Looking for mathematical optimizations when translating formulae to code

I'm writing an app which translates formulae into executable code. I've been experimenting with fairly obvious optimizations such as factoring (reducing number of multiplications) in order to make the ...
5
votes
2answers
777 views

Least square principles with Lagrange multiplier

I have a function to minimize: $$f(a_1,a_2,a_3,a_4)=\sum_{i=1}^n\left(\sum_{k=1}^3 a_k\ p_i^k -a_4\right)^2$$ subjected to this constraint: $$a_1^2+a_2^2+a_3^2=1$$ and $$a_4\geq0$$ I am trying ...
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 ...
1
vote
0answers
29 views

MLE estimation of parameters, converting normalized observations to integers and back

I am fitting a model's parameters to grouped data by maximizing the likelihood equation: $L(\theta)=N!\prod_{i=1}^{G}\frac{p_i(\theta)^{n_i}}{n_i!}$ $\theta$ is the vector of parameters. $n_i$ is ...
2
votes
1answer
59 views

Specific solvable cases of TSP

Did a quick search on polynomial time solvable TSP and found some references such as this one for special cases for the bottleneck TSP. Was wondering if anyone was aware of any references that catalog ...
1
vote
1answer
96 views

Puzzled by how to determine when a function takes on its maximum (or minimum)

I apologize for the specificity of the my question, but I'm concerned that I'm having trouble grasping an important concept. I'm puzzled by the answer provided for exercise 1.(v) in chapter 7 of ...
2
votes
1answer
428 views

Derivative of function including matrix logarithm

Is the following equation a first order approximation or incorrect for general matrix Lie groups? And what are the higher order terms? $$\frac{\partial}{\partial\mathbf x} (\log(\mathtt ...
10
votes
0answers
367 views

Is the layout of Burning Man's city “grid” optimal?

My intuition is that the layout of Burning Man's city "grid" optimizes for the smallest sum of all distances between any two points on the map. Am I correct? Is the proof obvious? Or is there another ...
2
votes
2answers
401 views

Simplex method: Optimality criterion

I have to show that if for a minimization problem, $z_j - c_j <0$, for all non basic variables then it has a unique optimal solution. The proof says "If we start with a feasible point $x$ ...
0
votes
1answer
163 views

Show $\nabla \bar{x}^{T} M \bar{x} = \lambda ( \nabla \bar{x}^{T} \bar{x} )$

I am trying to prove the sentence ...
1
vote
1answer
168 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
845 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\ ?$$
12
votes
4answers
6k views

Do dynamic programming and greedy algorithms solve the same type of problems?

I wonder if dynamic programming and greedy algorithms solve the same type of problems, either accurately or approximately? Specifically, As far as I know, the type of problems that dynamic ...
5
votes
1answer
346 views

What kinds of optimization problems can be solved by greedy algorithms accurately?

I was wondering what kinds of optimization problems can be solved by greedy algorithms accurately? I don't understand the following quote from Wikipedia: Greedy algorithms can be characterized ...
0
votes
1answer
115 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
1answer
478 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 ...
5
votes
2answers
181 views

How to solve mixed integer nonlinear programs?

I'm not a math expert so sorry for possible trivial questions. I have written this mixed integer nonlinear program (MINLP): $$ \begin{align} \min & \sum_{i \in ...
2
votes
1answer
298 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 ...
6
votes
0answers
227 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 ...
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 = ...
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 ...
3
votes
6answers
325 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.)
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
187 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 ...
1
vote
1answer
349 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 ...
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 ...
4
votes
2answers
465 views

Generalizing Lagrange multipliers to use the subdifferential?

Background: This is a followup to this question: Lagrange multipliers with non-smooth constraints Lagrange multipliers can be used for constrained optimization problems of the form $\min_{\vec x} ...
4
votes
0answers
777 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. ...
3
votes
2answers
266 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
259 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 ...
3
votes
2answers
409 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 ...
7
votes
3answers
412 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 ...
4
votes
2answers
271 views

Gradient descent in a distributed manner

Let $p(x_1,x_2,x_3)$ be a scalar function. The goal is to find $x_1,x_2,x_3$ to minimize $p(x_1,x_2,x_3)$. Now consider the gradient descent method: $$ \left( \begin{array}{c} x_1 \\ x_2 ...
9
votes
3answers
6k views

Optimum solution to a Linear programming problem

If we have a feasible space for a given LPP (linear programming problem), how is it that its optimum solution lies on one of the corner points of the graphical solution? (I am here concerned only with ...
2
votes
2answers
198 views

distance between lines in the space (with calculus)

If I have two lines $$ \eqalign{ & L_1 \left( t \right):p_1 + td_1 \cr & L_2 \left( q \right):p_2 + qd_2 \cr} $$ living in $\mathbb{R}^n$, there exists a classical formula to ...
1
vote
0answers
221 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, ...
10
votes
1answer
385 views

invex functions and their usefulness?

An invex function $f$ is a differentiable function from $\Bbb R^n$ to $\Bbb R$ that for some function $\eta : \Bbb R^n \times \Bbb R^n \to \Bbb R^n$ satisfies for all $x, u$, $f(x) - f(u) \geq \eta(x, ...
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 ...
5
votes
5answers
872 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 ...
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
1answer
125 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} + ...
1
vote
0answers
168 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
963 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.
10
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 ...
1
vote
1answer
213 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 ...
3
votes
2answers
111 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 ...