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)

2
votes
0answers
41 views

Optimizing potential

Let $X$ be a vector field on a Riemmanian manfiold $M$. I recently read that solving: \begin{equation} \operatorname{argmin}_{\phi}\int_M (\nabla \phi - X)^2 d\mu, \end{equation} where $\mu$ is ...
-1
votes
1answer
38 views

Finding the global minimum

Let $f~:~\Bbb R^2\to \Bbb R$ be defined as: $$f(x)=\left\|\begin{bmatrix}2&1\\3&1\\4&2\end{bmatrix}\begin{bmatrix}x_1\\x_2\end{bmatrix} - \begin{bmatrix}2\\1\\7\end{bmatrix}\right\|_2^2$$ ...
2
votes
1answer
199 views

Least-squares problem with quadratic equality constraint

I want to find the solution of a Lagrange equation whose inputs are matrices. First I have the equation Ax=0. By decomposing $A$ into $A_3$ (columns 9 to 11 of A), $A_9$ (the rest of the columns), ...
0
votes
2answers
56 views

Is Frank Wolfe a descent algorithm?

A colleague was explaining to me that the Frank-Wolfe algorithm is a descent algorithm (i.e. its objective value decreases monotonically at each iteration). However, when I tried simulating it, my ...
2
votes
0answers
98 views

Maximum value of $(1-F(t))t$ for probability distribution

Consider a continuous distribution on $(0,1)$ with cumulative distribution function $F$. For the value of $t\in(0,1)$ that maximizes $$P(t)=(1-F(t))t,$$ what is the lower bound of $P(t)$? For example, ...
1
vote
1answer
1k views

Smooth approximation of maximum using softmax?

Look at the Wiki page for Softmax function (section "Smooth approximation of maximum"): https://en.wikipedia.org/wiki/Softmax_function It is saying that the following is a smooth approximation to the ...
0
votes
0answers
18 views

Optimally superimposing two shapes

I have two sets of points, let's say, $Y$ and $X$. Each set has exactly $N$ elements, and each element $element$ is such that $element \in I\!R^{d}$. That is, I have two shapes with $N$ $r-\text{...
3
votes
0answers
81 views

Optimal cyclic permutations (Formulate as standard problem)

How can we find cyclic permutations $\prod_i$ to be applied to each of corresponding $i$'th rows of a square matrix $X$ of size $n \times n$ such that a given sum of pairwise costs $\sum_{ij}C\left[\...
0
votes
1answer
35 views

Minima of symmetric polynomials subject to two symmetric constraints

The homogeneous symmetric polynomial of degree $k$ in $n$ variables is $$ f_k(x_1,x_2,\dots,x_n) = \sum_{i_1<i_2<\cdots<i_k}x_{i_1}x_{i_2}\cdots x_{i_k}. $$ Consider the following ...
-1
votes
0answers
15 views

Deciding on supermarket daily orders given a fixed amount of money

I have completely no idea even where to start from, and I am sure this question has been discussed already, simply I need some key words and methods that solve this problem so that to start my survey. ...
0
votes
0answers
90 views

Solutions to recurrence relations

Consider functions $s_{m},c_{m},d_{m}$ defined by the following recurrence relations $$s_{1}=n$$ $$c_{1}=s$$ $$d_{1}=0$$ $$s_{2}=n$$ $$c_{2}=s-n$$ $$d_{2}=d$$ $s,n, d$ are integers. If $c_{m}>...
1
vote
1answer
37 views

Why the local optimum of this problem is always global?

I am reading the paper "Continuous methods for extreme and interior eigenvalue problems" by G.H. Golub and L.-Z. Liao. The papers says for the following problem, (Lemma 2.1 (i), $0>\lambda_i-c\ge \...
3
votes
1answer
161 views

Least squares with a quadratic inequality constraint

Is there a closed form solution for the following least squares problem: $$ \min_\mathbf{x}\|\mathbf{a+Bx}\|^2 ~~\text{s.t}~~\|\mathbf{x}\|^2 \leq \alpha^2$$ where $\mathbf{a} \in \mathbb{C^{M\times 1}...
0
votes
1answer
50 views

Find a least upper bound for $3^{x+y-4}+(x+y+1)2^{7-x-y}-3(x^2+y^2)$ with some constraint?

This is a question in vietnamese national math exam at the end of 12th grade. Given x,y are real numbers which satisfy the condition: $x+y+1=2(\sqrt{x-2}+\sqrt{y+3})$ Find a $m$ such that: ...
1
vote
0answers
16 views

Notation for arguments that maximize functions with priority

Suppose we have some functions $f_1(x), f_2(x), \ldots, f_n(x)$ with $x \in \mathbb{Z}^n$. We can denote the subset $X_1$ of $\mathbb{Z}^n$ that maximizes $f_1(x)$ as: $$X_1 = \underset{x \in \...
1
vote
1answer
24 views

Problem about find the extreme of a function (Multipliers of Lagrange)

Good morning, i have a problem with this: Find the maximum and minimum distances from the origin to the curve $g\left(x,y\right)=5x^{2}+6xy+5y^{2}$ I make this: Function to optimize: $f\left(x,y\...
0
votes
0answers
31 views

Negative bounds on variables in Linear Programming formulation

I am new to optimization theory and encountered the following problem: I am reviewing a formulation for a network problem that is fed into a mathematical solver and I noticed that on the "bounds" ...
0
votes
1answer
44 views

Optimize wrt a partial matrix?

I have a common optimization problem $$\arg\min_A \text{tr}( A^TWA),$$ where $W$ is a positive semi-definite matrix, and $A$ is the matrix to be optimized. If $A$ is completely unknown, with some ...
4
votes
1answer
59 views

Maximizing $\frac{\int_r^1xf(x)dx}{2-F(r)}$

Consider a continuous distribution on $(0,1)$ with probability distribution function $f$ and cumulative distribution function $F$. Define $$g(r)=\frac{\int_r^1xf(x)dx}{2-F(r)}$$ and let $r_M\in(0,1)$ ...
2
votes
2answers
4k views

Optimization of the surface area of a open rectangular box to find the cost of materials

A rectangular storage container with an open top is to have a volume of 10 cubic meters. The length of the box is twice its width. Material for the base costs ten dollars per square meter and for the ...
2
votes
1answer
35 views

IF statement as Linear Constraint

I am writing a linear program, but I am currently having troubles writing a certain constraint, which is basically an IF-statment. I will try to explain it as detailed as possible: IF: $x_{it'}(t' +...
0
votes
0answers
19 views

Impact of convexity under different changes of variables for different parts of optimization

Let $$ \min_x f(x)$$ such that $$ C(x) \le 0$$ where $C$, and $f$ each are convex under respective changes of variables. How does that impact the optimization? If standard algorithms are sensitive ...
0
votes
0answers
37 views

If the primal is unbounded, then the dual is infeasible.

In the context of duality in linear programming, prove that If the primal is unbounded, then the dual is infeasible. My book says that this is a corollary to complementary slackness. What's ...
0
votes
0answers
60 views

optimal, infeasible, degenerate solutions

Note that $c_i$'s in the $z_j-c_j$ row are not coefficients of the $x_i$'s. I use instead: $r_1, r_2, r_3$. I'm assuming there's a non-negativity constraint. we need to state necessary ...
12
votes
3answers
289 views

Variable leaving basis in linear programming - when does it happen?

In the simplex algorithm in linear programming, what are conditions for a variable to leave a basis (not necessarily basis for the/an optimal solution)? I'm supposed to list as many sufficient and ...
0
votes
0answers
9 views

How to find initial values when optimizing functions of ODEs?

I want to reproduce parts of a paper and therefore have to optimize a function $f(A,B)$, where $A$ and $B$ are the solutions of the following system of ODEs: $$\frac{d}{dt}A = c_1F + \nu_{\beta} -...
2
votes
1answer
42 views

Solve the closed form solution for argmax of $ x^Ty - x^T\ln(x)$

Let $y \in \mathbb{R}^n, \ln(x) = \begin{bmatrix} \ln(x_1) \\ \vdots \\ \ln(x_n) \end{bmatrix} \in \mathbb{R}^n$ Show that $$x^* = \text{argmax}_{x \in \mathcal{D}} \quad x^Ty - x^T\ln(x)$$ ...
0
votes
0answers
38 views

Minimum value will be attained by same z

Let $y=\left(\begin{array}{c}y_1\\y_2\\\vdots\\y_n\end{array}\right)$ be a fixed non zero vector in $R^n$. Let $S \subset R^n \setminus\{0,y\}$ is a finite set. Suppose $$min\big\{\sum_{i=1}^{n}{|y_i-...
0
votes
2answers
798 views

Optimization, rectangle inscribed inside arch of the curve.

A rectangle is to be inscribed under the arch of the curve $y = 4\cos(0.5x)$ from $x = \pi$ to $x = -\pi$. What are the dimensions of the rectangle with largest area, and what is the largest area? ...
2
votes
2answers
263 views

using the kronecker product and vec operators to write the following least squares problem in standard matrix form

I have a least squares problem with the following form: $$ \min_\mathbf{X} ~ \sum_{i=1}^n | \mathbf{u}_i^\top \mathbf{X} \mathbf{v}_i - b_i |^2 $$ where $\{\mathbf{u}_i\}_{i=1}^n$ and $\{\mathbf{v}...
0
votes
2answers
29 views

Optimization of the function of two variables

I have two functions $f(x,y)$ and $g(x,y)$. I want to minimize the sum of these functions w.r.t $x,y \in (0,1)$. I know that for fixed values of $x$, $f(.,y)$ is a decreasing function while $g(.,y)$ ...
-1
votes
1answer
15 views

Sum of convex and decreasing function

I have a sum of decreasing function and a convex function over some domain. Can I say that the sum is also a convex function (i.e. there exists a unique minimum)?
1
vote
1answer
36 views

Maximize the number of non zero elements of a product of binary matrices.

I want to find two binary matrices $A$ of size $N \times M$ and $B$ of size $M \times N$ such that: $AB=C$ is a strictly lower-triangular matrix ($j \geq i \implies C_{ij}=0$) The number of ...
0
votes
1answer
32 views

How to find the analytical solution of this optimization problem?

I have an optimization problem of the form $$\begin{align} \text{maximize}\quad&\sum_{i=1}^{k}\sum_{j=1}^{n}w_{ij}x_{ij}\\\text{s.t.}\quad \quad\quad\,\,& \sum_{i=1}^{k}x_{ij}\leq 1,\;\forall ...
3
votes
1answer
68 views

Team grouping troubles

Imagine there are 12 teams, numbered 1 through 12. There are 10 games those teams can compete in, with two teams needed per game. There are 10 rounds, and it is important that after the 10 rounds are ...
0
votes
0answers
24 views

Find rotation matrix to match points in parallel projection

I am given two sets of 3D points (actually 2D, see below) with corresponding pairs. I am seeking two 3D rotation matrices, such that (only) the X and Y components of the rotated points match best (...
6
votes
1answer
1k views

Why does SVD provide the least squares solution to $Ax=b$?

I am studying the Singular Value Decomposition and its properties. It is widely used in order to solve equations of the form $Ax=b$. I have seen the following: When we have the equation system $Ax=b$, ...
1
vote
2answers
36 views

Maximizing the sum of the squares of numbers whose sum is constant

I wonder how one goes about to find the maximum of $\sum v_i^2$, the $v_i$'s being positive integers whose sum $\sum_i v_i$ is fixed.
0
votes
0answers
17 views

Solving $I^* = \arg\min_{I'} \left( \|\phi_\ell(I) - \phi_\ell(I')\|_2^2 + R(I') \right)$ with gradient descent

I am trying to create the results from this a paper that is trying to understand the types of features a convolutional neural network is learning to recognize. I don't think understanding ...
0
votes
1answer
14 views

In Constrained Optimization, Restrict Domain to Open Set $A\subset\mathbb{R^N}$?

In constrained optimization and context of economics (e.g. utility function with quantity of goods as arguments subject to wealth), why do textbooks always restrict domain of the objective function ...
0
votes
1answer
461 views

How to solve for maximum area of a rectangle under a curve?

Having trouble with this optimization question and was hoping I could get some help with it. The function of the curve is $8^{-\frac{x}{5}}$. I would greatly appreciate a full explanation. I already ...
0
votes
0answers
15 views

Solve $ \max U = [\sum\limits_{i = 1}^2 {a_i^{{1 \over \sigma }} } \cdot X_i^{{{\sigma - 1} \over \sigma }} ]^{{\sigma \over {\sigma - 1}}} $

The problem is $$ \eqalign{ & \max U = \left[\sum\limits_{i = 1}^2 {a_i^{{1 \over \sigma }} } \cdot X_i^{{{\sigma - 1} \over \sigma }} \right]^{{\sigma \over {\sigma - 1}}} \cr & \...
0
votes
0answers
17 views

Momentum Potential Term in Optimization Problem for Implicit Euler Solver

I'm trying to understand the explanation of the implicit Euler solver (Section 3.1) set forth in this paper: Projective Dynamics: Fusing Constraint Projections for Fast Simulation For the purposes of ...
2
votes
0answers
35 views

Finding a maximum with some constraints

I would like to maximize the term $ l_1b_1+l_2b_2+l_3b_3-2 $ such that the following conditions hold: $ 1>l_1>l_2>l_3>0 $, $ l_1,l_2,l_3 \in \mathbb{Q} $, $ b_1,b_2,b_3 \in \mathbb{N} $...
0
votes
1answer
35 views

Is sup of max, same as max of sup?

Let $\sigma_1, \sigma_2 \dots \sigma_n$ be functions of $\omega \in \mathbb{R}_+$. Is $\sup_{\omega}(\max_{i=1:n} (\sigma_i))$ same as $\max_{i=1:n}( \sup_{\omega}(\sigma_i))$? Could you also please ...
1
vote
4answers
55 views

$\cos2\theta +\cos\theta +k = 0 $ - set of all values of $k$ for which there is a solution

The set of all values of $k$ (real), such that the equation $\cos2\theta +\cos\theta +k = 0 $ admits a solution for $\theta$ is? MY ATTEMPT: I substituted $\cos2\theta$ with $2\cos^2\theta - 1 $. On ...
1
vote
1answer
46 views

Are minimizing a function and root finding the same?

What is the relationship between minimizing a function and finding a root of an equation? Are the the same? I know in both problem we have similar algorithms, such as gradient decent, or newton's ...
0
votes
0answers
16 views

How to find the maximal length of a system?

Let P be the set of $(a,b,c)^t \in \mathbb{R}$ which satisfies the following inequalities: $-2a+b+c \leq 4$ $a-2b + c \leq 1$ $2a + 2b-c \leq 5$ where $a \geq 1 $, $b \geq 2$, and $c \geq 3 $. ...
4
votes
2answers
55 views

Maximizing product of five-digits numbers

From a French 2016 puzzle and math contest, where no calculator is allowed Using each of the digits $0,1,2,3,4,5,6,7,8,9$ exactly once, find two five-digit integers such that their product is ...
0
votes
0answers
11 views

Direction of a gradient at maximizer on the boundary

Let $u \in C(\bar{B})$ where $B=B_1(0) \subset \mathbb{R}^n$ is the unit ball. Assume $u$ attains its maximum at $x_0 \in \partial{B}$ and $\nabla u(x_0) \neq 0$. What can we say about the direction ...