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
0answers
5 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 ...
1
vote
2answers
22 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 ...
8
votes
6answers
434 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?
4
votes
1answer
29 views

A Question about Nested Maximizations

I am working on labor demand models where firms have to choose the optimal level of employment by maximizing profits. In particular, I have faced the following problem: Maximize with respect to $l$ ...
2
votes
0answers
15 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
26 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 ...
4
votes
1answer
371 views

Linear Programming with One Quadratic Equality Constraint

I have a problem which can be formulated as a Linear Programming with One Quadratic Equality Constraint: where variable x is n-dimensional vector and H is a Semi-Positive Definite n-by-n matrix. I ...
0
votes
0answers
9 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
36 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 ...
3
votes
1answer
31 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
vote
2answers
59 views

Theorem 6.4.1 Auslender Asymptotic cones and functions in optimization and variational inequalities

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 ...
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 ...
-1
votes
1answer
22 views

Lagrange primal and duality properties

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
24 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 ...
0
votes
1answer
148 views
+50

Proving that $\text{ri rge}\,A=\text{ri conv rge}\,A$

"If $A:\mathbb R^n\rightrightarrows\mathbb R^n$ is maximal monotone,then $\text{ri rge}\,A$ is convex". This is a proposition in auslender's book about the asymptotic cones. We can prove that ...
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)= ...
1
vote
1answer
296 views

Gradient-descent and Hidden Markov Models

I would like to use gradient-descent to fit the parameters of a simple 2-state HMM. This paper Levinson, S. E., Rabiner, L. R. and Sondhi, M. M. (1983), An Introduction to the Application of the ...
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
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
1answer
951 views

How do I construct the Jacobian for use in a Levenberg-Marquardt algorithm.

I am working on a 3D reconstruction system and I am looking to use a Levenberg-marquardt algorithm to do bundle adjustment. I am not too sure about how LM works and what it requires. The model I am ...
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). ...
2
votes
1answer
118 views

Horn–Schunck method. Explanation of iterative solution

I am reading this paper (explanation of Horn-Shunck method for finding optical flow) and trying to understand it. My stumbling block is obtainig solution of system of linear equations I(x, y, t) ...
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 ...
2
votes
1answer
1k views

primal to dual solution conversion ??

i have an optimization problem $$\text{ maximize } z=3x+4y$$ $$\text{ such that: } x+y ≤ 450 \text{ and } 2x+y ≤ 600$$ the optimal solution to this problems comes to be $x=0$; $y=450$; $p=150$ ...
0
votes
0answers
21 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 ...
-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 ...
0
votes
0answers
47 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 ...
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 ...
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 ...
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 ...
3
votes
1answer
462 views

Maximum likelihood estimators, hypergeometric and binomial

I'm trying to solve a two part problem. The set up is as follows: consider a bag with $\theta$ red marbles and $7-\theta$ blue marbles, with $\theta$ being unknown. Let $x$ denote the number of red ...
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 ...
4
votes
1answer
67 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
1answer
441 views

Linear programming: the optimum of the shortest path problem is attained by $x \in [0, 1]^m$

Let $G=(V,E)$ be a graph, where $|E|=m$, and suppose we formulate the shortest path problem on $G$ as follows: minimize ${}^t(1,\dots,1)x$ such that $Bx={}^t(1,-1,0,\dots,0), x\in \{0,1\}^m$, where $B ...
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
2answers
29 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
0answers
46 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
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 ...
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 ...
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 ...
1
vote
0answers
28 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
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 ...
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
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 ...
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 ...
4
votes
1answer
354 views

Derivation of Euler-Lagrange equation

Here is a simple (probably trivial) step in the derivation of the Euler-Lagrange equation. If we denote $Y(x) = y(x) + \epsilon \eta(x) $, I want to know why is $\dfrac{\partial ...
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)|$. ...