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)

4
votes
1answer
95 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
3answers
3k views

Prove $ax - x\log(x)$ is convex?

How do you prove a function like $ax - x\log(x)$ is convex? The definition doesn't seem to work easily due to the non-linearity of the log function. Any ideas?
4
votes
1answer
242 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 \sum_{i=1}...
4
votes
1answer
300 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
1answer
76 views

What exactly are the curves that are a best fit to the Harmonic Cantilever?

Let's start with a few references to get an idea: Daniel Goldwater: Harmonic Cantilever Book Stacking Problem Block-stacking problem Harmonic Series and Bricks Interesting related issues: Maximum ...
4
votes
0answers
320 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 ...
4
votes
1answer
116 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 ...
3
votes
2answers
485 views

How to maximize (baking) surface area?

I like eating crust, so I am trying different baking molds to try to get the most crust per dough. More generally, I'm interested in the reverse of this more specific question — how to maximize the ...
3
votes
5answers
441 views

How to minimize $\| y- Ax\|$ subject to $\|x\|=1$ and $x \geq 0$?

Given $y \in \mathbb R^n$ and $A \in \mathbb R^{n \times n}$, whis is some way for $$\min_x \| y- Ax\|$$ subject to $\|x\|=1$, and $x \geq 0$ (which means every components of $x$ is nonnegative)? ...
3
votes
3answers
656 views

The Weierstrass Approximation Theorem Vs The Runge's Phenomenon

I am learning about different interpolation methods in my internship. Today as I was looking this article on Wikipedia to learn about the Runge's Phenomenon exhibited by Polynomial Interpolation. I ...
3
votes
1answer
65 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
260 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 $\mathbf{A}\...
3
votes
1answer
117 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
87 views

If a continuous function has one relative extremum, then it is actually an absolute extremum

The following statement makes sense intuitively, but is there a way to prove it mathematically? (This is something we make use of in applied optimization in calculus.) If $f$ is continuous on an ...
3
votes
2answers
595 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
348 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
2answers
29k 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
389 views

A primitive function of $ e^{x^{2}} $

I made some efforts to set a closed form of primitive function of $ e^{x^{2}} $ i find this function : $ f(x)=\frac{x}{2x^{2}-1}e^{x^{2}} $ where : $f'(x)=(\frac{x}{2x^{2}-1}e^{x^{2}})'$= $\frac{...
3
votes
2answers
405 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
1answer
597 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 A\cdot\exp(\...
3
votes
1answer
608 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
0answers
345 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
1answer
169 views

Minimizing the cost of a path in a dynamic system

So suppose I want a path from 0 to $c>0$ on the real line, and I am going to use the function $S(t)$ to get there in (discrete) time $T$. That is, my position at time 0 is 0, my position at time $T$ ...
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
1k 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
2answers
536 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
3answers
1k 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
1answer
82 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$, ...
3
votes
1answer
207 views

binary quadratic optimization problem

I am trying to solve the following binary quadratic program. $$ \min_{\Delta} \Delta^T H \Delta + c^T\Delta \\ \text{Such that:} ~~~\Delta\in \{0,1\}^n ~~\text{and}~~ \sum_{i=1}^n \Delta_i \leq \Gamma ...
3
votes
3answers
904 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
4answers
164 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
2answers
188 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
6answers
417 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
1answer
310 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) ...
2
votes
0answers
165 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} & \theta^...
2
votes
3answers
125 views

Finding the range of a $y=-x^2(x+5)(x-3)$ without calculus?

I was helping a precalculus student with this question. The graph wasn't given. My only idea was to find the inverse and try to find its domain. When trying to find the inverse, I arrived at $0=y^4+2y^...
2
votes
1answer
140 views

Formulating an LP problem with vectors

We have $m$ vectors $v_1,v_2,\dots,v_m\in\mathbb{R}^n$ and $m$ numbers $t_1,t_2,\dots,t_m\in\mathbb{R}$ and we want to find a vector $y\in\mathbb{R}^n$ such that $$|v_i^Ty-t_i|\leq D$$ for $i=1,\...
2
votes
0answers
29 views

Optimization by Symmetry?

Let $$f(x,y,a,b) := \frac{xa+yb}{\sqrt{xa^2+yb^2}},$$ where $x,y,a,b$ are all positive. Define $$g(a,b) = \min_{x+y=1,\,x,y\ge 0}f(x,y,a,b).$$ How would one solve for $g(a,b)$? I have solved this by ...
2
votes
1answer
263 views

Dual residual for linearized ADMM

I am using linearized ADMM for a problem with a (non-smooth) convex loss function $f(x)$, and a hard constraint $x \in E$, where $E$ is an ellipsoid in $R^d$. I have encoded the hard constraint as $A ...
2
votes
2answers
39 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$ ...
2
votes
1answer
112 views

What's wrong in this dual derivation?

I have a function in the form \begin{align} f(q,M)=\sup_{0\leq \alpha \leq 1} -\alpha^T (R\odot M)\alpha+\alpha^Tq \end{align} which is a dual of a minimization problem, where $R$ and $M$ are ...
2
votes
1answer
48 views

Algebraic Riccati equation (DARE) stabilazability condition

I'm Trying to help in this question which involves Algebraic Ricatti equation. Honestly to say I never met this equation before. I'm struggling to understand the conditions stated in the limitations ...
2
votes
2answers
730 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
268 views

Proof of Non-Convexity

Am looking for a proof of non-convexity of the quotient of two matrix trace functions as given by $\frac{\operatorname{Tr}X^TAX}{\operatorname{Tr}X^TBX}$, when $TrX^TBX>0$ for two different ...
2
votes
1answer
316 views

Voronoi diagram with different metric functions

Given a metric space $(X,d)$ and finite number of points $(x_i)_{i=1}^n$ the Voronoi diagram (or the Dirichlet cell) $C_i$ is given by $$ C_i = \{x\in X:d(x,x_i)<\min\limits_{j\neq i}d(x,x_j)\}. $...
2
votes
1answer
258 views

Extrema of $f:\mathbb{R}^n\rightarrow \mathbb{R}$

My question is about finding the extrema of a multidimensional function, $f:\mathbb{R}^n\rightarrow \mathbb{R}$. From lecture I know that $H_f(x_0) < 0 $ implies a isolated maximum $H_f(x_0) &...
2
votes
1answer
120 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
118 views

Discrete optimization

I'm having troubles with searching for analytical solution of following problem. Let we work in 3-D space and have the set of points (uniform net at cube's facets): ($-1,\hspace{2mm} -1+j*h,\hspace{...
2
votes
1answer
788 views

How would you solve a Tikhonov Regularized Least Squares problem with nonnegative constraints?

For a Tikhonov Regularized Least Squares problem with nonnegative constraints, what are some methods that solve it? Are methods solving a Least Squares problem with nonnegative constraints and the ...
2
votes
4answers
10k views

Max distance between a line and a parabola

I am suppose to use calculus to find the max vertical distance between the line $y = x + 2$ and the parabola $y = x^2$ on the interval $x$ greater then or equal to $-1$ and less then or equal to $2$. ...