# Fundamentals of Optimization

{% hint style="info" %}

#### Definition 23

The standard form of optimization is

$$p^\star = \min\_\mathbf{x} f\_0(\mathbf{x}) \text{ such that } f\_i(\mathbf{x}) \leq 0$$
{% endhint %}

* The vector $$\mathbf{x}\in\mathbb{R}^n$$ is known as the **decision variable**.
* The function $$f\_0:\mathbb{R}^n\to\mathbb{R}$$ is the **objective**.
* The functions $$f\_i:\mathbb{R}^n\to\mathbb{R}$$ is the **constraints**.
* $$p^\star$$ is the **optimal value**, and the $$\mathbf{x}^\star$$ which achieves the optimal value is called the **optimizer**.

{% hint style="info" %}

#### Definition 24

The feasible set of an optimization problem is

$$\mathcal{X} = {\mathbf{x}\in\mathbb{R}^n:\ f\_i(\mathbf{x}) \leq 0 }$$
{% endhint %}

{% hint style="info" %}

#### Definition 25

A point $$\mathbf{x}$$ is $$\epsilon$$-suboptimal if it is feasible and satisfies

$$p^\star \leq f\_0(\mathbf{x}) \leq p^\star + \epsilon$$
{% endhint %}

{% hint style="info" %}

#### Definition 26

An optimization problem is strictly feasible if $$\exists \mathbf{x}\_0$$such that all constraints are strictly satisfied (i.e inequalities are strict inequalities, and equalities are satisfied).
{% endhint %}

## Problem Transformations

Sometimes, optimizations in a particular formulation do not admit themselves to be solved easily. In this case, we can sometimes transform the problem into an easier one from which we can easily recover the solution to our original problem. In many cases, we can introduce additional “slack” variable and constraints to massage the problem into a form which is easier to analyze.

{% hint style="info" %}

#### Theorem 7 (Epigraphic Constraints) <a href="#theorem-7" id="theorem-7"></a>

$$\min\_\mathbf{x} f\_0(x)$$ is equivalent to the problem with epigraphic constraints

$$\min\_{\mathbf{x}, t} t \quad : \quad f\_0(x) \leq t,$$
{% endhint %}

Theorem 7 works because by minimizing $$t$$, we are also minimizing how large $$f\_0(x)$$ can get since $$f\_0(x) \leq t$$, so at optimum, $$f\_0(x) = t$$. It can be helpful when $$f\_0(x) \leq t$$ can be massaged further into constraints that are easier to deal with.

{% hint style="info" %}

#### Theorem 8 (Monotone Objective Transformation) <a href="#theorem-8" id="theorem-8"></a>

Let $$\Phi:\mathbb{R}\to\mathbb{R}$$ be a continuous and strictly increasing function over a feasible set $$\mathcal{X}$$. Then

$$\min\_{\mathbf{x}\in\mathcal{X}}f\_0(\mathbf{x}) \equiv \min\_{\mathbf{x}\in\mathcal{X}} \Phi(f\_0(\mathbf{x}))$$
{% endhint %}

## Robust Optimization

For a “nominal” problem

$$\min\_\mathbf{x} f\_0(\mathbf{x}) \quad : \quad \forall i\in\[1,m],\ f\_i(\mathbf{x}) \leq 0,$$

uncertainty can enter in the data used to create the $$f\_0$$ and $$f\_i$$. It can also enter during decision time where the $$\mathbf{x}^\star$$ which solves the optimization cannot be implemented exactly. These uncertainties can create unstable solutions or degraded performance. To make our optimization more robust to uncertainty, we add a new variable $$\mathbf{u}\in\mathcal{U}$$.

{% hint style="info" %}

#### Definition 27

For a nominal optimization problem $$\min\_\mathbf{x} f\_0(\mathbf{x})$$ subject to $$f\_i(\mathbf{x}) \leq 0$$ for $$i\in\[1,m]$$, the robust counterpart is

$$\min\_\mathbf{x} \max\_{\mathbf{u}\in\mathcal{U}} f\_0(\mathbf{x}, \mathbf{u}) \quad : \quad \forall i\in\[1,m],\ f\_i(\mathbf{x}, \mathbf{u}) \leq 0$$
{% endhint %}


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://aparande.gitbook.io/berkeley-notes/eecs127-0/eecs127-2.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.