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

What is the largest perimeter of a convex set with given area and radius? [closed]

Just a thing I was pondering: Take a convex shape in the plane with area A, perimeter P, and contained in a closed ball of radius R. My conjecture is: $$P^{3} \leq 108AR$$ With equality achieved if ...
0
votes
0answers
6 views

Given M points and a weighted graph G, map the vertices to distinct points to minimize sum(edge_weight*edge_length)

Given an arbitrary undirected weighted graph G with N vertices, and an arbitrary set of M points P in euclidean 3-space, where M>=N, map the vertices to distinct points such that sum(edge_weight * ...
0
votes
0answers
12 views

Maximize the magnitude of a complex function

Given $$ B(\phi) ~=~ \cos(\phi - \phi_L) + \cos(\phi - \phi_L - \tilde{\phi}) ~e^{j{2\pi}d \left[(\cos\phi - \cos\phi_L )\;+\;(\sin\phi - \sin\phi_L) \right]}, $$ $d > 0$. $\phi_{m} = \arg ...
0
votes
0answers
15 views

Preservation of monotonicity under argmax

Suppose $f(x,y)$ is non-increasing in $y$ for all $x \in X$. Then, can we show that $x^*(y) = argmax_{x \in X}\{f(x,y)\}$ is also non-increasing in $y$? If so, what characteristics should the function ...
0
votes
0answers
13 views

Impact of removing active constraints in convex optimization

In active set methods for non negative least squares, we remove variables from the passive set to active set if the least squares solution gives negative values on those variables. What's the impact ...
1
vote
2answers
162 views

Minimize the minimum - Linear programming

Consider an optimization problem with variables $x_1, x_2, \dots, x_n \in \mathbb{R}$ (maybe subject to some linear constraints), and linear functions $\{f_i(x_1, \dots, x_n)\}_{1\leq i\leq m}$. We ...
1
vote
1answer
14 views

Chebyshev's approximation understanding

I am reading Boyd's book on convex optimization. Could you assisst me in understanding what this expression means: $$\text{minimize} \ \ \text{max}_{i=1,...,k}|a_i^Tx-b_i|$$ This is what I think ...
0
votes
2answers
33 views

Computing operator norm of a matrix

In my notes I have that $\left\|\, \begin{bmatrix}3&1\\1&1\end{bmatrix}\,\right\| = 2+\sqrt{2}$; but I'm struggling to get this. Here's what I have: $$\left\|\, ...
0
votes
1answer
398 views

Maximization with the Dual using the Simplex Method.

I have an exam in a few hours. I need to understand the solution to the following question Find the Maximal to the the following $2 x_1 + 3 x_2$ is the objective function. The constraints are ...
2
votes
2answers
708 views

Optimization: maximum area of a triangle under a parabola

Optimization: maximum area of a triangle in a parabola Inside a curve ($x^2-25$ - Parabola) a triangle is drawn with A as the vertex at the origin and the line joining points B and C lie on the ...
0
votes
0answers
18 views

Semidefinite programming with symmetric matrix constaints

\begin{align} &\arg\min\limits_{0 \le \rho < 1} \rho \\[1ex] s.t.\quad & \begin{bmatrix} 1 - \rho^2 & -\alpha \\ -\alpha & \alpha^2 \end{bmatrix} + \lambda \begin{bmatrix} -2mL ...
0
votes
1answer
16 views

LAD analytical minimization

Is it possible to minimize least absolute deviations analytically? Say given a sample $\{x_i\}_{i=1..n}$ find $$\arg\min_\lambda{\sum_{i=1}^{n}{|x_i-\lambda|}}$$
0
votes
1answer
19 views

Can a network migration problem be solved with linear programming

I'm trying to solve, using linear programming, the problem of determining in which order should network elements by migrated from one place to another. The idea is that resources such as bandwidth ...
1
vote
1answer
32 views

Find the global extrema of $f(x,y)=\sin(xy)$ on $D=[(x,y)| x = [0,\pi], y=[0,1]]$

Find the absolute maximum and absolute minimum of the function: $$f(x,y) = \sin(xy) \text{ on } D=[(x,y)| x = [0,\pi], y=[0,1]]$$ I took the partial derivatives and got: $$\frac{df}{dx} = \cos(xy)y ...
2
votes
1answer
921 views

How to see that K-means objective is convex?

I'm trying to proof that the objective of the K-means clustering algorithm is non-convex. The objective is given as $J(U,Z) = \|X-UZ\|_F^2$, with $X \in\mathbb{R}^{m\times n}, U\in ...
3
votes
1answer
698 views

Maximum likelihood estimators, hypergeometric and binomial

I'm trying to solve a two part problem. The set up is as follows: consider a bag with $\theta$ red marbles and $7-\theta$ blue marbles, with $\theta$ being unknown. Let $x$ denote the number of red ...
0
votes
0answers
13 views

Rosenbrock function matlab

I am new to MATLAB and I am asked to implement on matlab the following algorithm: for an unconstrained minimisation problem. I am asked to apply the BFGS method with armijo line search ...
0
votes
0answers
34 views

Unconstrained minimisation problem Newton's method

min f(x) = $ x_1^4 + 2x_1^2x_2^2 + x_2^4 $ is an unconstrained min problem. The first question asks to show that $(0,0)$ is the unique minimiser. I have done the following.. Would I need to add ...
2
votes
0answers
30 views

characterization of the solution to a generalized eigenvalue problem

Let's say we have the following optimization problem. (All the $\Sigma_{ii}$'s are positive definite.) $\max u^\top \Sigma_{12} v\quad$ $\text{subject to}\quad u^\top \Sigma_{11} u = 1\quad and\quad ...
0
votes
0answers
16 views

Reference request: monotone and strongly monotone with respect to derivatives

Recall, let $H$ be a real Hilbert space. A mapping $F:H \rightarrow H$ is said to be monotone if $$ \langle F(u)-F(v), u-v\rangle\geq 0, \quad \forall u,v\in H; $$ strongly monotone if there exists ...
0
votes
0answers
5 views

Axis-aligned bound constraints and algebraic optimization

What is the methodology for optimizing a function with a interval bounded constraint? I guess the solution has something to do with KKT conditions and linearizing the constraint, but I'm stuck and I ...
1
vote
0answers
27 views

How does one rigorously prove that gradient descent indeed decreases the function in question locally i.e. show $f(x^{(t+1)}) \leq f(x^{(t)})$?

How does one prove that gradient descent indeed decreases the function in question locally? In other words if we take a step in the negative of the gradient as in: $$ x^{(t+1)} = x^{(t)} - \eta ...
2
votes
0answers
20 views

Why polynomial $\psi^\top(t) A^{-1} \psi(t)$ attains maximum on $[-1, 1]$ at $\pm 1$, where $\psi_k(t) = t^k$?

Problem. Let $\psi(t) = (1, t, t^2, \ldots, t^{p-1})$ - a polynomial basis. Suppose there is a matrix $$ A = \int_{-1}^1 \psi(t) \psi^\top(t) dt, \ \text{i.e. } \ A_{ij} = [2 \, | \, i+j] \cdot ...
0
votes
0answers
9 views

Pseudo-Boolean functions restricted to integers

The Pseudo-Boolean functions are of the following form. $$ f : \mathbb{B}^n \to \mathbb{R} $$ I would like to know if there is a special sub-category of $$ f : \mathbb{B}^n \to \mathbb{Z} $$ with ...
1
vote
1answer
25 views

Solve dual of linear program without simplex

I have a linear program and need to determine and solve the dual program. The primal program is $\begin{array}{lcl} \text{Maximize: }\\ f(x) := 6x_1+4x_2\\ \text{Subject to:}\\ -2x_1-4x_2 \leq ...
0
votes
2answers
25 views

Find the point on the ellipse where the cylinder intersects the plane furthest from the origin?

I'm confused about how I should set this problem up. It is a lagrange problem. The cylinder x^2 + y^2 = 1 intersects the plane x + z = 1 in an ellipse. Find the point on the ellipse furthest from ...
1
vote
0answers
30 views

minimize trace(AX) over X with a positive semidefinite X

I want to minimize trace(AX) over X, under the constraint that X is positive semidefinite. I guess the solution should be bounded only for a positive semidefinite A, and it's zero, or the solution ...
1
vote
1answer
14 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
1answer
46 views

Values of parameter $\epsilon \in (0,1)$ that make a rational function decreasing

For $p \in (0,1]$, an integer $n \geq 2$ and $\epsilon \in (0,1)$, I want to show that $$\frac{p (1- \epsilon p)^{n-1}}{1- (1-p)^n}$$ is a decreasing function of $p$ for $\epsilon > g(n)$ for some ...
0
votes
0answers
20 views

Differentiation minimization

This question taken from web based engineering mathematics online test. My answer to this question as below. This system says it is incorrect. Is there any mistake? Plz help.
0
votes
0answers
5 views

Is $f(x)=-3x_1+x_2-x_3^2$ pseudoconvex at $\bar x$?

Is $f(x)=-3x_1+x_2-x_3^2$ pseudoconvex at $\bar x=[-115/588, -95/588, 5/14]^T$? Pseudoconvexity: If $\nabla f(\bar x)^T(x-\bar x)\ge0$, then $f(x)\ge f(\bar x)$ for any $x\in \mathbb{R^3}$ (in this ...
2
votes
3answers
118 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 ...
1
vote
0answers
69 views

What programs or websites solve linear integer or goal programming problems?

I don't think I can use Excel. My solver doesn't work so I can't even use Excel for regular linear programming. Something like this but for integer or goal programming. This seems to allow integer ...
1
vote
1answer
31 views

how to find mininimum $f(x)$ using $\int_{-\infty}^{\infty} f(x)g(x)dx$?

I would like to know the $f(x)$ which minimizes the $\displaystyle\int_{-\infty}^{\infty} f(x)g(x)\,dx$. Actually, this question start from the MMSE (Minimize Mean square error) ...
5
votes
4answers
316 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 ...
0
votes
0answers
24 views

How to form a dual problem in convex optimization (in a broad view)

After reading some papers, this problem confuses me. There are different forms of dual problem to the primal problem: $$\underset{x}\min \ \ f(x)$$ where $f(x)$ is a convex function. By ...
0
votes
2answers
25 views

Maximizing the Nullity of a Symbolic Gram Matrix

I have a symbolic gram matrix, that is, a matrix $AA^T$ with some entries being variables. I would like to find a solution for my variables which maximizes the nullity of this matrix, or equivalently, ...
2
votes
1answer
534 views

Using gradient descent and Newton's method combined

I have this function $f(\mathrm{X})$ where $\mathrm{X=A+B+C}$ where $\mathrm{A}$ is a diagonal element with variable $a$ on its diagonal. $\mathrm{B}$ is another diagonal matrix with variable $b$ on ...
0
votes
0answers
20 views

Travelling salesman - organising a tour of any European destination based on the cheapest flights available.

I apologise if this has only a tenuous link to a mathematics forum I'm sure everyone is familiar with the £10 one-way flights by Ryanair and similar airlines in Europe. I was wondering whether there ...
0
votes
1answer
57 views

the minimum and maximum values of the determinant of order $3\times3$ matrix with entries $\{0,1,2,3\}$

The minimum and maximum values of the determinant of order $3\times3$ matrix with entries $\{0,1,2,3\}$.
0
votes
0answers
12 views

Unbounded variables and dual of a linear program

I have to find the dual of \begin{cases} \max & -x_1 &-2x_2+x_3\\ & -3x_1 &+x_2&\le-1\\ & x_1 &-x_2&\ge 1\\ & -2x_1 &+7x_2&\le6\\ & -5x_1 & ...
0
votes
0answers
26 views

Minimize Energy function

I got the following equation: $$V = \frac{1}{2}x_2(t)^2 + \gamma(x_1(t),x_2(t))x_1(t)$$ Now the goal is to decrease this "energy" function in as little time as possible, as much as possible. ...
0
votes
1answer
28 views

How to determine constant $C$ in $p(x) = Cx^{-D}$?

Given a distribution obeying the power-law (fractal) relation, such as the cumulative distribution function $L_{cf}(> X) = CR^{-D}$, if $X$ is given, how does one find the constant $C$ from a given ...
0
votes
0answers
18 views

Linear integer programming

I am trying to find the optimal solution for the following linear integer programming: \begin{eqnarray} &&\underset{x_i, \forall i} {\text{maximize}} ~ \sum_{i=1}^N x_i a_i \\ && ...
1
vote
2answers
29 views

The number with minimum sum of differences

Let $a_1,a_2,...,a_n\in\mathbb{R}$. I wonder how to find the number $x$ with $$|x-a_1|+...+|x-a_n|=\mbox{min}\{|a-a_1|+...+|a-a_n|\mid a\in\mathbb{R}\},$$ namely the sum of the differences with ...
2
votes
0answers
49 views

Expected number of times a set of 10 integers (selected from 1-100) is selected before all 100 are seen

Suppose I have a set of 100 integers. I randomly choose 10 of those, make a note of which ones I selected, and repeat the process. What is the expected number of times this process must be repeated ...
0
votes
1answer
465 views

Find pressure in a sinusoidal function

Tiffany is a model rocket enthusiast. She has been working on a pressurized rocket filled with laughing gas. According to her design, if the atmospheric pressure exerted on the rocket is less than 10 ...
0
votes
3answers
38 views

Optimization question related to calculus. [closed]

Suppose we have arbitrary real numbers $a,b$. We want to maximize $a^2 + b^2$ subject to $a + b = c$, for some constant $c$. How would one do this?
1
vote
0answers
89 views

Utility maximization of n goods

I have a question that involves finding the optimal demand of $n$ goods for a consumer. However, I haven't anything like this before and I'm not sure how to proceed. The consumer has a utility ...
1
vote
2answers
43 views

Find the Min of P(x,y)

Find the Minimum of the following function : $$P(x,y) = \frac{(x-y)}{(x^4+y^4+6)}.$$ This is a math problem I found in an internet math competition but it is really complex to me !!!