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)

11
votes
5answers
1k 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
1answer
356 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 ...
7
votes
2answers
466 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 ...
6
votes
2answers
362 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 ...
4
votes
1answer
173 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
1k 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. ...
12
votes
3answers
2k 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 ...
5
votes
1answer
2k 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 ...
4
votes
1answer
347 views

Derivation of Euler-Lagrange equation

Here is a simple (probably trivial) step in the derivation of the Euler-Lagrange equation. If we denote $Y(x) = y(x) + \epsilon \eta(x) $, I want to know why is $\dfrac{\partial ...
3
votes
2answers
239 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
110 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.
1
vote
2answers
396 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 ...
14
votes
2answers
929 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 ...
10
votes
1answer
105 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 ...
8
votes
3answers
432 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
731 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 ...
6
votes
3answers
466 views

Newton's method in higher dimensions explained

I'm studying about Newton's method and I get the single dimension case perfectly, but the multidimensional version makes me ask question... In Wikipedia Newton's method in higher dimensions is ...
5
votes
2answers
585 views

Multilinear optimization

Are there any efficient algorithms to solve, multi-linear objective and multi-linear constraint optimization problems? The multilinear functions are sums of bilinear, trilinear (and so on) terms ...
5
votes
1answer
6k views

Degeneracy in Linear Programming

Consider the standard form polyhedron, and assume that the rows of the matrix A are linearly independent. $$ \left \{ x | Ax = b, x \geq 0 \right \} $$ (a) Suppose that two different bases lead to ...
4
votes
2answers
191 views

Least sum of distances

Problem: Let $A, B, C, D$ be points in a $3$-dimensional space. Find the point $X$ that minimizes the sum of the distances $AX+ BX + CX + DX$. Context: During a course, I was assigned a ...
4
votes
1answer
204 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 ...
4
votes
1answer
177 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
3answers
433 views

Optimal symmetric rank-1 approximation

I want to find $\mathbf{x}$ that minimizes $\|A-\mathbf{x}\mathbf{x}'\|^2$ where $\|\cdot\|$ is Frobenius norm. Differentiating with respect to $\mathbf{x}$ and setting to $\mathbf{0}$, I get ...
3
votes
2answers
316 views

Gradient-descent algorithm always converges to the closest local optima?

Assume $f(\vec x)$, which is Lipschitz continuous, has two local optima $\vec x_1^*$ and $\vec x_2^*$( $\vec x_1^*$ is the global minimum). We start the gradient-descent algorithm from $\vec x_0$ and ...
3
votes
1answer
279 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
243 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
88 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
180 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
700 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
713 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
1answer
50 views

Maximisation problem

I am trying the following question: If$$a+b+c+d=0,\;a^2+b^2+c^2+d^2=1$$ Then what is the maximum value of $ab+bc+cd+da?$ By the rearrangement inequality I can get $ab+bc+cd+da\leq 1$ but I am ...
1
vote
1answer
91 views

A problem on positive semi-definite quadratic forms/matrices

Suppose $a+b+c=0$ and (without loss of generality) $a\leq b\leq 0\leq c$, $a^2+b^2+c^2=1$, is the following quadratic form positive semi-definite? Thank you very much. \begin{equation*} \begin{split} ...
1
vote
0answers
51 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 ...
0
votes
1answer
58 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
501 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
133 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 ...
16
votes
4answers
750 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
266 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) = ...
8
votes
6answers
1k 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
593 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
2k 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
4answers
182 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)$$
7
votes
1answer
8k views

How to compute the Pareto Frontier, intuitively speaking?

I'm working on a multi-objective optimization problem and we have 'alternatives' that are quantified on two dimensions - value and cost. Now the question is 'how does one compute a pareto frontier'? ...
6
votes
3answers
126 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
140 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
1answer
54 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 ...
5
votes
2answers
530 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} ...
4
votes
3answers
803 views

Monotonicity of $\ell_p$ norm

Consider a $n$ dimensional space, it is known (Wikipedia) that for $p>r>0$, we have $$ \|x\|_p\leq\|x\|_r\leq n^{(1/r-1/p)}\|x\|_p. $$ I have two questions about the above inequality. $(\bf ...
4
votes
0answers
881 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. ...