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

Controlling a flying vehicle with multiple thrusters

I'm working on a problem involving a vehicle with $n$ rocket engines, as seen here: The task is, given the desired force $\vec F$ and torque $\vec \tau$, calculate the optimal thrust for each ...
0
votes
1answer
824 views

Shortest path problem: dual formulation and proof of total unimodularity

The IP formulation of the shortest path problem looks as follows: \begin{align*} \min & \sum_{u,v \in A} c_{uv} x_{uv}\\ \text{s.t } & \sum_{v \in V^{+}(s)} x_{sv} - \sum_{v \in ...
0
votes
1answer
23 views

Load balance N customers over K servers with different capacities

Let's say we have N customers that supply a stream of requests, but each customer i supplies different number of requests per minute - $R_i$. All requests are identical in terms of the amount of ...
3
votes
1answer
648 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
21 views

Finding an optimal way to distribute government aid cases across multiple government offices

Note, this is for a friend who is an actual government employee, very real world application here, and the implications could be much more far reaching than you might think. Solving this problem could ...
3
votes
1answer
65 views

How do computer programs find roots of high-degree polynomials?

My question is motivated by curiosity about the optimization of high-degree polynomial functions. Let's say your experiment data are modeled by a non-trivial 15th degree polynomial. Taking the ...
1
vote
1answer
21 views

l1 regularized minimization with equality constraint in ADMM

In section 6.3 of this note there is a method for minimizing a loss function with l1 regularization. i.e. minimize $l(\bf{x})+\lambda||x||_1$ How can I add the equality constraint $\sum\limits_{i} ...
2
votes
2answers
549 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
1answer
113 views

Normalized objective function in optimization problem

I have fairly standard linear optimization model with two objectives \begin{align*} \text{max}\, (f_1 &= 4x_1+5 x_2\,,\,f_2 = 1x_1 + 0x_2 ) \\ \text{subject to}& \\ 1x_1 + 1x_2 ...
1
vote
1answer
94 views

An optimal sequence of length 13

I'm looking for an optimal (or much better than I have now) increasing sequence $t_1, t_2, .., t_{13}: t_i \in N, 0 \le t_i<t_{i+1}$ where $3t_{12} + 4t_{13}$ is minimized, subject to the ...
0
votes
0answers
26 views

Obtaining zeroes in a matrix

I have a large matrix , with elements somewhere between 0 and 0.4 . I want to apply local unitaries, that is, unitary matrices of the form: $$U_{L} = U \otimes U \otimes U$$ in order to make my ...
2
votes
2answers
113 views

Finding minimum value of a function of two variables

I am given function $$ f(x,y)=Ax^2+2Bxy+Cy^2+2Dx+2Ey+F,\quad\text{where }A>0\text{ and }B^2<AC . $$ Prove that a point $(a,b)$ exists which $f$ has a minimum. I figured out that there is no ...
0
votes
1answer
25 views

Visualising the dual function

Consider the linear programming problem: min $-x_1-2x_2$ s.t. $3x_1+2x_2-6\leq 0$ $ -x_1+2x_2 -4\leq 0$ $0 \leq x_1 \leq 3/2, 0 \leq x_2 \leq 3/2$ Find the Lagrange dual objective function ...
1
vote
2answers
43 views

How to find the number of possible solutions of LP problems?

Let us assume that we have a linear optimization problem (LP) that has multiple optimal solutions. I would like to know if there is a solver or an algorithm that can provide the number of optimal ...
0
votes
0answers
29 views

How to find the maximum of this function of multiple variables?

Let $\mathbf{x}$ be a vector in $[a,b]^n\subseteq \mathbb{R}_+^n$ and $\mathbf{A}=[a_{ij}]$ a matrix in $\mathbb{R}^{k\times n}$. Let the rows of $\mathbf{A}$ be denoted by $\mathbf{A}_{i}$ for all ...
0
votes
0answers
42 views

Maximum of the product of two poisson mass functions

I have two questions regarding maximising the following function defined for $x, y \geq 0$: $f(x, y) = \displaystyle \sum_{i = 0}^{\infty} \frac{x^i e^{-x}}{i!} \frac{y^i e^{-y}}{i!}$ when $x, y > ...
2
votes
1answer
57 views

How to “separate” a matrix into two vectors?

I have a matrix $M$ and I would like to find two vectors $u$ and $v$, that minimize $$ \sum_{i,j} (M_{i,j}-u_iv_j)^2 $$ How can I do this (numerically)? Actually this is very simplified ...
0
votes
1answer
18 views

Limit the objective function in optimization

Is it correct to limit the objective function of an optimization problem sometimes? I heard we shouldn't limit the objective function at all. In other words, a namely problem like this, is possible? ...
0
votes
1answer
45 views

Why do high-frequency dynamics quickly go away in a step response?

As we know, a step input hits all the frequencies of a dynamical system. However, my professor told me today that the high-frequency response is only present for a short time at the very start, and ...
1
vote
1answer
33 views

Is my solution to this basic calculus optimization problem correct?

I needed assistance checking a solution to a calculus problem. Consider the graph of the function $f: [-\frac{\pi}{2}, \frac{\pi}{2}] \rightarrow \mathbb{R}$ given by $f(x) = \cos(x)$. Note that it ...
0
votes
0answers
19 views

Dynamic “Assignment Problem” (Hungarian Algorithm Extension?)

TL;DR: Trying to optimize assignments using Hungarian algorithm, but cannot determine costs until all assignments have been made due to dependencies. Using the terminology from Wikipedia's Assignment ...
0
votes
0answers
36 views

Solution of quadratic optimization with linear constraints

Hi, I want to solve a quadratic optimization problem defined as $\min \|\bf{a^T}\bf{x}\|^2_2$ $s.t. \|\bf{x}\|_1=1$ $\ \ \ \ \ \ \ \ x_i\ge0,\ i=0,1,...,n-1$ $\ \ \ \ \ \ \ \ \bf{b}^T\bf{x}-C\le0$ ...
1
vote
2answers
34 views

Maxima and Minima: $y = x^4$

Given a stationary point, I was taught to test if it was a maximum or a minimum using the concavity test, i.e. If $f''(x)>0$: concave up (thus a local minimum) If $f''(x)<0$: concave down ...
4
votes
1answer
45 views

Exercise 2.27 from Bazaraa (LP)

Consider the system $Ax=b$ where $A=[a_1,a_2,...,a_n]$ is an $m \times n$ matrix of rank $m$. Let $x$ be any solution of this system. Starting with $x$, construct a basic solution. There is a hint ...
2
votes
0answers
19 views

Is it possible to use regularization to minimize the (expected) number of non-zero digits in a number?

This question may be slightly related to this question on length of the representation of a number in a certain basis. Introduction / Background In image and video coding, particularly the ...
0
votes
0answers
30 views

Why is $f = f_{0} + \sum_{i}\alpha_{i}X_{i} + \frac{1}{2}\sum_{i}^{n} \sum_{j}^{n}A_{ij}X_{i}X_{j}$ the standard quadratic form in n dimensions?

The claim that $$f = f_{0} + \sum_{i}\alpha_{i}X_{i} + \frac{1}{2}\sum_{i}^{n} \sum_{j}^{n}A_{ij}X_{i}X_{j}$$ is the standard quadratic form for $n$ dimensions, where $\alpha$ is some $ 1 \times n$ ...
0
votes
1answer
33 views

Constrained optimization with alternates in special conditions

I have the following optimization problem. $$\max_{a b} acx+bdy+z \ \ \ \ \ \ $$ subjected to $$ c = \begin{cases} 1, & \text{if } 2xa-yb-z\geq 4\\ 0, & \text{if} \ 2ax<yb+z\\ ...
0
votes
0answers
22 views

constrained heat equation

Consider the following constrained minimum energy problem for 1-D heat equation for $x\in[0,1],t\in[0,\infty)$: $$u(x,t)=\underset{{0\leq u(x,t)\leq1}}{argmin}~\frac{\partial}{\partial ...
1
vote
3answers
80 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 ...
0
votes
0answers
29 views

Maximum area of a rectangle whose vertices lie on ellipse $x^2+4y^2=1$

Maximum area of a rectangle whose vertices lie on ellipse $x^2+4y^2=1$. I try to do it by lagrange multiplier as $F(x,y,t)= xy + t(x^2+4y^2-1=0)=0$. Differentiating w.r.t to x,y and solving i get ...
1
vote
0answers
31 views

KKT conditions for a convex optimization (optimal crowdsourcing with budget constraint)

I am having some troubles deriving the optimal solution of the following convex optimization problem, $w_j$, $c_{ij}$, and $B$ are fixed and non negative. \begin{align} & ...
1
vote
1answer
23 views

Penalty and minimization of a social cost

It is part of broader question in economics however it is about minimizing the expression (which depicts social cost of a crime): the expression is $$\min ...
0
votes
0answers
12 views

Maximization the difference of a monotone submodular function and a linear function with a cardinality constraint

I know maximizing a monotone submodular function with a cardinality constraint can be solved by a simple greedy heuristic with an approximation factor $1-1/e$. However, if the submodular function is ...
1
vote
2answers
54 views

Tangent line Exercise. $f (x) = 5e^{−(x−2)^2}$ . Find the coordinates of points where the hill is the most steep.

I have this exercise, look easy but I don't know where to start, I think that I need a extra function or value to continue with the calculus. Imagine that you are riding over a hill having its ...
0
votes
1answer
17 views

Multi-commodity flow problem. What if only one commodity? (Context: column generation)

What problem can arise when the number of commodities is only one when looking at a multi-commodity flow problem? This question was asked by my professor in the context of column generation and ...
4
votes
1answer
43 views

Common meeting point for 3 points to reach 4th point [closed]

Problem statement: We are 3 friends at 3 different locations $A, B, C$ and want to reach a location $D$. Each person will take a separate cab to a common meeting point $E$, and then take a single cab ...
0
votes
2answers
68 views

How can I solve the following linear program?

I want to find the answer for the following linear program. Max $v$ subject to $$v-5x_1-x_2 \le 0 $$ $$ v-x_1-4x_2 \le 0 $$ $$ v-2x_1-3x_2 \le 0 $$ $$ x_1+x_2 = 1 $$ $$ x_1, x_2 \ge 0 $$ $$ v \in R ...
0
votes
0answers
18 views

Neural network for regression

The way I understand regression for neural networks is weights being added to each x-input from the dataset. I want something slightly different. I want weights ...
2
votes
1answer
32 views

Add weights to inputs of x-value function to optimize regression [closed]

Say I have $n$ functions (not the regression function) each with $n$ inputs. These functions compute the x-values. The function is a simple summation function where the input is multiplied by a ...
1
vote
1answer
41 views

Find local maximum or minimum in 2 variable function

So, I encountered a question (don't worry it's not H.W.) where I have a function with two variables, and I need to find local maximum / minimum points if exists. (More precisely, it is a utility ...
0
votes
2answers
22 views

Kuhn-Tucker's Conditions for optimization problem with non linear inequalities constraints

My problem is to minimize the function \begin{align*} f(x,y,z,t)=& 3 t \left(2 x^2+4 x z\right) \left(2 t x y+t x z-2 t y^2-2 x z+4 y z\right) \\ &+\left(-t x^2+4 t x y+4 t y z+4 x z-8 y ...
2
votes
2answers
70 views

Otimization on a city with infinite many traffic lights.

Province Ave has infinitely many traffic lights, equally spaced and synchronized. The distance between any two consecutive ones is $1500m$. The traffic light stay green for 1.5 minutes, red for 1 ...
0
votes
0answers
21 views

Modification of a proof to work for an LP in inequality form

Suppose an LP is given in the inequality form : $\max\langle c,x\rangle$ subject to $Ax\leq b$. We call $x$ a basic feasible solution to this problem if there are $n$ linearly independent inequalities ...
0
votes
1answer
35 views

Find two integers that satisfy a property

The finite sequence of integers $Y_1, \dots, Y_M$ takes both positive and negative values, where $M$ is a fixed positive integer. Could you help me to find a formulation using dynamic programming that ...
0
votes
0answers
10 views

Neural network to optimize function weights

I have a problem that I believe a neural network could accomplish. I have a plot of data. The y values are straight forward values, but the x-values are computed. The function to compute the ...
2
votes
1answer
105 views

Simplex method - identity matrix

I want to solve the following linear programming problem: $$\min (5y_1-10y_2+7y_3-3y_4) \\ y_1+y_2+7y_3+2y_4=3 \\ -2y_1-y_2+3y_3+3y_4=2 \\ 2y_1+2y_2+8y_3+y_4=4 \\ y_i \geq 0, i \in \{ 1, \dots, 4 ...
1
vote
1answer
39 views

Apply Simplex method using M-method

I want to solve the following linear programming problem: $$\min (3y_1-y_2+2y_3) \\ 3y_1+2y_2-y_3 \leq 9 \\ 5y_2-y_3 \leq 1 \\ 4y_1-y_2 \geq 1 \\ y_1+y_2+y_3 \leq 3 \\ y_1, y_2, y_3 \geq 0$$ In this ...
0
votes
0answers
15 views

HMM optimization: Lagrange multiplier problem

In David Barber's textbook "Bayesian Reasoning and Machine Learning" he hints at the derivation of the Baum-Welch algorithm for HMM parameter learning: Textbook excerpt, (cannot include images yet, ...
2
votes
1answer
746 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 ...
0
votes
0answers
22 views

How to solve the following convex constrained optimization problem?

\begin{equation}\label{constrained optimization} \begin{aligned} \min\limits_{\mathbf{X}}&\|X_{(1)}\|_{*}+\|X_{(2)}\|_{*}+\|X_{(3)}\|_{*}+\lambda\|Ax-b\|_2^2 &\ \ s.t. X_{ijk}=M_{ijk}\ \ ...