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)

5
votes
1answer
347 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
343 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
498 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 ...
5
votes
0answers
173 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 ...
4
votes
1answer
110 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
74 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
105 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
4answers
459 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
711 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
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
2k 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
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
595 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
341 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
1answer
60 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
47 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
62 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
72 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
49 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
88 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
5k 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
157 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
86 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
141 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
494 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
266 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
171 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
736 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
252 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
262 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
82 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
442 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 ...
3
votes
1answer
443 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
338 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
426 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 ...
3
votes
1answer
369 views

Construct dual network for conversion of min-cut problem to shortest path problem

I was wondering if there is some typo in the following description from Section 8.4 p263 of Network Flows: Theory, Algorithms, and Applications by Ravindra K. Ahuja, Thomas L. Magnanti, and James B. ...
3
votes
1answer
293 views

Classifying singular points as local min, max or saddle points

I want to determine if a singular point is a local min, max or saddle point. We are dealing with singular points so we cannot use the hessian matrix. What I have written, and I think I must of missed ...
3
votes
0answers
254 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 ...
2
votes
1answer
107 views

Clarification on optimization problem, continued

Background This is a follow-up to this question. The problem statement is the same: Maximize $$f(\alpha_1, \dots, \alpha_5) = \sum_{1 \le i < j < k \le 5} \alpha_i \alpha_j \alpha_k$$ ...
2
votes
2answers
93 views

How to maximize an entropy function?

I'm very novice in optimization and have a convex optimization function of form $\sum_{i,k} p_{k,i}*\log{p_{k,i}} $ to minimize with the following constraints: $\forall i, a_i = \sum_{k=1}^{m} b_k. ...
2
votes
1answer
172 views

$f$ is convex function iff Hessian matrix is nonnegative-definite.

Let $f: \mathbb{R}^2 \rightarrow \mathbb{R}$, $f \in C^2$. Show that $f$ is convex function iff Hessian matrix is nonnegative-definite. $f(x,y)$ is convex if $f( \lambda x + (1-\lambda )y) \le ...
2
votes
3answers
181 views

Max perimeter of triangle inscribed in a circle

What is the maximum perimeter of a triangle inscibed in a circle of radius $1$? I can't seem to find a proper equation to calculate the derivative.
2
votes
1answer
68 views

How to maximize $\left({a+b \choose a} 2^{-a-b}\right)$?

How can you maximize $\left({a+b \choose a} 2^{-a-b}\right)$ assuming, $a,b \geq 0$ and $0< (a+b) \leq n$, where all the variables are non-negative integers? Is the maximum when $a=b=n/2$, ...
2
votes
1answer
137 views

Previous table of simplex algorithm

I have this problem of simplex method which shows cycle . Problem : Maximize $Z=10x_1-57x_2-9x_3-24x_4$ Constraint to : $ 0.5x_1-5.5x_2-2.5x_3+9x_4<=0 $, $ ...
2
votes
2answers
462 views

Proving the regular n-gon maximizes area for fixed perimeter.

It is often assumed that, given $n$, the regular $n$-gon will make the most efficient use of perimeter for area. I have never seen this proven. Anyone have something slick? (That is, how can we ...