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)

3
votes
1answer
399 views

Construct dual network for conversion of min-cut problem to shortest path problem

I was wondering if there is some typo in the following description from Section 8.4 p263 of Network Flows: Theory, Algorithms, and Applications by Ravindra K. Ahuja, Thomas L. Magnanti, and James B. ...
3
votes
1answer
303 views

Classifying singular points as local min, max or saddle points

I want to determine if a singular point is a local min, max or saddle point. We are dealing with singular points so we cannot use the hessian matrix. What I have written, and I think I must of missed ...
2
votes
1answer
110 views

Clarification on optimization problem, continued

Background This is a follow-up to this question. The problem statement is the same: Maximize $$f(\alpha_1, \dots, \alpha_5) = \sum_{1 \le i < j < k \le 5} \alpha_i \alpha_j \alpha_k$$ ...
2
votes
2answers
122 views

How to maximize an entropy function?

I'm very novice in optimization and have a convex optimization function of form $\sum_{i,k} p_{k,i}*\log{p_{k,i}} $ to minimize with the following constraints: $\forall i, a_i = \sum_{k=1}^{m} b_k. ...
2
votes
1answer
418 views

$f$ is convex function iff Hessian matrix is nonnegative-definite.

Let $f: \mathbb{R}^2 \rightarrow \mathbb{R}$, $f \in C^2$. Show that $f$ is convex function iff Hessian matrix is nonnegative-definite. $f(x,y)$ is convex if $f( \lambda x + (1-\lambda )y) \le ...
2
votes
3answers
212 views

Max perimeter of triangle inscribed in a circle

What is the maximum perimeter of a triangle inscibed in a circle of radius $1$? I can't seem to find a proper equation to calculate the derivative.
2
votes
1answer
68 views

How to maximize $\left({a+b \choose a} 2^{-a-b}\right)$?

How can you maximize $\left({a+b \choose a} 2^{-a-b}\right)$ assuming, $a,b \geq 0$ and $0< (a+b) \leq n$, where all the variables are non-negative integers? Is the maximum when $a=b=n/2$, ...
2
votes
1answer
142 views

Previous table of simplex algorithm

I have this problem of simplex method which shows cycle . Problem : Maximize $Z=10x_1-57x_2-9x_3-24x_4$ Constraint to : $ 0.5x_1-5.5x_2-2.5x_3+9x_4<=0 $, $ ...
2
votes
2answers
524 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 ...
2
votes
2answers
77 views

Minimum of $\prod_{1\le i\le n} (1+a_i)$ when $a_1a_2\cdots a_k = M.$

I asked a question here, and also got its generalization:(see tc1729's answer) $$\prod_{1\le i\le n} (1+a_i)\ge 2^{n}\sqrt{a_1a_2\cdots a_n}=2^n\cdot\sqrt M,$$for$$a_1a_2\cdots a_k = M.$$ But I ...
2
votes
2answers
74 views

Minimisation of a distance sum

I have a list $L$ of $N$ numbers, and I want to choose $k$ numbers $\{x_1,x_2, \ldots,x_k\} \subseteq L$ in such a way value $S$ of the those K numbers is minimum. $$ S = \sum_{0< i < j <= k} ...
2
votes
1answer
219 views

Minimize $\|Ax-b\|$ where $x$ is a binary vector

For a software project I'm involved on, I have a situation where I have a large vector that is the sum of some smaller vectors. I know all the possible small vectors, and I know that no two of them ...
2
votes
1answer
1k views

Classic optimization - fence problem

I'm taking a class in the fall and need to dust off my $10$-year-old calculus skills, particularly optimization. I'm attempting to remember how to tackle the classic fence problem, i.e. how to ...
2
votes
1answer
81 views

Use of low rank approximation of a matrix

I am trying to figure out why do we need a low rank approximation of a matrix. Why is it used and where? Any insights?
2
votes
1answer
665 views

Algorithm to find optimal cuts of pipe

I have varying lengths of pipe in inventory. When a customer requests various lengths I want to find the optimal way of cutting what I have in inventory. I need to make a program that does this. This ...
2
votes
5answers
327 views

How to minimize $\| y- Ax\|$ subject to $\|x\|=1$ and $x \geq 0$?

Given $y \in \mathbb R^n$ and $A \in \mathbb R^{n \times n}$, whis is some way for $$\min_x \| y- Ax\|$$ subject to $\|x\|=1$, and $x \geq 0$ (which means every components of $x$ is nonnegative)? ...
2
votes
1answer
1k views

Prove the supremum of the set of affine functions is convex

Let $\langle f_i \rangle _{i \in I}$ be a family of affine functions on a convex and compact set $\Omega \subset \mathbb{R^d}$ such that $f_i = a_i.x +b_i$ for $x \in \Omega$. Prove that f, defined by ...
2
votes
3answers
6k views

Optimization of the Area of a rectangle with regards to an Ellipse

The actual problem reads: Find the area of the largest rectangle that can be inscribed in the ellipse $$\frac{x^2}{a^2} + \frac{y^2}{b^2} = 1$$ I got as far as coming up with the equation for the ...
2
votes
2answers
110 views

Discrete optimization

I'm having troubles with searching for analytical solution of following problem. Let we work in 3-D space and have the set of points (uniform net at cube's facets): ($-1,\hspace{2mm} ...
2
votes
1answer
223 views

Proof of Non-Convexity

Am looking for a proof of non-convexity of the quotient of two matrix trace functions as given by $\frac{\operatorname{Tr}X^TAX}{\operatorname{Tr}X^TBX}$, when $TrX^TBX>0$ for two different ...
2
votes
1answer
388 views

Is this functional weakly lower semicontinuous?

Define $F\colon L^2([0,1]) \to {\mathbb R}$ by $$ F(R) = \int_0^1 \int_0^1 R(t) R(t') \exp\left(-|t-t'| - \left|\int_t^{t'} R(s)\,ds\right|\right) \,dt\,dt'.$$ Is $F$ weakly lower semicontinous, that ...
2
votes
1answer
253 views

Extrema of $f:\mathbb{R}^n\rightarrow \mathbb{R}$

My question is about finding the extrema of a multidimensional function, $f:\mathbb{R}^n\rightarrow \mathbb{R}$. From lecture I know that $H_f(x_0) < 0 $ implies a isolated maximum $H_f(x_0) ...
2
votes
1answer
156 views

Minimizing the cost of a path in a dynamic system

So suppose I want a path from 0 to $c>0$ on the real line, and I am going to use the function $S(t)$ to get there in (discrete) time $T$. That is, my position at time 0 is 0, my position at time $T$ ...
1
vote
1answer
47 views

Maximization of a ratio

Edit: Removed solved in title, because I realize I need someone to check my work. Ok, so the problem is a lot more straight forward than I originally approached it (which was a false statement -- so ...
1
vote
0answers
45 views

Is there any way to transform a non-convex optimization problem into a convex one?

I have an optimization problem which is described as $$\begin{array}{ll} \text{minimize}_x & c^{T}x\\ \text{subject to} & Gx \preceq h\\ & -x^{T}Px - qx - r \leq 0 \end{array} $$ where ...
1
vote
0answers
32 views

Finding the widest angle to shoot a soccer ball from the sideline using optimization!! [duplicate]

I'm trying to do an independent project for my Math class, but I was stuck and couldn't figure out how to use optimization to find position along the sideline that gives the widest angle to shoot. ...
1
vote
1answer
48 views

Confounding Lagrange multiplier problem

Optimize $f(x,y,z) = 4x^2 + 3y^2 + 5z^2$ over $g(x,y,z) = xy + 2yz + 3xz = 6$ According to the theorem the gradients must be parallell, $\nabla f = \lambda \nabla g$, so their cross product must ...
1
vote
1answer
230 views

Find the ellipse inscribed in a triangle having the maximum area

If we have a triangle of sides $a,b,c$, there are infinite ellipsis inscribed in the triangle. How can I find that having the maximum area? Is this ellipse the circle, or in what cases the maximum ...
1
vote
2answers
64 views

Max and Min using Lagrange Multipliers

Suppose A is a symmetric matrix. Show that the maximum and minimum of $\mathbf x ^T A \mathbf x$ subject to the constraint $\mathbf x ^T \mathbf x=1$ are the maximum and minimum eigenvalues of A. I ...
1
vote
2answers
35 views

Positivity of a function in $\mathbb{R}^{n}$

We place ourself in $\mathbb{R}^{n}$. We consider a given increasing function $$ g : \begin{aligned} &\mathbb{R}^{+} \to \mathbb{R} \\ &x \;\;\,\mapsto g(x) \end{aligned}$$ Finally, we ...
1
vote
1answer
47 views

$AB$ is a chord of a circle $C$. Let there be another point $P$ on the circumference of the circle, optimize $PA.PB$ and $PA+PB$

$AB$ is a chord of a circle $C$. (a) Find a point $P$ on the circumference of $C$ such that $PA.PB$ is the maximum. (b) Find a point $P$ on the circumference of $C$ which maximizes $PA+PB$. My ...
1
vote
2answers
186 views

Value minimizing mean absolute percentage error

What value for $c$ would minimize the formula: $$\frac{1}{n}\;\sum^{n}_{i=1}\left | \frac{y_i-c}{y_i}\right|$$ given the values $y_1, ..., y_n$. For example in the mean squared error we have the ...
1
vote
0answers
59 views

computing dual LP in graph matchings

I'm having a trouble converting the following LP to a dual LP. Help on some starting steps would be greatly appreciated!
1
vote
0answers
77 views

extreme value of increasing or decreasing function

From the three problems: one, two and three, it seems that if $f(x)$ is decreasing function with $a+b+c=abc$ or $a + b + c + a b + b c + c a = 1 + a b c$ then the maximum value of $f(a)+f(b)+f(c)$ ...
1
vote
1answer
127 views

Local extrema of continous, non-differentiable function

Ok, so looking through some questions I've found this answer: http://math.stackexchange.com/a/1667/102636 containing proof, that there are either inifinitely or no local extrema of continous and ...
1
vote
1answer
59 views

Guessing Game Stochastic Optimization

This is part of another post I did, but I think it has interest in its own right: Let $Y =\{X_{1},X_{2}...X_{N}\}$ be a set of $N$ random quantities with assocated set of distributions ...
1
vote
2answers
130 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
212 views

Determine all the extrema of a function subject to a non-linear constraint.

QUESTION Determine all extrema of the function $$f(x,y) = x+ 2y $$ subject to $$x^2 + y^2 - 80 = 0$$ ATTEMPT I don't think I understand what I'm supposed to do. This was in a test and I ended up ...
1
vote
1answer
89 views

Simultaneous Maximization and Minimization

I have a function with two variables say $$g(x,y)=f(x)−h(x,y)\ $$ where $$ f(x)= ax-bx^2\ $$ and $$h(x,y)=(x+y)^2\ $$ and $$ y>=0, x+y>=0\ $$My purpose is to maximize g(x,y) for x, ...
1
vote
1answer
363 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 ...
1
vote
0answers
28 views

Minimization values for a function [duplicate]

I have got function - non linear(I thk), and a set of variable S=[(x1,y1),(x2,y2)...]. The objective is to find the value for ...
1
vote
1answer
65 views

A minimization problem

Define $$L(w,u)=\frac{1}{2}\|w-u\|^2+\beta \left\|\frac{w}{x}\right\|,~w,u\in \Bbb{R}^n$$ where $$\frac{w}{x}=\left(\frac{w_1}{x_1},\ldots, \frac{w_n}{x_n}\right)$$ $$\|x\|=\sqrt{x_1^2+\cdots+x_n^2}$$ ...
1
vote
1answer
170 views

the implication of zero mixed partial derivatives for multivariate function's minimization

Suppose $f(\textbf x)=f(x_1,x_2) $ has mixed partial derivatives $f''_{12}=f''_{21}=0$, so can I say: there exist $f_1(x_1)$ and $f_2(x_2)$ such that $\min_{\textbf x} f(\textbf x)\equiv ...
1
vote
2answers
112 views

Determine the points where $f$ is has a local minimum/maximum. Multivariable calculus question.

This is not homework, but it is in my book and I find it hard to solve: Determine the points where $f$ is has a local minimum/maximum. Determine if it strong/weak and absolute/relative and ...
1
vote
1answer
185 views

Are these convex optimization problems equivalent?

Consider the optimization problem $$ \mathcal{P}_1: \qquad \min_{x \in \mathbb{R}^n} c^\top x \quad \text{sub. to } \ g(x,y_i) \leq 0 \ \ \forall i = 1,2,...,M$$ where $c \in \mathbb{R}^n$, and ...
1
vote
0answers
215 views

Showing a dual LP solves a primal LP

I originally asked this question: Does solving the LP dual SOLVE the primal LP? It was answered using an example of how the primal and dual solve each other (because of knowledge from strong ...
1
vote
3answers
493 views

A constrained linear least Frobenius norm problem:$\min_{X} \|A-XB\|_F$ subject to $Xv=0$?

Assume we are given two matrices $A, B \in \mathbb R^{n \times m}$ and a vector $v \in \mathbb R^n$. $\|\cdot\|_F$ is the Frobenius norm of a matrix. How can we solve $$\min_{X \in \mathbb R^{n ...
1
vote
1answer
390 views

How would you solve a Tikhonov Regularized Least Squares problem with nonnegative constraints?

For a Tikhonov Regularized Least Squares problem with nonnegative constraints, what are some methods that solve it? Are methods solving a Least Squares problem with nonnegative constraints and the ...
1
vote
1answer
74 views

Is $ \sum_{1 \le k \le n} (y_k - a x_k^b + c x_k^d + e)^2 $ convex?

Over at How many points to find a polynomial? it was suggested to minimize $$ f(a,b,c,d,e) = \sum_{1 \le k \le n} (y_k - a x_k^b + c x_k^d + e)^2 .$$ However I don't know if it is possible to find ...
1
vote
4answers
4k views

Max distance between a line and a parabola

I am suppose to use calculus to find the max vertical distance between the line $y = x + 2$ and the parabola $y = x^2$ on the interval $x$ greater then or equal to $-1$ and less then or equal to $2$. ...