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

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
7 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
10 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
1answer
37 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
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 ...
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 + ...
0
votes
0answers
130 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
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} + ...
2
votes
0answers
31 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} & ...
0
votes
1answer
13 views

How to model a multiobjective problem with a large dataset?

I have a large dataset of businesses (around 5k venues with distance from a predefined point, average price and service quality rating) and I need to create the objective functions to minimize the ...
3
votes
1answer
46 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
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 ...
2
votes
2answers
45 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 ...
2
votes
3answers
98 views

Conditional inequalities

Let a,b,c be positive real numbers such that $abc=1$. Prove that $$\frac 1{a^3(b+c)}+\frac 1{b^3(c+a)}+\frac 1{c^3(a+b)} \ge \frac 32$$ We can derive the following inequalities from the given equality ...
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 ...
4
votes
1answer
46 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
2answers
2k views

Optimization of the surface area of a open rectangular box to find the cost of materials

A rectangular storage container with an open top is to have a volume of 10 cubic meters. The length of the box is twice its width. Material for the base costs ten dollars per square meter and for the ...
0
votes
0answers
10 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 | ...
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 ...
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 ...
8
votes
6answers
469 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
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 ...
4
votes
1answer
373 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
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 ...
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
vote
2answers
61 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
26 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
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 ...
0
votes
1answer
160 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
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)= ...
1
vote
1answer
297 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
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
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
1answer
956 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
119 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
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 ...
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 ...
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 ...