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
541 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
176 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
82 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
109 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
545 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
820 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
298 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
233 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
549 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
0answers
285 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
627 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
363 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
0answers
44 views

Online stochastic convex optimization.

I need to find/approximate the argument that minimizes a stochastic convex function $F(\theta, Z)$: $$ {\arg\min_{\theta}} E_{Z}[ F(\theta, Z) ]$$ Where $Z$ is some random variable (we could assume ...
3
votes
2answers
243 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
68 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
64 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
117 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
57 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
163 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
19k 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
393 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
100 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
160 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
698 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
283 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
179 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
2k views

Prove the supremum of the set of affine functions is convex

Let $\langle f_i \rangle _{i \in I}$ be a family of affine functions on a convex and compact set $\Omega \subset \mathbb{R^d}$ such that $f_i = a_i.x +b_i$ for $x \in \Omega$. Prove that f, defined by ...
3
votes
1answer
950 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
76 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
271 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
303 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
90 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
495 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
369 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
319 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
501 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
462 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
319 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 ...
2
votes
4answers
70 views

Is the opposite of the Second Derivative Test also true?

Given the Second Derivative Test, one case says : If $f(x_0)''<0$, then $f$ has a local maximum at $x_0$. Is it also true that, if $f$ has a local maximum at $x_0$, $f(x_0)'' < 0$ ?
2
votes
0answers
150 views

Lagrange multiplier expression

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\\ \text{subject to} & ...
2
votes
1answer
116 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
313 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
2answers
107 views

Minimizing Frobenius norm for two variables

I need to minimize squared Frobenius norm: $\|\mathbf{A} - \mathbf{x}\mathbf{y}^T\|_F^2$. Namely I need to prove that for this norm to reach minimum $\mathbf{x}$ should be eigenvector of ...
2
votes
3answers
346 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
72 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
153 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
3answers
900 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 ...