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.
19,471
questions
0
votes
0answers
2 views
Multi-Stage Combinatorial Optimization
I am not sure if I used the corret terminology. I think the problem is a multi-stage combinatorial optimization problem. The problem is like this:
There is a dynamic equation
$$
S_{k+1} = f(S_k,\pi_k)
...
2
votes
0answers
9 views
Understanding Karush-Kuhn-Tucker conditions
Suppose we may want to use the K–T conditions to find the optimal solution to:
\begin{array}{cc}
\max & (\text { or } \min ) z=f\left(x_{1}, x_{2}, \ldots, x_{n}\right) \\
\text { s.t. } & g_{...
1
vote
0answers
18 views
Determining the number of switching times in a bang-bang control with nonlinear switching function
In optimal control, if the Hamiltonian $H$ is linear in the control $u$, then the optimality condition
$$\frac{\partial H}{\partial u}$$
gives no information about the optimal control $u^*$. The way ...
0
votes
1answer
50 views
Can we tell if ANY Function is Convex or Non-Convex?
Reading the mathematical definition of convexity (https://en.wikipedia.org/wiki/Convex_function), it seems that there is a relatively clear definition as to what makes a function "convex":
...
0
votes
1answer
26 views
Why is this symmetric rank one update "the symmetric solution that is closest?"
Trying to understand symmetric rank one updates and there is this like in the Wikipedia page that says...
A twice continuously differentiable function $x\mapsto f(x)$ has a
gradient ($\nabla f$) and ...
1
vote
0answers
16 views
Discretization of the Optimization Problem
Say that $g:[0,1] \rightarrow \mathbb{R}$ is a smooth function that has a unique maximizer.
Let $x_1,\cdots,x_n$ be a set of equally spaced points on $[0,1]$.
Question: How close does the discretized ...
0
votes
0answers
18 views
Lipschitz Continuity of the Value Function [duplicate]
Suppose that $g:[0,1]^2 \rightarrow \mathbb{R}$ is a smooth function. Define the value function
$$ g^*(x) = \max_{t \in [0,1]} g(x,t). $$
Question: Under what conditions would $g^*$ be a Lipschitz ...
2
votes
2answers
146 views
Can this Minimization Problem be Proved through Induction?
Consider the following function (this function has $n$ dimensions):
$f(x_1,...,x_n)=10n+\sum_{i=1}^n(x_i^2-10\cos(2\pi x_i));\quad -5.12\leq x_i\leq 5.12$, $\text{minimum at }f(0,...,0)=0$.
Using ...
2
votes
0answers
17 views
Interpretation of "Noise" in Function Optimization
I am trying to better understand the meaning of "noise" with regards to function optimization - specifically, why "Noisy" functions are more difficult to optimize compared to "...
0
votes
1answer
25 views
Minimization of basis pursuit using ADMM
This note describes how to perform Basis Pursuit using the ADMM method. I am confused about how to map the general algorithm given in the note for this particular context. Can someone explain how it ...
4
votes
0answers
35 views
Optimization with inner product condition
I designed an optimization problem to improve the performance of the neural network learning process on the gradients. I spent hours, but unfortunately it did not work out.
Given vectors ${\bf a}_1, {\...
0
votes
0answers
22 views
How to adjust a probability over time while gaining more information? (bayesian statistics)
I'm struggling with a probability problem at work, which I need to understand more in order to devise an algorithm. It seems like a problem typically suited for a bayesian approach, but after hours on ...
1
vote
2answers
79 views
Simply Put - Are Most Functions in the "Real World" Non-Convex?
Is it "safe" to say that natural phenomena in the real world are often characterized and modelled by functions exhibiting irregular and complicated behaviors, and such functions are almost ...
1
vote
0answers
40 views
Is there a such thing called the "Classic Convergence Theorem"?
Has anyone heard of the "classical convergence theorem" before?
I tried searching online for this theorem but couldn't really find anything.
My Question: Does this theorem have a different ...
5
votes
1answer
94 views
Do we have any way of knowing if natural phenomena in the real world follow the "Lipschitz Condition"?
Recently, I keep coming across terms containing "Lipschitz" pertaining to statistical models and machine learning. This includes terms such as "p-lipschitz (rho), lipschitz convexity, ...
-1
votes
1answer
34 views
simple linear programming problem with integer constraints
Given positive numbers $a, b, c, d, e$, how do I find the maximum value of $ax + by$ such that $cx + dy \leq e$ and $x, y$ are non-negative integers?
0
votes
0answers
35 views
Identification Problem
I want to find the parameters $A_{n\times n}$ and $B_{n\times m}$ of this model: $$x(k+1) = Ax(k) + Bu(k),$$
$\textbf{what I know}:$ $x_{n\times1}(k)$ is a vector of theoretical data, $u_{m\times 1}(k)...
3
votes
0answers
75 views
+50
Uniform convergence of objective function implies convergence of minimizers
Let $A,A_h\in M_{n\times m}(\mathbb{R})$ be $n\times m$ matrices with $\Vert (A-A_h)x\Vert\leq h^2 \Vert x\Vert$ for $h\in (0,1)$ and $e\in \mathbb{R}^n$.
Now consider for a fixed $\lambda>0$ the ...
0
votes
0answers
39 views
Newton-Raphson method convergence criteria for a system of two equation with two unknowns
I am having a system of two non-linear equations and I want to compute the root. For example the system is
$$f_1(x,y)=0 \tag{1}$$
$$f_2(x,y)=0.\tag{2}$$
In this post, it is shown that the root of the ...
0
votes
2answers
32 views
Convergence of Optimization Algorithms on Non-Convex Functions
Have any major results been established on the use of gradient descent for optimizing non-convex and noisy functions?
It seems like the majority of the desirable properties of gradient based ...
-1
votes
0answers
22 views
Lagrange multipliers - 3 constraints for Max and Min [closed]
Can anyone help me on this topic, please!
Find the maximum and minimum values of the function
f(x,y)=2x^2+2y^2
subject to the constraints x≥0,y≥3 and x+y≤8.
Thank you in advance !!
2
votes
3answers
53 views
Find $a$ such that ${x_1}^2+{x_2}^2$ takes the minimal value where $x_1, x_2$ are solutions to $x^2-ax+(a-1)=0$ DO NOT USE CALCULUS
My thinking:
Let $x_1 = \frac{a+\sqrt{a^2-4a+4}}{2}$ and $x_2 = \frac{a-\sqrt{a^2-4a+4}}{2}$
By the AGM (Arithmetic-Geometric Mean Inequality):
We have
$x_1\cdot x_2\le \left(\frac{x_1\cdot \:x_2}{2}\...
1
vote
0answers
29 views
Finding $\max_{0\leq x\leq3} |f'(x)|$, $\max_{0\leq x\leq3} |f''(x)|$, and $\max_{0\leq x\leq3} |f^{(4)}(x)|$ numerically
In an numerical analysis project I need as an intermediate step to calculate the following:
$$\max_{0\leq x\leq3} |f'(x)|,\ \ \max_{0\leq x\leq3} |f''(x)|\ \ \text{and}\ \ \max_{0\leq x\leq3} |f^{(4)}...
0
votes
0answers
8 views
Finding Hilbert Basis of a cone
This is more of a general question, I don't necessarily have a specific question I've been given.
Part of one of my modules includes finding Hilbert Basis of cones; a question I'm given might look ...
2
votes
1answer
55 views
If $\ z_k\ $ are complex numbers, sort of uniformly spread out on the unit circle, then what is $\ \sup \{\ \vert z_0 + \ldots + z_{n-1} \vert\ \}\ ?$
Let $\ n\in\mathbb{N}\ $ and suppose $\ z_k = x_k + iy_k,\ $ where $ \vert z_k \vert = 1\ $ and $\ \frac{2k\pi}{n} < \arg(z_k) < \frac{2(k+1)\pi}{n}\quad $ for all $\ k\in \{ 0,\ \ldots,\ n-1 \}....
0
votes
1answer
25 views
Convex function inequality with eigenvalues of Hessian matrix are bounded above and away from zero
We have a twice continuously differentiable function $f:\mathbb{R}^d\to\mathbb{R}$ and $\mu,L>0$ constants
We have $\mu\cdot E\preccurlyeq\nabla^2f(x)\preccurlyeq L\cdot E$. that means that the ...
0
votes
1answer
25 views
How to show that an optimization problem is equivalent to the Least Squares problem?
I hope you guys can lend me a hand with this one.
Let $A\in \mathbb{R}^{m\times{n}}$ and $b\in \mathbb{R}^{m}$, and consider the following optimization problem:
$\min_{x\in\mathbb{R}^{n}} \max_{y\in\...
0
votes
1answer
31 views
Why do the derivatives of a function lead towards the extremum of the function?
Is there some theorem in mathematics that formalizes the idea that "for some function, at a given point, moving in the negative direction of the gradient leads you to some (local) extremum point&...
1
vote
0answers
21 views
Minimum of the Rastrigin Function
In the context of Optimization, the Rastrigin Function is used as a popular example to the test the ability of different Optimization Algorithms to find the global minimum of this function. This ...
0
votes
0answers
4 views
Can you check if a boundary point is a local constrained maxima with SO sufficient conditions?
Consider the problem of maximizing some continous $f(x,y)$ subject to the following two non-negativity constraints $g_1,g_2$ and an equality constraint $h$:
$g_1=-x\leqslant0,g_2=-y\leqslant0,h(x,y)=...
1
vote
2answers
91 views
Let $a,b\in \mathbb{R}$ such that $ab=2$. Find the max value of $\frac{3}{2\left(a+b\right)^2}$ and $a, b$ where max is attained, without calculus.
My thinking:
By Arithmetic and Geometric mean inequality (AGM):
$ab\le \left(\frac{a+b}{2}\right)^2$
We know $ab=2$
$\rightarrow$ $2\le \left(\frac{a+b}{2}\right)^2$
$\rightarrow$ $2\le \frac{a^2+b^2}...
0
votes
0answers
26 views
Bounded convex function on a non-compact set
Let $f : A \rightarrow \mathbb R$ where $A \subset \mathbb{R}^n$ is an unbounded (but closed) convex set. If $f$ is bounded and convex, can we say anything about the extremum of it?
For $n=1$ and $A=\...
0
votes
0answers
11 views
Generators of a polyhedral cone and half spaces
I'm told that $A = \begin{pmatrix}
-6 & 1 & 5\\
0 & 0 & -1 \\
1 & -5 & 4
\end{pmatrix}
$ and I want to find the generator of the polyhedral cone: $C=${$x \in \mathbb{R}^3: Ax\...
0
votes
1answer
22 views
Optimization problem for competition design
My question is about a particular constrained optimization problem, but the problem is motivated by a hypothetical.
Motivating story: I'm organizing a competition where $n$ players will play $d$ ...
-1
votes
1answer
29 views
Supporting hyperplance theorem proof. [closed]
I've read the proof of supporting hyperplane theorem here (page 5 in pdf) I have some questions regarding the proof, that are not clear for me now.
Also I include the proof image here:
Why $\{x_k\} ...
1
vote
0answers
14 views
Constrained Calculus of Variations: minimise surface area given volume enclosed
I wish to find a curve $u(x)$ (symmetrical about the y-axis), such that the surface area of revolution about the x-axis:
$$A[u]=2\pi \int_{x_1}^{x_2} u(x) \sqrt{1+u'(x)^2} dx$$
is minimised.
The ...
1
vote
0answers
17 views
Convex Relaxation Problem (theory )
I was wondering if any of you folks could help me with this optimization problem. I want to show if I find a solution $X^*$ for $(P'')$ for which $rank(X ^* ) = 2$, then $X ^* = uu^T $. Here is the ...
1
vote
0answers
22 views
Closed form solution for an $\ell{1}$ optimization problem with a quadratic constraint and bounded variables
Consider the following optimization problem
$$
\min \lVert{x}\rVert_{1} \quad\text{s.t} \quad \lVert{y - Ax}\rVert_2 \leq \varepsilon \quad \text{and} \quad x \in [0,1]^n,
$$
where $A \in \mathbb{R}^{...
0
votes
0answers
20 views
Find scale factors to maximize images size
I have two images with dimensions $w_1 \times h_1$ and $w_2 \times h_2$ respectively. I want to display them in a screen of size $w_{screen} \times h_{screen}$. My goal is to resize those images with ...
0
votes
0answers
16 views
Orthogonality leading to a simpler optimization problem (procrustes, Stiefel manifold)
I have seen somewhere doing the following "trick" to simplify an optimization problem. I would like to understand the logic behind it.
Take two matrices $A$ and $B$ of dimension $N \times N$ ...
4
votes
1answer
64 views
Derivative of Mahalanobis pairwise distance matrix respect to transformation matrix
For a set of vectorial observations $x_i$ stored in the matrix $X$, I would like to obtain the gradient of the pairwise Mahalanobis distance matrix $D$ with respect to the Mahalanobis transformation ...
0
votes
0answers
58 views
Finding minimizer of sum of quadratic matrix form minus log(det(X))
I am looking to solve the following problem. The first task is to comment on the convexity/concavity of the problem and then I need to compute minimizer of the problem.
$$\min f \left( \Psi \right) = ...
0
votes
1answer
26 views
Importance of the KKT Conditions
Does anyone know why the KKT Conditions are considered such a fundamental result in optimization?
As far as I understand, the KKT Conditions appear to be a set of conditions that if satisfied - ...
0
votes
1answer
15 views
Solving linear equation with max min function
For a particular problem, I got some equations of the form
$a = \min(1-b,0.9)$
$b = \max(\min(1-a,0.7)$, $\min(c, 0.8))$
$c = \max(\min(1-a,0.9)$, $\min(1-c, 0.9))
a,b,c \in [0,1]$
The system has a ...
1
vote
0answers
26 views
Using repeated/higher-order prefix sums (cumulative sum/scan) to calculate fast linear combinations
A few years ago, I learned certain algorithms that use "prefix sums" (also called cumulative sums) for calculating certain array operations in a faster way.
For example, if your input array $...
0
votes
0answers
20 views
finding the range in which a function is positive
I have the functions $ f(v) = w-\frac{wz}{z+v}$ and $g(v) = \frac{xy}{y-v}-x$ where all the variables are constants except $v$. I need to find the range of values of $v$ in which
$g(v)-f(v) >0$
how ...
1
vote
0answers
9 views
Notating an (arg)max relative to some ordering
Suppose we want to write an expression stating that $x$ satisfies the property $f(x) \geq f(x'), \forall x' \in X$. A fairly common way of doing this in optimization and economics literature is
$$ x \...
3
votes
1answer
52 views
Minimum Distance between a kitten and a puppy moving on a coordinate plane
At time $t= 0$, the kitten is at $(1,0)$ and the puppy is at $(-1,0)$. The kitten starts walking counterclockwise along the unit circle, and the puppy runs right along the $x$-axis. If the puppy's ...
0
votes
0answers
12 views
How to implement waiting time in objective function time violation?
I would like to build an objective function for the vehicle platoon problem. the objective function called minimize time violation.
vehicle platoon means trucks travelling in a straight line to reduce ...
0
votes
4answers
70 views
Why does $df(x,y)=0$ imply that $\frac{\partial f}{\partial x}=0$ and $\frac{\partial f}{\partial y}=0$?
When finding "critical points" of a multivariable function, we look for the argument of the function where the function's derivative is zero, e.g. $\arg_{x,y \ \in \ \mathbb{R}} \min{f(x, y)}...
