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
217 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
342 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
234 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
861 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 ...
5
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
124 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
140 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
880 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.
9
votes
3answers
3k 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
208 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 ...
1
vote
0answers
142 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} & ...
8
votes
1answer
271 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
329 views

How can I simplify this quadratic optimization?

I want to minimize $x^t P x + q^t x$ subject to the following constraint: For all $b \in B$, $|x^b| \le C \sum_{b' \in B} |x^{b'}|$ where $B = {1, ..., n}$ and $x^b$ is the $b$th component ...
5
votes
5answers
4k views

How many bananas can a camel deliver without eating them all?

This is a fun puzzle I was assigned on the first day of highschool (over a decade ago). I just dug it up randomly from under my bed and thought I'd share it with the SE community. At the time, I ...
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
105 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
147 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 ...
0
votes
0answers
221 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
2answers
182 views

To minimise max bin sizes in two-level balls-and-bin problem

Basically we consider two levels of mapping (the first is called partition and second mapping strategy) of balls into bins. And try to find the best partition strategy (the first level of mapping) to ...
0
votes
2answers
62 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 ...
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
5k 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
83 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
56 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\}$, ...
5
votes
1answer
109 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 ...
3
votes
1answer
96 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 ...
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 ...
4
votes
2answers
263 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 ...
1
vote
1answer
582 views

a property of log determinant

Let $X$ be a symmetric positive definite matrix, and $D$ be a symmetric matrix satisfying $\operatorname{tr}(X^{-1}DX^{-1}D) < 1$. How to show that $$f(X+D)\le ...
1
vote
1answer
69 views

The lower bound of the product between two variables

I wonder how I can determine the minimum of the product between variables $x$ and $y$ (in terms of $\theta$), given that both $x < 1 - \theta$ and $y < 1 - \theta$, and $x + y = 1$? So far I ...
4
votes
2answers
206 views

discontinuous optimization

I'm solving the following problem: $$ \max_\rho \;\; \rho \; \min\left[\left( \frac{bn}{an-bm} \right)[(a-m)-\rho], \frac{b}{a}[a-(p+\rho)]\right]$$ where all constants and variables are defined ...
2
votes
1answer
249 views

Extrema of $f:\mathbb{R}^n\rightarrow \mathbb{R}$

My question is about finding the extrema of a multidimensional function, $f:\mathbb{R}^n\rightarrow \mathbb{R}$. From lecture I know that $H_f(x_0) < 0 $ implies a isolated maximum $H_f(x_0) ...
4
votes
0answers
106 views

When can the optimal value of a SDP be achieved?

Looking at semidefinite programs, are there any sufficient conditions for the solvability (i.e. the optimal value can be achieved, that is infimum=minimum)? Obviously if the problem is unbounded, the ...
2
votes
1answer
89 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
98 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 ...
1
vote
1answer
94 views

Please help me find the maxima of this expression

I want to find $p$ which maximizes the given functional. $p$ is a function of the form $\mathbb{R}^2 \to \mathbb{R}$. $\Omega$ is a region in the 2-d plane. $\underset{p}{\sup} \int_\Omega \{ ...
0
votes
2answers
97 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 ...
2
votes
3answers
233 views

Issue with textbook exercise on vectors

the following is a question from my textbook on vectors: EDIT: Added text, so that the post is self-contained even without the picture. The points $A$ and $B$ have position vectors ...
1
vote
1answer
197 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 ...
3
votes
0answers
114 views

Optimal tax rate

Suppose you have two countries A and B, with a tax rate $T_A$ and $T_B$, respectively. The tax is redistributed to all people equally. Hence if you live in A and you make $I$ as income then you will ...
0
votes
1answer
141 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. ...
6
votes
3answers
955 views

Lagrange Multipliers

I would like to find the extrema of the function $f(x,y)=x^2+4xy+4y^2$ subject to $x^2+2y^2=4$ using Lagrange Multipliers. Is it possible to get for the Lagrange multipliers the value zero? I don't ...
3
votes
1answer
440 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
153 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 ...
2
votes
1answer
248 views

real-time linear programming

I'm going to implement in C a light-weight embedded lp-solver for a production system. I need to be able to sequentially solve a series of (possibly unrelated) linear programming problems with ~6-60 ...
1
vote
1answer
160 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 ...
3
votes
2answers
138 views

Calculate max/min of $x_1 x_2+y_1 y_2+z_1 z_2+w_1 w_2$

What is a good way to calculate max/min of $$x_1 x_2+y_1 y_2+z_1 z_2+w_1 w_2$$ where $x_1+y_1+z_1+w_1=a$ and $x_2+y_2+z_2+w_2=b$ and $x, y, z, w, a, b \in \mathbb{N} \cup \{0 \}$, and please explain ...
4
votes
1answer
104 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 ...
2
votes
1answer
173 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 ...