The Stack Overflow podcast is back! Listen to an interview with our new CEO.

Tag Info

New answers tagged optimization

0

It is tricky. In the definition of $F$ we have to evaluate $u(0)$ and $u(1)$. This implies that by writing $W^{1,2}([0,1])$ we already select the continuous representation, which exists by the Sobolev embedding theorem. This is an extremely important point. In that way, the function with $u(0)=1$ and $u(x)=0$ else is not in $W^{1,2}([0,1])$, since it is not ...

0

Define the function $$f(y)=-ky+\sum_{i=1}^n \max(0, y-x_i)$$ Without loss of generality, assume that $x_1,x_2,...,x_n$ are in increasing order. Like I said in my comment, we shouldn’t try to take derivatives since $f$ is not differentiable, but we can notice that its graph consists of a sequence of connected line segments whose slopes satisfy some nice ...

-1

You can introduce a new variable $z$ and minimize $z$ subject to $$z \ge \left(\frac{a_i-x}{a_i+x}\right)^2$$ for all $i$.

-1

Step two1 in "how to do a math problem": label the parts of the problem. So give the set you want a name. "Let $S = \{x \in \mathrm{Range}(A) : \mathbf{B}x = b\}$. ... $$\min_{x \in S} ||x||$$ ... " 1 : The number of this step in any particular "how to do a math problem" may vary.

0

The reason is: If $g,h : A \to \mathbb R$ are functions with $$g(y) \le h(y) \qquad \forall y \in A$$ then $$\inf_{y \in A} g(y) \le \inf_{y \in A} h(y).$$ To prove this, take a sequence $y_n$ with $h(y_n) \to \inf_{y \in A} h(y)$. Then, $$\inf_{y \in A} g(y) \le g(y_n) \le h(y_n).$$ Now, $n \to \infty$ gives the desired inequality.

0

WLOG assume $w=(1,0,...,0)$ and $n = (n_1,n_2,0,...,0)$; i.e. pick coordinates so that $w$ is the first unit vector, and $n$ is in the plane spanned by the first and second unit vectors. Write $v=(v_1,...,v_k)$. Then $v\cdot w=\alpha$ means $v = (\alpha,v_2,...,v_k)$ and $v\cdot v=1$ means that $v_2^2+\cdots + v_k^2 = 1-\alpha^2$. Thus, if $\alpha > 1$ ...

0

See bib of this presentation for some example references to market impact models.

-1

As stated, the problem is rather trivial, unless I'm misunderstanding something. If the relation between $Y,Z$ is arbitrary, and we want to maximize $I(X;Y)$ then the condition $I(X;Z) = 0$ adds nothing. Just maximize (without constraints) $I(X;Y)$. Using bits: $$I(X;Y) \le H(Y) - H(Y|X) \le 1$$ This bound is achieved if $H(Y) = 1$ (fair coin) and $H(... -1 I start with the bound $$1\geq H(Y)=I(X; Y)+I(Y; Z|X)$$ $$I(X; Y)\leq1-I(Y; Z|X)\leq1$$ Now it is obvious that$Z\perp Y, X$and$Y=X_1$uniformly distributed over$\{0, 1\}$does the job 0 For those coming here via a search: I found two workable solutions. Bayesian Model Based optimization can help here (in R, use mlrMBO). But it wasn't working very well for me (it was slow and hard to adapt to my application). I ended up coding up a variant of Simulated Annealing, which is usually espacially usefull for high-dimensional spaces with ... 2 The determinant on its own does not tell us about the definiteness of a matrix, but it does give us some information.$H$is positive definite if and only if all of its eigenvalues are positive. The determinant is the product of the eigenvalues. You can see that if the determinant were, for instance, zero or negative, then we would instantly know$H$is not ... 0 Considering $$L(x,\lambda,\epsilon) = \lambda_1(C_1-5(1-x)-x-\epsilon_1^2)+\lambda_2(C_2-3(1-x)-7x-\epsilon_2^2)+\lambda_3(1-x-\epsilon_3^2)+\lambda_4(x-10-\epsilon_4^2)$$ with$\epsilon_kconvenient slack variables, the stationary points are the solutions for $$\nabla L = 0 = \cases{4\lambda_1-4\lambda_2-\lambda_3+\lambda_4 = 0\\ C_1-5(1-x)-x-\... 0 Just recursively evaluate your expression from x_0=(\alpha, \beta) which gives$$x_{n+1} = \left(\frac{\alpha_n+\beta_n}{2} , 0\right) = \left(\frac{(\frac{\alpha_{n-1}+\beta_{n-1}}{2})+0}{2} , 0\right)$$Which gives you$$x_n = \left(\frac{\alpha+\beta}{2^n} , 0 \right)Which as expected gives that the whole algo converges to 0 with ratio \frac{1}{2}... 0 Is your function constant? If I read correctly you have \begin{align*} \underset{\text{w.r.t}\; x\in \mathbb{R}}{\text{maximise}}\; &\;-A\,\dfrac{C_1^{-m}}{m} -(1-A)\dfrac{C_2^{-m}}{m} = \gamma\\ \text{subj.to}&\quad h_1(x)\leq 0\\ &\quad h_2(x)(x)\leq 0\\ &\quad \alpha\leq h_3(x) \leq \beta \end{align*} Maximizing a constant function under ... 0 Unless I'm misinterpreting the question, I believe that \beta should always be 0, since every iteration concludes with a projection onto the x-axis. So if we remove the \beta term and focus on the effect of the dual projections on the x-coordinate, we see that the limit is \frac{1}{2}. 2 In a linear optimisation problem, the optimal solution (minimum or maximum) are always on the vertex of the constraint polygon. In the problem here, the constraint polygon is a triangle whose vertex are at (0,0), (1,0) and (0,1). On which vertex is the minimum depends on the value of a and b. Let first evaluate the function ax+by at these ... 1 You treat x,y,z as variables that depend on a fourth variable t, and differentiate the equation with respect to t. For example, look at your equation-x^2+y^2+z^2-1=0.$$Apply the differentiation \frac{d}{dt} to both sides of the equation to see that$$\frac{d}{dt}(-x^2+y^2+z^2-1)=\frac{d}{dt}0,\\-2x\frac{dx}{dt}+2y\frac{dy}{dt}+2z\frac{dz}{dt}=0....

3

I suppose your D2f(0) means the Hessian matrix of $f$ at $(0,0)$. You may just use a standard example in dimension 1 and consider $f(x,y) = x^3$. Then obviously the gradient is $[0,0]^T$ at $(0,0)$ and the Hessian at $(0,0)$ is the zero matrix, which has $0$ (nonnegative) as eigenvalues. But, from the graph of $f$, it is obvious that $(0,0)$ is not a local ...

0

Let $f:\mathbb{R}^2\rightarrow\mathbb{R}$ be defined by the expression $$f (x_1,x_2) = ({x_1} − {x_2}^2 )({x_1} - \dfrac{1}{2}{x_2}^2)$$ for all pair $(x_1,x_2)\in\mathbb{R}^2$. For every fixed $d\in\mathbb{R}^2$, we have that $x = (0, 0)$ is a local minimizer for function $\psi$ defined by $\psi(\lambda) ≡ f (x + \lambda d)$, but $x$ is not a local ...

2

A local extremum has a derivative of $0$ so you can differentiate this function and let the derivative be $0$. It is easy in this case, since the derivative is $$-\sum_{i=1}^n p(a_n-x)^{p-1}$$ In case of $p=2$, you just need to solve a linear equation which can be done without a computer. However first derivative just tell you local extrema. To check ...

0

I would do it as follows. First, define the set $I$ of possible shifts with two days off in a row : shift $1$ : mondays and tuesdays off shift $2$ : tuesdays and wednesdays off shift $3$ : wednesdays and thursdays off etc Complete with other types of shifts $J$ such as shift $i$ : mondays and wednesays off Second, define binary variables $y_i \in \{... 2 Take$(x,y) = (3,4)$and$(x,y) = (-3,-4)$. Both these points satisfy$|x| \le |y|$but$(3,4) \ne (0,0)$. Hence the cone is not pointed. 2 As pointed out by Calvin, the$|d|$comes from the fact that the directional derivative is in$\mathbb{R}^{n}$. Let me say some words here. If$U$is an open subset of$\mathbb{R}^{n}$and$f: U \to \mathbb{R}$has all its$n$partial derivatives over$U$, we say$f$is of class$C^{1}$. Now, let's assume$f$is$C^{1}$and take$U \subset \mathbb{R}^{2}$... 0 Here is a non-calculus solution, but it requires some linear algebra knowledge. However, if you want to use calculus, apply the Lagrange multiplier technique with the Lagrange function $$\Lambda(x,\lambda):=\frac{1}{2}\,\|x\|_2^2+c^\top x-\lambda^\top A x\,,$$ where$x\in\mathbb{R}^n$and$\lambda\in\mathbb{R}^m$(provided that$A$is an$m$-by-$n$matrix). ... 3 Consider the function$F=-\theta$aka the negative polar angle (taken between$-\pi$and$\pi$) near$p$with$x=1, y=0$(happens to also be$r=1, \theta=0$). Then the negative gradient of$F$is$\frac{1}{r} \hat{\theta}$and the gradient flowline through$p$is the unit speed parametrized arc of unit circle. Now consider$\beta(t)$with$\theta(t)=t$,$r(...

1

Here's how to prove an improved upper bound of $2^{n+1}$. Take the same graph on $n$ vertices as in your example, and consider the following group: $G=\left\langle a_1,\ldots,a_n,z| a_i^2=z^2=[a_i,z]=1\quad \forall i, [a_i,a_j]=\begin{cases} 1 \quad\textrm{if \{i,j\} is an edge} \\ z \quad\textrm{otherwise}\end{cases}\right\rangle$. I believe this group ...

0

Fix $n$ as a positive integer and fix $m \in \{1, ..., n\}$. Let $\mathcal{P}$ be the set of all vectors $p=(p_1, ..., p_n)$ that satisfy these constraints: \begin{align} &\sum_{i=1}^n p_i = 1\\ &p_i \geq 0 \quad \forall i \in \{1, ..., n\}\\ &p_1 \leq p_2 \leq ... \leq p_m\\ &p_m \geq p_{m+1} \geq ... \geq p_n \end{align} Now fix constants $... 0 I agree with the other answers that if you want an optimization problem, then an open region may not actually obtain its least upper bound on an objective. Also, the statement of linear programming does not include the ability to directly state strict inequalities. However, sometimes all you want to ask is a feasibility question rather than an optimization ... 2 Let$\mathbb{N}$denote the positive integers. Given$n\in\mathbb{N}fixed, we look for \begin{align*} &f:\mathbb{N}\to\mathbb{R}\\ &f(x)=\frac{n^4}{x}+4\left(n^2+3\right)x-4x^2-5n^2\qquad\longrightarrow\qquad\max\tag{1}\\ \end{align*} provided thatx\leq \frac{n^2}{4}$The additive constant$-5n^2$in (1) is not relevant for determining ... 0 Let$x$= number of hardcover books$y$= number of paperbacks maximize$(20-5)x + (15-3)y$subject to:$x + y \geq 1005x + 3y \leq 450 x \geq 0y \geq 0$This is an LP optimization problem which can be solved easily. you can search online how to solve a basic LP problem. You can even solve it graphically. 1 By the gluing lemma, the map $$g : x \in \mathbb{R}^n \mapsto \begin{cases}x &\text{if \|x\| \leq 1}\\\|x\|^{-1}x&\text{if \|x\| \geq 1}\end{cases} \in \mathbb{R}^n$$ is continuous and its image lies in the disc$\mathbb{D}^n = \{p \in \mathbb{R}^n: \|p\| \leq 1\}$. On the other hand, since$| \cdot | : t \in \mathbb{R} \mapsto |t| \in \...

0

Lagrange multipliers, also called Lagrangian multipliers (e.g., Arfken 1985, p. 945), can be used to find the extrema of a multivariate function  subject to the constraint , where  and  are functions with continuous first partial derivatives on the open set containing the curve , and  at any point on the curve (where  is the gradient). For an extremum of  ...

2

You can replace the Hadamard product of a vector by a matrix product with the diagonal matrix formed from that vector, e.g. let \eqalign{ X &= {\rm Diag}(x), \quad Y &= {\rm Diag}(y), \quad Z &= {\rm Diag}(z) \\ } then the function can be written in a number of ways \eqalign{ f &= x\circ y\circ z \\&= YZx = ZXy = XYz \\ } The ...

0

Hint: Let $g_b(x, y)=a$ $x^2-2bxy-7x+2y^2+133=a$ Solve equation for x: $x=(1/2)[2by+7 + \sqrt \Delta]$ $\Delta=(2by+7)^2-4(2y^2+133-a)=(4b^2-8)y^2+2by-483+4a$ Now x is maximum if $\Delta$ is maximum. For this take derivative of $\Delta$ equate it to zero and so on.

0

Take a set $X$ with just two points. On $X\times X$ define $f(x,y)=1$ if $x=y$ and $0$ otherwise. This is example where min and max cannot be switched but $f$ is continuous.

1

If $f\colon \Bbb R^n\times \Bbb R^n \times \Bbb R^n \to \Bbb R^n$ is given by $f({\bf x}, {\bf y}, {\bf z}) = {\bf x}\circ {\bf y} \circ {\bf z}$, then $f$ is trilinear. Thus its total derivative is the linear map ${\rm D}f({\bf x},{\bf y},{\bf z}): \Bbb R^n \times \Bbb R^n \times \Bbb R^n \to \Bbb R^n$ given by $${\rm D}f({\bf x},{\bf y}, {\bf z})({\bf h}_1,... 0 You can maximize a minimum or minimize a maximum with a single LP, but min-min and max-max are both non-convex. 2 The problem is stated as a global optimization (maximize the probability of finding the ball in no more than k attempts), but it seems true (assumed, not proved here [*]) that it's equivalent to iteratively (greedily) maximize the probability of finding the ball in the next attempt. Let c_i be the probability of finding the white ball when attempting an ... 1 Suppose that K^{-1} = LL^T is a Cholesky decomposition where L is n \times p. Then we can rewrite$$ Wa = b, \quad WW^T = K \implies\\ Wa = b, \quad (LW)(LW)^T = I \implies\\ (LW)a = (Lb), \quad (LW)(LW)^T = I. $$That is, if we make the substitution M = LW and y = LB, then your problem is equivalent to solving$$ Ma = y, \qquad MM^T = I. $$... 1 p(2m+2) = \left( \frac{1}{4} \right)^m \frac{3}{4}, for m \geq 0. So \operatorname{E}(N) = \sum_{i=0}^{\infty} (2i+2) \left( \frac{1}{4} \right)^m \frac{3}{4} Now, see that \left( \operatorname{E}(N) - 2 \left( \frac{3}{4} \right) \right) \times 4 = \operatorname{E}(N) + \operatorname{E}(2). Your distribution is geometric, so you are just solving ... 2 The set is bounded by 8 planes (assume signs for x,y,z then remove the absolute values, you get 8 equations \pm x\pm y\pm z=1 for the boundaries. These define planes. Now, for each of these planes, you can find 3 points in the set \{(\pm1,0,0),(0,\pm1,0),(0,0,\pm1)\} which belong to the plane. Which polyhedron does that yield? 0 This is the Gauss-Newton algorithm. (See especially the Notes section.) 1 The objective value does change. The optimal basis doesn't have to change, that is the set of independent column doesn't change. Let B be the index for basic variable.$$\min c_B^Tx_BA_Bx_B=bx_B \ge 0$$We have$$x_B = A_B^{-1}b$$and the previous objective value is$$c_B^TA_B^{-1}x_B$$changing c_B would change the cost. If you are ... 0 In order to serve as an introduction to optimal control, we present a formulation as simple as possible, to the interpolation problem. In order to apply this algorithm, adequate discretization of the integral formulation will be necessary. So regarding the interpolation problem$$ \min J = \int_{t_i}^{t_f}\left(1+\frac{1}{2}\rho v^2\right)dt \ \ \text{s. t....

1

You can avoid the derivative by noticing that $$\sin105°={\sqrt2\over2}{1+\sqrt3\over2}, \quad \cos105°={\sqrt2\over2}{1-\sqrt3\over2}$$ and inserting that into your formula gives: $${1\over PQ}+{1\over PR}=(1+\sqrt3)\sin(45°+\alpha).$$ Hence maximum is reached for $\alpha=45°$.

0

There are at least a couple of ways to approximate the bilinear constraint with linear constraints, possibly using some binary variables in the process. I can't think of any way to linearize it exactly.

0

The Euler-Lagrange equation for this problem says that, given the integral $$\int_0^\infty \underbrace{e^{-rt}f(c(t))\,e^{-\left(\int_0^t c(h)\,dh\right)t}}_{=\,L(c,\dot{c};t)}dt,$$ the extremum is given by $$\frac{\partial L}{\partial c}-\frac{d}{dt}\,\frac{\partial L}{\partial \dot{c}}=0.$$ But now $\dot{c}$ does not appear in $L,$ so this simplifies down ...

6

$n=1$ makes no sense, while for $n=2$ the only allowed value is $x=2$. Thus assume $n>2$. Using Descartes' rule of signs on $x^2f'(x)=-8x^3+4(n^2+3)x^2-n^4$ we see that $f'(x)$ has zero or two positive roots. Next, $f'(1) = -n^4+4 n^2+4<0$ while $f'\left(\frac{n^2}{4}\right) = 2 \left(n^2-2\right)>0$, so that $f$ has two positive roots. Since $\... 1 I didn't get around to posting the method I used, but here it is. Problem Minimize$cell\_size$Subject to$f(cell\_size, (n_n)) <= t$Where$f(x, (y_n)) = \prod_{i} {\lceil \frac {y_i} {x} \rceil}x$is a positive number$y$is a sequence of positive numbers$t$is a number, larger than or equal to 1 Solution Without loss of generality, it ... 2 Starting with: $$L(\boldsymbol{\mathcal{x}}, \boldsymbol{\lambda}, \boldsymbol{\alpha}) = f(\boldsymbol{\mathcal{x}}) + \sum_i \lambda_i g^{(i)} (\boldsymbol{\mathcal{x}}) + \sum_j \alpha_j h^{(j)}(\boldsymbol{\mathcal{x}}) \tag{4.14}$$ If the constraints are satisfied, then$g^{(i)}(x)=0$and$h^{(j)}(x)\leq0$. Therefore, the terms with$\lambda\$ all ...

Top 50 recent answers are included