Artificial Intelligence: Representation and Problem Solving Optimization

Slide Note

This lecture explores optimization and convex optimization in the field of Artificial Intelligence, covering topics such as defining optimization problems, discrete and continuous variables, feasibility, and different types of optimization objectives. The content delves into the challenges and solutions involved in optimization, providing insights into various functions and algorithms used to find optimal solutions in both combinatorial and continuous spaces.

emersynn Follow

Uploaded on Mar 06, 2025 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.

Download Presentation

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.

E N D

Presentation Transcript

Artificial Intelligence: Representation and Problem Solving Optimization (1): Optimization and Convex Optimization 15-381 / 681 Instructors: Fei Fang (This Lecture) and Dave Touretzky feifang@cmu.edu Wean Hall 4126 1 3/6/2025

Logistics Complete the CMU 'course hours worked' survey 2 Fei Fang 3/6/2025

Recap What we have learned so far Search & Satisfiability in discrete space 8-queen, Graph coloring, 3-SAT, Finite options This section: Generalize to discrete / continuous space 3 Fei Fang 3/6/2025

Outline Optimization Convex Optimization 4 Fei Fang 3/6/2025

Optimization Problem: Definition Optimization Problem: Determine value of optimization variable within feasible region/set to optimize optimization objective min ? s.t. ? ?(?) Optimization variable ? ? Feasible region/set ? Optimization objective ?: Optimal solution: ? = argmin ?(?) ? Optimal objective value ? = min ? ?(?) = ?(? ) 5 Fei Fang 3/6/2025

Optimization Problem: Definition min ? s.t. ? ?(?) Optimization variable ? ? Discrete variables: Combinatorial optimization Continuous variables: Continuous optimization Mixed: Some variables are discrete, and some are continuous 6 Fei Fang 3/6/2025

Optimization Problem: Definition min ? s.t. ? ?(?) Feasible region/set ? Unconstrained optimization: = ? Constrained optimization: ? Find a feasible point ? can already be difficult 7 Fei Fang 3/6/2025

Optimization Problem: Definition min ? s.t. ? ?(?) Optimization objective ?: ? ? = 1: Feasibility problem Simple functions Linear function ? ? = ??? Convex function (this lecture) Complicated functions Even can be implicitly represented through an algorithm which takes ? as input, and outputs a value 8 Fei Fang 3/6/2025

Optimization Problem: Definition min ? s.t. ? ?(?) Minimization can be converted to maximization (and vice versa) max ? s.t. ? Same optimal solution Optimal objective value ? = ? ? ? = ?(?) 9 Fei Fang 3/6/2025

Optimization Problem: Example min ? s.t. ? ?(?) Example: Traveling Salesman Problem (TSP) Problem: ? cities, distance from city ? to city ? is ?(?,?), find a tour (a closed path that visits every city exactly once) with minimal total distance Variable ?: ordered list of cities being visited ?? is the index of the ?? city being visited Feasible set ? = {?:each city visited exactly once} ? = {?:? 1..??; ?? ??= ? = 1, ? {1..?}} Objective function ? ? =total distance when following ? ? 1? ??,??+1 + ?(??,?1) ? ? = ?=1 10 Fei Fang 3/6/2025

Optimization Problem: Example min ? s.t. ? ?(?) Example: 8-Queens Problem Variable ?: location of the queen in each column ?? is the row index of the queen in ?? column Feasible set ? = {?:no queens in the row, col, diag} ? = {?:? 1..88;?? ??,|?? ??| |? ?|, ?,? {1..8}} Objective function ? ? = 1 (dummy) Variable ??,??: index of row and column of the i? queen Feasible set ? = {?,?:no queens in the row, col, diag} ? = {?,?:?,? 1..88; ?? ??= ? = 1, ? {1..8}; ?? ??= ? = 1, ? 1..8 ; ?? ?? ?? ??, ?,? 1..8 } Objective function ? ? = 1 (dummy) 11 Fei Fang 3/6/2025

Optimization Problem: Example ?? ?? 1.0 2.0 3.5 2.1 3.98 7.0 Example: Linear Regression Problem: Find ? such that ?? ???, ? = 1..3 Variable ? Feasible region Objective function ? ? ? 3 3 2 min ? |?? ???| min ? ?? ??? ?=1 s.t. ? ?=1 s.t. ? 12 Fei Fang 3/6/2025

Optimization Problem: How to Solve No general way to solve Many algorithms developed for special classes of optimization problems (i.e., when ?(?) and satisfy certain constraints Convex optimization problem (CO) Linear Program (LP) (Mixed) Integer Linear Program (MILP) Quadratic program (QP), (Mixed) Integer Quadratic program (MIQP), Semidefinite program (SDP), Second-order cone program (SOCP), Existing solvers and code packages for these problems Cplex (LP, MILP, QP), Gurobi (LP, MILP, MIQP), GLPK (LP, MILP), Cvxopt (CO), DSDP5 (SDP), MOSEK (QP, SOCP), Yalmip (SDP), 13 Fei Fang 3/6/2025

Optimization Problem: Why Useful Why formulate problems as optimization problems? For many class of optimization problems, algorithms or algorithmic frameworks have been developed Decouple representation and problem solving Lazy mode Formulate a problem as an optimization problem Identify which class the formulation belongs to Call the corresponding solver Done! 14 Fei Fang 3/6/2025

Convex Optimization: Definition Convex Optimization Problem: min ? s.t. ? ?(?) An optimization problem whose optimization objective ? is a convex function and feasible region is a convex set A special class of optimization problem 15 Fei Fang 3/6/2025

Convex Optimization: Definition Convex combination A point between two points Given ?,? ?, a convex combination of them is any point of the form z = ?? + 1 ? ? where ? [0,1] When ? (0,1), ? is called a strict convex combination of ?,? ? ? ? 16 Fei Fang 3/6/2025

Convex Optimization: Definition Convex set Any convex combination of two points in the set is also in the set A set is convex if ?,? , ? 0,1 , z = ?? + 1 ? ? 17 Fei Fang 3/6/2025

Quiz 1: Convex Set Which of the following sets are convex? A: = ? B: = C: = ?0,?0 ? D: = 1 2, where 1 and 2 are convex sets E: = 1 2, where 1 and 2 are convex sets 18 Fei Fang 3/6/2025

Convex Optimization: Definition Convex function Value in the middle point is lower than average value Let be a convex set. A function ?: is convex in if ?,? , ? 0,1 , ? ?? + 1 ? ? ?? ? + 1 ? ?(?) If = ?, we simply say ? is convex 19 Fei Fang 3/6/2025

Convex Optimization: Definition How to determine if a functions is convex? Prove by definition Use properties Sum of convex functions is convex If ? ? = ?????? ,?? 0,??? convex, then ?(?) is convex Convexity is preserved under a linear transformation If ? ? = ?(?? + ?), ? convex, then ?(?) is convex If ? is a twice differentiable function of one variable, ? is convex on an interval ?,? iff (if and only if) its second derivative ? ? 0 in ?,? 20 Fei Fang 3/6/2025

Convex Optimization: Definition (not required) If ? is a twice continuously differentiable function of ? variables, ? is convex on iff its Hessian matrix of second partial derivatives is positive semidefinite on the interior of ? is positive semidefinite in ? if ? ?, ? ?,???(?)? 0 ? is positive semidefinite in ? iff all eigenvalues of ? are non-negative Alternatively, prove ??? ? ? = ????,? 2 21 Fei Fang 3/6/2025

Convex Optimization: Definition Concave function A function ? is concave if ? is convex Let be a convex set. A function ?: is concave in if ?,? , ? 0,1 , ? ?? + 1 ? ? ?? ? + 1 ? ? ? The following is a convex optimization problem if ? is a concave function and is a convex set max ? s.t. ? ?(?) 22 Fei Fang 3/6/2025

Convex Optimization: Definition Affine function An affine function is a function of the form ? ? = ??? + ? where ? ?,? If a function ? is both convex and concave in ?, then ? is an affine function Proof (not required): Let ? ? = ? ? ?(0). Clearly ?(?) is convex and concave. By definition, ?(?) satisfies (i) ? ? + ? = ? ? + ?(?); (ii) ? ?? = ??(?). Let ??1 Therefore ? ? = ????(??) = ??? where ??= ?(??). So ? ? = ? ? + ? 0 = ??? + ? ? be the canonical basis of ?, then ? = ?????. 23 Fei Fang 3/6/2025

Quiz 2: Convex Function Which of the following functions are convex? A: ? ? = ???,? B: ? ? = log?,? (0,+ ) 2 C: ? ? = ?2= ??? D: ? ?,? = ????,? ? ?,? ?,? ? E: ? ? = ?3,? Counter Example for D:?,? , ? = 1, ? ?,? = ??. http://m.wolframalpha.com/input/?i=z%3D-xy ? 1, 1 = ? 1,1 = 1, ? 0,0 = 0 http://m.wolframalpha.com/input/?i=z%3D-xy 24 Fei Fang 3/6/2025

Convex Optimization: Local Optima=Global Optima min ? s.t. ? ?(?) Given an optimization problem, a point ? ? is globally optimal if ? and ? ,? ? ? ? Given an optimization problem, a point ? ? is locally optimal if ? and ? > 0such that ?:? and ? ?2 ?,? ? ? ? Theorem 1: For a convex optimization problem, all locally optimal points are globally optimal 25 Fei Fang 3/6/2025

Convex Optimization: Local Optima=Global Optima Proof of Theorem 1: Prove by contradiction. Assume ? is a local optima with optimality radius ?, and ? ,? ? > ? ? . Let ? = ?? + 1 ? ? where ? = 1 ? 2 ? ?2. (1) ? due to convexity of (2) ? ?2= ? ?? 1 ? ?2= 1 ? ? ?2 ? ? ?2=? = 2 ? 2 ? ?2 (3) ? ? ?? ? + 1 ? ? ? < ?? ? + 1 ? ? ? = ? ? So ? is not local optima. Contradiction. 26 Fei Fang 3/6/2025

Convex Optimization: How to Solve Recall discrete setting Local search Iteratively improving an assignment Continuous and differentiable setting Iteratively improving value of ? Based on gradient 27 Fei Fang 3/6/2025

Convex Optimization: How to Solve For ?: ? , gradient is the vector of partial derivatives A multi-variable generalization of the derivative Point in the direction of steepest increase in ? 28 Fei Fang 3/6/2025

Convex Optimization: How to Solve Gradient descent: iteratively update the value of ? A simple algorithm for unconstrained optimization min ? ??(?) Algorithm: Gradient Descent Input: function ?, initial point ?0, step size ? > 0 Initialize ? ?0 Repeat ? ? ???? ? Until convergence Variants How to choose ?0, e.g., ?0= 0 ??+1 ???(??? ??+1 ??? ??) ??? ??+1 ??? ?? How to update ?, e.g., ??+1= 2 2 How to define convergence , e.g., ??+1 ?? 2 ? 29 Fei Fang 3/6/2025

Convex Optimization: How to Solve Theorem 2: For differentiable ? and small enough ?, for any ? with ??? ? 0, ? ? ???? ? ? can be convex or non-convex Proof (not required): (Recall Taylor expansion ? ? + ? = ? ? + ??? ??? + ?( ?2 Consider a small ?, use Taylor expansion ? ? ???? ? = ? ? + ??? ?? ???? ? = ? ? ? ??? ? 2 ???? ? ? ? ? ??? ? 2 < ?(?) Last inequality holds for ? <1 < ? ? 2)) 2 + ? ???? ? 2 2+ ? 2+ ??2??? ? 2 2 2 2 2> 0 ? since ??? ? 2 (Informal) For convex and differentiable ? and small enough ?, gradient descent converges to global optimum 30 Fei Fang 3/6/2025

Convex Optimization: How to Solve Projected Gradient Descent: iteratively update the value of ? while ensuring ? Algorithm: Projected Gradient Descent Input: function ?, initial point ?0, step size ? > 0 Initialize ? ?0 Repeat ? ? (? ???? ? ) Until convergence ? projects a point to the constraint set Variants How to choose ? , e.g., ? (?) = argmin 2 ? ? 2 ? 31 Fei Fang 3/6/2025

Convex Optimization: How to Solve Unconstrained and differentiable Gradient descent Set derivative to be 0 Closed form solution (Not covered) Newton s Method (if twice differentiable) Constrained and differentiable Projected gradient descent (Not covered) Interior Point Method (Not covered) Non-differentiable ?-Subgradient Method Cutting Plane Method 32 Fei Fang 3/6/2025

Convex Optimization: Apply Model a problem as a convex optimization problem Define variable, feasible set, objective function Prove it is convex (convex function + convex set) Solve the convex optimization problem Build up the model Call a solver Examples: fmincon (MATLAB), cvxpy (Python), cvxopt (Python), cvx (MATLAB) Map the solution back to the original problem 33 Fei Fang 3/6/2025

Summary Optimization Problems Convex Programs Gradient Descent 34 Fei Fang 3/6/2025

Convex Optimization: Additional Resources Text book Convex Optimization,Chapters 1-4 Stephen Boyd and Lieven Vandenberghe Cambridge University Press https://web.stanford.edu/~boyd/cvxbook/ Online course Stanford University, Convex Optimization I (EE 364A), taught by Stephen Boyd http://ee364a.stanford.edu/courseinfo.html https://youtu.be/McLq1hEq3UY 35 Fei Fang 3/6/2025