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

piecewise linear minimization equivalent to linear programming

Just ask a dumb problem: \begin{equation} \begin{aligned} & {\text{min max}_{i=1,\cdots,n}} & &a_i^Tx+b_i\\ \end{aligned} \end{equation} is equivalent to an LP \begin{equation} ...
1
vote
0answers
17 views

Maximum flow on a directed, acyclic graph

What would be the best algorithm to use for finding max-flow/min-cut on a directed, acyclic graph with integer flows, capacities, and vertex demands? I've been thinking Dinic's Algorithm would be ...
0
votes
0answers
9 views

How to solve exponential matrix factorization with constrain: $UV^T>0$

recently I would like to optimize the following loss function: $$L=\sum_{ij}W_{ij}(X_{ij}-exp(-\sum_{l} U_{il}V_{jl}))^2$$ $$s.t. \sum_lU_{il}V_{jl} > 0$$ Where $W \in \mathbb{R}^{m \times n}, X ...
17
votes
13answers
3k views

Why does a distance and its square reach their minimum at the same point?

There is a question in my calculus textbook that asks to find a point on the parabola $y^2 = 2x$ that is closest to point $(1,4)$. They want us to first use the distance formula, but then proceeded ...
0
votes
3answers
86 views

Finding the Shortest Distance from Point to Plane

I am trying to find the shortest distance from the point (3,0,-8) to the plane x+y+z = 8 and I keep getting the same incorrect solution. First, I found the equation fo the distance to be: ...
0
votes
0answers
22 views

How to use Expectation Maximization (EM) in Item Response Theory (IRT)?

Could you give a worked example on the steps of Expectation Maximization in Item Response Theory if we use the Two Parameter Rasch Model. The student abilities are unknown and the question parameters ...
1
vote
1answer
7 views

Solving a polynomial equation along a set of lines numerically.

Assume that I for some reason want to solve multidimensional polynomial equations $$p(x_1,x_2,\cdots,x_k) = 0$$ or possibly (if there is no solution) $$\min_{\forall x_{.}} \{p(x_1,x_2,\cdots,x_k)\}$$ ...
0
votes
0answers
11 views

Numerically, what is the best stopping criterion for optimization problems?

Assuming the objective function is $F(x)$ and we want to minimize it. What is the best stopping criterion? Here are some criteria in my mind. (1) $F(t) - F(t-1) < \xi$ (2) $F(t) < \xi ...
-2
votes
1answer
31 views

Books on Statistics and Optimization

I'm trying to close gaps in my education especially in Statistics and Optimization theory. I had an awful class on Statistics so I want to learn it by myself. As for Optimization we had a pretty good ...
-2
votes
1answer
119 views

Double obstructing wall problem, what is the optimal walk path and length?

Every day, you walk from point A to point B which are exactly $2$ miles apart straight line distance, however, each day, there is a $50$% chance of there being an obstructing wall perpendicular to the ...
-4
votes
0answers
21 views

How to divide rectangle for a circle and more small rectangle

I have a rectangle $500cm \times 1500cm$ I want to divide for radius $7 cm$ and small rectangle $5cm \times 12cm$ But What its most useful and optimal way ? (I think $f=500 \times 1500 - (5 \times ...
0
votes
1answer
14 views

Is it correct to write $argmin(x, y) \sum_i^n |p_{x_i} - x| + |p_{y_i} - y| = argmin(x) \sum_i^n |p_{x_i} - x| + argmin(y) \sum_i^n |p_{y_i} - y| $?

$argmin(x, y) \sum_i^n |p_{x_i} - x| + |p_{y_i} - y| = argmin(x) \sum_i^n |p_{x_i} - x| + argmin(y) \sum_i^n |p_{y_i} - y| $ Is it a legit way of separating argmins to show independence of $x$ and ...
0
votes
0answers
21 views

Probability of an event occuring $n$ times, given that it can occur $n$ times or does not occur at all.

Suppose you have an event whose probability is $\rho$. This event either does not occur at all or occurs $n$ times, because when it occurs once, all the others occurrences are linked to the first. ...
0
votes
0answers
33 views

Positivity of the last component of non negative least squares based on active set method

I have followed the instructions given in Lawson and Hanson book for non-negative least squares using active set method. I am having a trouble in justifying one of the statements they have made about ...
1
vote
1answer
16 views

Elementary derivation of max/min of quadratic trig polynomial

Let $\alpha, \beta, \gamma, \delta$ be fixed real numbers, and $x$ a variable in $[0,\pi)$. Consider the expression \begin{equation} (\alpha^2+\beta^2)\cos^2(x) + ...
1
vote
0answers
47 views

Why Was Backprop Invented?

I'm currently researching artificial neural networks and I keep wondering why do we use "backpropagation" to train a neural network. An ANN is basically just a very large and complex function ...
2
votes
0answers
75 views

Tricky proof of a result of Michael Nielsen's book “Neural Networks and Deep Learning”.

In his free online book, "Neural Networks and Deep Learning", Michael Nielsen proposes to prove the next result: If $C$ is a cost function which depends on $v_{1}, v_{2}, ..., v_{n}$, he states that ...
1
vote
1answer
306 views

how to find the input for this optimization problem?

Suppose I have a neural network, with input variables $a,b,c,d,f,g$ and output variables $m,n,o,p,q$. Given different input values, the neural network will output corresponding $m,n,o,p,q$. Now I ...
2
votes
1answer
3k views

Why do we use gradient descent in the backpropagation algorithm?

The common approach for training neural networks, as far as i know, is the backpropagation algortihm, which uses gradient descent to reduce the error. (i) why should one use a fixed learning rate / ...
2
votes
1answer
181 views

Gradient descent with adaptive learning ratio.

I have a neural network, trained with SGD (stochastic gradient descent) with learning ratio $\alpha$. Each iteration I try to recalculate the weights with a rule: $$\Delta \vec{w} = -\alpha ...
0
votes
3answers
24 views

Understanding when to use the chain rule when differentiating trig functions.

I'm trying to solve an optimization problem that involves finding the maximum angle that subtends two points. The two points are $b = (0, 5)$ and $t = (0, 14)$. The third point is the point that is ...
-1
votes
1answer
22 views

Periodic point of dynamical system

Hi please help me someone with the proof: We have a function $f:\mathbb{R}\longrightarrow\mathbb{R}$ continous and invertible, discrete dynamical system is given by $x_{n+1}=f(x_n)$ (a): prove that ...
0
votes
1answer
34 views

Show f takes on maximum boundary for function

Suppose $\Omega$ is a bound set in $\mathbb{R}^2$ and $\bar\Omega$ its closure. Assume $f\in C^2(\Omega)\cap C^0(\bar\Omega)$. Moreover, assume $f$ satisfies the partial differential ...
2
votes
2answers
65 views

Showing that mean of vectors minimizes the sum of the squared distances.

Let $S=\{x_1,...,x_n\}$ be a set of vectors in $\mathbb{R}^d$. Now we have to pick a vector $\mu$, such that the following expression is minimized: $$ L(\mu)=\sum_{x\in S} ||x-\mu||_2^2. $$ I think ...
1
vote
1answer
17 views

Method for calculating minimum number of transmissions?

(This is a real issue I face.) I have $42$ files I want to transmit. I tried sending them in a single archive but four of them had issues, and as a result the entire archive was rejected. I do know ...
0
votes
0answers
12 views

Can the time complexity of maximum-flow algorithm using fattest path method be represented by |V| and |E| only?

I've got a problem with "fattest path" heuristic in Max-Flow algorithms. ( http://www.eecs.berkeley.edu/~luca/cs261/lecture10.pdf ) The problem is 'prove or disprove that the time complexity can be ...
0
votes
0answers
25 views

How to Find the Maximum of a Function Represented by a Back-Propagation Neural Network?

First, I train a standard feed-forward neural network over a training set of data points. I get an approximate function, say $F(x)$, represented implicitly by that neural network. 1. How do I ...
1
vote
0answers
28 views

Nonlinear Least Squares vs. Extended Kalman Filter

What is the relationship between nonlinear least squares and the Extended Kalman Filter (EKF)? I've learned both topics separately and thought I understood them, but am now in a class where the EKF ...
1
vote
0answers
106 views

Construct a matrix of polynomials to optimize condition-like score

I'm a physicist currently working on my PhD. Within my studies, my colleagues & I encountered a (strictly mathematical) problem that baffles us (and anyone else we've talked to so far) and is also ...
5
votes
2answers
181 views

Smallest possible triangle to contain a square

I was looking at this stack exchange question* and started thinking about the case of a polygon with 4 sides: a square. The question asks for a program that can take a polygon of N sides and return ...
14
votes
8answers
2k views

How can I find 3 positive numbers that have a sum of 1 and the sum of their squares is minimum?

How can I find 3 positive numbers that have a sum of 1 and the sum of their squares is minimum? So far I have: $$x+y+z=1$$ $$z=1-(x+y)$$ $$f(x,y)=xyz=xy(1-x-y)$$ But I'm stuck from here. Hints?
0
votes
0answers
14 views

Basic Linear Algebra/Root finding question

What is the general method for solving this problem? $\theta_n.1_T'.z_T=0_n$ where $\theta_n$ is a n x 1 vector of parameters that are free to vary, $1_T'$ is a 1 x T vector of ones, $z_T$ is a T x ...
0
votes
0answers
10 views

Optimizations in Laplacian Eigenmap/Graph Embedding?

Note -- this question is closely related to this question that asks why the optimization constraint has to be $y^TDy=1$ instead of simpler $y^Ty=1$. Maybe answering this question will automatically ...
1
vote
3answers
82 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
16 views

Find $\alpha, \beta$ s.t. the following is minimized

Hello I would like to find $\alpha,\beta$ s.t. $$ e(\alpha,\beta) = ||\sqrt{1+\gamma^2}-\alpha-\beta\gamma||_\infty = || f_{\alpha,\beta}||_{\infty} $$ Is minimum (consider $\gamma \in [0,1)$, ...
0
votes
0answers
18 views

Optimization of a function over probability distributions

I'm trying to solve certain optimization problems dealing with probability distributions. Consider the space of probability distributions $\{ 1, ..., N\} \to [0, 1]$ I have a function $f : (\{ 1, ...
1
vote
1answer
41 views

Use Lagrange multiplier to find the distance between the point $(3,4,0)$ and the surface of the cone $z^2=x^2+y^2$

Use Lagrange multiplier to find the distance between the point $(3,4,0)$ and the surface of the cone $$ z^2=x^2+y^2 $$ I wrote the equation of the distance: $$f(x,y,z)=(x-3)^2+(y-4)^2+z^2$$ and ...
0
votes
1answer
22 views

Constrained maximization of …

I have to maximize $U(x,y)= Min(ax+y, by+x)$ s.a $p_{1}x +p_{2}y =m$. I try the traditional solution for a leontieff $(ax_{1}+y= by_{1}+x)$ function but I'm not sure.. beacause exist regions where one ...
1
vote
1answer
77 views

How to write lagrangian terms related to only one variable in a semidefinite constraint?

I have a semidefinite problem as follows(which is nonconvex) \begin{alignat}{3} &\min_{x_{un}} \min_{t,H,w} &&t+f( w)\cr &\text{s.t. } &&\begin{bmatrix} K\odot H ...
0
votes
0answers
19 views

Modeling simple linear equations

This should be pretty simple but I'm blanking on this. I need to model (graph) how path 1 becomes equally as efficient as path 2 as the distance of path 2 increases. distance of path 1 (from A to B) ...
2
votes
1answer
424 views

Gradient-descent and Hidden Markov Models

I would like to use gradient-descent to fit the parameters of a simple 2-state HMM. This paper Levinson, S. E., Rabiner, L. R. and Sondhi, M. M. (1983), An Introduction to the Application of the ...
1
vote
0answers
15 views

analytical solution to solve maximization problem

My question is the following: Let $f(x_1, ..., x_n, \theta): \mathbb R^{n+1} \rightarrow \mathbb R$ be a function in which we are interested in maximizing in terms of $\theta$. The traditional ...
-1
votes
0answers
17 views

optimization problem from my textbook

Given the objective function of a constrained optimization problem is $f(x₁, x₂)= c $ and the constraint is $g(x₁, x₂) = b$. How can I Show with a diagram that a unique optimum solution exist; unique ...
0
votes
0answers
16 views

Eppstein's k-Shortest Paths Algorithm [on hold]

I was trying to work on a variation of Eppstein's k-Shortest Path Algorithm. Is there an Java-based implementation available for use somewhere, or maybe can someone help me with implementing it? I ...
0
votes
0answers
16 views

Are any tools or techniques available to solve the “placement of safety points” problem?

Definition 0. Given a metric space $X$ and subsets $H$ and $S$ thereof, define: $$d(H,S) = \sup_{h \in H} \inf_{s \in S}d(h,s)$$ Here's some extremely dodgy intuition. Imagine $S$ is a set of ...
4
votes
2answers
39 views

L1 regularized unconstrained optimization problem

I am encountering an unconstrained minimization problem. The problem is of the form $$\min_x \frac{\|x-a\|_2^2}{2}+\lambda\|x\|_1$$ where $x,a \in R^n$ and $x$ is the optimization variable. ...
44
votes
7answers
1k views

What is the optimal path between $2$ fixed points around an invisible obstructing wall?

Every day you walk from point A to point B, which are $3$ miles apart. There is a $50$% chance each walk that there is an invisible wall somewhere strictly between the two points (never at A or B). ...
2
votes
3answers
47 views

Maximum of $xy+y^2$ subject to right-semicircle $x\ge 0,x^2+y^2\le 1$

Maximum of: $$ xy+y^2 $$ Domain: $$ x \ge 0, x^2+y^2 \le1 $$ I know that the result is: $$ \frac{1}{2}+\frac{1}{\sqrt{2}} $$ for $$ ...
0
votes
1answer
631 views

Dual cone of a L1 norm cone?

I am listening to convex optimization lectures and I hear that dual cone of a $L1$ norm cone is a $L-\infty$ norm cone. Can anybody please explain how? I understand that every point in the dual cone ...
6
votes
6answers
200 views

Extreme of $\cos(A)\cos(B)\cos(C)$ in a triangle without calculus.

If $A,B,C$ angles of a triangle, show extreme value of $$\cos(A)\cos(B)\cos(C)$$ I have tried using $A+B+C=\pi$, and applying all and any trig formulas, also AM-GM, but nothing helps. On this topic ...