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
365 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
111 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
974 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
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 ...
1
vote
0answers
146 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
285 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
110 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
293 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
102 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 ...
2
votes
1answer
94 views

Two equilateral triangles

In an old IMC Shortlist, I found the following problem: Given a triangle $T$, consider the equilateral triangles $T_1\subset T\subset T_2$ such that $T_1$ is the greatest equilateral triangle ...
2
votes
1answer
100 views

An optimal regression problem/proof

I want to find a function $f$ that given $x$ will predict $y$. The expected prediction error of $f$ is $$e = E[(Y-f(X))^2]=\int \int [y-f(x)]^2 p(x,y) dx dy$$ the expectation of $(Y-f(X))^2$ with ...
0
votes
2answers
100 views

Lagrangian dual in continuous domain

The continuous max flow problem is posed as follows : sup $\int_\Omega p_s(x)dx$ subject to : $|p(x)| \le C(x); \forall x \in \Omega $ $p_s(x) \le C_s(x); \forall x \in \Omega $ $p_t(x) \le ...
1
vote
1answer
205 views

Is maximizing $\det A$ equivalent to minimizing $\mbox{tr} A^2$?

Question: $A\in\mathbb{R}^{n\times n}$ is a positive definite matrix with constant trace, i.e., $A>0$ and $\mbox{tr} A=k$. Let $\lambda_1\ge\cdots\ge\lambda_n>0$ be the eigenvalues of $A$. Can ...
0
votes
1answer
147 views

How to approach this sum-minimization problem

I am new to math. How to approach the following problem? $\min_{a,b} \sum_{t=1}^N (-4aX_t\sin(Z_tb) -4aY_t\cos(Z_tb)+a^2Z_t^2 + X_t^2 + Y_t^2)$ where $X_t,Y_t,Z_t$ for $t\in \{1,...N\}$ are given. ...
8
votes
2answers
455 views

Generalization of the Sultan's dowry problem

We know the solution of the Sultan's dowry problem: To reject the first $n/e$ candidates and then to select the first who exceeds the best of the sample. How to find the best strategy if we want ...
3
votes
1answer
484 views

Finding tight constraints on a linear inequality

I have $a^\intercal M b > 0$, where $\forall a_i > 0$, $\forall b_j > 0$, and M is known. I'd like to find a tight linear constraint on $b$ which is independent of $a$ (other than the ...
3
votes
1answer
164 views

setting up a dynamic programming problem with multiple states and controls

For an optimization problem with multiple states ($x$), controls ($y$), and random disturbances ($z$), the Euler equation for a stochastic dynamic programming problem is: $D_yU(x,y,z)+\beta E ...
15
votes
4answers
640 views

Gerrymandering/Optimization of electoral districts for one particular party

I'm asking this on behalf of Zach Weiner (actually it's my own initiative in order to promote this site). Original text is here, and is as follows: Hey-- This is Zach from SMBC, and I have a math ...
1
vote
1answer
163 views

Having such integral, how to optimize it in maple?

So we have : (1/3)*sig0*h^3*(int(int(sin((1/3)*arctan(y, x)), x = 0 .. r), y = 0 .. 2*Pi)) Is it possible to optimise it? (in maple or any other way...) How I ...
2
votes
1answer
178 views

Finding the maximum of a function

I want to find the maximum of the following function, $$ f(x, y) = e^{m e^{-x}+n e^{-y}-x-y}(mrxe^y+nsye^x+mn(r+s)xy), 0 \le x, y \le 1 $$ where $r, s, m,$ and $n$ are positive constants. At the ...
4
votes
1answer
107 views

Find the maximum

I would appreciate if somebody could help me with the following problem: Find the maximum of the function $$f(x,y,z) = x$$ on the curve defined by the equations $F(x,y,z) = G(x,y,z) =0$ with ...
10
votes
1answer
368 views

A (mathematically) sound investment strategy

It is common wisdom in the investment community that a long-term investor saving for his future would do well to invest in high-risk/high-return assets when he is young, slowly switching his portfolio ...
1
vote
0answers
56 views

Minimization of matrix of vectors in polar field

The problem I am facing is the reduction of vibrations of a rotating object. I have a series of vibration measurements taken at 5 different states with magnitude and phase components, and a set of ...
1
vote
2answers
313 views

A question on inequality of arithmetic and geometric means

Let $x_i>0, i=1,...,n$ and $x_1+..+x_n=K$. From the inequality of arithmetic and geometric means, we have $$x_1x_2...x_n\le \left( \frac{x_1+x_2..+x_n}{n} \right)^n$$ The equality holds if and only ...
7
votes
1answer
252 views

Stochastic assignment problem

Given an $n \times n$ real matrix $C$, we can try to maximize $$\Phi(C, \pi) = \frac{1}{n} \sum_{i} C_{i,\pi(i)} $$ over $\pi \in S_n$, the set of all permutations on $n$ objects. What can one say ...
8
votes
1answer
363 views

Manifold with minimum surface distance between two points

The book "The World is Flat" uses flatness as a metaphor for a global economy. In fact, a spherical world would seem to be better than a flat world in terms of reducing the distances between two ...
2
votes
0answers
569 views

Dynamic programming problem and shortest path problem

I was wondering if any dynamic programming problem can always be converted to a source-sink shortest path problem in a network with source and sink nodes given? And vice versa? Is any dynamic ...
0
votes
1answer
174 views

Relaxation of a linear constraint in a quadratic programming problem

the problem i have is like following: $x'Qx + f'x \rightarrow \min_x$ subject to $Ax \le 0$. $Q \ge 0$, so there's nothing wrong there, usual QP with a linear constraint. Is there a way to ...
7
votes
3answers
618 views

Decomposing a discrete signal into a sum of rectangle functions

Hello math@stackexchange community ! I have a simple question that seems to have a non trivial answer. Given a discrete one dimensional signal $w(x)$ defined in a finite range, and the boxcar ...
1
vote
0answers
27 views

How can I learn to create and solve Rational Choice models?

I have some scenarios I would like to model using rational choice theory (i.e. utility maximizing agents). For example, a two population type (I suspect this means two representative agents), two ...
2
votes
2answers
804 views

How to 'minimize' correlation between series

Hi fellow mathemagicians, let's say that I have 3 series of numerical results (they represent 'drawdowns') : ...
1
vote
0answers
174 views

Duality for Support Vector Machines

SVM classifier for two linearly separable classes is based on the following convex optimization problem: \begin{equation*} \frac{1}{2}\sum_{k=1}^{n}w_k^2 \rightarrow \min \end{equation*} ...
2
votes
2answers
112 views

optimize cuts from sheet of metal - what type of math is that?

A person has a sheets of metal of a fixed size. They are required to cut parts from the sheets of metal. It's desireable to waste as little metal as possible. Assume they have sufficient ...
0
votes
1answer
75 views

Does a collection of non-linear inequalities have “extreme points”

Say I have a collection of m non-linear inequalities, where each of the $i = 1... m$ inequalities has the form: $g_i(x) \leq 0$ where $g_i: \mathbb{R}^n \rightarrow \mathbb{R}$ and $g_i(x)$ is ...
1
vote
1answer
53 views

Can this integer programming problem be converted into another with nonnegative cost coefficients?

Suppose there is an integer programming problem: $$\min_{x_i \in \{0,1 \}, i=1,\cdots,k} \sum_{i=1}^k c_i x_i$$ subject to $$ \sum_{i=1}^k a_i x_i \leq W. $$ Suppose the cost coefficients are ...
4
votes
1answer
168 views

Derive maximal sum of binomial terms

How to determine a positive value of variable $m$, so that the following formula is maximized. $$\frac{(1-q)^m}{\sum_{x=m/c}^{m}{\binom{m}{x} (1-q)^{m-x} q^x}}$$ where $1<c<m$, $0<q<1$, ...