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
23 views

Teacher/student exam assignment matching problem - equivalent problem?

I have a sort of matching problem. I am wondering if you know if this problem reduces to a familiar one. It arises from my friend's job, and something we were wondering about this morning on the ...
-2
votes
0answers
5 views

interior point in linear programming with matlab [on hold]

I use matlab program language during which I write the block matrix : lhs = [zeros(5,5),A.',eye(5);... A,zeros(3,3),zeros(5,3);... diag(z),zeros(5,5),diag(x)], such that A,z,x are ...
0
votes
2answers
295 views

Optimal Basic Feasible Solutions

In linear programming, is it true that you can only have at most 2 optimal basic feasible solutions? If so, why?
0
votes
0answers
10 views

Non-convex constraint made cost

Consider the non-convex optimization problem $$ \min_{x \in X} \ f(x) \quad \text{s.t.:} \ \ g(x) \leq 0, \ h(x) = 0 $$ where $X \subset \mathbb{R}^{2n}$ is compact and convex, $f$ and $g$ are ...
0
votes
0answers
12 views

Which matrix norm gives the minimal variation of eigenvalues?

This is a follow-up of this question. The original question is intentionally as general as possible, because I was interested in the most general possible answer. I am now trying to understand its ...
1
vote
1answer
29 views
+100

Regression with error coming from rounding

I am looking at the following model: $c$ is a fixed vector in $\mathbb{R}_+^n$ and for any $x \in \mathbb{R}_+^n$ we obtain a value $y =[c^Tx]$, i.e. rounding $c^Tx$ to the nearest integer. I want ...
5
votes
1answer
926 views

How to define the characteristic length scale in a downhill simplex method?

I am currently converting a minimization problem from Matlab to C++, using the Numerical Recipes implementation of the Nelder and Mead Downhill simplex method. The function requires me to define a ...
2
votes
2answers
29 views

Smallest value taken by a quadratic polynomial in two variables.

Let $p$ be a degree $2$ polynomial with integer coefficients, say $$p(x,y) = Ax^2 + By^2 + Cxy + Dx + Ey + F.$$ I would like to find an algorithm which solves the following: Problem 1: Given ...
0
votes
3answers
40 views

Optimizing an expression containing sum of square roots of squared terms

For optimization problems involving square root, it is common to optimize the squared expression instead of that containing the square root. What if we have sum of squared expressions ? Consider the ...
1
vote
2answers
652 views

Shortest distance between two curves

Let $C_1= \{ (x, y) \in \mathrm{R}^2 : y = x^2 +1 \}$ and $C_2= \{ (x, y) \in \mathrm{R}^2 : x = y^2 +1 \}$, find the points which minimize distance between $C_1$ and $C_2$. What I tried is: we know ...
1
vote
0answers
15 views

Equivalent optimization problems?

I am wondering if the set of optimizers of the problem $$ \min_{x \in X} \ f(x) \quad \text{subject to: } g(x) \leq 0, \ h(x) = 1 $$ is the same of the one of $$ \min_{x \in X} \ f(x) + h(x) \quad ...
0
votes
0answers
21 views

Multivariable Gradient Descent

If I have a function $S: \mathbb{R}^2 \to \mathbb{R}$ that describes energy falloff in space. I have a source $S$ positioned at $(S_x, S_y)$ and the intensity at any given point in space (x, y) is ...
0
votes
1answer
23 views

Matlab: need help with optimization

I am trying to minimize the objective function over [x(1),x(2)]: exp(x(1))*(4*x(1)^2+2*x(2)^2+4*x(1)*x(2)+2*x(2)+1)+b subject to constraint ...
0
votes
1answer
33 views

Min and max of a product.

Let $x_i\in X_i\subset \mathbb{R}$ so that each $X_i$ is a compact set with no isolated points for all $1\leq i\leq n$. Let: $a_i\in X_i$ so that $|x_i|\leq|a_i|$ for all $x_i\in X_i$. $b_i = ...
0
votes
0answers
13 views

Solving bi-linear programming in MATLAB [on hold]

Can anyone suggest any solver in MATLAB to solve a bilinear programming problem? Or any tutorial for the same?
0
votes
1answer
27 views

Optimization with a constraint given by a differential equation

I have the following differential equation $$\ddot\theta(t) = -k\sin{\omega t}\sin{\theta(t)} \quad \text{where} \quad \theta(0)=\theta_0, \dot\theta(0)=v_0$$ where $\omega$ is a known constant and ...
4
votes
1answer
184 views

Book on advanced topics of Network Flows

I am taking linear optimization class. Could you suggest me good fundamental textbook on advanced topics of network flows. To be more specific I am interested in: Multicommodity flow and multicut, the ...
1
vote
1answer
15 views

Least surface of volume with constraints

We know that in 2D/3D the shape with the least surface of a certain volume is a circle/sphere (e.g. soap bubbles). Now Imagine we have a flat surface (tabletop) that can be used as part of the surface ...
9
votes
1answer
181 views
+50

How fat is a triangle?

The slimness factor of a geometric shape in 2 dimensions is the ratio between the side-length of its smallest containing square and its largest contained square. This is an important factor in ...
0
votes
1answer
714 views

How to describe minimization of L1 norm error using linear programming?

Given a set of $n$ pair points $(x_1, y_1), ..., (x_n, y_n)$ in the plane, I need to find a line $ax + by = c$ that fits the points of the L1 norm error points as closely as possible. I need a linear ...
5
votes
2answers
62 views

When is $\min_{x\in X,y\in Y}f(x,y)=\min_{x\in X}(\min_{y\in Y}f(x,y))$?

When is $$ \min_{x\in X,y\in Y}f(x,y)=\min_{x\in X}(\min_{y\in Y}f(x,y))? $$
0
votes
1answer
45 views

Finding Critical Points - Two points on a parabola st joining line is minimised

I have that two points A,B lie on a parabola y = x^2 such that the line segment between them is always perpendicular to the tangent line at A's position. A sits at (a,a^2). Firstly, I found the slope ...
6
votes
3answers
59 views

Interesting, unusual max/min problems?

So I've got to that stage of my elementary mathematics subject for engineers when we talk about differentiation and solution of max/min problems. And I'd like to entertain and engage the students ...
0
votes
1answer
15 views

Comparing two circularly shifted matrices

I am looking for a way to compare two matrices A and B where B is the result of circularly shifting rows of A i.e. A = [1 2 3;4 5 6], B = [4 5 6;1 2 3] Is there an operator or metric that would ...
6
votes
0answers
85 views
+50

Intuition behind accelerated first-order methods

$\newcommand{\prox}{\operatorname{prox}}$ $\newcommand{\argmin}{\operatorname{argmin}}$ Suppose that we want to solve the following convex optimization problem: $\min_{x \in \mathbb{R}^n} g(x) + ...
2
votes
2answers
35 views

Augmented Lagrangian

Consider the following equality constraint minimization problem: minimize $\text{ }f(x)$ subject to $Ax=b$ Its Lagrangian is then: $L(x,y) = f(x) + y^T(Ax-b)$ We can use then gradient ascent to ...
0
votes
0answers
30 views

Dual of a polyhedra vs. dual of an optimalization problem

There are lot of fields where the term duality appear. Is there any relationship between dual of an optimalization problem and dual of a polyhedra?
0
votes
0answers
22 views

k- maximally link disjoint paths and equations

This problem is NP-complete and also discussed to some extent in Graph problems which are NP-Complete on directed graphs but polynomial on undirected graphs from the level of my reading from various ...
4
votes
4answers
133 views

Notation for the set of all arguments corresponding to local minima.

The notation $$\mathop{\mathrm{arg\, min}}_{x \in X} f(x)$$ is sometimes used for the set of all $x \in X$ corresponding to global minima of the function $x \in X \mapsto f(x).$ Is there notation for ...
-2
votes
1answer
36 views

Maximum area of a rectangular field that can be fenced and divided in half by a fence

A rectangular pasture is to be fenced then divided in half by a fence parallel to 2 opposite sides. If a total of 6000m of fencing is used, what is the maximum area that can be fenced? I have no idea ...
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. ...
2
votes
0answers
74 views

Finding optimal velocity profile using Dynamic Programming

This question has been asked on scicomp but I thought maybe it's more a mathematical problem of how Bellman's idea is to be applied here. The main problem for me is: How to introduce the time ...
0
votes
0answers
20 views

Concave Quadratic Program

Let $X \subset \mathbb{R}^n$ be compact and convex. Consider $$ x^* := \arg\min_{x \in X} x^\top Q x + c^\top x $$ where $Q \prec 0$. I am wondering if there are cases where $x^*$ can be written as ...
1
vote
1answer
20 views

Does existence of global minimum imply coercivity?

It is known that a coercive function over a closed, unbounded set has a global minimum. Is the converse true ? The larger context for this question is the following question: Suppose we are given a ...
0
votes
1answer
32 views

Using bordered Hessian matrix to determine non-degeneracy and type of constrained extremum

I have the following problem: $\def\f{f(x_1,x_2,x_3)}\def\1{x_1}\def\2{x_2}\def\3{x_3}\def\n{\nabla}\def\g{g(x_1,x_2,x_3)}\def\l{\lambda}\def\q{\begin{pmatrix}}\def\p{\end{pmatrix}}$ Find the ...
1
vote
3answers
1k views

How to plot a phase portrait for this system of differential equations?

I beg your help.. I'd like the phase portrait for this system. I don't know how to use Mathematica/Matlab ... :( If anyone can make this portrait and post a print screen here, I would thank you ...
1
vote
0answers
38 views

Write down the HJB equation

Suppose that we have to solve the following optimal control problem \begin{align} V(t,x) = \min_{\alpha}\mathbb{E} \left[\int_{0}^{T}L(t,x,\alpha)dt + F(e^{-\beta t}X^{\alpha}_{T})\right] ...
1
vote
1answer
39 views

Local minimum of the function:

Find the local minimum of the function: $$\def\f{f(x_1,x_2,x_3)}\def\1{x_1}\def\2{x_2}\def\3{x_3}\def\n{\nabla}$$ $$\f=\1^2-2\1\2+2\2^2+\3^2 \text{ in } \mathbb{R}^3$$ $\n\f=(2\1-2\2,-2\1+4\2,2\3) ...
1
vote
0answers
20 views

Hint for KKT Optimization problem

Can anyone help me with the following optimization problem please? I have to find the $\max f(c,y_1^1,\cdots,y_{N-1}^1,\cdots,y_1^M,\cdots,y_{N-1}^M)=c$ subject to the constraints ...
0
votes
1answer
44 views

Model $\min \frac{1}{2} \parallel Ax-B \parallel_2 + \lambda_1 \parallel Cx \parallel_1 + \lambda_2 \parallel Dx \parallel_\infty $ into standard form

I need to solve the following convex optimization problem: $\min \frac{1}{2} \parallel Ax-B \parallel_2 + \lambda_1 \parallel Cx \parallel_1 + \lambda_2 \parallel Dx \parallel_\infty$ s.t $x ...
0
votes
1answer
20 views

Distribute N items in K sets with minimum overlap

I am working on an optimization problem to distribute N distinct items (each of the items is available in infinite quantity), among K sets. Each set should have T items. (The constraint of T can be ...
1
vote
0answers
33 views
+50

computing the derivative of a transformation matrix

I am trying to find a geometric transformation between two images, where the transformation is a simple scaling matrix. So, if I denote the two image functions as $r$ and $f$ and the scaling matrix as ...
3
votes
4answers
1k views

Find maximum and minimum value of function $f(x,y,z)=y+z$ on the circle

Find maximum and minimum value of function $$f(x,y,z)=y+z$$ on the circle $$x^2+y^2+z^2 = 1,3x+y=3$$ We have that $$y=3-3x$$ So we would like find minimum and maximum value of function ...
2
votes
1answer
74 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?
0
votes
0answers
7 views

Using EM versus estimating all parameters directly

My question is really a request for a clarification, and pertains to whether or not there are questions for which it is necessary to use EM or if it's more of a convenience. Let's presume we have n ...
0
votes
0answers
24 views

Minimum of summed sequence

Define M non-negative sequences, \begin{equation} a_{m,1}\geq a_{m,2}\geq,...,\geq a_{m,K}\quad \text{for}\ m=1,..,M \end{equation} and cyclic shifted versions $a^{\zeta_m}_{m,k}$ with shift value ...
6
votes
4answers
1k views

Is it possible for the Lagrange multiplier to be equal to zero?

I would like to find the extrema of the function $f(x,y)=x^2+4xy+4y^2$ subject to $x^2+2y^2=4$ using Lagrange Multipliers. Is it possible to get for the Lagrange multipliers the value zero? I don't ...
3
votes
2answers
85 views

How to use mathematically the I and D of a PID controller

I am trying to mathmatically understand how the $P$, $I$, and $D$ parameters work on a system, quite having a hard time doing so. I've only been able to show that the Steady State Error (SSE) never ...
0
votes
3answers
39 views

Definition of Global Convergence

I am confused by the notion of "global convergence" as used in numerical optimization literature, and did not find an exact definition for that yet. Now I try to double check my understanding here. ...