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.

Filter by
Sorted by
Tagged with
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 ...