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.
7
votes
3answers
2k views
Gradient Descent with constraints
In order to find the local minima of a scalar function $p(x), x\in \mathbb{R}^3$, I know we can use the gradient descent method:
$$x_{k+1}=x_k-\alpha_k \nabla_xp(x)$$
where $\alpha_k$ is the step size ...
0
votes
2answers
196 views
Essential problem
I want to find one method or approach or idea which compute following statement:
$$
\sup_{t \in [0,1]} \left( \inf_{X \in C^1([0,1])} \left\| \frac{dX(t)}{dt} - A(t)X(t) - F(t) \right\| \right)
$$
...
5
votes
1answer
315 views
Trace minimization with constraints
For positive semi-definite matrices $A,B$, how can I find an $X$ that minimizes $\text{Trace}(AX^TBX$) under 'either' one of these constraints:
a) Sum of squares of Euclidean-distances between pairs ...
3
votes
1answer
197 views
Duality. Is this the correct Dual to this Primal L.P.?
Given a problem:
Find the dual:
$$
Primal =\begin{Bmatrix}
max \ \ \ \ 5x_1 - 6x_2 \\
s.t. \ \ \ \ 2x_1 -x_2 = 1\\
\ \ \ \ \ \ \ \ \ \ \ \ \ \ x_1 +3x_2 \leq9\\
...
10
votes
4answers
2k views
How do Lagrange multipliers work to find the lowest value of a function subject to a constraint?
I have been using Lagrange multipliers in constrained optimization problems, but I don't see how they actually work to simultaneously satisfy the constraint and find the lowest possible value of an ...
8
votes
3answers
2k views
Lagrange Multipliers with Inequality Constraints
I do not have much experience with constrained optimization, but I am hoping that you can help. My current problem involves a more complex function, but the constraints are similar to the ones below. ...
5
votes
6answers
1k views
Linear Programming Books
Do you know of a good book on linear programming? To be more specific, i am taking linear optimization class and my textbook sucks. Teacher is not too involved in this class so can't get too much help ...
5
votes
2answers
953 views
Euler-Lagrange, Gradient Descent, Heat Equation and Image Denoising
For an image denoising problem, the author has a functional $E$ defined
$$E(u) = \iint_\Omega F \;\mathrm d\Omega$$
which he wants to minimize. $F$ is defined as
$$F = \|\nabla u \|^2 = u_x^2 + ...
8
votes
4answers
968 views
Looking to understand the rationale for money denomination
Money is typically denominated in a way that allows for a greedy algorithm when computing a given amount $s$ as a sum of denominations $d_i$ of coins or bills:
$$
s = \sum_{i=1}^k n_i ...
2
votes
1answer
67 views
Cubes, squares and minimal sums
I have trouble solving the following task: i need to find positive integers a and b such that
1) $a \neq b$
2) $ \exists c \in \mathbb{N} : ~ a^2 + b^2 = c^3$
3) $\exists d \in \mathbb{N}: ~ a^3 + ...
1
vote
0answers
146 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
50 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.
8
votes
1answer
197 views
Simple question: the double supremum
Let $f:A\times B\to \mathbb R$. Is it always true that
$$
f^* = \sup\limits_{a\in A,b\in B}f(a,b) = \sup\limits_{a\in A}\sup\limits_{b\in B}f(a,b).
$$
I proved it by the $\varepsilon$-$\delta$ ...
5
votes
1answer
142 views
On minimizing the area of an enclosing surface subject to nonnegative Gaussian curvature
This is inspired by this previous question on physical processes that might give rise to convex hulls.
Consider the problem of gift-wrapping a three-dimensional object using an inextensible material, ...
3
votes
2answers
550 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.
2
votes
1answer
88 views
Simple resource for Lagrangian constrained optimization?
Just had an optimization lecture. I understand unconstrained methods like Newton and Gradient descent just fine, as well as the ideas that give rise to them. I don't really understand the ideas that ...
2
votes
2answers
810 views
Maximizing volume of a rectangular solid, given surface area
Maximize the volume of a rectangular solid, given that the sum of the areas of the six faces is $6a^2$ for a constant $a$.
So basically they tell you it's a rectangle with 6 sides. 2 sides are ...
0
votes
1answer
81 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 ...
6
votes
5answers
1k 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 ...
29
votes
4answers
771 views
AM-GM-HM Triplets
I want to understand what values can be simultaneously attained as the arithmetic (AM), geometric (GM), and harmonic (HM) means of finite sequences of positive real numbers. Precisely, for what points ...
36
votes
1answer
1k views
What's the largest possible volume of a taco, and how do I make one that big?
Let $f$ be a continuous, even, positive 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)$. View the ...
20
votes
5answers
630 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 ...
7
votes
1answer
192 views
Graph theory problem (edge-disjoint matchings)
Find the smallest number $x$ so that if an $n$-vertex simple graph has at least $x$ edges then it contains $k$ pairwise edge-disjoint perfect matchings* ($k$ is a positive integer, $n$ is an even ...
2
votes
3answers
444 views
Calculating the max and min of $\sin(x)+\sin(y)+\sin(z)$
I took the partial derivatives of $\sin(x)+\sin(y)+\sin(z)$ and it didn't work out, so I am trying to use Lagrange's method (with the constraint: $x+y+z=\pi$)... I am not sure how to set this up.
...
11
votes
1answer
219 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 ...
10
votes
5answers
417 views
Why is convexity more important than quasi-convexity in optimization?
In the mathematical optimization literature it is common to distinguish problems according to whether or not they are convex. The reason seems to be that convex problems are guaranteed to have ...
9
votes
4answers
3k 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 ...
7
votes
1answer
210 views
Maximum subset sum of $d$-dimensional vectors
This is a $d$-dimensional generalisation of the post Inequality with Complex Numbers. (See my comment under Robert Israel's answer.)
Generalising Potato's proof for $d$-dimensions, we can show the ...
5
votes
1answer
228 views
Maximizing the volume of a rectangular prism
A rectangular prism has a surface area of $300$ square inches. What whole number dimensions give the prism the greatest volume?
This is a math olympiad problem. It involves the volume and surface ...
10
votes
3answers
960 views
Best fit ellipsoid
Given a collection of points $P \subset \mathbb R^3$, a crude characterization of the "shape" of $P$ is sometimes given by the principal components. We construct a covariance matrix, e.g., if $P$ is ...
7
votes
3answers
356 views
Optimization problem for a parity-check code
I have $n$ data blocks and $k$ parity blocks distributed across $m$ boxes where each box can contain atmost $b$ blocks. Each parity block is Ex-or of some data blocks (for ease of understanding we can ...
4
votes
1answer
61 views
Angular alignment of points on two concentric circles
I have two concentric circles $C_1$ and $C_2$ with radii $r_1,r_2$ such that $r_1< r_2$and a set of finite points $P=\left \{ p_1,p_2...p_n \right \}$ and $Q=\left \{ q_1,q_2...q_n \right \}$ are ...
4
votes
0answers
565 views
Convergence of Gauss-Newton method for piecewise linear functions
Notation for Gauss-Newton method
Non-linear least squares problems are often solved by the Levenberg-Marquardt algorithm, which can be viewed as a Gauss–Newton method using a trust region approach.
...
3
votes
1answer
104 views
Proof that $E_n = \int_0^1 \left| \ln t - P_n(t) \right|\mathrm{d}t = 1/(n+1)^2$
Assume one wants to minimize the distance between $f(x)=\ln x$ and $P_n(t)$ where $P_n$ denotes a polynomial of degree $n$. Etc $P_1 = ax 0+ b$. One way to judge whether the polynomial is a good ...
2
votes
1answer
388 views
Solution Technique to Optimize Sets of Constraint Functions with Objective Function that is Heaviside Step Function
I have the following constraint inequalities and equalities:
$$Ax \leq b$$
$$A_{eq}x = b_{eq}$$
The problem is that the objective function, which I am asked to minimized, is defined as
...
1
vote
2answers
80 views
Max and min value of $7x+8y$ in a given half-plane limited by straight lines?
So, there are four inequalities:
$$\begin{eqnarray*}
y &\geq &-3x+15; \\
y &\leq &-11/3x+56/3; \\
x &\geq &0; \\
y &\geq &0.
\end{eqnarray*}$$
If we draw all those ...
1
vote
2answers
94 views
Find the values of $x$, $y$ and $z$ minimizing $\frac{r^2x}{y+z}+\frac{s^2y}{x+z}+\frac{t^2z}{x+y}$
$$\frac{r^2x}{y+z}+\frac{s^2y}{x+z}+\frac{t^2z}{x+y}$$
$r$, $s$, $t$ are positive coefficients. Find the values of non-negative variables $x$, $y$ and $z$ so that the above expression is a minimum.
14
votes
4answers
534 views
Gerrymandering/Optimization of electoral districts for one particular party
I'm asking this on behalf of Zach Weiner (actually it's my own initiative in order to promote this site). Original text is here, and is as follows:
Hey--
This is Zach from SMBC, and I have a math ...
8
votes
6answers
193 views
Optimization problem (in linear algebra course!)
Let $a_1, a_2, \ldots, a_n$ be real numbers such that $a_1 + \cdots + a_n = 0$ and $a_1^2 + \cdots +a_n^2 = 1$. What is the maximum value of $a_1a_2 + a_2a_3 + \cdots + a_{n - 1}a_n + a_na_1$?
I'd ...
8
votes
1answer
772 views
On problems of coins totaling to a given amount
I don't know the proper terms to type into Google, so please pardon me for asking here first.
While jingling around a few coins, I realized that one nice puzzle might be to figure out which $n$ or so ...
7
votes
2answers
323 views
Generalization of the Sultan's dowry problem
We know the solution of the Sultan's dowry problem:
To reject the first $n/e$ candidates and then to select the first who exceeds the best of the sample.
How to find the best strategy if we want ...
4
votes
2answers
341 views
Generalizing Lagrange multipliers to use the subdifferential?
Background:
This is a followup to this question:
Lagrange multipliers with non-smooth constraints
Lagrange multipliers can be used for constrained optimization problems of the form
$\min_{\vec x} ...
3
votes
2answers
185 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 ...
2
votes
1answer
72 views
Control on Conformal map
Let $\Omega$ be smooth simply connected open set of $\mathbb{R}^2$ such that $\overline{\Omega}$ is compact. We know that there exists a conformal diffeomorphism $\psi$ from $\mathbb{D}$ to $\Omega$. ...
1
vote
0answers
35 views
KKT: Explain visually the optimality condition $F_0\cap G_0\cap H_0=\emptyset$
I am trying to understand visually what this condition actually mean. It is the optimality condition in KKT. It means something like that constraint -set, objective -set and hyperplane -set has no ...
1
vote
2answers
133 views
How can I infer a result using primal feasibility, dual feasibility, and complementary slackness?
I am trying to find the minimum of $-x_1$ with restrictions $\bar g\leq\bar 0$ so that
$$\bar g=\begin{pmatrix}
(x_1+2)^2+(x_2-4)^2-20\\
(x_1+2)^2+x_2^2-20\\
-x_1\end{pmatrix}\leq ...
1
vote
1answer
201 views
Need help with Lagrange Multipliers
I need to maximize $U = BM$ with constraits:
$6B +3M = 60$, $B>0$ and $M>0$.
The Lagrange function is $L=U + \lambda (6B+3M-60) + KB + HM$.
So
$$\partial_{\lambda}L= 6B+3M-60=0$$
...
0
votes
0answers
61 views
Explain $x^*$ of subgradient in KKT -conditions: primal optima or dual optima?
I asked this question here but I noticed that this notation $x^*$ may actually mean two things: primal optimality and dual optimality. Please, explain this notation particularly here: I understand ...
0
votes
1answer
58 views
Explain Complementary Slackness $\mu_i g_i(x^*)=0\forall i$
Wikipedia here explains it like this:
I understand it so that either $\mu_i=0$ or $g_i=0$ but this answer here:
"If μ1≠0 and μ2≠0, then x is one of the two points at the intersection of the two ...
9
votes
2answers
517 views
Augmented Reality Transformation Matrix Optimization
i am a software developer, i'm working on an Augmented Reality system.
I'd like to receive some advice in order to optimize my math model. My program has to be slim and fast.
Here's the situation:
...
