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

Help with Linear Algebra Optimization Problem. 4 people crossing a bridge

"Four people, A, B C and D need to get cross a river. The only way to cross the river is by an old bridge, which holds at most 2 people at a time. Being in dark, they can not cross the bridge ...
1
vote
2answers
26 views

Find the maximum and minimum of the function $f$

Find the maximum and minimum of $f(x, y)=xy-y+x-1$ at the set $x^2+y^2\leq 2$. I have done the following: Since the region $x^2+y^2\leq 2$ is closed, $f$ has a maximum and a minimum, which is ...
2
votes
1answer
14 views

Proof of convergence for the proximal point algorithm

I'm trying to come up with a super simple proof of convergence on the proximal point algorithm, which uses the iteration scheme $x^{i+1} = \mathbf{prox}_{tf}(x^i)$ where $\mathbf{prox}_{tf}(z) = ...
-1
votes
0answers
26 views

How to hedge a sports bet

Suppose I've got a $200 ticket on the Golden State Warriors to win the NBA Finals at 5 : 1. The finals start next week, with the Cavs listed at 2 : 1 to beat the Warriors and the Warriors 4 : 9 to ...
0
votes
0answers
15 views

Algorithm - Maximum subarrays with sum and OR

I was thinking on the following problem: Given an array A. The value of an interval from i to the index j is defined as follows: Take the maximum value from that interval, and add it to the OR ...
0
votes
0answers
8 views

What would be the objective functions for this problem?

I have the following data (this is just a sample of my entire dataset): # Distance PriceIndex Rating 1 400 3 5 2 420 2 4 3 500 1 2 Considering the ...
-1
votes
0answers
12 views

Absolute value equality of variables in optimization problem

I am trying to solve an optimization problem using either MATLAB's built-in $linprog$ function, or with MATLAB $CVX$ front-end. These tools provide an easy way to model constraints such as $A \cdot x ...
0
votes
0answers
16 views

Find the extremas of the fuction $f$

I have to find the extremas of $f(x, y)=3x+2y$ subject to $2x^2+3y^2 \leq 3$. Since the region $2x^2+3y^2 \leq 3$ is closed, $f$ has a maximum and a minimum, which is either at the boundary or at ...
-1
votes
1answer
38 views

Theorem of Lagrange multipliers - Extremas of $f$

I have to find the extremas of $f(x, y, z)=x+y+z$ subject to $x^2-y^2=1$, $2x+z=1$. I have done the following: We will use the theorem of Lagrange multipliers. The constraints are ...
0
votes
0answers
20 views

Linear Algebra L2 minimization

Im really confused about how to solve this question or even what its asking. Any help would be much appreciated! Let A be an m x n real matrix ($m \gt n$). Let x* be the minimizer of $||Ax - b||^2 + ...
1
vote
1answer
16 views

Shortest Path with Constraint

What is the length of the shortest path that goes from $(0,2)$ to $(12,1)$ that touches the $x$-axis? I tried using calculus to solve this problem (i.e.: distance is: $$ \sqrt{(x-0)^2 + (0-2)^2} + ...
3
votes
1answer
48 views

An Extension to the Generalized Eigenvalue Problem

Given two square matrices $A_1,A_2 \in \mathbb{R}^{n\times n}$, the generalized eigenvalue problem is finding the scalar $\lambda \in \mathbb{C}$ and vector $x \in \mathbb{C}^{n}$ such that $$ ...
0
votes
0answers
26 views

Maximising an area

I was wondering if someone could possibly explain this question: "A stadium should be oblong on plan with straight sides of length h and semi-circular arcs of radius r at either end. The facade must ...
1
vote
0answers
5 views

An equality between maximums of two logdet expression

I have the following question. Let $K$ be a positive-definite $N\times N$ real-valued matrix (I'll denote this by $0\prec K$ and will subsequently assume all matrices are $N\times N$ and real-valued) ...
1
vote
1answer
25 views

Application Farkas Lemma

Let $A$ be a $m \times n$ matrix and $C$ a $k \times n$ matrix. Let $b \in \mathbb{R}^m$ and $d \in \mathbb{R}^k$. Show that exactly one of the following holds: a) There exists an $x \in ...
2
votes
2answers
46 views

What is the interpretation of the following optimization problem?

Suppose we have $N$ variables $x_1,\ldots,x_N$. Let $\mathbf{A}$ a $M \times N$ matrix, and $\mathbf{b}$ a $M \times 1$ vector. I have the following minimization problem: \begin{array}{rl} \min ...
-1
votes
1answer
19 views

Subgradient Method Example [on hold]

can anyone show me an example(function) of subgradient method(unconstrained)? subgradient algorithm https://inst.eecs.berkeley.edu/~ee227a/fa10/login/l_cvx_alg.html ...
5
votes
1answer
49 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
11 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 | ...
2
votes
0answers
34 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
16 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
133 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
30 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
31 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
12 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
472 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
34 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
29 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
29 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
30 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
36 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
24 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 ...
0
votes
1answer
31 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
81 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
52 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
31 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
32 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
72 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 ...
-1
votes
1answer
38 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 ...