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)

0
votes
1answer
93 views

How is min max f(x,y) defined when solving a dual problem?

I am trying to solve a dual problem. And it is said that min max f() is always smaller or equal to max min f(). For example, $\max_{y \in Y} \min_{x \in X} f(x,y)$ is always smaller or equal to $ ...
1
vote
0answers
30 views

abstract optimization problem

Suppose we have general optimization problem $f(x)\rightarrow min$, where x is an element of some algebraic structure (e.g. x is rotation matrix and is an element of SO(3)). There are plenty of ways ...
1
vote
1answer
59 views

Maxima/minima of $f(x)=\frac{\sin(\frac{1}{2} Nx) }{\sin(\frac{1}{2} x)}.$

How do I find: the $\bf maxima$ and minima of the function $f$ with $ f$ given by: $$f(x)=\frac{\sin(\frac{1}{2} Nx) }{\sin(\frac{1}{2} x)}, \;\;(N=1,2,3...)$$ What I did, is: Minima: I set: ...
2
votes
3answers
96 views

Maximizing a product of factorials

I would like to maximize $n_1! n_2! \cdots n_k!$ under the constraint $n_1 + n_2 + \cdots + n_k = N$ and $n_i > 0$ for all $i$. Intuitively, I think the maximum occurs when all $n_i$ are $1$ except ...
0
votes
1answer
388 views

Feasible direction for a point

I am slightly confused with what I am asked to do when trying to prove that a boundary point satisfies the first order necessary conditions for it to be a minimum, ie that the dot product of the ...
1
vote
0answers
44 views

Minimization problem with PMP

Problem: Solve $\int_0^1(x^2+u^2)dt \rightarrow min$, subject to $x'(t) = u(t) + x(t)$ and $x(0) = 0$. Our approach to the solution We solve this problem using the Pontryagin Maximum Principle. ...
0
votes
2answers
65 views

find minimum of a function: $X^2 + X + 1$?

How do you find the minimum value of $X^2 + X + 1$? I know it's $3/4$ from intuition. How do you prove it?
0
votes
1answer
85 views

Minimize the mean square error $\frac{1}{m}\sum_{i=1}^m \| x_i - S(t_i)\|_2^2$ for a Bezier curve

The problem is 2.1 from here. I am trying to minimize the mean error $$ E(\alpha_1,\alpha_2) = \frac{1}{m}\sum_{i=1}^m \| x_i - S(t_i)\|_2^2 $$ Where $x_i$, lie on the curve $\gamma$ and $S(t_i)$ ...
4
votes
1answer
109 views

How find this minimum $\sum_{i=1}^{n}a^2_{i}-2\sum_{i=1}^{n}a_{i}a_{i+1},a_{n+1}=a_{1}$

let $a_{1},a_{2},\cdots,a_{n}\ge 0$,and such $a_{1}+a_{2}+\cdots+a_{n}=1$. Find this follow minimum $$I=a^2_{1}+a^2_{2}+\cdots+a^2_{n}-2a_{1}a_{2}-2a_{2}a_{3}-\cdots-2a_{n-1}a_{n}-2a_{n}a_{1}$$ My ...
2
votes
0answers
38 views

Minimization problem using PMP

Problem: I have to give the minima, subject to $x'(t) = u(t)$, $x(0) = 0$ and $x(1) = 1$ of the following function: $\int_0^1 u(t) dt$ I have to find this minima using the Pontryagin's Maximum ...
0
votes
1answer
124 views

Minimize distance between a line and a point

PROBLEM: We want to minimize the distance between a fixed point $(t_0,x_0)$ with $t_0 \leq 0$ and a line, $t = 0$. Formalise this problem as a Lagrange problem. Solve this equation by the Euler ...
0
votes
1answer
43 views

Providing an example function

Give an example of a function $f: \mathbb{R}^2 \to \mathbb{R}$ for which the function $f(tx,ty)$, for $t \in \mathbb{R}$, has a local minimum at $t = 0$ for all $(x,y) \in \mathbb{R}^2$, but $(0,0)$ ...
1
vote
1answer
56 views

Maximizing Value of Function

I have three variables $p \geq 0$, $q \geq 0$, $r \geq 0$ and a positive constant $m$. Let $m = p + q +r$. How can I show that the maximum value of $pq + r$ is no more than $\frac{m^2}{4}$? It's ...
0
votes
1answer
42 views

“Almost orthogonalizing” matrices using a signature matrix

Suppose $A$ and $B$ are two real symmetric $n \times n$ matrices (If simpler, consider $A$ and $B$ to be 0/1 matrices, say, adjacency matrices of d-regular graphs). Then $||AB||_{op} \leq ...
1
vote
2answers
676 views

How do I solve this optimization question?

A fence 8 feet tall runs parallel to a tall building at a distance of 2 feet from the building. What is the length of the shortest ladder that will reach from the ground over the fence to the wall ...
0
votes
1answer
168 views

Optimization Word Problem: Hard time setting up the objective function

So the biggest problem that I have with these questions is to establish an objective function. It really irks me that I can do all the steps after setting up the equation, but without it, Im obviously ...
0
votes
1answer
43 views

About unbounded linear functional

I'm reading the chapterfrom a optimization book and cannot understand the example listed below:" " Actually i have seen its linear. My question is why f is unbounded?
0
votes
2answers
707 views

Absolute maximum and absolute minimum of f(x)= ln x on [1,2]? [closed]

Can somebody help me with this one. Find the absolute maximum and absolute minimum of $f(x)$ = $ln(x)$ on $[1,2]$.
1
vote
1answer
41 views

Limit of maximizer not equal to maximizer of limit

I am looking for functions $f_n,f$ defined on a subset of $\mathbb{R}$ with unique maximizers $\alpha_n, \alpha$, such that $f_n$ converges to $f$ pointwise, but the $\alpha_n$ do not converge to ...
0
votes
1answer
219 views

Solving non-negative least squares by analogy with least squares (Matlab)

There is a least-squares problem Ax = b. It can be solved using backslash in Matlab (x = A \ b). Let's assume that I have the ...
0
votes
3answers
129 views

Find the max value of a function at a given interval

Trying to determine local max for a function at interval $[-4, 6]$. $$f(x)= x^3 -3x^2-24x + 7$$ Is the proper next step to take the derivative of $f(x)$ and find the roots, set roots = to zero?
2
votes
2answers
47 views

Maximize expected return

making a practice exam I had to make the following problem which I couldn't solve unfortunately... Problem In the springtime, a student has $N$ days to find a summer job for one month. Each day, ...
1
vote
2answers
41 views

Relaxed optimization problems

The original problem is \begin{align} \min & f(x) \tag{1}\\ \text{s.t.} & \text{constraint 1} \tag{2}\\ & \text{constraint 2} \tag{3}\\ \end{align} However, it is very hard to deal with ...
0
votes
1answer
149 views

Minimizing absolute value of a sum of cosines

We know that the function $\cos(Cx)$ is in the range $[-1,1]$ for any constant $C$. I am interested in bounding the absolute value of sums of such quantities, in some sense capturing a correlation. ...
1
vote
0answers
37 views

Decomposition of a symmetric semi-definite matrix into sums of sparse symmetric semi-definite matrix

I'll first provide the background. Let $x\in\mathbb{R}^N$ be decomposed into $n$ non-overlapping blocks of variables $x^{(1)},\ldots,x^{(n)}$. We say that $f:\mathbb{R}^N\rightarrow\mathbb{R}$ is ...
1
vote
1answer
58 views

Name this partition of a set problem.

I have a problem related (presumably) to set theory and I can't find the name of it. I just want you to name it so I can do some more research. Given a set $S$of $n$ elements $S= \{s_{1}, s_{2}, ...
0
votes
1answer
159 views

nth root algorithm: value of initial guess?

I wonder what value one would choose to maximize efficiency to make an initial guess for the nth root algorithm (supplementary constraint: only with the five operations: +, -, *, /, % (integer ...
2
votes
0answers
166 views

Megiddo's algorithm for lines of least weighted sum distance from a set of points

I came across the following problem: Given a set of n points (coordinate in 2d plane) within a rectangular space, find out a line ($ax+by=c$), from which the sum of the perpendicular distances of all ...
1
vote
2answers
92 views

What is this mathematics sub-field called?

I would love to answer another question on this site, but I am totally unfamiliar with the required technique. I mean, I don't even know the sub-field's name. The field I am looking for is one that ...
3
votes
1answer
1k views

Proving that a greedy algorithm yields the optimal solution for a problem

I'm a college computer science student, working on a project. In my project i have an optimization problem, which i belive is optimally solveable with a greedy algorithm approach. In every case i have ...
0
votes
3answers
49 views

Optimisation: Minimise series

Let $a_i\geqslant 0$ for $i=1,\ldots,n$. Show how to minimize $$\sum_{i=1}^n\frac 1 {a_i+x_i}$$ subject to $$\sum_{i=1}^n x_i = b$$ where $x_i\geqslant 0$ for $i=1,\ldots,n$ and $b>0$. ...
12
votes
3answers
589 views

Formula for picking time closest to (but after) target

Let's say you have an arbitrary length of time. You are playing a game in which you want to push a button during this time span after a light comes on. If you do so, you win ($+1$), if not, you lose ...
1
vote
1answer
25 views

Minimizing f(x) when f(x) can only be probed via a random process

Background: I'm writing a piece of software to run on a mid-tier HPC cluster, to perform automatic parameter optimization. Say I have a function f(x). I need to find x that minimizes f(x). For our ...
0
votes
0answers
29 views

Finding dual of incredibly complex LP; any trick?

This is homework, so only hints please. This is about a LP relaxation of the minimum cost perfect matching problem, with another constraint that shrinks the solution space in a way that a lot of ...
2
votes
0answers
41 views

Minimize $\sum_{k=0}^3(x_k^2 + u_k^2)$

Together with some friend we are making exercises containing the Bellman equation and we faced a pretty difficult one: $x_{k+1} = x_k + u_k$ for $k = 0,1,2,3$, with starting state $x_0 = 5$ and ...
1
vote
0answers
65 views

computing dual LP in graph matchings

I'm having a trouble converting the following LP to a dual LP. Help on some starting steps would be greatly appreciated!
1
vote
2answers
4k views

Difference between minimizing and maximizing functions

Could someone please explain the difference between minimizing and maximizing functions or give me some links to explain the difference in very very very simple terms? I have searched online and I ...
1
vote
3answers
192 views

Optimising function of two variables with Lagrange multipliers

I am trying to find formulae for the $x$ and $y$ that maximise the function $f(x,y)=a(x + p)^bc(y + q)^d$, subject to the constraints: $$x \geq 0$$ $$y \geq 0$$ $$x + y + p + q \leq M$$ Where $a$, ...
4
votes
1answer
61 views

Minimise $a + b + c + d$ s.t. $a^3+b^3=c^3+d^3$

a, b, c, and d are all different positive integers. I've tried googling optimisation and constrained optimisation, but I've not found anything applicable as yet. EDIT: I tried using Lagrange ...
2
votes
3answers
956 views

Proving the regular n-gon maximizes area for fixed perimeter.

It is often assumed that, given $n$, the regular $n$-gon will make the most efficient use of perimeter for area. I have never seen this proven. Anyone have something slick? (That is, how can we ...
0
votes
1answer
36 views

Compute $p \in P_2$ that minimizes $||x^{3}-p||$ in the '2'-norm

So far I've got an orthogonal base with: $\psi_0 = 1$, $\psi_1 = x$ $\psi_2 = x^{2}-\frac{2}{6}$ Am I supposed to calculate $p$ as: $\alpha_0\psi_0+\alpha_1\psi_1+\alpha_2\psi_2$ with: $\alpha_i ...
0
votes
1answer
38 views

Avoid evaluation of a very large matrix in non-negative matrix factorization

This is somewhere in between a math and a programming question, so please send me back to SO if you think it's off-topic. I'm implementing non-negative sparse coding, a regularized variant of ...
1
vote
1answer
2k views

Deducing that a matrix is indefinite using only its leading principal minors

$A$ is indefinite iff $A$ fits none of the above criteria. Equivalently, $A$ has both positive and negative eigenvalues. Also equivalently, $x^TAx$ is positive for at least one $x$ and ...
1
vote
0answers
121 views

How Matlab optimization works without Jacobian or Hessian

How does Matlab optimization tools works. It just gets the error function and doesn't need Jacobian (first derivatives) or Hessian (second derivatives)? How it is possible?
1
vote
2answers
58 views

Thief, exponential reward, optimal strategy

A thief robs a house every night. His profit each night is independent of others, and is a random variable with $Exp(1/\lambda)$ distribution. Every night, there is a probability $0<q<1$ that he ...
3
votes
1answer
234 views

The 2nd total derivative (Hessian) of a composite function -Version 1

Let $f\in C^2(\mathbb R^n,\mathbb R)$ and $Df:A\subset\mathbb R^n\to L(\mathbb R^n,\mathbb R)$ so that $Df_x:\mathbb R^n\to\mathbb R$ is $f$'s total derivative at $x\in\mathbb R^n$. ...
2
votes
0answers
86 views

Minimize the perimiter of a triangle with an inscribed circle

A circle touches the two legs of an angle. How can one draw a line that intersects both legs, such that the circle lies within the triangle with as sides the two legs and the drawn line, and such that ...
0
votes
1answer
23 views

Lower bound on maximal value

A bag contains $n$ items with different values. The total value is $1$. I am allowed to pick one item, and pick the item with the maximal value. Obviously, in the worst case I will get a value of $1 ...
4
votes
2answers
90 views

Maximize $\prod\limits_{i=1}^n m_i$

Someone visits a market where one hundred different types of fruit are sold. All types cost $1$ euro per pound. The utility the buyer receives from buying $m_1$ pounds of the first type of fruit he ...
1
vote
0answers
38 views

Optimization with definite integral

if I have to maximize $\left[\int_0^N c(i)^k\,\mathrm di\right]^{1/k}$ subject to $\int_0^N p(i) c(i) \,\mathrm di \leq I$ where $I, k$ are constants, and $c(i)$ is our choice variable. I saw in ...