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)

4
votes
1answer
31 views

Is $\det(U_1\Lambda_1 U_1^t +U_2\Lambda_2 U_2^t +I)\le \det(\Lambda_1 +\Lambda_2 +I)$ correct?

I want to simplify or find an upper bound for the determinant $|K_1+K_2+I|$ where $I$ is identity matrix, $K_1$ and $K_2$ are positive semi-definite matrices of size $n$ and thus can be written as ...
0
votes
0answers
9 views

How to solve this optimization problem (Interpolation on trigram, bigram, and unigram for language model)?

I am a newbie in optimization and learn about the language model in NLP. I am studying the basic interpolation method to estimate the probability of the current word given the last 2 words, $P(w_i | ...
0
votes
0answers
13 views

Second-order Quadratic Constraint

I would like to solve the following optimization problem using the gradient ascend method: \begin{array}{ll} \text{maximize}_{\theta} & \theta^TQ_1\theta + b_1^T\theta\\ \text{subject to} & ...
1
vote
0answers
15 views

How do we derive efficiency from robustness in the virtual ant solution to the traveling salesman problem?

Using virtual ants/swarm intelligence to solve the Traveling Salesman Problem is an example of using a robust system to solve an efficiency problem. We normally think of robustness and efficiency as ...
0
votes
0answers
53 views

Linear - Quadratic optimization for system of objectives

I have two distinct data sets, $\{x^{\mu},J^{\mu}\}$, $\mu=1,\ldots,n$ and $\{x^{\nu},V^{\nu}\}$, $\nu=1,\ldots,m$ that also include uncertainties $\delta J^{\mu}$ and $\delta V^{\nu}$. In these I fit ...
2
votes
2answers
28 views

Maximum perimeter for triangle inscribed in circle

How to prove that isosceles triangle has maximum perimeter from all trangles inscribed in circle? I found that from all isosceles trinagles - equilateral has maximum perimeter: Maximum perimeter of ...
2
votes
0answers
17 views

Optimization on Stiefel Manifold

$$\text{Find}~~U, V$$ $$\text{to maximize}~~f(U,V)=\text{tr}(U^TAVN)$$ $$\text{subject}~~U^TU=I_p,V^TV=I_p$$ where $N=\text{diag}(\mu_1,\cdots,\mu_p)$ with $\mu_1>\mu_2>\cdots>\mu_p>0$. I ...
1
vote
3answers
29 views

Constrainted optimization involving logarithms

The problem is to minimize $ f(x_1, x_2 ,x_3, x_4):= - \Big[ \log ({\frac{1}{4} + x_1}) + \log ({\frac{1}{2} + x_2})+ \log ({\frac{1}{5} + x_3})+ \log ({\frac{3}{4} + x_4}) \big]$ such that ...
0
votes
0answers
11 views

Deriving Dual Averaging from (Sub)gradient Descent

Here the presenter tries to derive a simple Dual Averaging from (sub)gradient descent. I have a little problems understanding the steps. (Sub)gradient descent: Loop through: $$ x_{k+1} = x_k - t_k ...
1
vote
0answers
38 views

First fundamental theorem of calculus for line integrals [on hold]

Please, could someone look at this tricky question? Find the work done by force $F(x,y)=(3y^2+2) \hat i+16x \hat j$ in moving a particle from $(-1, 0)$ to $(1,0)$ along the upper half of the ellipse ...
8
votes
6answers
454 views

Finding the largest triangle inscribed in the unit circle

Among all triangles inscribed in the unit circle, how can the one with the largest area be found?
3
votes
1answer
33 views

Hessian-Matrix positive definite $\iff$ $a$ local minimum?

It is commonly known that if $f$ is twice differentiable, $\nabla f(a) = 0$ and $H_f(a)$ positive definite, $a$ is a local minimum. So, in short: $H_f(a)$ positive definite $ \implies $ $a$ local ...
-1
votes
1answer
24 views

Lagrange primal and duality properties [on hold]

max Lprimal(x,lamb,mu) >= f(x*) + lamb g(x*) + mu h(x*) s.t. lamb >= 0 min Ldual(lamb,mu) = min max Lprimal(x,lamb,mu) What is the purpose and properties of the lagrange dual function, why do I need ...
0
votes
1answer
28 views

Dynamic programming approach for multidimensional problem

I use a dynamic programming approach to optimize the behaviour of individuals playing a game.I have one strategy matrix that describes the behaviour of individuals in situation 1, which depends on ...
1
vote
0answers
14 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
29 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
43 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
35 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
23 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
12 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
27 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
80 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
21 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
49 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
30 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
65 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
30 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
69 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
65 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
29 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
106 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? [closed]

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
26 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
1answer
25 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
50 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
26 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 ...