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)

0
votes
1answer
58 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
2answers
1k views

Solving a set of equations with Newton-Raphson

I want to solve this set of equations with Newton-Raphson. Can anybody help me? $$ \cos(x_1)+\cos(x_2)+\cos(x_3)= \frac{3}{5} $$ $$ \cos(3x_1)+\cos(3x_2)+\cos(3x_3)=0 $$ $$ ...
0
votes
1answer
100 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 ...
54
votes
1answer
2k 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 ...
6
votes
7answers
3k 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 ...
21
votes
5answers
766 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
5answers
332 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
556 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 ...
9
votes
3answers
6k views

Optimum solution to a Linear programming problem

If we have a feasible space for a given LPP (linear programming problem), how is it that its optimum solution lies on one of the corner points of the graphical solution? (I am here concerned only with ...
12
votes
1answer
346 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 ...
12
votes
4answers
6k 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
353 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 ...
4
votes
1answer
155 views

$a,b,c>0,a+b+c=21$ prove that $a+\sqrt{ab} +\sqrt[3]{abc} \leq 28$

$a,b,c>0,a+b+c=21$ prove that $a+\sqrt{ab} +\sqrt[3]{abc} \leq 28$ I have tried to use AM-GM inequality, but get no result as follows: $$a+\sqrt{ab}+\sqrt[3]{abc}\leq ...
2
votes
4answers
917 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. ...
10
votes
5answers
807 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 ...
10
votes
3answers
1k 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
1answer
314 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
2answers
240 views

How to explain lagrange multipliers to a lay audience?

So I will be giving a seminar to a scientifically mature lay audience (think bio/social science undergrad level). I have been told that I should count on less than half the audience to have experience ...
5
votes
1answer
1k 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 ...
3
votes
2answers
102 views

What numerical methods are known to solve $L_1$ regularized quadratic programming problems?

What numerical methods are suitable to solve the following problem $$\min_x \tfrac{1}{2}x^T A x + b^Tx + \lambda ||x||_1$$ where $x,b\in\mathbf{R}^n$, and $A\in \mathbf{R}^{n\times n}$ is positive ...
3
votes
2answers
105 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.
10
votes
1answer
93 views

Using a compass and straightedge, what is the shortest way to divide a line segment into $n$ equal parts?

Sometimes I help my next door neighbor's daughter with her homework. Today she had to trisect a line segment using a compass and straightedge. Admittedly, I had to look this up on the internet, and ...
10
votes
3answers
2k views

What do curly less than sign mean?

I am reading "Convex Optimization" by Stephen Boyd. He is using a curved greater than and curved less than equal to signs. $f(x^*) \succcurlyeq \alpha$ or $f(x*) \preccurlyeq \alpha$ Can someone ...
7
votes
4answers
459 views

Arithmetic mean is less than geometric mean (Spivak Calculus 3rd Chapter 2 Problem 22)

If $a_1, \ldots, a_n \ge 0$, the arithmetic mean $$A_n={a_1 + \cdots + a_n \over n}$$ and the geometric mean $$G_n = \sqrt[n]{a_1 \cdots a_n}$$ satisfy $G_n \le A_n$. As a first step to prove this ...
7
votes
3answers
416 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 ...
7
votes
3answers
625 views

Decomposing a discrete signal into a sum of rectangle functions

Hello math@stackexchange community ! I have a simple question that seems to have a non trivial answer. Given a discrete one dimensional signal $w(x)$ defined in a finite range, and the boxcar ...
4
votes
1answer
145 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 ...
3
votes
1answer
111 views

How to calculate lim inf and lim sup for given sequence of sets

Let the indicator function be defined as $$I(x) \triangleq \begin{cases} 1, & \quad x \geq 0 \\ 0, & \quad x < 0 \end{cases}$$ and $I_{\nu}(x) \in [0,1]$ be a continuous approximation of ...
3
votes
2answers
126 views

find maximum area

Consider a problem here : There is a wall in your backyard. It is so long that you can’t see its endpoints. You want to build a fence of length L such that the area enclosed between the wall and the ...
3
votes
0answers
80 views

Convergence of sequences of sets

Assume we have the indicator function $$I(x) \triangleq \begin{cases} 1, & \quad x \geq 0 \\ 0, & \quad x < 0 \end{cases}$$ and the sequence of its approximation functions $\{ I_{\nu}(x) ...
3
votes
1answer
155 views

Finding the extrema of $E(\vec{r})=\frac1a x^2+\frac1b y^2+ \frac1c z^2$ with respect to constraints geometrically

I have a function, $$E(\vec{r})=\frac1a x^2+\frac1b y^2+ \frac1c z^2.$$ Where $\vec{r}=(x,y,z)$ and $a>b>c>0$. I wish to find the maximum and minimum of this function with respect to the ...
3
votes
1answer
115 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
479 views

When $\min \max = \max \min$?

Let $X \subset \mathbb{R}^n$ and $Y \subset \mathbb{R}^m$ be compact sets. Consider a continuous function $f : X \times Y \rightarrow \mathbb{R}$. Say under which condition we have $$ \min_{x \in ...
2
votes
1answer
581 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
0answers
45 views

Sequence of solutions of approximated problem converging to stationary solution of the original problem

Let $I(x)$ be the indicator function defined as $$I(x) \triangleq \begin{cases} 1, & x \geq 0 \\ 0, & x < 0 \end{cases}$$ and let $L(x,\alpha) \in [0,1]$ be a smoothing function that ...
1
vote
2answers
216 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 ...
0
votes
1answer
56 views

Find minimal $\alpha_3$ such that $u\in H^3(\Omega)$ and $u(x,y,z)=x^\alpha(1-x)y(1-y)z(1-z)$

My instructor presented me the quiz below but forgot to define key terms such as minimality and $H^3$. Quiz Let $u(x,y,z)=x^\alpha(1-x)y(1-y)z(1-z)$. Find the minimal $\alpha_3$ such that $u\in ...
0
votes
2answers
407 views

How to prove equality from poincare inequality?

Let $$D = \{y \in C^1(0,1) : y(0) = y(1) = 0\}$$ Suppose there exists a $C_0$ such that $$\int_{0}^{1} y^2 \ dx \leq C_0 \int_{0}^{1} (y')^2 \ dx$$ for all $y \in D$, and for all $C < C_0$ ...
0
votes
1answer
126 views

Optimizing $x^2+y^2$ from two given equations? [duplicate]

What is the maximum value of $x^2+y^2$, where $(x,y)$ are solutions to: $$2x^2+5xy+3y^2=2$$ and $$6x^2+8xy+4y^2=3$$ Note: Calculus is not allowed. I tried everything I could but whenever I got for ...
15
votes
4answers
643 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 ...
14
votes
1answer
252 views

Fastest curve from $p_0$ to $p_1$

I'm trying to solve a problem in path planning: Given points $p_0$ and $p_1$ and vectors $v_0$ and $v_1$, find a function $p(t)$ st. $p(0) = p_0$, $p(T) = p_1$, $p'(0) = v_0$ and $p'(T) = ...
14
votes
2answers
720 views

Maximum total distance between points on a sphere

What is the configuration (set of locations) of $n$ points on the surface of a sphere such that the sum of distances is maximum for $n=1,2,3,...$? The sum of distances is measured by summing the ...
8
votes
6answers
645 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
2answers
460 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 ...
8
votes
1answer
1k 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 ...
6
votes
1answer
782 views

Why are additional constraint and penalty term equivalent in ridge regression?

Tikhonov regularization (or ridge regression) adds a constraint that $\|\beta\|^2$, the $L^2$-norm of the parameter vector, is not greater than a given value (say $c$). Equivalently, it may solve ...
5
votes
1answer
95 views

dual problem of a Semidefinite programming in a non-standard forme

I have a problem with calculating the dual problem of : $$ \mbox{Minimize } tr(Y) + \frac{1}{\eta} tr(Z) $$ $$ \begin{pmatrix} Y & X \\ X & Z+\varepsilon I \end{pmatrix} \succeq 0 ...
5
votes
4answers
171 views

Finding minimum $\frac{x+y}{z}+\frac{x+z}{y}+\frac{y+z}{x}$

I would appreciate if somebody could help me with the following problem Q. Finding maximum minimum $$\frac{x+y}{z}+\frac{x+z}{y}+\frac{y+z}{x}(\text{where} ~~x,y,z>0)$$
5
votes
3answers
116 views

Determine the minimum of $a^2 + b^2$ if $a,b\in\mathbb{R}$ are such that $x^4 + ax^3 + bx^2 + ax + 1 = 0$ has at least one real solution

I just wanted the solution, a hint or a start to the following question. Determine the minimum of $a^2 + b^2$ if $a$ and $b$ are real numbers for which the equation $$x^4 + ax^3 + bx^2 + ax + 1 = 0$$ ...
5
votes
1answer
50 views

Fundamental Optimization question consisting of two parts.

A) Find all extrema of $$f(x)=\sum_{k=1}^{n} x_{k}^{2} $$ subject to the constraint $\sum_{k=1}^{n}\vert x_k\vert^p=1$ B) prove that $$\frac{1}{n^{(2-p)/(2p)}}(\sum \vert x_k\vert^p)^{(1/p)}\le (\sum ...