Questions tagged [optimization]
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.
14,752
questions
0
votes
0answers
3 views
Benchmark/standard bang-bang optimal control example
So I was just curious if someone could give me a reference of a standard bang-bang control problem. I would very much like a problem where there is an analytic solution for the state and the control. ...
0
votes
0answers
7 views
Related Rates/Optimization Help
(This is a weird one) - (given information comes after question $1(b)$
$1(a)$ You're listening to country music and drinking a beer in your above ground pool/watering trough shaped like an inverted ...
0
votes
0answers
8 views
Gradient Descent with constraints?
I trying to minimize this objective function.
$$J(x) = \frac{1}{2}x^THx + c^Tx$$
First I thought I could use Newtown's Method, but later I found Gradient Descent, which is more suitable for this ...
0
votes
0answers
5 views
Cross validation multivariate kernel regression in R
This question is general- I have a data set of n observations, consisting of a single response variable y and p regressor variables ( here, n ~50, p~3 or 4).
I am planning to implement Nadaraya-Watson ...
0
votes
1answer
18 views
Show that Lagrange multiplier is the optimal value
I am trying to solve the following problem.
Minimize $$f(x,y) = x^2 + y^2$$
Subject to $$g(x,y) = ax^2 +2bxy +cy^2-1 = 0$$
$$(x,y)\in\mathbb{R^2}$$
Where $$a>0,c>0,2b>a+c$$
a) Use Lagrange ...
0
votes
0answers
2 views
Measurability of the Knothe-Rosenblatt (rearrangement) transport map in Optimal Transport
Allow me to explain the setup first:
Let $\mu(dx_1,dx_2) = f(x_1,x_2)dx_1dx_2$ and $\nu(dy_1,dy_2) = g(y_1,y_2) dy_1dy_2$ be two probability measures on $(\mathbb{R}^2, \mathcal{B}(\mathbb{R}^2))$ (...
1
vote
0answers
39 views
Permutation with largest odd order
Let $S_n$ denotes symmetric group of $n$ symbols. What is the maximal odd order of permutation in $S_n$?
In other words, what is the value of $\max\{\text{ord }\sigma : \sigma\in S_n, \text{ord }\...
0
votes
0answers
17 views
similar to landau's function, but all elements are odd
Everyone knows about landau's function, then I was curious about the lcm of partition "n" which element's are all odd numbers.
for example:
$$8=3+5 \Rightarrow f(8)=15$$
$$19=3+5+11 \Rightarrow f(...
0
votes
0answers
17 views
Matrix optimization to maximise coverage
Apologies if I am framing the question wrong, but I am trying to solve the following problem.
I have a dataset in excel with companies going down and various indicators across the columns. I am ...
0
votes
0answers
28 views
A question about multivariable calculus and optimization
My question contains a lot of heuristics, and a tad of rigor, so bear with me.
Consider the function $f(x) :\mathbb{R}\rightarrow \mathbb{R}$, such that $f(x)\geqslant 0\; \forall x\in \mathbb{R}$, ...
1
vote
0answers
21 views
Kalman filter: Bayesian derivation, can $E(X_t\mid \{y\}_1^t)=arg\,\underset{x_t}{max} \; P(X_t=x_t\mid \{y\}_1^t)$?
Looking for a rigorous derivation of Kalman Filter, i eventually come up with this two derivations:
Derivation of Kalman Filtering and Smoothing Equations
Kalman Filtering: A Bayesian Approach
The ...
0
votes
2answers
22 views
Optimize absolute value $\min |x| + |y|$
How do you convert $\min |x| + |y|$ to a linear program?
Is this method correct?
$$\min w + z$$
$$w >= x$$
$$w >= -x$$
$$z >= y$$
$$z >= -y$$
0
votes
1answer
16 views
(Kind Of) Maximising the Variance of a Hypergeometric Distribution
I am playing around with a hypergeometric distribution.
Consider an urn with $N$ balls with $R$ red balls and $B$ blue balls. Where $1\leq n\leq N$ is a sample size, and $m\in(0,1]$ a margin of ...
0
votes
1answer
16 views
Minimize SSE function
Consider a data set in which each target $t_n$ is associated with a weighting factor $r_n > 0$, so that the sum-of-squares error funtion becomes
$$SE(w)= \frac{1}{2} \sum_{n=1}^N r_n \left(\...
2
votes
2answers
27 views
Maximization of quotient of quadratic forms
I have a problem with finding:
$$\max_{a \in \mathbb{R}^p} \frac{a’Ca}{a’Ba},$$
where $C$ and $B$ are $p \times p$ symmetric matrices.
After differentiation I get the following result:
$$\frac{2a’...
0
votes
0answers
19 views
Univariate LASSO
Consider the problem $$\min_{x\in\mathbb{R}}\left\{f(x)\equiv\frac{1}{2}||ax-y||_2^2+\lambda|x|\right\}$$ where $\lambda\geq 0,x\in\mathbb{R},a,y\in\mathbb{R}^m$ are given.
Assume that $y\ne 0$ and $...
0
votes
1answer
20 views
what's the solution to $\underset{x}{argmin}(\frac{1}{2\lambda}||x-\gamma_k||^2_2+\lambda_0||Bx||_1)$
$$\arg\min_x \left( \frac{1}{2\lambda} \|x-\gamma_k\|^2_2 + \lambda_0 \|Bx\|_1 \right)$$
where $\lambda_0,B,\lambda,\gamma_k$ are known, and $x \in \mathbb R^{n\times 1}$. Is there a closed form ...
0
votes
1answer
21 views
Can anyone explain what is the pseudoconcave or pseudoconvex in easier way to me?
I have searched " pseudoconvex" in wiki: https://en.wikipedia.org/wiki/Pseudoconvex_function
However,i still don't understand what is this,the wiki said every convex is pseudoconvex,but the converse ...
0
votes
1answer
20 views
Finding endpoints for radius of cylinder when optimizing surface area
I was working on an optimization problem for minimizing the surface area of a cylinder given that the volume is fixed at $1500 cm^3$. I found the critical point and classified it as a minimum of the ...
1
vote
1answer
46 views
LMI-constrained least-squares problem in Mosek
I want to solve a least-squares problem of the form:
$$\begin{array}{ll} \text{minimize} & \|Ax-b\|_2^2\\ \text{subject to} & \mathcal{L}(x)\succeq0\end{array}$$
with $\mathcal{L} : \mathbb{...
0
votes
0answers
20 views
Derivation of Minimax game equation
GANs were introduced with as two networks playing the minimax game. The notation used in the original paper was this one:
We want our discriminator to be very good ...
0
votes
0answers
13 views
Maximization with positive semidefinite constraints
I need to solve the following optimization problem
$$
\begin{matrix}
\max_{w, \alpha} & & \alpha \\
\mathrm{s.t.} & & w(P - \alpha Q)w \geq 0, \\
& & \alpha \geq 0, \\
& &...
0
votes
0answers
17 views
Robbins Monro algorithm applied to the MLE for mean of a sequence of gaussian random variables
I'm studying the stochastic approximation algorithms, in particular the Robbins-Monro algorithm.
I have the next exercice that my teacher gave us.
Problem:
We observe a sequence of identically ...
0
votes
1answer
16 views
Is it necessary to add the non-active constraints within the Lagrangian for solving a convex optimization problem?
Suppose we have a convex optimization problem as below $$\min~~ f_0(x)$$ $$\text{s.t. }f_1(x)\leq 0\\ f_2(x)\leq 0\\ \vdots \\f_{m-1}(x)\leq 0\\ f_m(x)\leq 0.$$ Suppose we know, through some way, ...
0
votes
1answer
40 views
An Application of Farkas' Lemma
The Farkas' lemma I know is:
Exactly one of the following systems has a solution.
\begin{equation}
\left\{
\begin{array}{l}
Ax=b,\ x\geq0 \\
A^Ty\geq0, \ y^Tb<0
\end{array}...
1
vote
0answers
16 views
finding maximum of a sum of a fraction including ceil function in its denominator
I'm trying to find the maximum of the sum $$\sum_{i=1}^n \frac{i}{(\lceil \frac{i}{r} \rceil + 1)r}$$ where $\frac {n}{M} \leq r\leq 1 $ and $n\leq M$ and M is a known integer.
Since the fraction ...
0
votes
0answers
18 views
How to prove the inequality (3.19) in book Numerical Optimization?
I will briefly introduce the problem here.
$\theta_k$ is the angle between the chosen descent direction $p_k$ and the steepest descent direction $-\nabla f_k $, that is
\begin{equation} \cos \...
1
vote
1answer
34 views
Smallest radius sphere intersect with the quadric surface
There is a sphere equation:
$${x_1}^2 + {x_2}^2 + {x_3}^2 = R^2.$$
A quadratic surface, given by level $C$ and a set of parameters $a, e, i$, has formula:
$$a {x_1}^2 + e {x_2}^2 + i {x_3}^2 + C = ...
0
votes
0answers
10 views
Minimizing Disttance Between 2 Points on 2 Distinct Elliptical Orbital Functions
The objective is to find the minimum distance from a point $(A_1, P_1, \phi_1)$ on the first orbit to a point $(A_2,P_2, \phi_2)$ on the second orbit. For a measure of distance we can use the function
...
0
votes
0answers
48 views
How to walk from north pole to south pole during daylight while minimizing the max speed?
If we started out at fall equinox, ignoring revolution of the earth and assuming the earth is perfectly spherical, one need to walk from $\varphi = 0$ to $\varphi = \pi$ while maintaining that $0<\...
0
votes
0answers
18 views
function parameterization with known sums!
I want to find a function, let's say $y= a x + b$ but I don't have sample $(x,y)$ pairs but what I have is samples of following form $((x_1, x_2, ..., x_n), \sum_{i=1}^n y_i)$ where n is also a known ...
0
votes
0answers
25 views
Silo Lagrange optimisation.
I am looking at lagrange questions and I am stuck on where to start with this question. I understand you have to get the constraint but I'm not exactly sure on what to do after that part? Any help is ...
0
votes
0answers
6 views
the effects of adding a position function the minimization of problem without constraint
Considering the problem of minimusation without constraint following :
$$
(P_1)~:~Min_{w\in\mathbb{R}^2 }~~E(w)
$$
With $w=(w_1,w_2)$.
We add the term :
$$
H (w)= \sum_{i=1}^{2}{\frac {(w_i / \...
7
votes
3answers
163 views
Find the smallest value of the following expression $\sqrt{(x-9)^2 +4} + \sqrt{x^2+y^2}+ \sqrt{(y-3)^2 +9}$
Find the smallest value of the following expression:
$$\sqrt{(x-9)^2 +4} + \sqrt{x^2+y^2} + \sqrt{(y-3)^2 +9}$$
I tried to derive the expression with respect to $x$ and $y$ and then equal the ...
0
votes
0answers
14 views
How do I create a cost function based on the Little's law?
Little's law states that L = λ.W, where L is the average number of items in a queue, λ is ...
1
vote
0answers
12 views
deciding to insert a variable a to the basic set in the next step and exclude 𝒂 basic one 𝒃
Let's say you are in the middle of applying the Simplex Method to an LP problem. You've reached a tableau and by checking the sign of the objective coefficients you decided to insert a variable a to ...
0
votes
0answers
10 views
Roto-translation optimization to minimize the volume between two surfaces
I have not huge knowledge about continuous optimization problems, but I'm addressing an interesting task and I'm not sure if it is feasible or not.
I have a pair of surfaces, say $\mathcal{S}_1$ and $...
0
votes
0answers
19 views
Show that Each LP problem in standard form enjoys the following three properties? [on hold]
a. if LP problem has no optimal solution, then it is either infeasible or unbounded?
b. if LP problem is feasible, then it has a basic feasible solution?
c. if LP problem has an optimal solution, ...
1
vote
0answers
10 views
How to create a penalty function in two dimensions for a profile curve?
I have a computer model that models a physical process that is represented by the black line shown in the attached figure Desired Result. A traditional penalty function would compare the individual $Y$...
0
votes
1answer
41 views
Backtracking Line Search Algorithm - Why make $a$ smaller every time?
I am studying line search methods and I stumbled upon the "backtracking algorithm" for calculating a step length $a_k$ that gives a sufficient decrease in our function. To actually compute this ...
0
votes
1answer
11 views
exists r > 0 such that ∇2f (x) > 0 for any x ∈ B(x0,r).
Let f : U ⊆ Rn → R be a twice continuously differentiable function. Let x0 be an interior point of U such that ∇^2f(x0)> 0(hessian). Prove that there exists r > 0 such that ∇2f (x) > 0 for any x ∈ B(...
2
votes
2answers
38 views
Why is this limit equivalent to the max? [duplicate]
Reading this paper on the Adam optimizer, I can't see how the step from equation 10 to 11 happens... (https://arxiv.org/pdf/1412.6980.pdf)
0
votes
0answers
33 views
Struggling to find a convex formulation of a bilinear constraint
I've run into a wall in formulating a convex program for finding equilibria in an economic model I've been working on. I have one bilinear/quadratic constraint left that is getting in my way. Any ...
0
votes
0answers
13 views
Optimization with positive slope solution
Provided the following parameters:
1. $c_{n}$ and $c_{0}$ are known constants and can't be optimized
2. $c_{1}$ through $c_{n-1}$ are bounded by $[c_{0},c_{n}]$
3. $ \forall(c_{i} - c_{i-1}) \geq 0$ ...
0
votes
0answers
10 views
how does method of multipliers solve the problem of unboundedness of lagrangian and non differentiability of dual problem
$L_ρ(x,z,y) = f(x) + y^T (Ax − b)+\frac{\rho}{2}||Ax - b||2$
$g(y) = \text{min}_x\{L_ρ(x,y)\} $
Method of multipliers claims to have good convergence properties but I wonder how it solves the ...
1
vote
0answers
35 views
Linear transformation of overdetermined linear system
Assume that we have the following over-determined linear system
\begin{cases}
z_{1}=c + \phi z_0\\
z_{2}=c + \phi z_{1}\\
\dots\\
z_{n} = c + \phi z_{n-1}
\end{cases}
with $n>2$ and all $z_{0}, \...
0
votes
0answers
27 views
TSP with revenue maximization [on hold]
How to approach a travelling salesman problem with an aim to maximize revenue at each town visited in a certain number of days (total number of towns is greater than what can be visited in the given ...
0
votes
0answers
22 views
why do we need complementary slackness in KKT conditions?
I am quite confused about complementary slackness in KKT Conditions.
here are my series of questions
why do we need complementary slackness?
does strong duality implies complementary slackness? if ...
2
votes
1answer
29 views
Approximate Change of Basis Matrix/ Solution to Algebraic Riccatti System
Let $B,Q,P$ be compatible matrices. Is there a closed-form solution to
$$
\|PBB^TP^T -M\|_{F}=0;
$$
where $F$ is the Frobenius norm.
Ideas:
Solve the simplified algebraic Riccati equation
$$
PBB^...
0
votes
0answers
11 views
Suppose that f is quadratic with Hessian Q. We choose dk+1 = γkgk+1 + dk. Find a formula for γk
Consider the following algorithm for minimizing a function f:
x(k+1) = x(k) + αkdk, where αk = arg minα≥0 f(x(k) + αdk). Let gk = gradient of f(x(k)).
Suppose that f is quadratic with Hessian Q. We ...
