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)

3
votes
3answers
888 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
595 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
2answers
475 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
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
6answers
414 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
587 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
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
254 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
4answers
161 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
393 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
116 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
0answers
341 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
85 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
1answer
179 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
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
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
1answer
81 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
307 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
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
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 ...
2
votes
1answer
257 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
0answers
28 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
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
1answer
477 views

Is this functional weakly lower semicontinuous?

Define $F\colon L^2([0,1]) \to {\mathbb R}$ by $$ F(R) = \int_0^1 \int_0^1 R(t) R(t') \exp\left(-|t-t'| - \left|\int_t^{t'} R(s)\,ds\right|\right) \,dt\,dt'.$$ Is $F$ weakly lower semicontinous, that ...
2
votes
1answer
111 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
137 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
2answers
7k views

Calculus “Word Problem”

Here is the problem: A rectangle has its base on the x-axis and its upper two vertices on the parabola y=12-x^2 What is the largest area the rectangle can have, and what are its dimensions? Well, I ...
2
votes
2answers
215 views

distance between lines in the space (with calculus)

If I have two lines $$ \eqalign{ & L_1 \left( t \right):p_1 + td_1 \cr & L_2 \left( q \right):p_2 + qd_2 \cr} $$ living in $\mathbb{R}^n$, there exists a classical formula to ...
2
votes
1answer
307 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
266 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
39 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
1answer
247 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
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
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$. ...
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
4answers
181 views

Dual of a Linear Program

\begin{align} \min_{x} c^Tx \\ s.t.~Ax=b \end{align} Note that here $x$ is unrestricted. I need to prove that the dual of this program is given by \begin{align} \max_{\lambda} \lambda^Tb \\ s.t.~\...
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
417 views

Minimize $\|Ax-b\|$ where $x$ is a binary vector

For a software project I'm involved on, I have a situation where I have a large vector that is the sum of some smaller vectors. I know all the possible small vectors, and I know that no two of them ...
2
votes
1answer
97 views

Minimum of $f(x,y)=|ax-by|$.

What is the minimum of function \begin{align} f(x,y)=|ax-by| \end{align} subject to constrains \begin{align} 0 \le x \le C_1\\ 0 \le y \le C_2 \end{align} I found a similar question here Minimum of $|...
2
votes
3answers
214 views

Lagrange method with inequality constraints

Please can someone help me with the follwoing optimisation: Minimize $-x+y$ subject to $0 \leq x \leq a$ and $0 \leq y \leq 1$ and $x^2 \leq y$. I am not sure how to deal with inequality constraints....
2
votes
2answers
85 views

Minimum of $\prod_{1\le i\le n} (1+a_i)$ when $a_1a_2\cdots a_k = M.$

I asked a question here, and also got its generalization:(see tc1729's answer) $$\prod_{1\le i\le n} (1+a_i)\ge 2^{n}\sqrt{a_1a_2\cdots a_n}=2^n\cdot\sqrt M,$$for$$a_1a_2\cdots a_k = M.$$ But I ...
2
votes
2answers
701 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
81 views

Minimisation of a distance sum

I have a list $L$ of $N$ numbers, and I want to choose $k$ numbers $\{x_1,x_2, \ldots,x_k\} \subseteq L$ in such a way value $S$ of the those K numbers is minimum. $$ S = \sum_{0< i < j <= k} ...
2
votes
2answers
221 views

Simultaneous Maximization and Minimization

I have a function with two variables say $$g(x,y)=f(x)−h(x,y)\ $$ where $$f(x)= ax-bx^2\ $$ and $$h(x,y)=(x+y)^2\ $$ and $$ y\ge0, x+y\ge0.$$ My purpose is to maximize $g(x,y)$ for $x$, ...
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
1answer
79 views

Optimization of parallelepiped inside an ellipsoid

Let $K \in R^3$ the ellipsoid given by the equation $ \frac{x^2}{a^2} + \frac{y^2}{b^2} + \frac{z^2}{c^2} = 1 $ with $a,b,c > 0$ , let $(x,y,z) \in K$ on the first octant, consider the ...
2
votes
5answers
437 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)? ...
1
vote
1answer
60 views

Maximization of a ratio

Edit: Removed solved in title, because I realize I need someone to check my work. Ok, so the problem is a lot more straight forward than I originally approached it (which was a false statement -- so ...
1
vote
2answers
402 views

Value minimizing mean absolute percentage error

What value for $c$ would minimize the formula: $$\frac{1}{n}\;\sum^{n}_{i=1}\left | \frac{y_i-c}{y_i}\right|$$ given the values $y_1, ..., y_n$. For example in the mean squared error we have the ...
1
vote
2answers
663 views

Sign restriction on the Lagrange multiplier? Why?

Say we are given a linear program where the goal is to minimize $c^Tx$ with the constraints $Ax\ge b$. Why is there a sign restriction on the Lagrange multiplier associated with the active constraints ...