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)

2
votes
1answer
28 views

Use of binary variables in LP problems

I can't figure out how to write the following condition to an LP. I have four nonnegative variables: $X_A$, $X_B$, $X_C$, and $X_D$. The condition which should be satisfied is this: If $X_A$ and ...
1
vote
1answer
27 views

Help with minimizing integral

I want to make a formal argument that for the following optimzation problem $\underset{S}{\operatorname{argmin}} \int_0^D (x(t) - S)^2$ the minimum solution is to set S to the mean of x(t) in the ...
0
votes
0answers
21 views

Proof of orthogonality in the gradient descend algorithm.

Ok, this is perhaps an easy question but I'm stuck, so any help will be cherished. The gradient descent algorithm updates the weights as: $$\textbf{w}_{t+1} = \textbf{w}_{t} - \eta\nabla ...
0
votes
0answers
25 views

Limit of complex function at infinite order

Hello :) I'm trying to prove a theorem which is showing to be little difficult to do...So the problem is to prove the following: \begin{equation} \lim_{n\to\infty} \sup_\omega \left\lvert ...
-1
votes
0answers
4 views

Minimizing the distance between two set of vectors such that the angle of both set is equal

Suppose I have two set of vectors K1,I1 and K2,I2 forming a surface S1 and S2 respectively in R2 or R3. The angle between K1 and I1 is T1 and K2 and I2 is T2 respectively. The goal is to minimize the ...
1
vote
0answers
17 views

Optimization of area of rectangle within semicircle [duplicate]

The semi-circle is given by $y=\sqrt{25-x^2}$ Find the length and width of the rectangle such that it's area is optimized. How do I deal with problems such as these?
0
votes
0answers
8 views

Optimization Problem, including block bids.

Block order optimization Hello, We're a bit stuck on this problem, which involves bidding in blocks. We're given $Q, K, s(1),s(2),...s(24)$ $$ \underset{q}{\text{maximize}} ...
0
votes
0answers
5 views

Does one counterexample suffice to show that LPT-rule is not optimal for $P \mid \mid C_{\max}$ when $\#\text{jobs} \leq 2\cdot \#\text{machines}$

Excuse me for a somewhat trivial question, but my I can't seem to find closure. For a homework assignment, we are asked to show the following: Consider the problem $P \mid \mid C_{\max}$. ...
0
votes
0answers
6 views

Given M points and a weighted graph G, map the vertices to distinct points to minimize sum(edge_weight*edge_length)

Given an arbitrary undirected weighted graph G with N vertices, and an arbitrary set of M points P in euclidean 3-space, where M>=N, map the vertices to distinct points such that sum(edge_weight * ...
0
votes
0answers
13 views

Maximize the magnitude of a complex function

Given $$ B(\phi) ~=~ \cos(\phi - \phi_L) + \cos(\phi - \phi_L - \tilde{\phi}) ~e^{j{2\pi}d \left[(\cos\phi - \cos\phi_L )\;+\;(\sin\phi - \sin\phi_L) \right]}, $$ $d > 0$. $\phi_{m} = \arg ...
0
votes
0answers
15 views

Preservation of monotonicity under argmax

Suppose $f(x,y)$ is non-increasing in $y$ for all $x \in X$. Then, can we show that $x^*(y) = argmax_{x \in X}\{f(x,y)\}$ is also non-increasing in $y$? If so, what characteristics should the function ...
0
votes
0answers
13 views

Impact of removing active constraints in convex optimization

In active set methods for non negative least squares, we remove variables from the passive set to active set if the least squares solution gives negative values on those variables. What's the impact ...
1
vote
1answer
14 views

Chebyshev's approximation understanding

I am reading Boyd's book on convex optimization. Could you assisst me in understanding what this expression means: $$\text{minimize} \ \ \text{max}_{i=1,...,k}|a_i^Tx-b_i|$$ This is what I think ...
0
votes
0answers
27 views

Nonlinear optimization with eigenvalue problem as a constraint

I have an unknown matrix $\mathbf{A} \in \mathbb{R}^{2n \times 2n}$ which is a function of $n$ parameters $a_i, i=1,2,...,n$. The objective is to find these $a_i$'s and the objective function is as ...
1
vote
1answer
27 views

Lagrangian Multiplier for liner problem

I have a (probably) stupid question but I can't find the answer. I have the following problem (my problem is much more complicated but as an example) : \begin{equation} \begin{matrix} \displaystyle ...
0
votes
2answers
34 views

Computing operator norm of a matrix

In my notes I have that $\left\|\, \begin{bmatrix}3&1\\1&1\end{bmatrix}\,\right\| = 2+\sqrt{2}$; but I'm struggling to get this. Here's what I have: $$\left\|\, ...
0
votes
0answers
19 views

Semidefinite programming with symmetric matrix constaints

\begin{align} &\arg\min\limits_{0 \le \rho < 1} \rho \\[1ex] s.t.\quad & \begin{bmatrix} 1 - \rho^2 & -\alpha \\ -\alpha & \alpha^2 \end{bmatrix} + \lambda \begin{bmatrix} -2mL ...
0
votes
0answers
20 views

If the primal is unbounded, then the dual is infeasible.

In the context of duality in linear programming, prove that If the primal is unbounded, then the dual is infeasible. What I tried: The short version is that unbounded primal means a column ...
0
votes
1answer
16 views

LAD analytical minimization

Is it possible to minimize least absolute deviations analytically? Say given a sample $\{x_i\}_{i=1..n}$ find $$\arg\min_\lambda{\sum_{i=1}^{n}{|x_i-\lambda|}}$$
0
votes
1answer
19 views

Can a network migration problem be solved with linear programming

I'm trying to solve, using linear programming, the problem of determining in which order should network elements by migrated from one place to another. The idea is that resources such as bandwidth ...
6
votes
0answers
56 views

Heuristics for topological sort

I have a number of modules connected in a Directed Acyclic Graph. My problem is to find an optimal execution order (minimize the total execution time). Any topological sort suffices for a valid ...
2
votes
1answer
92 views

Convert a piecewise linear function into a linear optimisation problem.

Consider $$f(x) = \left\{\begin{matrix} 1-x, & 0 \le x < 1\\ x-1, & 1 \le x < 2\\ \frac{x}{2}, & 2 \le x \le 3 \end{matrix}\right.$$ where $x \ge 0$. Convert $$\min z = ...
0
votes
0answers
14 views

Rosenbrock function matlab

I am new to MATLAB and I am asked to implement on matlab the following algorithm: for an unconstrained minimisation problem. I am asked to apply the BFGS method with armijo line search ...
0
votes
0answers
35 views

Unconstrained minimisation problem Newton's method

min f(x) = $ x_1^4 + 2x_1^2x_2^2 + x_2^4 $ is an unconstrained min problem. The first question asks to show that $(0,0)$ is the unique minimiser. I have done the following.. Would I need to add ...
0
votes
0answers
5 views

Axis-aligned bound constraints and algebraic optimization

What is the methodology for optimizing a function with a interval bounded constraint? I guess the solution has something to do with KKT conditions and linearizing the constraint, but I'm stuck and I ...
2
votes
0answers
30 views

characterization of the solution to a generalized eigenvalue problem

Let's say we have the following optimization problem. (All the $\Sigma_{ii}$'s are positive definite.) $\max u^\top \Sigma_{12} v\quad$ $\text{subject to}\quad u^\top \Sigma_{11} u = 1\quad and\quad ...
0
votes
0answers
27 views

Convergence of Algorithm in optimization

$\bf[8.54]$ Let $f:\Bbb R^n\to\Bbb R$ be differentiable. Consider the following procedure for minimizing $f$: $\qquad$ Initialization Step $\quad$ Choose a termination scalar ...
2
votes
0answers
20 views

Why polynomial $\psi^\top(t) A^{-1} \psi(t)$ attains maximum on $[-1, 1]$ at $\pm 1$, where $\psi_k(t) = t^k$?

Problem. Let $\psi(t) = (1, t, t^2, \ldots, t^{p-1})$ - a polynomial basis. Suppose there is a matrix $$ A = \int_{-1}^1 \psi(t) \psi^\top(t) dt, \ \text{i.e. } \ A_{ij} = [2 \, | \, i+j] \cdot ...
1
vote
0answers
57 views

When does a variable goes out with the revised Simplex method?

Let be the following linear program. \begin{cases} \max & 3x_1& +x_2\\ &x_1&-x_2 &\le -1\\ &-x_1 &-x_2&\le -3\\ &2x_1 &+x_2 &\le4\\ x_1,x_2\ge 0 ...
0
votes
0answers
10 views

Pseudo-Boolean functions restricted to integers

The Pseudo-Boolean functions are of the following form. $$ f : \mathbb{B}^n \to \mathbb{R} $$ I would like to know if there is a special sub-category of $$ f : \mathbb{B}^n \to \mathbb{Z} $$ with ...
0
votes
0answers
16 views

Reference request: monotone and strongly monotone with respect to derivatives

Recall, let $H$ be a real Hilbert space. A mapping $F:H \rightarrow H$ is said to be monotone if $$ \langle F(u)-F(v), u-v\rangle\geq 0, \quad \forall u,v\in H; $$ strongly monotone if there exists ...
1
vote
1answer
26 views

Solve dual of linear program without simplex

I have a linear program and need to determine and solve the dual program. The primal program is $\begin{array}{lcl} \text{Maximize: }\\ f(x) := 6x_1+4x_2\\ \text{Subject to:}\\ -2x_1-4x_2 \leq ...
0
votes
2answers
25 views

Find the point on the ellipse where the cylinder intersects the plane furthest from the origin?

I'm confused about how I should set this problem up. It is a lagrange problem. The cylinder x^2 + y^2 = 1 intersects the plane x + z = 1 in an ellipse. Find the point on the ellipse furthest from ...
1
vote
0answers
30 views

minimize trace(AX) over X with a positive semidefinite X

I want to minimize trace(AX) over X, under the constraint that X is positive semidefinite. I guess the solution should be bounded only for a positive semidefinite A, and it's zero, or the solution ...
2
votes
1answer
17 views

Question about the constraint in Laplacian eigenmaps

When calculating Laplacian Eigenmaps, the original paper mentions about the constraint $$y^TDy=1$$ as "removes an arbitrary scaling factor in the embedding". My understanding is that it prevents $y$ ...
1
vote
1answer
32 views

Find the global extrema of $f(x,y)=\sin(xy)$ on $D=[(x,y)| x = [0,\pi], y=[0,1]]$

Find the absolute maximum and absolute minimum of the function: $$f(x,y) = \sin(xy) \text{ on } D=[(x,y)| x = [0,\pi], y=[0,1]]$$ I took the partial derivatives and got: $$\frac{df}{dx} = \cos(xy)y ...
1
vote
0answers
27 views

How does one rigorously prove that gradient descent indeed decreases the function in question locally i.e. show $f(x^{(t+1)}) \leq f(x^{(t)})$?

How does one prove that gradient descent indeed decreases the function in question locally? In other words if we take a step in the negative of the gradient as in: $$ x^{(t+1)} = x^{(t)} - \eta ...
0
votes
0answers
20 views

Differentiation minimization

This question taken from web based engineering mathematics online test. My answer to this question as below. This system says it is incorrect. Is there any mistake? Plz help.
0
votes
0answers
5 views

Is $f(x)=-3x_1+x_2-x_3^2$ pseudoconvex at $\bar x$?

Is $f(x)=-3x_1+x_2-x_3^2$ pseudoconvex at $\bar x=[-115/588, -95/588, 5/14]^T$? Pseudoconvexity: If $\nabla f(\bar x)^T(x-\bar x)\ge0$, then $f(x)\ge f(\bar x)$ for any $x\in \mathbb{R^3}$ (in this ...
1
vote
1answer
31 views

how to find mininimum $f(x)$ using $\int_{-\infty}^{\infty} f(x)g(x)dx$?

I would like to know the $f(x)$ which minimizes the $\displaystyle\int_{-\infty}^{\infty} f(x)g(x)\,dx$. Actually, this question start from the MMSE (Minimize Mean square error) ...
0
votes
2answers
25 views

Maximizing the Nullity of a Symbolic Gram Matrix

I have a symbolic gram matrix, that is, a matrix $AA^T$ with some entries being variables. I would like to find a solution for my variables which maximizes the nullity of this matrix, or equivalently, ...
0
votes
0answers
20 views

Travelling salesman - organising a tour of any European destination based on the cheapest flights available.

I apologise if this has only a tenuous link to a mathematics forum I'm sure everyone is familiar with the £10 one-way flights by Ryanair and similar airlines in Europe. I was wondering whether there ...
1
vote
3answers
81 views

the minimum and maximum values of the determinant of order $3\times3$ matrix with entries $\{0,1,2,3\}$

The minimum and maximum values of the determinant of order $3\times3$ matrix with entries $\{0,1,2,3\}$.
0
votes
0answers
12 views

Unbounded variables and dual of a linear program

I have to find the dual of \begin{cases} \max & -x_1 &-2x_2+x_3\\ & -3x_1 &+x_2&\le-1\\ & x_1 &-x_2&\ge 1\\ & -2x_1 &+7x_2&\le6\\ & -5x_1 & ...
44
votes
7answers
1k views

What is the optimal path between $2$ fixed points around an invisible obstructing wall?

Every day you walk from point A to point B, which are $3$ miles apart. There is a $50$% chance each walk that there is an invisible wall somewhere strictly between the two points (never at A or B). ...
6
votes
2answers
187 views

Optimal path around an invisible wall [duplicate]

The Problem On an infinite plane there are two points, $A$ and $B$, a unit distance apart. There is a $50\%$ probability that there is an invisible wall somewhere between the two points. The ...
0
votes
0answers
26 views

How to form a dual problem in convex optimization (in a broad view)

After reading some papers, this problem confuses me. There are different forms of dual problem to the primal problem: $$\underset{x}\min \ \ f(x)$$ where $f(x)$ is a convex function. By ...
0
votes
1answer
29 views

How to determine constant $C$ in $p(x) = Cx^{-D}$?

Given a distribution obeying the power-law (fractal) relation, such as the cumulative distribution function $L_{cf}(> X) = CR^{-D}$, if $X$ is given, how does one find the constant $C$ from a given ...
0
votes
0answers
18 views

Linear integer programming

I am trying to find the optimal solution for the following linear integer programming: \begin{eqnarray} &&\underset{x_i, \forall i} {\text{maximize}} ~ \sum_{i=1}^N x_i a_i \\ && ...
1
vote
2answers
29 views

The number with minimum sum of differences

Let $a_1,a_2,...,a_n\in\mathbb{R}$. I wonder how to find the number $x$ with $$|x-a_1|+...+|x-a_n|=\mbox{min}\{|a-a_1|+...+|a-a_n|\mid a\in\mathbb{R}\},$$ namely the sum of the differences with ...