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,318
questions
1
vote
1answer
28 views
How to minimise given function?
Let a is fixed $f:R^{n^2}\times R^n\to R$ such that $f(A,u)=u^TAu+a^Ta$ where $A$ is a symmetric, invertible matrix. Find $u$ such that $f$ attains the minimum for that $A$.
I know that suppose f ...
0
votes
2answers
37 views
The real numbers $x,y$ and $z$ are such that $x-7y+8z=4$ and $8x+4y-z=7$. What is the maximum value $x^2-y^2+z^2?$
The real numbers $x,y$ and $z$ are such that
$x-7y+8z=4$ and $8x+4y-z=7$. What is the maximum value of $x^2-y^2+z^2?$
From those equations I got:
$12z-5x=13y$
$12x+5z=13$
$12y+5=13z$
$12-5y=13x$
...
0
votes
0answers
9 views
How to minimize a scalar cost function over two parameters spaces?
I wish to find out an analytical expression that minimizes a scalar cost function over two parameter spaces. Lets say I have a scalar cost function defined as:
\begin{equation}
\begin{split}
\hat{e}=...
1
vote
0answers
10 views
subgradient of composition
Are there general rules or references of subgradient of composition? For example, consider the composition $f(x)=h(g(x))$ where $h$ is convex nondecreasing and $g$ is convex, then the subgradient of $...
1
vote
1answer
11 views
Constrained Optimization / derivative on curves equal zero / convergence
Consider the minimization Problem
$$\min_{v\in\mathbb{R}^d\ :\ ||\boldsymbol{v}||=1} f(v)$$
where $f$ is smooth.
Let's define the sequence $\boldsymbol{v}_n$ by
$$\alpha_n=\operatorname{argmin}_{\...
3
votes
1answer
21 views
Rewrite a max-min Problem by partitioning the domain
Consider the following max-min problem:
$$\sup_{x\in D_{X}}\inf_{y\in D_Y} f(x, y),$$
where $f:D_{X}\times D_{Y}\to \mathbb{R}$.
Assume that $D_{Y}$ can be partitioned into $k$ disjoint union of sets ...
2
votes
2answers
37 views
Minimizing the error for a second degree interpolating polynomial
Construct the second degree polynomial $q_2(t)$ that approximates $g(t) = \sin(\pi t)$ on the interval [0,1] by minimizing
$$\int_0^1 [g(t) - q_2(t)]^2dt$$
A useful integral: $\int_0^1 (6t^2-6t+1)^...
0
votes
0answers
19 views
Given three integers A,B,C, how to find number of positive integral solutions of $a*b>c^2$ with a,b,c having upper bounds A,B,C resp.
A and B can be as large as $10^9$. However, $C$ is given to be within 5k types.
I tried writing a code, but it's in $O(A*C)$ and it's taking a huge time when $A, C$ exceeds say $5k$.
1
vote
0answers
37 views
Harmonic Sum Associated with a Partition
Let $\mathcal{X}$ be a finite set. Let $\mathcal{A} = \{A_1,\dots,A_N\}$, where $N\le |\mathcal{X}|$, be a partition of $\mathcal{X}$. Define
$$\small
H(\mathcal{A}) = 1+\frac{1}{2}+\dots + \frac{1}{|...
0
votes
0answers
25 views
Minimizing $L^1$ Norm Subject to Linear Dynamics
Suppose $u\in\mathbb{R}^m$, $x\in\mathbb{R}^n$, and define the linear dynamics of the system as
$$
\dot{x} = Ax+Bu
$$
The problem that I am trying to solve is
$$
\min_{\|u\|_{\infty} \leq 1} \...
1
vote
0answers
21 views
Proof of convergence of projected gradient descent via induction
Background
I'm working through the "The constrained case" in section 3.2 of Bubeck's Convex Optimization: Algorithms and Complexity. The part I'm confused about is the proof of Theorem 3.7:
Let $f$...
0
votes
3answers
54 views
Find the shortest distance between a line and a parabola
Given the two curves,
$$ x - y - 3 = 0$$
$$ x + (y+2)^2 = 0$$
How do i find the shortest distance between the two?
My solution: find a point on the first line,
x1 = 6, y1 = 3
find the point on ...
2
votes
1answer
23 views
Separating hyperplane from a set to an outer point
Hello I am trying to find an equation for a separating hyperplane to the set $S$ from an outer point $y$ defined as:
$S=\{x: x_{1}^{2}+x_{2}^{2}+x_{3}^{2}\le4, x_{1}^{2}-4x_{2}\le0\}$ and $y=(1,0,2)^{...
1
vote
0answers
16 views
Solution is unbounded, optimization problem in Matlab after modification.
The solutions seems to be unbounded even if the array A is changed to [-4 1 5; 4 1 5; 1 1 1];
Anything wrong with syntax. Could not figure out.
Any help.
0
votes
0answers
10 views
Proof verification - Show that the following optimization problem has solution
I want prove that the following optimization problem has solution
$$min_{x \in \mathbb{R}^n} ||x||_{q, \epsilon}^{q} + \dfrac{1}{2\rho}\left\|Ax -b\right\|^2_2$$ where $||x||_{q, \epsilon}^{q}=\sum_{...
0
votes
0answers
23 views
A simple question about S-procedure
In the appendix of Convex Optimization book (by Boyd and Vandenberghe) the following is written about the S-procedure.
The implication $$x^TF_1x+2g_1^Tx+h_1\leq 0,~~x^TF_2x+2g_2^Tx+h_2\leq 0$$ where $...
0
votes
0answers
35 views
What is the best smooth approximation of the two-variables absolute function $f=|x|+|y|$?
I would like to use the approximation of $f=a_x|x|+a_y|y|$ in my finite-element procedure, where $a_x$ and $a_y$ are constants and $x$ and $y$ are the unknowns that are subject to minimization in the ...
0
votes
2answers
42 views
Finding optimal way to steer a system to origin with input constraints
For the system $$\ddot{x}+x=u$$ with $\|u\| \le 1$, find the optimal way to steer the system from
(a) $(x(0),\dot{x}(0))$ to $(0,0)$
(b) $(x(0),\dot{x}(0))$ to $x=0$
and minimize $$\...
0
votes
0answers
16 views
Maximization over function
I'm trying to solve the following problem
\begin{align}
\max_{P(t),\bar{v}}~\int_0^{T}\left\{\int_{\bar{v}-P(t)}^{\bar{v}}G(u)du\int_{\bar{v}}^{v_m}f(v)dv
+\left(\int_{P(t)}^{\bar{v}}\int_{0}^{v-P(t)}...
0
votes
0answers
13 views
Over-complete dictionary and sparse basis selection optimisation problem
I am trying to solve the following problem:
Given the matrix $T \in \mathbb{R}^{D \times N}_{\geq 0}$, find matrices $U \in \mathbb{R}^{D \times K}_{\geq 0}$ and $W \in \mathbb{R}^{(D+K) \times N}_{\...
0
votes
0answers
16 views
Solving and optimizing a vector equation for time
I have a parameterized function of 3-d vectors defined as:
$$
t(A\vec{u} - \vec{v}) = \vec{p}
$$
Where $t$ is time, $\vec{u}$ is a variable vector, $A$ is a scalar constant, and $\vec{v}$ and $\vec{p}$...
0
votes
0answers
26 views
How to solve the problem which is a sum of convex and nonconvex functions?
I attempt to solve an optimization which is a sum of two convex functions and one non-convex function described as follows:
$$g(x,y) = a{\log_2}{\left( {1 + x} \right)} + b\log_2 \left[ 1 + c(x - dy) ...
0
votes
1answer
21 views
Find an optimal solution formula from multiple variables analytically
If I have an optimization problem as follows:
\begin{equation}
\label{eqn:for3b}
\begin{aligned}
(\mathbf{P}_1) \phantom{10} & \max_{\boldsymbol{\pi}} \phantom{5} \sum_{i=1}^I\pi_i(a_i - b_i).
\...
0
votes
1answer
42 views
If a saddle point is on the boundary, is it a local extremum?
Consider the function $f(x)=x^4-4x^3$, which has a saddle point when $x=0$. Now, define the same function on $[0,10]$. How to characterize $x=0$ now? Is it a local extremum (local maximum)? I am ...
3
votes
3answers
74 views
How to find a point on a line that minimizes sum of distances from three given points?
This is a cross-post of a question on MathOverflow where it didn't get much attention: https://mathoverflow.net/questions/337892/how-to-find-a-point-on-a-line-that-minimizes-sum-of-distances-from-...
0
votes
0answers
19 views
Maximum Likelihood via the Chain Rule
So I have a random variable with the pdf:
$$ z \sim N( g(\tau), \sigma_{z}^{2}) = p(z | g(\tau))$$
With $g(\tau)$ a concave function (ie one global maximum). I want to find the maximum likelihood ...
0
votes
0answers
29 views
Constraint on derivative of decision variable
I would like to address an optimization problem where the derivative of one of the decision variables is constrained. Specifically, let $x,y,z$ be time-dependent vector-valued variables and we want to ...
1
vote
1answer
24 views
Managing requests competing for my resource
I have a blog that has a good following within my specific industry. I have until now kept it Ad free but now wish to entertain offers.
I currently have three separate offers each with a different ...
1
vote
1answer
23 views
Remove fixed variable from quadratic program
I have a convex quadratic optimization problem with $n+1$ variables $x_i$
$$\text{minimize}\,f(x)=x^Tc+\frac{1}{2}x^TQx$$
$$s.t.$$
$$Ax=a$$
$$Bx\leq b$$
with exactly two equality constraints
$$x_1=-...
1
vote
1answer
45 views
How can we solve this simple linear program?
Let $$a:=\begin{pmatrix}.2&.1\\.7&.05\end{pmatrix}$$ and $$b:=\begin{pmatrix}.01&.9\\.4&.3\end{pmatrix}.$$ I want to maximize $$\sum_{ij}a_{ij}\min(x_i,b_{ij}y_j)$$ subject to $x_1,x_2,...
2
votes
0answers
57 views
Finding maximum value of function when $\frac{dy}{dx}=0$ is too complex to solve.
I came across this question regarding the maximum of the Lemur population.
We are supposed to do this without the use of any graphing software.
I have differentiated the function but it still ...
1
vote
0answers
33 views
Compare Lipschitz constants for Two different Functions
This is about Lipschitz constant and a function $f$ is defined and continuous on an interval $[a,b]$, and is differentiable on the interior $(a,b)$ and $x,y \in [a, b]$. I understand you can write:
$$...
0
votes
1answer
29 views
Optimal monthly contribution towards debt vs. savings
Starting with:
\$0 in savings and \$50000 in debt
the savings earns 2.5% interest and the debt loses 5% interest yearly
you gain \$2000 of income each month to distribute among either savings or debt ...
0
votes
0answers
14 views
Minimizing a multivariable function with respect to one variable
Consider $f(x,a,b,c) = \sqrt{1+ax} - \sqrt{1+bx} + cx$. All variables are positive, and as of right now, $b>a$ and $b>c$, possibly much larger than all of them. Keeping $a$, $b$, $c$ fixed, I'd ...
1
vote
1answer
20 views
Finding the smallest set containing sums of pairs from the set
Let $n \in \mathbb{N}$ be a positive integer. Can you find one of the smallest sets $S \subset \mathbb{N}$ containing $n$ such that $1 \in S$, and for every $c \in S, c \neq 1$, there exist $a \in S$ ...
1
vote
1answer
32 views
Where can I find a (well-documented) simple solver for linear optimization problems with both equality and inequality constraints?
I need to solve a linear optimization problem subject to both equality and inequality constraints in C++ (using MSVC 15). Mathematically, this can be solved by the simplex algorithm. Since I don't ...
0
votes
0answers
10 views
A maximization problem involving random variables
Consider random variables $X$ and $Y$ that are jointly normally distributed,
$$
\begin{pmatrix} X \\ Y \end{pmatrix} \sim \mathcal{N}
\left[
\begin{pmatrix} \mu_X \\ \mu_Y \end{pmatrix} ,
\begin{...
6
votes
3answers
100 views
+250
How to solve a “foraging” problem on a directed graph?
I'm a little squirrel living in a forest with, say, eight trees $A,B,C,\ldots,H$. I can jump from tree to tree, though not all jumps are possible. (The fact that I can jump from $A$ to $B$, for ...
1
vote
1answer
38 views
Why is minimizing the Heaviside step function a combinatorial problem?
I was going through this lecture on ML Youtube @ 59:28 and the Heaviside step function as a loss function was introduced and two things were mentioned:
The function is not convex, so stay away if ...
1
vote
1answer
13 views
Intuition behind Diffuse Interface models in image processing
I am reading an article entitled "Diffuse Interface Models on Graphs for Classification of High Dimensional Data." Seems like the idea is to use the Ginzburg-Landau functional, in association with ...
0
votes
0answers
9 views
What is the performance difference between the Total Variation norm and Dirichlet energy norm in image processing
I have been looking at some image processing material lately, and see that two common norms are the Total Variation norm and the Dirichlet energy--also called the $H^1$ seminorm. Now these norms look ...
0
votes
0answers
16 views
Solving very very large equation for minimum with variable constraints.
We are trying to find a way to solve the following problem.
We need to find a way to formalise and then solve for a minimum a very large (~100 million variables) simultaneous equation with the ...
0
votes
1answer
41 views
Equality constrained non-negative linear least squares
I have the following constrained linear least-squares problem:
$$\min_{x \in \mathbb{R}^n} \frac{1}{2}||Ax-b||_2^2,$$
$$\text{subject to } \sum_{i=1}^n x_i = 1 \text{ and } x_i \geq 0, \text{ for } ...
0
votes
0answers
29 views
What is the minimum of the function $[0,1]\to[0,\infty), \lambda \mapsto e^{-aλ^2}+e^{-b(1-λ)^2}$, where $a>b>1$
Doing some estimates in machine learning, I stumbled into minimizing the following function:
$$f :[0,1]\to[0,\infty), \lambda \mapsto e^{-aλ^2}+e^{-b(1-λ)^2},$$ where $a>b>1$. However, imposing ...
1
vote
1answer
25 views
Difference between arbitrary Evolutionary and Genetic Algorithm
I'm new to this site. I am not really sure if this the right section for this question - it might belong to computer science.
Recently I started working on my master thesis about solving multi-...
0
votes
0answers
19 views
Multi objective optimizations with the same constraints
I have two objective functions $f_1(x_1)$ and $f_2(x_2)$. The optimization problems are as follows:
\begin{equation}
\begin{aligned}
(\mathbf{P}_1) \phantom{10} & \underset{x_1,x_2}{\text{max}} \...
1
vote
1answer
17 views
Writing the arguments of solution function of $\max_x F (z+y-x,x,x-y)$ [on hold]
Suppose that we wanted write an expression for the function that gives the $x$ which solves $$\max_x F (z+y-x,x,x-y),$$
for any given parameters $y,z$.
Is there a reason to write this function as
$$
...
5
votes
1answer
48 views
Proof Verification: Showing a function is affine if its convex and concave
I know this question has been asked several times but the answers don't really make sense to me (I'll explain misunderstandings:)
Question: Suppose that a function $f: \mathbb R^n \rightarrow \mathbb{...
0
votes
0answers
42 views
Optimization: Symmetric function with 3 variables
Solve
$$
\max_{x,y,z \in (0,1)} [f(x,y,z)+g(x,y,z)],
$$
where
$$
f(x,y,z):= - \bar{x}\bar{y}z \log \frac{\bar{x}\bar{y}z}{\bar{x}\bar{y}z+\bar{x}y \bar{z}+x\bar{y}\bar{z}} - \bar{x}y \bar{z} \log \...
1
vote
0answers
46 views
In optimization, what guarantees the existence of a minimizer?
Uniqueness of minimizer for a problem of the type $\min f(x), x \in \mathcal{C}$, $\mathcal{C}$ convex, is that $f$ is strictly convex.
I am curious what is the theorem that gives existence of such a ...
