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)

1
vote
2answers
230 views

How can I infer a result using primal feasibility, dual feasibility, and complementary slackness?

I am trying to find the minimum of $-x_1$ with restrictions $\bar g\leq\bar 0$ so that $$\bar g=\begin{pmatrix} (x_1+2)^2+(x_2-4)^2-20\\ (x_1+2)^2+x_2^2-20\\ -x_1\end{pmatrix}\leq ...
1
vote
1answer
612 views

Need help with Lagrange Multipliers

I need to maximize $U = BM$ with constraits: $6B +3M = 60$, $B>0$ and $M>0$. The Lagrange function is $L=U + \lambda (6B+3M-60) + KB + HM$. So $$\partial_{\lambda}L= 6B+3M-60=0$$ ...
0
votes
4answers
155 views

Maximizing the Magnitude of the Resultant Vector

Given a set of $n$ two-dimensional unit vectors: $\left\{ \mathbf{v}_1, \dots, \mathbf{v}_n \right\}$, I want to find the coefficients $\left\{ \alpha_1, \dots, \alpha_n \right\}$, $0 \leq \alpha_i ...
0
votes
2answers
90 views

Help finding local extrema of $f(x)=\frac{x}{\sqrt{2}}-3\sin\frac{x}{2}$

Find the local extrema of $f(x)=\dfrac{x}{\sqrt{2}}-3\sin\dfrac{x}{2}$ on the interval $0 \leq x \leq 2\pi$ $f^{\prime}=\dfrac{1}{\sqrt{2}}-3\cos \left(\dfrac{x}{2}\right) \left ( ...
0
votes
1answer
115 views

Explain Complementary Slackness $\mu_i g_i(x^*)=0\forall i$

Wikipedia here explains it like this: I understand it so that either $\mu_i=0$ or $g_i=0$ but this answer here: "If μ1≠0 and μ2≠0, then x is one of the two points at the intersection of the two ...
-2
votes
2answers
3k views

Minimum ladder over wall optimization

A fence 6 feet tall runs parallel to a tall building at a distance of 2 feet from the building. We want to find the the length of the shortest ladder that will reach from the ground over the fence to ...
8
votes
5answers
356 views

Are derivatives defined at boundaries?

Given a differentiable function $f : [-5,5] \rightarrow \mathbb{R},$ I was under the impression that the derivative $f'$ has domain $(-5,5).$ However, according to Wikipedia ...a differentiable ...
6
votes
0answers
183 views

Optimization of relative entropy

Wondering if my following question is an application of information theory: Lets say we have a factory and ship boxes of stuff outside. If a competitor stands outside my factory, observes the stream ...
5
votes
1answer
393 views

Optimizing a functional with a differential equation as a constraint

I am working on solving the following optimization problem. I think it is well-poised but, if not, please give me some pointers that could make the question make more sense. We have a parametric ...
5
votes
1answer
356 views

Find extremes of function $f(x,y,z) = x^2y + y^2z + x - z$

I am preparing for an exam tuesday morning and I would like to ask you, if someone could please review my solution for the following excercise. I don't have the correct answer so I am unable to check ...
5
votes
1answer
509 views

Find minimum in a constrained three-variable equation

After my last question I have worked through the math quite a bit and now I'm stuck again. This time my question is less wordy. I have two equations for $t$, one with respect to each $a_{x}$ and ...
4
votes
1answer
119 views

Minimize Frobenius norm with unitary constraint

I am trying to find a unitary tramsformation, $M$, that minimizes $\Vert MA-B \Vert_F^2$ where $A$ and $B$ are $N\times L,\;L\ge N$. I know how to solve it without the unitary constraint. I thought ...
4
votes
2answers
78 views

How do I maximize $|t-e^z|$, for $z\in D$, the unit disk?

I guess this question doesn't have a closed form solution for all $t\in \Bbb C$, but I know one for $t=1$ provided by Daniel Fischer in a question I asked. $$\begin{align} \left\lvert ...
4
votes
1answer
106 views

How find this minimum $\sum_{i=1}^{n}a^2_{i}-2\sum_{i=1}^{n}a_{i}a_{i+1},a_{n+1}=a_{1}$

let $a_{1},a_{2},\cdots,a_{n}\ge 0$,and such $a_{1}+a_{2}+\cdots+a_{n}=1$. Find this follow minimum $$I=a^2_{1}+a^2_{2}+\cdots+a^2_{n}-2a_{1}a_{2}-2a_{2}a_{3}-\cdots-2a_{n-1}a_{n}-2a_{n}a_{1}$$ My ...
4
votes
1answer
133 views

What is the minimal isoperimetric ratio of a polyhedron with $5$ vertices?

I'm asking and answering this question to provide a partial answer to this question and a comment on this answer at MO. The isoperimetric ratio $\mu$ of a solid is the ratio $A^3/V^2$, where $A$ is ...
4
votes
4answers
477 views

Approximate a function over the interval $[0, 1]$ by a polynomial of degree $n$ (or less).

To approximate a function $G$ over the interval $[0,1]$ by a polynomial $P$ of degree $n$ (or less), we minimize the function $f:R^{n+1} \to R$ given by $F(a) = \int_0^1 (G(x) - P_a(x))^2\,dx$, where ...
4
votes
2answers
761 views

Change-making problem - counterexample for greedy algorithm

Let D be set of denominations and m the largest element of D. We say c is counterexample if greedy algorithm is giving answer different from optimal one. I found statement that if for given set ...
4
votes
0answers
295 views

(easier version)What is a working example for finding the maximum of a algebraic function $f(a,b,c,d,e)$ with 4 equality …

edit 2: If you are founding an answer would be interesting to you, please upvote this question, because i may use those point in order to start a new bounty. Edit 3: Can somebody answer? Edit 4:I ...
4
votes
1answer
231 views

Computing the volume of a set efficiently

Given a set of vectors $\mathbf v_i$ for $i=1,\dots,k$, $\mathbf v_i \in \{0,1\}^n$, is that possible to efficiently find the volume of the set, $$\left\{\mathbf x \in [0,1]^n:\mathbf x \le ...
4
votes
1answer
87 views

Is $f(t)=t^\alpha$ for $\alpha\in(0,1)$ a sub-additive function? [duplicate]

Possible Duplicate: Does $|x|^p$ with $0<p<1$ satisfy the triangular inequality on $\mathbb{R}$? Is the function $$f(t)= t^{\alpha},\quad \alpha\in (0,1)$$ a subadditive ...
4
votes
1answer
476 views

Question about the simplex method complexity

So I know that in general the simplex method for linear and convex quadratic programming can require exponential time. But assuming a positive semidefinite quadratic program that is solvable by the ...
4
votes
2answers
1k views

Minimize a matrix function with constraints

Let $A, X\in\mathbb{R}^{n\times n}$. The scalar objective function is $$J=\mathrm{tr}(AX)$$ If no constraints, let the derivative of $J$ with respect to $X$ be zeros, then we have $$A=0$$ Suppose $A$ ...
4
votes
8answers
3k views

Maximizing the sum of two numbers, the sum of whose squares is constant

How could we prove that if the sum of the squares of two numbers is a constant, then the sum of the numbers would have its maximum value when the numbers are equal? This result is also true for ...
4
votes
0answers
261 views

Extremal curve passing through a set of points

I'm having trouble recasting the following question in a form amenable to the calculus of variations. Question: Given a set of $n$ points $P=\{(x_1,y_1),..(x_n,y_n)\}$ what is the curve passing ...
4
votes
1answer
1k views

Dynamic programming - A type of balanced 0-1 matrix

I was reading the Wikipedia article of Dynamic programming, however, I'm having a hard time understanding the explanation given in the example for a type of balanced 0-1 matrix. The problem is stated ...
4
votes
3answers
600 views

Optimally combining samples to estimate averages

Suppose I have two tables, each of unknown size, and I'd like to estimate the average of their true sizes. I hire 2 contractors: one guarantees good precision (i.e., her measurement ...
4
votes
2answers
349 views

Sparsest matrix with specified row and column sums

Given a sequence of row sums $r_1, \ldots, r_m$ and column sums $c_1, \ldots, c_n$, all positive, I'd like to find a matrix $A_{m\times n}$ consistent with the given row and column sums that has the ...
3
votes
2answers
113 views

How to maximize area of two circles inside a rectangle without overlapping?

Two circles have to be drawn inside a rectangle of dimensions $W\times H$ such that the area of both circles is to be as large as possible without overlapping. Let the radii of the circles be $r_1$ ...
3
votes
1answer
55 views

Spacing of fence posts with minimal distance to other fence posts

Definition 1: A "fence" is a set of "fence post positions", where each pair of adjacent positions has the same difference (the spacing), e.g. $\{1,2, 3, 4\}$. A fence is described by three values ...
3
votes
2answers
63 views

Determine the smallest number P

I have here a hard problem, which I couldn't solve. Denote $M$ the set of all functions $f:[0,1]\to\mathbb{R}$ with the following properties: $f(x)\ge0, \forall x$ in $[0,1]$, $f(1)=1$, $f(x+y)\ge ...
3
votes
4answers
79 views

Optimization with a constrained function

Okay so I understand how to find points of extrema when for example, We have $3x^2 + 2y^2 + 6z^2$ subject to the constaint $x+y+z=1$. I followed the method of the Lagrange multiplier and resulted in ...
3
votes
1answer
53 views

Nonconvex set converging to a convex set despite holes

I'm looking at the example in Figure 4-7 of "Variational Analysis" (Rockafellar and Wets). Basically, there's a sequence of sets $C_{\nu}$ riddled with holes, and it states that the sequence ...
3
votes
2answers
111 views

significance of zeros of a transfer function?

In control theory, the poles of a transfer function give information about the stability and behavior of a system. I'm not sure and can't find anywhere what the significance of the zeros of a ...
3
votes
2answers
10k views

Find the maximum or minimum value of the quadratic function.

Find the maximum or minimum value of the quadratic function by completing the squares. Also, state the value of $x$ at which the function is maximum or minimum. $y=2x^2-4x+7$ $x^2$ has a coefficient ...
3
votes
3answers
224 views

Compute the minimum distance between the centre to the curve $xy=4$.

I wish to solve the following problem: Compute the minimum distance between the center to the curve $xy=4$. But I don't know where to start from?
3
votes
1answer
88 views

Effecient way to find optimal solution in a 2 player game

I have a function: \begin{equation*} f(a_1,\ldots,a_7,b_1,\ldots,b_4)=-14-7 a_1+30 a_1 a_2-7 a_4-2 a_4 a_5+21 a_6+21 a_7+16 a_1 b_1-24 a_1 a_2 b_1+6 a_4 b_1-6 a_4 a_5 b_1+6 a_1 b_2-6 a_1 a_2 b_2+8 a_4 ...
3
votes
2answers
144 views

Optimization for constrained problem

I'm reading about Lagrange multipliers from a Pattern recognition book appendix and on one point the following is stated: $\begin{align} ...
3
votes
3answers
555 views

How to find the minimum value of the expression?

Let $x$, $y$, $z$ be three nonegative real numbers and $x^2 + y^2 + z^2 = 5.$ Find the minimum of the expression $$E=\dfrac{1}{2}(x^2 y^2 + y^2 z^2 + z^2 x^2) + \dfrac{96}{x + y + z + 1}.$$ What ...
3
votes
0answers
269 views

Optimizing non linear programs of two variables

The scenario is; We've got $n$ stationary 360$^{\circ}$ sensors in an confined area (each sensor is located at some arbitrary $\left(x,y\right) = \left(x_{n},y_{n}\right)$), once a unit $t$ enters ...
3
votes
2answers
174 views

How many points to find a polynomial?

I would like to fit a formula $ax^b + cx^d+ e$ to a set of points. I have two questions. If my data were perfect, how many points do I need in the worst case to get $a,b,c,d,e$ exactly? If my data ...
3
votes
1answer
776 views

Shortest distance between two shapes

This is the scenario of my problem. I have an image of two objects ( of arbitrary shape, not convex, not touching or crossing each other, kept a few space apart). And I am supposed to find the ...
3
votes
3answers
75 views

Minimize $\| ACE \|$ by geometrical means

I have the following figure Where $AB=10$m, $BD=12$m and $DE=12$m. The point C can slide along the segment BD. Now the problem is to minimize the distance from A to D going along the dashed line. ...
3
votes
1answer
83 views

Maximum of an expression with four variables

Assume $0 < p_1 \le p_2\le p_3 \le p_4$. What is the maximum of the following expression? $$ \frac{\left(p_1+p_4\right)\left(p_2+p_3\right)}{\left(p_1+p_3\right)\left(p_2+p_4\right)} $$ Is that ...
3
votes
1answer
254 views

What is the complexity of computing the minimum distance between two convex polyhedra that both have $n$ faces?

EDIT: (in response to what deinst said) sometimes using a sledgehammer for some menial task is rather convenient - especially if it also has the complexity $O(n)$ (which is what my question is about) ...
3
votes
0answers
273 views

Least Square Method with Positive Parameters

this is my first post here in the Stack Exchange. A friend told me about this forum and I'm giving it a try. I searched a bit past threads, but couldn't find what I wanted, so I'm posting the problem ...
3
votes
2answers
88 views

a plausible maximum or minimum

Is the following statement true? Let $a_1\ge a_2\ge \cdots \ge a_n>0$, $b_1\ge b_2\ge \cdots \ge b_n>0$, then $$\max\limits_{\sigma\in S_n}\;\;\prod\limits_{i=1}^n(a_i+b_{\sigma ...
3
votes
1answer
455 views

Derivative of function including matrix logarithm

Is the following equation a first order approximation or incorrect for general matrix Lie groups? And what are the higher order terms? $$\frac{\partial}{\partial\mathbf x} (\log(\mathtt ...
3
votes
6answers
351 views

Optimizing $a+b+c$ subject to $a^2 + b^2 + c^2 = 27$

If $a,b,c \gt 0$ and $a^2+b^2+c^2=27$, find the maximum and minimum values of $a+b+c$. How to solve this one? (Here's the source of inspiration for the problem.)
3
votes
2answers
291 views

Lagrange multipliers with non-smooth constraints

I read in a textbook a passing comment that Lagrange multipliers are not applicable if there are points of non-differentiability in the constraints (even if the constraints are continuous). For ...
3
votes
2answers
442 views

linear least squares minimizing distance from points to rays - is it possible?

I'm writing a tool whose purpose is to process data from a sensor that provides the true bearing to a target, and combine measurements taken at various times into an estimate of the target's position ...