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
0answers
198 views

Duality for Support Vector Machines

SVM classifier for two linearly separable classes is based on the following convex optimization problem: \begin{equation*} \frac{1}{2}\sum_{k=1}^{n}w_k^2 \rightarrow \min \end{equation*} ...
0
votes
2answers
95 views

Explain this statement $\bar 0 \in \partial f(x^*)$ where $\partial f(x^*)$ is subgradient

I haven't understood this theorem "$x^*$ is global minimum iff $\bar 0\in \partial f(x^*)$". What does it mean? Visually? P.s. Studying Nonlinear-optimization -course, 2.3139.
10
votes
5answers
793 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
2answers
147 views

Find the minimum value of $A=\frac{2-a^3}{a}+\frac{2-b^3}{b}+\frac{2-c^3}{c}$

Let $a, b$ and $c$ three positive real numbers such that $a+b+c=3$. Find the minimum value of $$A=\frac{2-a^3}{a}+\frac{2-b^3}{b}+\frac{2-c^3}{c}.$$ Here is my attempt. By symmetry we can assume that ...
6
votes
1answer
992 views

Why is Dantzig's solution to the knapsack problem only approximate

For a bunch of items with values $v_i$ and weights $w_i$, and with a total weight $W$ that our bag can carry, how do we achieve maximum total value without breaking the bag? Dantzig proposed that we ...
5
votes
4answers
318 views

How find this maximum $S_{\Delta ABC}$

in $\Delta ABC$,and $\angle ABC=60$,such that $PA=10,PB=6,PC=7$, find the maximum $S_{\Delta ABC}$. My try:let $AB=c,BC=a,AC=b$, then $$b^2=a^2+c^2-2ac\cos{\angle ABC}=a^2+c^2-2ac$$ then ...
4
votes
8answers
4k 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
2answers
2k views

Math notation for location of the maximum

My question is about notation. I have maximum of the function $f(x)$. This can be expressed as $\max(f)$ How can I express in compact form that $x_0$ is the location of that maximum.
3
votes
3answers
1k 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 ...
3
votes
1answer
275 views

Extrema homework — maximizing the viewing angle of a picture on a wall

I have hit a problem in my homework and don't know how to solve it. Here it is: "A picture with height of 1.4 meters hangs on the wall, so that the bottom edge of the picture is 1.8 meters from the ...
3
votes
1answer
98 views

Simple optimization trick

Let $f,g:X\to\Bbb R$ be two functions where $X$ is any set. Then $$ \left|\sup_x f(x) - \sup_x g(x)\right|\leq \sup_x|f(x) - g(x)|. $$ This fact is fairly easy to prove, but it seems to be a ...
3
votes
2answers
2k views

Dimensions of a box of maximum volume inside an ellipsoid

Finding the dimensions of the maximum volume box inside the ellipsoid. I assume that the volume of a box, $V(x,y,z) = xyz$ (they did not give this to me, but this is the volume of a box right?) ...
2
votes
1answer
250 views

Optimisation Problem on Cone

The problem I've got here is to prove that semi vertical angle of a cone with maximum volume with total surface area constant is equal to $arcsin(\frac{1}{3})$ I am trying to do that by making some ...
1
vote
2answers
45 views

If a nonnegative function of $x_1,\dots,x_n$ can be written as $\sum g_k(x_k)$, then the summands can be taken nonnegative

Suppose that $f:\mathbb{R}^n\to [0,\infty)$ is a function that can be written in the form $$f(x_1,\dots,x_n)=g_1(x_1)+g_2(x_2)+\dots+g_n(x_n) $$ Can we also choose all $g_k$ to be nonnegative? ...
1
vote
1answer
76 views

Armijo rule intuition and implementation

I am minimizing a convex function $f(x,y)$ using the steepest descent method: $$\mathbf{x}_{n+1}=\mathbf{x}_n-\gamma \nabla F(\mathbf{x}_n),\ n \ge 0$$ My function is defined over a specific domain ...
1
vote
0answers
92 views

Trace minimization when some matrix is unknown

The problem is as follows: $\displaystyle\min_{V}$ trace($V^TH^T\Phi HV$)$\\$ s.t. $V^TV=I_d$ in the case when $H$ is not known. When $H$ is known, the solution is given by the eigenvectors ...
1
vote
2answers
43 views

Global maxima/minima of $f(x,y,z) = x+y+z$ in $A$

Find the global maxima/minima of $f(x,y,z) = x+y+z$ for points inside of $A = \{ (x,y,z) \in \mathbb{R}^3: x^2-y^2 = 1 \wedge 2x+z = 1 \}$ I renamed the conditions of $A$ to a function $g(x,y,z) ...
1
vote
1answer
126 views

Binomial Coefficient: monotonically decreasing in this range?

relating to this question, I'd like to ask a further one. Again we have $$f(x)={k-1 \choose x-1} p^x (1-p)^{k-x}$$ We know that this term is maximal for $x=kp$, before increasing, afterwards ...
1
vote
3answers
892 views

Ladder Optimization Problem

A fence 4 feet tall runs parallel to a tall building at a distance of 4 feet from the building. What is the length of the shortest ladder that will reach from the ground over the fence to the wall of ...
1
vote
0answers
43 views

Maximizing a given function?

I have a function as below, $f(\alpha) = \frac{{1 - \alpha }}{2}\ln \left( {1 + \frac{{AB}}{{B + \frac{{1 - \alpha }}{{C\alpha }}}}} \right)$, where $A$, $B$, $C$ are constant, and $0 < \alpha ...
1
vote
1answer
58 views

A non-linear optimization problem

I have the following optimization problem on the variables $a_1, ..., a_n$: $$ minimize \frac{\sum_{k=1}^{n}\max(k\cdot a_{k},1)}{\sum_{k=1}^{n}a_{k}} $$ $$ such\ that\ \ 0\leq a_k\leq 1\ \ \ (k=1, ...
1
vote
2answers
284 views

Applying the Lagrangian function to find critical points

So I have the following function $$ f(x,y) = x^2+y^2 $$ subject to $$ g(x,y) = x+y-1 = 0. $$ And I have to use the Lagrangian to find the critical points, and determine wether they are ...
1
vote
1answer
150 views

Find the minimum of this expression

This is a problem in my exam and I can't find the solution using elementary inequality knowledge. Can anyone here help me solve this. Thanks $a,b,c $ are positive real numbers which satisfy ...
0
votes
2answers
69 views

How to place the biggest number of cans in this box

A rectangular box has dimensions of 108 cm x 144 cm for its bottom. I want to place the biggest number of cans of 12 cm of diameter in it. How can I place this biggest number? It couldn't be as ...
0
votes
1answer
59 views

Gordan’s lemma equivalent statement

Let $A$ be an $m × n$ matrix. Recall that Gordan’s lemma states that the system $$\{d : Ad < 0\}$$ is inconsistent if and only if the system $$λ ≥ 0 ∈ R ^m , λ \not= 0, A ^T λ = 0$$ is consistent. ...
0
votes
1answer
93 views

Maximum area for back yard with given length of its fence

I've encountered this question : We have 900 ft of fence and we want to construct a back yard for a 100 ft building. If we are using the building as part of the barrier for the yard, ...
0
votes
1answer
42 views

Convexity of set

If $C\subset\mathbb{R}^m$ is a convex set, $A$ is an $m\times n$-matrix and $b\in\mathbb{R}^m$, how do I prove that the set $S=\{x\in\mathbb{R}^m|Ax+b\in C\}$ is convex? I know that the definition of ...
0
votes
1answer
33 views

How to set up matrix to compute best coefficients

Suppose we're given a non-linear spring with the following relationship between the applied weight ($x$) and displacement ($y$): $y = ax + bx^3$. I've done a sequence of $m$ tests measuring the ...
0
votes
1answer
105 views

How to perform the optimization when gradient is a matrix $\mathbf{R}^{n\times n}$

I am trying to optimize this cost function by using Gauss-Newton method. $$f = \sum_{i = 1}^n Tr{(Z^TZ)}$$ where $Z$ is a $4\times4$ matrix and it is a function of real vector ...
0
votes
2answers
111 views

Constraint minimization of sum of Non-symmetric matrices

I am trying to find closed form solution to following problem \begin{equation} \begin{array}{c} \text{min} \hspace{4mm} \big(\lambda_1\left( \mathbf{y}^T V^{(1)}\mathbf{x} \right)^2 + ...
0
votes
1answer
46 views

Computing $\sup_{\left \| u \right \|=1} d(u,F)$ in a closed subspace of a normed space.

I have come across with the following problem: Let $E$ be a normed space and $F$ a closed subspace of $E$. It's asking to compute $\sup\limits_{\left \| u \right \|=1} d(u,F)$. What I know it's ...
0
votes
1answer
2k views

How to find the speed that minimizes the total cost of a trip?

Here are some facts about semi-trucks and a trip between Chicago and New Orleans. (a) The trip is 750 miles. (b) Running at 50 mph, the truck gets around 4 miles per gallon. (c) For each mph ...
0
votes
1answer
254 views

Finding Shortest distance between a Sphere and Ellipsoid?

Suppose that ,I have a Sphere and an ellipsoid as Sphere: $(x-x_1)^2 + (y-y_1)^2 + (z-z_1)^2 = R_1^2$ Ellipsoid: $\large\frac{(x-x_2)^2}{a^2} + \frac{(y-y_2)^2}{b^2} + \frac{(z-z_2)^2}{c^2} = 1$ ...
0
votes
2answers
60 views

To prove the existing and uniqueness of a solution

Let function $f$ be differentiable and convex in $R^{n}$. How can it be proved that $\forall \lambda > 0$ solution of system equations $f'(x) = -\lambda x$ exists exclusively ($\exists \hspace{3mm} ...
0
votes
1answer
1k views

Calculus Optimization - Finding the minimum cost

In oil pipeline construction, the cost of pipe to go underwater is 60% more than the cost of pipe used in dry-land situations. A pipeline comes to a river that is 1 km wide at point A and must be ...
0
votes
1answer
90 views

How to solve this optimization problem?

Suppose I have the following problem: Maximize: $\quad\quad x_1+x_2+x_3+x_4$ Subject to: $\quad\quad \dfrac{\gamma\;a_1\;x_1}{\gamma\;a_2\;x_4+1}\geq1$, $\quad\quad\quad\quad\;\;\quad\quad ...
0
votes
3answers
655 views

Lagrange multipliers - finding maximum/minimum

I have solved the question, and obtained the critical points, but don't know how to show its a maximum or minimum of a function. I don't understand other answers because symbols confuse me so much and ...
0
votes
1answer
115 views

How to minimize cost of group of items given that weights of item sums up to fixed value and atmost 'n' number of items are allowed?

Given that we have a set of items :- { (c1, w1) , (c2, w2), (c3, w3) , ... } where (ci, wi) are the respective cost and weight of the ith item. Its required to minimize total cost of items C such ...
65
votes
1answer
3k views

What's the largest possible volume of a taco, and how do I make one that big?

Let $f$ be a continuous, even function over some interval $I=[-a,a]$ such that the total arc length of $f$ over $I$ is at least $2$, $f(0)=0$, and $f$ is increasing on $(0,a)$. [You might imagine ...
35
votes
1answer
766 views

A System of Matrix Equations (2 Riccati, 1 Lyapunov)

Setup: Consider the following system of real matrices, \begin{align} {\bf P} &={\bf F}({\bf I}_{n}-{\bf K} {\bf H}^\top){\bf P}{\bf F}^\top+{\bf Q}, \;\;\;\;\;\;\;\;\text{where}\;\;\;\;{\bf ...
25
votes
1answer
626 views

Can Three Equilateral Triangles with Sidelength $s$ Cover A Unit Square?

A previous question on the site asked for a short proof of the fact that three equilateral triangles with unit side length cannot be arranged to cover a square with unit side lengths. Given the truth ...
8
votes
7answers
7k views

Operations research book to start with

for somebody having a quite strong background in Mathematics, which are some good books for the domain of Operations research? I guess there are textbooks covering topics like linear and nonlinear ...
15
votes
4answers
11k views

Do dynamic programming and greedy algorithms solve the same type of problems?

I wonder if dynamic programming and greedy algorithms solve the same type of problems, either accurately or approximately? Specifically, As far as I know, the type of problems that dynamic ...
16
votes
1answer
422 views

Arnol'd's trivium problem #68

I came across this blog that says that its French version has answers to most of Arnol'd's trivium problems, and I figured I'd try my hand at some of the ones they don't have. Number 68 raised my ...
5
votes
1answer
353 views

Conjugate Gradient Method and Sparse Systems

What is it about conjugate gradient that makes it useful for attacking sparse linear systems. Why would steepest descent be significantly worse? Please keep in mind that I am still trying to fully ...
22
votes
5answers
846 views

Math Wizardry - Formula for selecting the best spell

Imagine we have a wizard that knows a few spells. Each spell has 3 attributes: Damage, cooldown time, and a cast time. Cooldown time: the amount of time (t) it takes before being able to cast that ...
18
votes
2answers
724 views

Largest circle between $y=x^n$ and $y=\sqrt[n]{x}$

Something I have been wondering about for a while. Let us look at the area between $x^n$ and $\sqrt[n]{x}$ when $x\in [0,1]$. Where $n$ is a positive integer. Below is an image. With a given n, how ...
17
votes
5answers
368 views

If $A+B+C+D+E = 540^\circ$ what is $\min (\cos A+\cos B+\cos C+\cos D+\cos E)$?

Let each of $A, B, C, D, E$ be an angle that is less than $180^\circ$ and is greater than $0^\circ$. Note that each angle can be neither $0^\circ$ nor $180^\circ$. If $A+B+C+D+E = 540^\circ,$ what is ...
12
votes
3answers
603 views

Formula for picking time closest to (but after) target

Let's say you have an arbitrary length of time. You are playing a game in which you want to push a button during this time span after a light comes on. If you do so, you win ($+1$), if not, you lose ...
12
votes
2answers
8k views

Taking derivative of $L_0$-norm, $L_1$-norm, $L_2$-norm

I am a little confused about taking derivatives w.r.t. the norms. $L_0$-norm: $L_0$ means number of non-zero elements in a vector. Say, I am interested in an $x_i$. ...