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)

1
vote
1answer
59 views

Toeplitz equality constrained least-square optimization

What is the fastest known algorithm for least-square optimization problem with a linear equality constrain \begin{align*} &\min \|K x - y\|^2 + \mu \|x\|^2\\ \text{s. t. }& Q x = v ...
1
vote
0answers
21 views

Optimization problem: combination of values

Problem: Given an unlimited amount of empty boxes and a limited amount of items N, each with a specific value but not necessarily an unique value. A box has to be filled with at least 1 item and the ...
0
votes
1answer
20 views

Case of convex function

I have a following problem. a) Let $A \subseteq \mathbb{R}^n$ be convex set and $f\colon A \to \mathbb{R}$ convex function. Show that a set $f^{-1}(-\infty, a)$ is convex for all $a\in \mathbb{R}$. ...
2
votes
1answer
442 views

Why is Newton's method faster than gradient descent?

Can you provide some intuition as to why Newton's method is faster than gradient descent? Often we are in a scenario where we want to minimize a function f(x) where x is a vector of parameters. To do ...
0
votes
2answers
24 views

Union of convex hulls

I'm trying to prove the following: Let $A,B \subseteq \mathbb{R}^n$. Prove that $\mathcal{C}(\mathcal{C}(A) \cup \mathcal{C}(B)) = \mathcal{C}(A \cup B)$. Any suggestions?
0
votes
1answer
41 views

Is the optimization problem right?

If we want optimize the following problem $$ \min_x \{a(x)+c(x)\} $$ and we have $$ a = \min_y b(y) $$ then, could we directly optimize the following problem? $$ \min_x \{b(x)+c(x)\} $$
-2
votes
3answers
705 views

Max and min of a wire cut into a square and triangle

A piece of wire $10 m$ long is cut into two pieces. One piece is bent into a square and the other is bent into an equilateral triangle. Find the maximum and minimum possible area that can be enclosed. ...
1
vote
1answer
114 views

Boundary solution to a max-min problem

Find the maximum and minimum values of $$f (x, y) = x − x^2 + y^2$$ on the rectangle $0 ≤ x ≤ 3, 0 ≤ y ≤ 2.$ I derived the determinant of the corresponding Hessian matrix and it turn out to be ...
0
votes
1answer
58 views

quadratic constraints

Is it possible to reformulate the following quadratic constraints to conic constraints so that I use an SOCP solver $$ ( x_1^2 + x_2^2 ) - ( y_1^2 + y_2^2 ) \leqslant c $$ ...
2
votes
0answers
61 views

Can the minimum be given by an integral?

for $a,b > 0$, $$ \begin{align} &\int_{0}^{\infty} \frac{\sin (ax) \sin (bx)}{x^{2}} \ dx \\ &= \int_{0}^{\infty} \frac{a \cos (ax) \sin (bx) + b \sin(ax) \cos(bx)}{x} \ dx \\ &= ...
1
vote
1answer
73 views

Find max/min values of the sum of squares

How to find max/min values for the sum of squares: $n_1^2 + n_2^2 + ... + n_i^2$ where $n_1 + n_2 + ... + n_i = c$ Is it true that max value is always obtained when $n_1 = n_2 = ... = n_i$?
1
vote
1answer
63 views

dijkstra's algorithm in time O(k|V|+|E|)

Can somebody can help me with this problem: I have to calculate the minimum distance from a source node $s$ for undirected and connected graphs $G = ( V, E)$ with weights on the arcs belonging to the ...
1
vote
0answers
58 views

Efficiently deleting 2s from a random NxM matrix

Edit: There were 2 important logic errors in the code below. They have been fixed! update: I still don't have an answer to this question, but I recently made a massive improvement to my current ...
0
votes
1answer
29 views

convert summation to matrix formula: why is it true

Assume we have a matrix $Y \in R^{n \times k}$ and a matrix $W \in R^{n \times n}$ that gives mutual weight between each $n$ datapoints $y_i$ and $y_j$. Also we define degree matrix $D_{ii} = ...
0
votes
1answer
74 views

Solve this linear program using 2 phase simplex

Minimize $2x_1 + 3x_2 + 3x_3 + x_4 − 2x_5$ Subject to $x_1 + 3x_2 + 4x_4 −x_5 = 2$ $x_1 + 2x_2 − 3x_4 +x_5 = 2$ $−x_1 − 4x_2 +3x_3 = 1$ $x_1, x_2, x_3, x_4, x_5 \geq 0$ Im not sure if im doing ...
0
votes
1answer
625 views

Optimization problem with open box to be constructed

An open box is to be constructed so that the length of the base is 3 times larger than the width of the base. If the cost to construct the base is 5 dollars per square foot and the cost to construct ...
1
vote
2answers
52 views

Linear systems of inequations

Ok so I have a systems with $6$ inequations and $3$ variables, and a point that may or may not solve this system. To check whether this point solves the inequations is straightforward, my problem is ...
0
votes
1answer
90 views

Minimizing the functional using Euler Lagrange and Cauchy matrix

I'm given this problem where I need to minimize $$I(U) = \int_0^1 u'(x)^2dx$$ with $u(0) =a_0, u(1) = a_1$ among all functions that satisfy $$0 = \int_0^1 u(x)\cos(b_i x)dx, \quad i = 1,2,\cdots,N.$$ ...
0
votes
1answer
241 views

Easy (?) application of Lagrange multiplier

I am reading a book about utility theory and there is a exercise (without solution). I can't stop thinking about this, since the normal Lagrange multiplier approach seems not to work. We want to ...
1
vote
1answer
14 views

Maximizing with two arguments with iteration

I would like to show that: $$ \displaystyle\max_{(x,y) \in X\times Y} f(x,y) = \displaystyle\max_{x} \displaystyle\max_{y} f(x,y) $$ which I obviously believe to be true, although I may be wrong. ...
0
votes
1answer
34 views

Finding the optimal solution

Find the optimal solution of the problem $$\min \Bigg \{ \int_0^1 [x^\prime (t)^2 + 2x(t)^2]e^t dt : x(0) = 0, x(1) = e - e^{-2}\Bigg \}$$ and the value of the minimum. Not sure how to approach this ...
0
votes
2answers
29 views

lower and upper bound on the unit disk

let $a>0$ and $b>0$ constant, $D$ the unit disk and $f(x,y)=a + \frac{2(x^2 + y^2)}{\rho^2}ab + \frac{1}{\rho^4}(x^2 + y^2)^2(3a+b)$ find $\sup_{(x,y)\in D}{f(x,y)}$ and ...
2
votes
3answers
776 views

Minimizing the cost of a pipeline over land and water.

An oil refinery is located on the north bank of a straight river that is $2$ km wide. A pipeline is to be constructed from the refinery to storage tanks on the south bank of the river $6$ km east ...
0
votes
1answer
43 views

unnecessary constraint in optimization problem

I have some optimization problem (optimizing parameter $\alpha$)with those constraints: $$\alpha_i\ge0$$ $$\sum\limits_i \alpha_i y_i =0$$ and a third constraints: $$w-\sum\limits_i \alpha_i y_i x_i = ...
1
vote
1answer
60 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
16 views

Given two non-negative vectors $r,c$, is there always a non-negative matrix A whose marginals are $r$ and $c$?

Let $A$ be an nxm matrix. We can easily determine its row and column marginals $r$ and $c$: $r=A1$ $c=1^TA$. Suppose however, that you are given non-negative marginals $r,c$. Is there always a ...
1
vote
2answers
23 views

Optimization Calculus Question

Find the maximum point on the graph $$y = x^a(1-x)^b$$ where $a > b$ and the interval of $x$ is $0 < x < 1$.
0
votes
1answer
59 views

Was my inference regarding $u(z)=log(z)$ correct?

I have already solved the problem but would appreciate a clarification in part (b). A has initial wealth $w$ and faces a loss $l$ with known probability $\pi$. Insurance available at unit price ...
1
vote
2answers
70 views

Quadratic programming for special equation issues

My problem is how to find $\tau_1$ and $\tau_2$ s.t maximize the objective function is $$E=M-\alpha V$$ subject to $$-0.0062\le\tau_1\le0.499$$ $$-0.479\le\tau_2\le0.0262$$ $$\tau_1+\tau_2\le0.02$$ ...
0
votes
1answer
52 views

Normalization in Linear Regression

In linear regression problems it is important not to have a curve that overfits the input data or training examples. In other words, the curve should generalise your training data so you can predict ...
4
votes
4answers
91 views

Minima and maxima of $\left({\frac{\sin 10x}{\sin x}}\right)^2$ on $[0,\pi]$

Find the minima and maxima of $\left({\frac{\sin 10x}{\sin x}}\right)^2$in the interval $\left [ 0,\pi \right ]$. This is a question from BdMO that still haunts me a lot. I would like to find an ...
2
votes
1answer
37 views

Forming peaceful teams

Let us have set of $n=mk$ people that have to be divided into $m$ teams, each with $k$ members. Let us denote the set of the people $S=\{1,2,\dots,n\}$ and the teams $S_i\subset S$. We consider a ...
2
votes
0answers
88 views

Why is TSP 3-opt better than 2-opt?

For Travelling salesman problem, I've seen a couple of people claim that 3-opt yields a better solution than 2-opt (and 4-opt better than 3-opt, etc.) but I've never seen why and never seen any proof. ...
0
votes
1answer
2k views

How to find the speed that minimizes the total cost of a trip?

Here are some facts about semi-trucks and a trip between Chicago and New Orleans. (a) The trip is 750 miles. (b) Running at 50 mph, the truck gets around 4 miles per gallon. (c) For each mph ...
1
vote
2answers
43 views

Global maxima/minima of $f(x,y,z) = x+y+z$ in $A$

Find the global maxima/minima of $f(x,y,z) = x+y+z$ for points inside of $A = \{ (x,y,z) \in \mathbb{R}^3: x^2-y^2 = 1 \wedge 2x+z = 1 \}$ I renamed the conditions of $A$ to a function $g(x,y,z) ...
1
vote
0answers
68 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 ...
0
votes
1answer
48 views

Steepest descent method analytically

I want to use steepest descent method to minimize the function below and show the first method of iteration analytically with starting point xt[1,1] f(x) = x^3 + xy + x^2y^2 – 3x I have gone to the ...
1
vote
0answers
112 views

Maximum of a convolution

I have a function $f:{\mathbb R}\rightarrow {\mathbb R}_+$ which has a unique maximum at $x=0$. $f$ can be symmetric or asymmetric. I am interested on the mollified-f function ...
0
votes
0answers
32 views

What is a good optimization algorithm/tool for otimization on Partially Ordered set?

Actually I'm interested to minimize following kind of functions: $f: U \rightarrow V$ where: $U$ is a vector space and $V$ is a Ordered vector space, i mean Partially Ordered Vector space. ...
3
votes
5answers
1k views

Circle inscribed in triangle

What's the radius and area of circle of max area that can be inscribed in a isoceles triangle with $2$ equal sides of length $1$? Radius formula is given, $r = \dfrac{2A}{P}$, where $A$ is area of ...
0
votes
1answer
21 views

Solving for critical points

I calculated cost to find a minimum as $C=0.11xy+0.12xz+0.12yz$ for volume $xyz=668.25$. I ended up with critical points $c_x=0.11-80.19y^2=0$, and $c_y=0.11y-80.19x^2=0$ after makin the function $2$ ...
2
votes
0answers
41 views

Effective convexity criterion for the finite point set in $\mathbb{R}^3$

I need to find effective convexity criterion for the finite point set. Below there is description of what is meant by "effective" criterion. Definition. Let $M = \{A_{1}, \ldots, A_{n}\}$ be the ...
0
votes
0answers
43 views

How can be a conservative field constraint be efficiently implemented in a continuous optimization problem?

Suppose we have the following continuous optimization problem: $$ \underset{x}{\mathrm{minimize}}f\left(x\right) $$ subject to $$ \exists X:\nabla X=Jac\left(X\right)=x $$ where $f$ is a function ...
2
votes
0answers
27 views

Stationary points and gradient?

Wolfram Alpha tells me that $xy^2$ only has the stationary points (0,0).... but why? We get the gradient $$(y^2 , 2xy)$$ and this is surely 0 as long as $y=0$ meaning $x$ can be whatever it wants to ...
0
votes
1answer
63 views

A problem related to linear assignment with constraints.

Suppose I have two sets of numbers $\{a_1,\ldots,a_n\}$ and $\{b_1,\ldots,b_n\}$, an integer $m < n$, and a number $r\ge0$. I wish to choose a subset $C$ of $\{1,2,\ldots,n\}$ with $|C|=m$ that ...
0
votes
1answer
25 views

Two-constraints optimization?

How would one go about trying to calculate the highest/lowest values of a two variable function given that $(x,y)$ must lie on the upper half of the unit circle? If it was just the unit circle, I'd ...
2
votes
0answers
21 views

The problem of support vector machine - How to minimize $||w||^{2}$ subject to constraints of the form $\alpha w_{1}+\beta w_{2}+b\geq\pm1$

I am studying the subject of support vector machines from an online course. I am given four points and their classification $$ x_{1}=((5,4),+),\, x_{2}=((8,3),+) $$ $$ x_{3}=((3,3),-),\, ...
1
vote
1answer
38 views

How many samples of $y$ and $x$ given variances?

On a homework problem, I am given two variables, $x$ and $y$, with variances $4$ and $16$, respectively. The question is how many observations should I draw of $y$ in order to estimate the difference ...
0
votes
1answer
628 views

Prove that there are an infinite amount of critical points and they are all local (and absolute) minimums on $x^2+4y^2-4xy+2$

I am studying for a fast approaching Calc 3 midterm exam and ran into this problem in the textbook. Show that $f(x,y) = x^2+4y^2-4xy+2$ has an infinite number of critical points and that $D = 0$ ...
1
vote
2answers
38 views

Finding Optimization of Rectangle

I have the following problem and I want to find the minimum. A rectangle fence is being built. One side of the rectangle costs 5 dollars per foot, while the other 3 sides cost 3 dollars per foot. The ...