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
9 views

Functional Minimization of Exponential Decay

I would like to find a function $f$ that minimizes the functional: $$\ln(f(x))f(x)-\frac1x$$ over some range of $x > 0$. Is this a good application for functional calculus and the Euler-Lagrange ...
2
votes
0answers
28 views

Find extremum of functional

I want to find the extremum of $$J(y)= \int_1^2 \frac{\sqrt{1+y'^2}}{x}dx, \ y(1)=0, \ \ y(2)=1$$ I thought to use the following theorem: If $y$ is a local extremum for the functional $J(y)= ...
0
votes
1answer
41 views

Why does the functional have a local minimum at $0$?

Definition: Let $J: A \to \mathbb{R}$ be a functional , where $A \subset V$ and $(V, ||\cdot||)$ a linear space with norm. Let $y_0 \in A$ and $h \in V$ such that $y_0+ \epsilon h \in A $ for ...
0
votes
1answer
33 views

Is inequality $tr(A^{-1^T} B) tr(A^T B^{-1}) \leq constant$ correct?

I have the following optimization problem \begin{align} \min_{A} &tr(A^{-1^T} B)\cr \text{subject to} &x^T A x > 0 \cr & A_{ii}=1 \end{align} where $A$ and $B$ are some positive ...
0
votes
0answers
20 views

Maximizing the following function

I need to find values of $k_1$, $k_2$ and $k_3$ that maximize $C^{m_1}_{mm_1} \cdot C^{m_2}_{k_1-mm_1} \cdot C^{n_1}_{nn_1} \cdot C^{n_2}_{k_2-nn_1} \cdot C^{p_1}_{pp_1} \cdot C^{p_2}_{k_3-pp_1}$ ...
0
votes
0answers
11 views

Matching student-company at a fair (A variation of The Marriage Problem)

This problem is connected to the famous http://en.wikipedia.org/wiki/Stable_marriage_problem#Algorithm We have $s$ students and $c$ companies, where $s<c$. (Roughly speaking, $c \approx 20$ and $s ...
2
votes
1answer
40 views

Can critical point that $f''$ has different sign in its every neighborhood be a local extreme point?

Suppose that $f$ is a second order derivable function on $[0,1)$, and $f'(0)=0$. It is true that: If there exits $\delta>0$ such that $f''(x)\geq0$ for all $x\in[0,\delta)$, then $0$ is a local ...
-1
votes
1answer
26 views

Representing a series of Matrix inner product with a single matrix product.

I have a set of constraints in my optimization problem, constraints in the form , $\langle A, e_i e_j^T \rangle = r_{ij} ,\forall i,j \epsilon S$, where $A$ is an $n*n$ semidefinite and symmetric ...
1
vote
1answer
79 views

How to minimize the expectation?

Given random variables $X_0, X_1, \ldots, X_n$ with finite expectations $m_0, m_1, \ldots, m_n$ I want to prove that the numbers $a_i = \frac{\det \Lambda_{i0}}{{\det \Lambda_{00}}}$ minimise the ...
0
votes
0answers
20 views

Solving the quadratic optimization problem with quadratic inequality constraint

I have a quadratic optimization problem which which both objective function and constraint are convex. As the problem is very big, I used decomposition technique and divide the problem to smaller ones ...
0
votes
0answers
43 views

Solving constrained linear programming problem

For the variable $t$, problem is to find best multipliers $k$ which minimizes the objective function. Time: $t_1$, $t_2$, $t_3$,... given in input Multiplier $k_1$, $k_2$, $k_3$,... (These are ...
0
votes
2answers
28 views

Minimize multi-variable function one variable at a time

I am wondering if I can minimize a multi-variable function one variable at a time. In other words, is it true that: $min_{x_1,x_2} f(x_1,x_2)=min_{x_1} min_{x_2} f(x_1,x_2)$
2
votes
1answer
64 views

Functional Maximization

So how do we solve a problem like this: Find the function $s(x)$ such that $s(x)$ maximizes $$\int_0^{s^{-1}(k)} s(x) dx $$ where $x\in[0,10]$, $s(x)\in[0,1]$, and $k\in[0,1]$ ($k$ is a constant). ...
0
votes
1answer
29 views

Critical point - relative minimum

Checking the function $f:\mathbb{R}^2 \rightarrow \mathbb{R}, (x, y) \rightarrow (y-3x^2)(y-x^2)$ we can take an idea for the difficulty of finding conditions that ensure that a critical point is a ...
4
votes
1answer
66 views

Solution to an apparently simple Optimization Problem

I'm stuck at a proof of a property that is stated in a paper. Imagine we have a diagonal matrix $$\Sigma=\begin{pmatrix}\lambda_1& &0\\ &\ddots&\\0&&\lambda_n\end{pmatrix}$$ ...
0
votes
0answers
11 views

I want to find a maximum of a function by Maple. How to restrict the variables to be integers? [on hold]

For example, I want to find the maximum of $x^2+y^2$ with $0\le x,y\le 10$ in Maple. I can type $$maximize(x^2+y^2,x=0..10,y=0..10).$$ But if I restrict $x$ and $y$ to be both integers, then how can ...
2
votes
3answers
64 views

Finding Extrema of $f(x,y)=x^4+y^4-4xy$

Let $f(x,y)=x^4+y^4-4xy$ How do I find all the relative extrema and saddle points of $f$ which lie within the open square ${(x,y) | -2<x<2,-2<y<2}$. And also if $f$ was in the closed ...
1
vote
0answers
27 views

How to understand a proposition of subgradient

The question is from the following: Convex Optimization Algorithm (p.512)----- Prof. Bertsekas Let $f: R^n \rightarrow (-\infty, \infty]$ be a proper convex function. For every $x \in ...
0
votes
1answer
37 views

How can we continue to get the critical points?

A service requires the dimensions of a rectangle box are such that the length plus twice the width plus twice the height do not exceed $274cm$ ($l+2w+2h \leq 274$). What is the maximum volume of the ...
4
votes
4answers
104 views

Casino turns 50% of your losses into “free play”, are odds in your favor?

As a limited-time promotion, if you gamble during your first week at this casino, and you suffer a net loss of money, the casino will give you half of your losses (up to a certain amount) as "free ...
1
vote
1answer
12 views

Is there a way to find a good lower bound on $\Vert p_n \Vert_\infty$ without finding the extrema?

Let $$p_n(x):=x^n+c_{n-1}x^{n-1}+ \cdots + c_0$$ be defined over some interval $[a,b]$. Is there a way to find a good lower bound on $\max_{x\in [a,b]} | p_n (x) |$ without actually finding the ...
0
votes
4answers
43 views

Which function do we want to minimize?

A ray of light travels from the point $A$ to the point $B$ across the border between two materials. At the first material the speed is $v_1$ and at the second it is $v_2$. Show that the journey is ...
-1
votes
1answer
32 views

Do we have to use the Lagrange multipliers method? [on hold]

Draw a cylindrical container (with a lid), so as to contain $1$ liter of water, using a minimal amount of metal. Could you give me some hints how we could do that?? Do we have to use the Lagrange ...
3
votes
1answer
25 views

Lagrange multipliers method - absolute maximum and minimum

Using the Lagrange multipliers method I have to find the absolute maximum and minimum value of $f(x, y)=x^2+y^2-x-y+1$ in the unit disc. So, I have to find the extremas of $f(x, y)=x^2+y^2-x-y+1$ ...
1
vote
1answer
29 views

Combinatorial optimization problem

I'm having trouble writing a general algorithm for what at first glance appears to be a simple problem. If I have a volume $V_{required}$ that can be made from two smaller, different volumes how can ...
2
votes
1answer
22 views

Find numerical minimum of a function with many parameters

I have a function $$f(\vec{r}_1\dots,\vec{r}_N)=\mathrm{The \ sum\ of\ square roots\ of\ the \ eigenvalues\ of\ }\Omega(\vec{r}_1\dots,\vec{r}_N)$$ And I want to find one of its local minima with ...
0
votes
0answers
18 views

Sum of abs of negative eigenvalues divided by sum of abs of all eigen values.If the result is convex?

Let $\lambda_1 (X)\geq \lambda_2 (X)\geq\ldots\geq\lambda_n (X)$ denote the eigenvalues of a matrix $X\in S^n$. Let $f(X)= \sum_{i\colon λ_i<0}|\lambda_i(X)|$ and $g(X)= \sum_i|\lambda_i (X)|$. ...
0
votes
1answer
11 views

Maximization of a statistical property of a subset of random numbers

I have encountered a maximization problem which could be formulated as a discrete mathematics problem arising from statistics, but I don't know where to start or which techniques could be applied to ...
1
vote
0answers
24 views

Hungarian algorithm , Kuhn paper, definition of transfer and theorem 1 proof

http://tom.host.cs.st-andrews.ac.uk/CS3052-CC/Practicals/Kuhn.pdf Is the paper. I am looking at the definition of transfer, essential, inessential and the proof of theorem 1. Consider qualification ...
2
votes
1answer
49 views

Calculating the distance function and projection

Let $\Omega=\{x\in\mathbb R^n\mid\langle a,x\rangle=b\}$. We define the distance function and projection as follows $$d(x;\Omega)=\inf\{||x-\omega||\mid\omega\in\Omega\}$$ ...
0
votes
2answers
26 views

Maximization problem with constraint: no differentiation

$$\max \ \min[\alpha x_1, \beta x_2, \gamma x_3] \ \ \text{s.t.} \ \lambda_1 x_1 + \lambda_2x_2 + \lambda_3x_3 = c, \\\ \alpha, \beta, \gamma, \lambda_i, c \ \text{are constants}$$ Well, that ...
0
votes
0answers
7 views

Sorting signals to achieve highest possible similarty

I am currently trying to develop an algorithm in Matlab that sorts signals, which I have as columns of a matrix, to achieve the highest possible similarity of the signal with its neighbors. My first ...
0
votes
0answers
10 views

Analysis of Optimizatiointechniques: Regret Analysis vs. Direct convergence? [closed]

When it comes to convergence rate analysis of optimization algorithms (like gradient descent and its family), there seems to be to be two main: Direct analysis, i.e. bound on $$ |f(x_t) - f(x^*)| ...
4
votes
2answers
200 views

Why do Lagrange Multipliers work?

I know that the Lagrange multiplier method helps us evaluate critical points of $f$ on the closed boundary of the restriction. In other words we solve:$$\nabla f=\lambda \nabla g$$ But why does ...
1
vote
1answer
25 views

Which points in the interior of a parallelogram are as far as possible from the corners?

Question 1: Given a parallelogram $P=ABCD$, how does one construct/determine the points $X \in P$ which are as far as possible from the corners? That is, the points $X$ for which $$ ...
0
votes
1answer
29 views

Gradient in mirror descent

Mirror descent can be in general written as \begin{equation*} \nabla\Phi(x_{t+1})=\nabla\Phi(x_t)-\lambda_t\nabla f(x_t), \end{equation*} where $f$ is the objective function and $\Phi$ is a convex ...
1
vote
1answer
23 views

Dual residual for linearized ADMM

I am using linearized ADMM for a problem with a (non-smooth) convex loss function $f(x)$, and a hard constraint $x \in E$, where $E$ is an ellipsoid in $R^d$. I have encoded the hard constraint as $A ...
1
vote
1answer
35 views

To show that $f(y)$ has only one maximum in $y\in[0,1]$

I have function $$f(y)=\frac{1}{2} y \log \left(\frac{a^2 b \left(\frac{2}{y}-2\right)}{a b \left(\frac{2}{y}-2\right)+a+1}+1\right)$$ where $a,b>0$ and $y\in[0,1]$. I want to show that $f(y)$ ...
2
votes
0answers
45 views

What honeycomb has the highest volume to edge length ratio?

This question is analagous to the Kelvin Problem where the solution, the Weaire-Phelan Structure, has the highest volume to surface area ratio; however, the cell volume is compared to edge length ...
0
votes
1answer
19 views

Proving the existence of multiple maxima

Given a function of two variables, say f(x,y), what are some known techniques to prove that it has multiple maxima? I can see via simulation that this is the case, but trying to figure out a formal ...
0
votes
0answers
21 views

joint optimization problem with somewhat symmetric function

I have just brief question that the method that I use to solve optimization problem is legit. I have function $\max_{x,y}F(x,y)$, and first order condition gives me following equation. ...
1
vote
2answers
46 views

Is it convex function?

I have a function and I don't know it is whether convex or non-convex: $$J(c,\alpha)=\int_\Omega ( \alpha c-I(x))^2u \, dx+ \|\alpha\|^2$$ where $0 \le u \le 1$, $I(x): \Omega \to R$, $c$ is constant ...
0
votes
1answer
51 views

Algorithms For Large-Scale $\ell_{\infty}$ Minimization

The general problem I want to solve is well studied: $$ \min_x \Vert Ax\Vert_\infty \;\;\; \mathrm{s.t.} \;\;\; Bx=c, $$ which is equivalent to the following linear program: $$ \min_{t,x} \, t ...
1
vote
0answers
28 views

Optimization involving convex-concave function

Let $f(x,y)$ be a function defined on $[0,1]^2$ and define \begin{align} g(a,b) = f\left(\frac{a+b}{2}, \frac{a-b}{2}\right) \end{align} where $a$ and $b$ are such that $\frac{a+b}{2} ...
0
votes
1answer
38 views

MATLAB: minimize function using x value from previous iteration

I'm trying to develop an algorithm for a proximal point method defined as: $$ \underset{x \in \rm I\!R^n}{\arg\min} f(x) + \lambda g(x) $$ where f(x) is a convex and coercive function and also ...
0
votes
0answers
16 views

Optimization methods to find valleys in a map

I have a map of some size say $1000\times1000$ pixels that is in a equivalent sized array. Instead of searching the map for a global minimum what I'd like to do is find a cluster of connected minimums ...
1
vote
0answers
41 views

Can I clamp singular values of $3\times3$ matrix without effectively computing SVD?

I have a $3\times3$ matrix $A$, and compute its SVD $U \Sigma V^\star = A$. I clamp the singular values in $\Sigma$ to some small range (e.g. $[0.5, 1.5]$ ) and reconstruct matrix $\widetilde{A}=U ...
1
vote
2answers
57 views

proving that $(\text{aff}\,C-\text{aff}\,C)\subset\text{aff}(C-C)$

In proof of Theorem 6.4.1, the author assumes that $\text{rge}\,A\subset\text{aff}\,C$ and for $\epsilon>0$ claims that $\epsilon^{-1}(C-\text{rge}\,A)\subset\text{aff}\,(C-C)$, that I can't verify ...
0
votes
1answer
43 views

solving Non-liner optimization with non-liner constraint using fmincon in Matlab [closed]

I'm trying to solve a non-liner optimization problem with a non-liner constraint by applying fmincon function in matlab. However, I got the following error: "Failure in initial user-supplied nonlinear ...
0
votes
1answer
26 views

How to analysis the global and local maxima of $h(x) = (1-f(x))(1-g(x))$

I want to maximize $h(x) = (1-f(x))(1-g(x))$, where $f(x)=exp(-u(x))$ and $g(x)=exp(-v(x))$ and $u,v \ge 0 $. $h'(x) = -f'(x)(1-g(x))-g'(x)(1-f(x)) = 0$ results to that the points with the ...